What does evolutionary calculation mean

Evolutionary Algorithm

 

Concept and origin

Evolutionary algorithms (EA) are broadly applicable stochastic metaheuristics. They imitated processes of biological evolution on an abstract level [Nissen 1997] [Gerdes et al. 2004]. The term Evolutionary Computation is used synonymously [Bäck 2002] [Fogel 2006] [Eiben and Smith 2007].
The core mechanisms of evolution are the replication and variation (through mutation and recombination) of genetic information as well as a selection in favor of the best carriers of traits. In evolutionary algorithms, alternative solutions to the given application problem correspond to the individuals of an evolving population. In the course of the artificial evolutionary process, better and better solutions are created.

 

Precursors and main forms

The EVOP method by Box [1957] and the work of Bremermann [1962] are important forerunners. Today's mainstreams emerged from the 1960s. One differentiates:

  • Genetic algorithms [Michalewicz 1999] [Bäck 2002],
  • Genetic programming [Koza 2005],
  • Evolution strategies [Beyer and Schwefel 2002],
  • Evolutionary programming [Fogel 2006].

On the one hand, genetic algorithms and genetic programming are conceptually related. On the other hand, evolutionary strategies and evolutionary programming, although developed independently, share similarities.

 

properties

The operators of evolutionary algorithms work on a representation of the application problem, which is often binary or real-valued, but can also take other forms. The coordination of solution representation, variation operators and selection mechanism is of great importance. This is also where the differences between the main EA currents lie. Fine tuning of the process parameters is also important. It can be done manually or self-adaptively.
For a targeted search, only information on the quality (fitness) of the solutions is necessary. These fitness values ​​are usually calculated from target function values, but can also be determined differently. There are no restrictive requirements for the objective function.
Evolutionary algorithms distinguish themselves from other modern heuristics primarily through their population-based approach. In this way, parallel and interacting searches are carried out in different areas of the solution space. Local suboptima can be overcome.
Stochastic procedural elements are used deliberately. The variation operators continuously generate new solution structures (exploration). Thanks to the selection, solutions are focused on promising regions of the search area (exploitation). The right balance between exploration and exploitation is critical to success.
There are numerous starting points to adapt EA to the given task and thus to increase its performance, e.g. via the solution representation and complementary search operators, intelligent decoding and repair mechanisms, the design of the fitness function, a targeted initialization or the combination with other solution methods.
As a population-based method, EA are computationally intensive. The methodologically necessary generation of many random numbers is also complex. Like all heuristic methods, EA cannot guarantee that a globally optimal solution will be found.

 

Current developments

Estimation of distribution algorithms are currently gaining in importance [Lozano et al. 2006]. They combine elements of evolutionary algorithms with methods of machine learning and probabilistic modeling.
In addition, concepts have developed that are not evolutionary, but are still viewed as related. These include e.g. ant algorithms [Dorigo and Stützle 2004] and particle swarm optimization [Kennedy et al. 2001].

 

literature

Bäck, T. (Ed.): Handbook of Evolutionary Computation. Institute of Physics Publishing: Bristol, 2002.

Beyer H.-G., Schwefel, H.-P .: Evolution Strategies: A Comprehensive Introduction. In: Natural Computing 1 (2002), pp. 3–52.

Box, G.E.P .: Evolutionary Operation: A Method for Increasing Industrial Productivity. In: Applied Statistics. 6/2 (1957), pp. 81-101.

Bremermann, H.J .: Optimization through Evolution and Recombination. In: Yovits, M.C .; Jacobi, G.T .; Goldstein, G. D. (Ed.): Self-Organizing Systems. Spartan Books: Washington, 1962, pp. 93-106.

Dorigo, M .; Stützle, T .: Ant Colony Optimization. MIT Press: Cambridge, 2004.

Eiben, A .; Smith, J.E .: Introduction to Evolutionary Computing. 2. corr. Print, Springer: Berlin, 2007.

Fogel, D.B .: Evolutionary Computation. Toward a New Philosophy of Machine Intelligence. 3rd ed., Wiley & Sons: Hoboken, 2006.

Gerdes, I .; Klawonn, F .; Kruse, R .: Evolutionary Algorithms. Vieweg: Wiesbaden, 2004.

Kennedy, J .; Eberhart, R.C .; Shi, Y .: Swarm Intelligence. Morgan Kaufmann: San Francisco, 2001.

Koza, J.R .: Genetic Programming IV. Routine Human-Competitive Machine Intelligence. Kluwer: Boston, 2005.

Lozano, J.A .; Larrañaga, P .; Inza, I .; Bengotxea, E .: Towards a New Evolutionary Computation: Advances in the Estimation of Distribution Algorithms. Springer: Berlin, 2006.

Michalewicz, Z .: Genetic Algorithms + Data Structures = Evolution Programs. 3rd edition (correct print), Springer: Berlin 1999.

Nissen, V .: Introduction to Evolutionary Algorithms. Vieweg: Wiesbaden, 1997.

author


 

Prof. Dr. Volker Nissen, Technical University of Ilmenau, Institute for Information Systems, Postfach 10 05 65, 98684 Ilmenau

Author info


Item Actions