Evolutionary Algorithm

from Wikipedia, the free encyclopedia
The antenna of the Space Technology 5 satellites was developed with an EA.

Evolutionary algorithms ( EA ) are a class of stochastic , metaheuristic optimization methods , the functioning of which is inspired by the evolution of natural living things.

Based on nature , solution candidates for a certain problem are artificially evolved, so EA are nature- analogous optimization methods . The assignment to the stochastic and metaheuristic algorithms means above all that EA usually does not find the best solution for a problem, but if it is successful, a sufficiently good one, which is desirable in practice, especially for NP-complete problems. The methods of different EA differ from each other primarily in the selection , recombination and mutation operators used , the genotype - phenotype mapping and the problem representation .

The first practical implementations of evolutionary algorithms were published in the late 1950s, but scientists had already expressed their views on the potential of evolution for machine learning in the previous decades .

There are four main currents, the concepts of which can be distinguished from one another, at least historically :

  • genetic algorithms
  • evolutionary algorithms
  • genetic programming and
  • evolutionary programming

Today these boundaries are becoming increasingly blurred. An EA is designed appropriately for a specific application, with many different algorithms and individual operators being developed over the last few decades that can be used today.

The applications of EA go beyond optimization and search and can also be found in art , modeling and simulation , especially in the investigation of evolutionary biological issues .

introduction

Evolutionary algorithms are primarily used for optimization or search . Specific problems that can be solved with EA are extremely diverse: B. The development of sensor networks , stock market analysis or RNA structure prediction. They can also find satisfactory solutions to problems of which little is known about their nature. This is due to the properties of their natural model.

Natural role model Evolutionary Algorithm example
organism Solution candidate car door
Reproductive success Fitness function value Flow resistance
Natural mutation mutation Change of shape

In biological evolution, the genes of organisms are exposed to naturally occurring mutations , which creates genetic variability . Mutations can have a positive, negative or no effect on heirs. Since reproduction ( recombination ) occurs between successful individuals , species can adapt to a prevailing selection pressure over long periods of time (e.g. climate changes or the development of an ecological niche ). This simplified concept is idealized in computer science and artificially reproduced in the computer . The quality of a solution candidate is explicitly calculated with a fitness function so that different candidates can be compared.

In practice, e.g. B. the shape of a car door can be optimized so that the aerodynamic resistance is minimal. The properties of a potential solution are stored in the computer as a genome . Frequent problem representations are genomes from binary or real numbers or a sequence of known elements (for combinatorial problems , e.g. Traveling Salesman ).

The strong simplifications that are made in comparison to evolution pose a problem in relation to researching evolutionary biological questions with EA. Results cannot simply be transferred to the more complex nature .

procedure

The rough process of evolutionary algorithms usually consists of an initialization and a loop that is run through until a termination criterion is met:

  1. Initialization : The first generation of solution candidates is generated (mostly randomly).
  2. Evaluation : Each generation solution candidate is assigned a fitness function value based on its quality.
  3. Go through the following steps until a termination criterion is met:
    1. Selection : selection of individuals for recombination
    2. Recombination : combining the selected individuals
    3. Mutation : random change in the descendants
    4. Evaluation : Each generation solution candidate is assigned a fitness function value based on its quality.
    5. Selection : determination of a new generation

The various EA differ in the choice of operators (recombination, selection, ...). They also differ in different problem representations, the corresponding fitness function or additional steps. Recombination does not necessarily have to take place here, since the individuals can also reproduce asexually . EA are often combined with artificial neural networks or local search . Depending on the application at hand, there are advantages and disadvantages with regard to special operators or concepts.

Components

Evolutionary algorithms differ from one another primarily in the respective genetic representation , the fitness function and the genetic operators used : mutation , recombination and selection .

The rastrigin function is a multimodal function because it has many local extremes. This is a disadvantage for the recombination operator.

Mutation and recombination are the search operators of evolutionary algorithms with which the search space is explored. Applying them to solution candidates cannot guarantee an improvement, but the selection process gives the search process a direction that, if the concept is successful, leads to the global optimum. While completely new areas of the search space can be opened up with the mutation operator, the recombination above all enables the merging of successful schemes ( building block hypothesis ). A successful search is based on a combination of both properties. The success of a recombination operator depends on the nature of the fitness landscape. The more local optima the fitness landscape has, the more likely the recombination of two individuals who are at a local optimum will generate a descendant in the valley in between. Mutation is almost independent of this property of the fitness landscape.

The design of the various components determines how the evolutionary algorithm behaves when optimizing the given problem in terms of convergence behavior , required computing time and the development of the problem space. In particular, the genetic operators must be carefully matched to the underlying representation so that both the known, good regions of the problem area can be used and the unknown regions can be explored. The relationships between the search space and the problem space play a role here. In the simplest case, the search space corresponds to the problem space (direct problem representation).

Theoretical foundations

No-free lunch theorem

The no-free-lunch theorem of optimization states that all optimization strategies are equally effective if the set of all optimization problems is considered. On the same basis, no evolutionary algorithm is fundamentally better than another. This can only be the case if the set of all problems is limited. This is exactly what is inevitably done in practice. An EA must therefore take advantage of problem knowledge (e.g. by choosing a certain mutation strength). So if two EA are compared, then this restriction is implied.

Schematic Theorem

John H. Holland's schematic theorem is widely seen as explaining the success of genetic algorithms. It simply means that short bit patterns with above-average fitness spread quickly in a generation that is evolved by a genetic algorithm . In this way, statements can be made about the long-term success of a genetic algorithm.

Virtual alphabets

With the theory of virtual alphabets, David E. Goldberg showed in 1990 that, in contrast to a representation with real numbers, an EA that uses classic recombination operators (e.g. uniform or n-point crossover) cannot reach certain areas of the search space to a representation with binary numbers . It follows from this that EA with a real representation must use arithmetic operators for recombination (e.g. arithmetic mean ). With suitable operators, real-valued representations are, contrary to earlier opinion, more effective than binary ones.

application areas

The areas in which evolutionary algorithms are used in practice are almost unlimited and range from industry to research and art ( evolutionary art ).

economy

EA are used to verify and optimize prototypes . For example, the speed of microprocessors , the power consumption of mobile phones or the reusability of products ( recycling ) are optimized. Also in the design of telecommunication networks , infrastructure in general or sensor networks . In the financial world, EA is used to analyze stock markets, design game theory analyzes or agent-based simulations and optimize portfolios for maximum profit and minimum risk. They are even used to optimize farms, to test long-term effects, to develop management strategies or to simulate experiments that cannot be carried out in practice.

research

Especially in molecular biology , where enormous amounts of data ( big data ) arise and connections cannot be recognized without computer support, evolutionary algorithms are used to perform sequence analysis , sequence alignment , the creation of phylogenetic trees , protein structure prediction , search for coding areas or the visualization of extensive data.

EA are used to build artificial neural networks, a popular algorithm is NEAT . Robert Axelrod's attempt to find suitable strategies for the iterated prisoner's dilemma using genetic algorithms gave rise to the development of the concept of evolutionary game theory. Due to their population -based nature , evolutionary algorithms can also be used in agent-based modeling of social or economic systems.

In spectroscopy , genetic algorithms are used to solve multidimensional optimization problems. Here, an experimental spectrum, which requires a large number of parameters to describe, is adapted to a calculated model spectrum with the help of evolutionary strategies. The cross-correlation between the experimental and theoretical spectrum is often used as a fitness function .

Art and music

With the help of evolutionary algorithms, complex structures or tone sequences can be designed that have an aesthetic effect on people . This is partly automated and often with human interaction, with people making the decision for the EA about what they perceive to be beautiful .

history

In 1956, George Friedman designed a machine for his master's thesis at the University of California, Los Angeles , which was supposed to develop circuits using the principle of natural selection , but this machine was never built. Even artificial life was early explored by EA. The Italian Nils Barricelli (1912–1993) developed a concept in 1954 in which beings represented by numbers "live" on a two-dimensional grid and are formed into new generations through mutation and reproduction. He showed that self-replicative structures are formed, i.e. structures that copy themselves into the next generation. With regard to machine learning , the British computer scientist Alan Turing wrote as early as 1950:

“You have to experiment with teaching a machine and see how well it learns. [...] There is an obvious connection between this process and evolution [...] However, one can hope that this process will run faster. "

- Alan Turing : Computing Machinery and Intelligence

In the early 1950s, the British statistician George Box suggested optimizing production in chemical plants by varying parameters such as temperature or chemical composition with massive trial and error and evaluating the potential improvements by hand in order to then vary again with the improvements found. Although decision makers weren't keen on experimenting on a running production at first, the concept that Box Evolutionary Operation dubbed was used to increase productivity in several chemical plants by the early 1960s. Many practical problems were subsequently approached with evolutionary algorithms; the evolution strategy in Europe ( Ingo Rechenberg and Hans-Paul Schwefel ) and the genetic algorithm ( John H. Holland ) in the USA emerged, the latter being the to is the most popular approach today and the term genetic algorithm is often used across the board for all EA. However, this has no practical significance for the selection of a specific concept. At the latest with the rapidly increasing availability of computing power, evolutionary algorithms were found in all conceivable areas where they were used for optimization and search. Especially in art and music, as well as in the research of artificial life ( Avida ).

Today not only have the original concepts grown together, but many other approaches and mixed concepts have also emerged. EA are important tools for industry and research .

Types of evolutionary algorithms

By setting the problem of the optimization problem, an objective function and a problem space containing potential solutions are given. The difference between the problem space of the application and the search space of the algorithm is that an EA can represent a solution differently in order to process it better and to output it again later in its original form (genotype-phenotype mapping, artificial embryogenesis ). This is particularly useful when the representation of a possible solution can be significantly simplified and the complexity does not have to be processed in the memory. Different evolutionary algorithms mainly differ in the following properties (compare the introductory flowchart ):

  • Search space (e.g. binary numbers , real numbers, tree structures )
  • Search operators (e.g. mutation and recombination)
  • Fitness assignment and selection based on the objective function
  • The way in which previous generations are included in the selection (include / exclude parent generation)
  • Relationship between the search space and the problem space (genotype-phenotype mapping)

Classic variants

The four first historically developed methods can no longer be differentiated in form today, in particular the names of individual types are often used as a synonym for the entire field of evolutionary algorithms. In addition, there is now a plethora of other processes and an unmanageable number of combinations for which there is no uniform naming. In the following illustration, the classic concepts are described in historical form.

Genetic Algorithms (GA)

Expression of the genotype in a cell

Genetic algorithms became famous primarily through the work of John H. Holland . They use binary problem representation and therefore mostly need a genotype-phenotype mapping. This means that solution candidates represented in binary must first be converted in order to be able to be evaluated with the fitness function. Because of this property, they are closest to the biological model of all evolutionary algorithms. The genetic material of natural organisms is encoded in four nucleic acids similar to binary numbers . On this basis, natural mutation and recombination occur. The appearance (phenotype) is not the genetic material itself, but arises from it through a multi-step process . The principle of genotype-phenotype mapping is simplified in a similar way. The binary representation is suitable for fast processing in computers. In the course of research in the field of EA, however, this has not proven to be a clear advantage over other methods.

The selection of the reproductive individuals is done with GA with fitness-proportional selection, the reproduction itself through n-point crossover . The recombination of more than two parent genomes is also possible and in some cases leads to better results. The mutation in GA is easy to imagine, since the genomes consist of individual bits that can be inverted, duplicated or deleted (including entire sequences). A theoretical investigation of the convergence behavior of genetic algorithms is provided by the scheme theorem by John H. Holland.

Evolution strategies (ES)

Evolution strategies use direct problem representations (e.g. real numbers). The problem and search area are therefore identical. In the case of complex problems, this means that the evolution strategy cannot explore the entire problem space if classic crossover operators are used ( virtual alphabets ). ES primarily use mutation as a search operator and in some cases no recombination at all. The mutation represents the addition of a normally distributed value, with the variance (mutation strength ) not being constant. Since the algorithm converges with increasing solution quality (scheme theorem), it is advantageous to adapt the variance. In this way it can be guaranteed that the ES seeks its goal in ever finer steps. Two methods have become established for adaptation.

  • Adaptive adaptation (1/5 success rule): The 1/5 success rule states that the quotient of the successful mutations (i.e. mutations that improve the adaptation) to all mutations should be around one fifth. If the quotient is larger, the variance of the mutations should be increased; if the quotient is smaller, it should be reduced.
  • Self-adaptivity: Every individual has an additional gene for the mutation strength itself. This is not possible in biology, but evolution in the computer finds a suitable variance in this way without human restrictions.

Genetic Programming (GP)

Representation of a function as an expression tree . Sub-trees can be moved, changed or deleted (mutation) and complete trees can be combined (recombination).

The goal of genetic programming is to create structures designed to convert a specific input into a specific output ( computer programs , circuits, or mathematical functions ). The solution candidates are represented by trees .

The symbolic regression problem is looking for a specific function (e.g., a polynomial like ). Pairs are given, each with a value from and the associated value from . It is therefore known how the function you are looking for maps values. With GP tree structures are evolved, which mostly reproduce the symbolic function exactly.

A fundamental work on genetic programming was written by John Koza . He also saw the possibility of solving symbolic regression using GP. In research on GP, ​​this problem has often been used as a benchmark test .

Evolutionary Programming (EP)

Similar to the GP, structures such as computer programs are sought, which are not represented by trees, but by finite automata . Only the numerical properties of the automata are varied, their structure is fixed. Searches are only made via mutation, recombination does not take place. Individual individuals are viewed as different species, so to speak. Evolutionary programming has seen little development after its inception.

See also

literature

Evolutionary algorithms in general

Genetic Algorithms

Evolution strategies

  • Ingo Rechenberg : Cybernetic Solution Path of an Experimental Problem (1965). In: DB Fogel (Ed.): Evolutionary Computation - The Fossil Record. IEEE Press, 1998, ISBN 0-7803-3481-7 .
  • Ingo Rechenberg: evolution strategy. Optimization of technical systems according to the principles of biological evolution. Frommann Holzboog, 1973, ISBN 3-7728-0373-3 (diss. From 1970).
  • Ingo Rechenberg, Evolution Strategy '94. Frommann Holzboog, 1994, ISBN 3-7728-1642-8 .
  • Hans-Paul Schwefel : Evolution and Optimum Seeking . Wiley & Sons, New York 1995, ISBN 0-471-57148-2 .
  • Hans-Georg Beyer : The Theory of Evolution Strategies. Springer, Berlin / Heidelberg / New York 1998, ISBN 3-540-67297-4 .
  • Hannes Geyer et al .: Comparison between classic and nested evolution strategies using the example of a nonlinear regression on surface tensions in R². Internal report CI-66/99 of the Collaborative Research Center 531: "Design and Management of Complex Technical Processes and Systems Using Computational Intelligence Methods", Dortmund 1999, PDF

Genetic programming

Evolutionary programming

Web links

Evolutionary algorithms in general

Genetic Algorithms

  • Steffen Harbich: Introduction of genetic algorithms with application example. 2007
  • Genetic Algorithms . Wikiversity course.
  • JGAP - Free Java Framework for the implementation of genetic algorithms, also supports genetic programming; very many unit tests for quality assurance, extensive Javadoc documentation
  • EvoJ - Small but effective and distributable Java framework for genetic algorithms.
  • Jenetics - genetic algorithm written in Java 11 and uses the Java Stream API to evaluate the individual generations.
  • HeuristicLab - Free .NET environment for heuristic optimization (genetic algorithms, evolution strategies, neighborhood searches, etc.)
  • Boxcar2D , a genetic algorithm that constructs a 2-dimensional vehicle to overcome terrain

Hybrid algorithms

  • Geneva ("Grid-enabled evolutionary algorithms"), a free library (Affero GPLv3) for optimization with evolution strategies, genetic and swarm algorithms as well as simulated annealing and parameter scans. Supports problem descriptions with mixed parameter sets as well as optimization in clusters as well as grid and cloud

Individual evidence

  1. Jump up ↑ JD Lohn, DS Linden, GS Hornby, WF Kraus: Evolutionary design of an X-band antenna for NASA's Space Technology 5 mission. In: Antennas and Propagation Society International Symposium. Vol. 3, IEEE, June 20-25, 2004, pp. 2313-2316
  2. ^ A b c Peter Bentley, David Corne: Creative Evolutionary Systems . P. 10.
  3. ^ A b David B. Fogel: Evolutionary Computation: Toward a New Philosophy of Machine Intelligence . P. 59.
  4. ↑ a b Cecilia Di Chio et al .: Applications of Evolutionary Computation: EvoApplications 2012 .
  5. ↑ Karsten Weicker: Evolutionary Algorithms . P. 25.
  6. ↑ Mitsuo gene Runwei Cheng: Genetic Algorithms and Engineering Optimization . P. 8.
  7. ^ William M. Spears: The Role of Mutation and Recombination in Evolutionary Algorithms. P. 225f.
  8. ^ Bill Worzel: Genetic Programming Theory and Practice VI . P. 62.
  9. ↑ Oscar Cordón: Genetic Fuzzy Systems: Evolutionary Tuning and Learning of Fuzzy Knowledge Bases . P. 95
  10. ↑ a b J. Stender, E. Hillebrand, J. Kingdon: Genetic Algorithms in Optimization, Simulation and Modeling . P. 70.
  11. ↑ Ernesto Sanchez, Giovanni Squillero, Alberto Tonda: Industrial Applications of Evolutionary Algorithms
  12. ↑ Shu-Heng Chen: Evolutionary Computation in Economics and Finance . P. 6.
  13. ↑ Wayne Wobcke, Mengjie Zhang: Application of a Memetic Algorithm to the portfolio optimization problem . In: AI 2008: Advances in Artificial Intelligence . Springer-Verlag, p. 512.
  14. ^ David G. Mayer: Evolutionary Algorithms and Agricultural Systems . P. 2.
  15. ^ Gary Fogel, David Corne: Evolutionary Computation in Bioinformatics
  16. ↑ The evolution of cooperation . Oldenbourg, Munich 1987; 7. A. ibid. 2009, ISBN 978-3-486-59172-9
  17. ↑ W. Leo Meert, Michael Schmitt: Application of genetic algorithms in automated assignments of high-resolution spectra . In: International Reviews in Physical Chemistry . tape 25 , no. 3 , July 1, 2006, ISSN  0144-235X , p. 353-406 , doi : 10.1080 / 01442350600785490 .
  18. ↑ AM Turing : Computing machinery and intelligence . In: Mind , 59, pp. 433–460. 1950. loebner.net ( Memento of the original from July 2, 2008 in the Internet Archive ) Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice. @1@ 2Template: Webachiv / IABot / loebner.net
  19. ↑ Ingo Rechenberg: Evolution strategy - optimization of technical systems according to the principles of biological evolution (PhD thesis) ( German ). Frommann-Holzboog, 1973.
  20. ^ John H. Holland: Adaptation in Natural and Artificial Systems . University of Michigan Press, 1975, ISBN 0-262-58111-6 .
  21. ↑ Lukáš Sekanina: Evolvable Components: From Theory to Hardware Implementations . P. 27.
  22. ^ Chuan-Kang Ting: On the Mean Convergence Time of Multi-parent Genetic Algorithms Without Selection . In: Advances in Artificial Life , 2005, ISBN 978-3-540-28848-0 , pp. 403-412.
  23. ↑ Ingo Rechenberg: Evolution strategy. Optimization of technical systems according to the principles of biological evolution . Frommann Holzboog, 1973, ISBN 3-7728-0373-3 (diss. From 1970), chapter 15
  24. ^ Julian F. Miller: Cartesian Genetic Programming . P. 63.