Begining of page
verzija na srpskom  
Evolutionary Algorithm Web Service      
 
   
Evolutionary Algorithm

Web service

XML configuration files

Web application
(Jun 5. 2002.)
 		 

This page describes Web Service that executes Parallel Evolutionary Algorithm (Parallel EA) and other applications that uses created Web Service. The motivations for this approach is to utilize computing resources available on the Internet in order to provide the computing power required for solving difficult problems.

Many NP- Hard problems are successfully solving with EA techniques. At the same time, communication between Web service that executes algorihm and application that uses service in EA usually isn’t large and (at the same time) computational efforts are significant.

Evolutionary algorithm

Under the most frequent classification, Evolutionary Algorithms, together with Fuzzy Logic and Neural Networks, is part of so-called Soft Computing. EA includes Genetic Algorithms, Evolutionary Programming, Evolutionary Strategies and Genetic Programming and some similar techniques.

Evolutionary Algorithms are applying on some optimization problems - either theoretical (job shop scheduling, traveling salesman) or practical (economic modeling, pipeline projecting); in machine learning; in game theory; in neural networks; in geometric reasoning etc.

Darwin’s evolution theory and Mendel’s laws of inheritance are theoretical inspirations of Evolutionary Algorithms. If Darwin’s theory describes natural processes, then EA imitate natural processes attempting to solve particular problem.

According to Darwin, individuals in population are competing for resources. Facts that lie in essence of natural selection process are:

  • Better-fitted individuals survive and they have stronger influence on forming new generations.
  • Individual in new generation is formed by recombination of parent’s genetic material.
  • From time to time mutation (random change of genetic material) takes place.

Great deals of popularity of EA lies in fact that getting new solutions has, indeed, parallel nature. Holland observed that parallel nature of reproductive paradigm and inherent efficiency of parallel processing ten years before formal genesis of EA.

Also, Evolutionary Algorithms are easy to hybridize: they easy can be combined with other algorithms that solve specific problem. New, hybrid, algorithm has good features of both base algorithms .

EA has following structure:

  • Search space – space of all possible solutions.
  • Population – set of actual candidates for solution; elements of population are called individuals or items, or search nodes, or points in search space.
  • String space – space that contains string representations of individuals in population.
  • Functions for conversion between points in search space and points in string space (coding and decoding).
  • Set of genetic operators for generating new strings (and new individuals).
  • Fitness function – it evaluate fitness (degree of adaptation) for each individual in population.
  • Stochastic control of genetic operators.

Basic steps in EA are:

  1. Initialization – generating initial population by random sampling.
  2. Evaluation – calculating fitness for all individuals in population.
  3. Selection – choosing surviving individuals in population, according to values of fitness function.
  4. Recombination (includes crossover and mutation) – changing individual’s representation.
  5. Repeating steps 1 to 4 until fulfilling finishing criteria.

Features that made distinction between EA and any other problem-solving method are:

  • EA works with codes that represent individuals, not with pure individuals.
  • EA search in several points (population) simultaneously, therefore it is very robust.
  • EA uses probabilistic transition rules, rather than deterministic.
  • EA (in its pure form) doesn’t exploit additional information about problem’s nature.

Begining of page

Web service

Evolutionary Algorithms (EA) Web service, named EaWebService (.wsdl  | .asmx ), can be used in all scenarios that involve optimization via EA. At the same time, it can be used in GP-like manner.

In order to execute EA, application sends to Web service five XML strings:

  • parameterXML - parameters of the EA that will be executed. Some of those parameters (such are replacement in population, selection, finishing criteria, random generator, report) aren’t depending of item representation and some others (like population, init, instance, crossover and mutation) are. Each parameter is XML node with elements that determine parameter value. EaWebService supports three types of item representation (as binary string, as float and tree-like representation as XML stream);
  • problemArgumentsXml – problem (in XML representation) that should be solved by EA. For instance, function expressions are represented in XML format and same code can optimize different functions;
  • initDataXML – when it is appropriate, initial data won’t be set with random generator, but read from XML supplied with this parameter;
  • topologyXML – links among Web Services of the same kind that collaborate (work in parallel) in order to find solution;
  • knownSolutionXML – represents known solution, so EA can stop when solution is reached (mainly used in testing purposes);

Web Service reports back (in XML format) solution and additional results that are needed. Question which data are needed and when they are needed is answered by setting XML report subnode in parameterXML argument, to specific value.

Web Service allows application to interrupt ongoing execution and report back current result in any moment of execution.

This service also (using reflection) allows applications to obtain information about classes that represent specific part of EA and, on that way, make easier and faster creation of EA.

This service is, at the same time, very complex, very efficient and can grow easily.

Easiness of growing is due to the fact that service is heavily based on interfaces. So, whenever some class method or property is accessed from outer space, it is done by obtaining interface and accessing interface’s method or property (not class directly).

Web service’s complexity and efficiency come from the fact that Web Service is multi-threaded application with Execute thread, StopExecution thread, Migrate thread and Cleanup thread.

Begining of page

XML configuration files

XML strings are validated (via schemas) on the EaWebService server.

Following links represent repository of the XML strings that can be supplied as parameters of the web service: 

Begining of page

Web application

When such core service is created, author (even if he is not expert in EA) can experiment (by setting values of XML elements) in order to obtain best stochastic parameters to solve specific problem, or easily switch from one problem domain to another. Consumer application just has to handle strings in XML format that are parameters of EA, and properly render and show report string (again in XML format).

One example of consumer Web application (denoted as EaWebApplication ) that covers almost all different properties of proposed web service and different ways of using it is given there.

Begining of page

All necessary questions, comments, sugestions and corrections send to address: 

vladaf@matf.bg.ac.yu    or

vladofilipovic@hotmail.com

Begining of page


Begining of page


Katedra Predmeti Magistarske studije Nauka Zaposleni

Copyright (c) 2000, Matematièki fakultet Univerziteta u Beogradu