Fig 1: Problem solution using evolutionary algorithms
Evolutionary algorithms are stochastic search methods that mimic the metaphor
of natural biological evolution. Evolutionary algorithms operate on a population
of potential solutions applying the principle of survival of the fittest to
produce better and better approximations to a solution. At each generation,
a new set of approximations is created by the process of selecting individuals
according to their level of fitness in the problem domain and breeding them
together using operators borrowed from natural genetics. This process leads
to the evolution of populations of individuals that are better suited to their
environment than the individuals that they were created from, just as in natural
adaptation.
Evolutionary algorithms model natural processes, such as selection, recombination, mutation, migration, locality and neighbourhood. Figure 1 shows the structure of a simple genetic algorithm. Evolutionary algorithms work on populations of individuals instead of single solutions. In this way the search is performed in a parallel manner.
Fig 2: Structure of a single population evolutionary algorithm
At the beginning of the computation a number of individuals (the population) are randomly initialised. The objective function is then evaluated for these individuals. The first/initial generation is produced.
If the optimization criteria are not met the creation of a new generation starts. Individuals are selected according to their fitness for the production of offspring. Parents are recombined to produce offspring. All offspring will be mutated with a certain probability. The fitness of the offspring is then computed. The offspring are inserted into the population replacing the parents, producing a new generation. This cycle is performed until the optimization criteria are reached.
Such a single population evolutionary algorithm is powerful and performs well on a broad class of problems. However, better results can be obtained by introducing many populations, called subpopulations. Every subpopulation evolves for a few generations isolated (like the single population evolutionary algorithm) before one or more individuals are exchanged between the subpopulations. The Multipopulation evolutionary algorithm models the evolution of a species in a way more similar to nature than the single population evolutionary algorithm.
From the above discussion, it can be seen that evolutionary algorithms differ substantially from more traditional search and optimization methods. The most significant differences are:
Evolutionary algorithms search a population of points in parallel, not a single
point.
Evolutionary algorithms do not require derivative information or other auxiliary
knowledge; only the objective function and corresponding fitness levels influence
the directions of search.
Evolutionary algorithms use probabilistic transition rules, not deterministic
ones.
Evolutionary algorithms are generally more straightforward to apply
Evolutionary algorithms can provide a number of potential solutions to a given
problem. The final choice is left to the user. (Thus, in cases where the particular
problem does not have one individual solution, for example a family of pareto-optimal
solutions, as in the case of multiobjective optimization and scheduling problems,
then the evolutionary algorithm is potentially useful for identifying these
alternative solutions simultaneously.)
--------------------------------------------------------------------------------
For more detailed descriptions see:
GAlib: Matthew's Genetic Algorithms Library
GAlib A C++ Library of Genetic Algorithm Components GAlib contains a set of
C++
genetic algorithm objects.
http://lancet.mit.edu/ga/
Hartmut Pohlheim, GEATbx: Genetic and Evolutionary Algorithm Toolbox for use
with MATLAB.
http://www.geatbx.com/docu/algindex.html