Evolutionary algorithm

Evolutionary Algorithms (EA ) are a class of stochastic metaheuristic optimization method, the operation is inspired by the natural evolution of living beings. Based on the nature of candidate solutions to a given problem are artificially evolved, EA are so natural analog optimization methods. The assignment to the stochastic and metaheuristic algorithms mainly means that EA usually not the best solution for a problem, but a sufficiently good, which is desirable even at success in practice, especially in NP- complete problems. The method of different EA differ from one another primarily by the used selection, recombination and mutation operators, the genotype -phenotype mapping, and the problem representation.

The first practical implementations of evolutionary algorithms have been published in the late 1950s, however, expressed already in previous decades, scientists on the potential of evolution in machine learning. There are four main currents whose concepts are at least historically to distinguish: genetic algorithms, evolutionary algorithms, genetic programming, and evolutionary programming. Today, these boundaries are becoming increasingly blurred. For a particular application is an EA suitably designed, wherein in the last decades many different algorithms and some operators have been developed which can be used now.

The applications of EA go beyond optimization and search and can also be found in art, modeling and simulation, in particular in the study of evolutionary biology problems.

• 3.1 No- free -lunch theorem
• 3.2 schema set
• 3.3 Virtual Alphabets

• 4.1 Economics
• 4.2 research
• 4.3 Art and music

• 6.1 Classical variants 6.1.1 Genetic Algorithms ( GA)
• 6.1.2 Evolution Strategies ( ES)
• 6.1.3 Genetic Programming (GP )
• 6.1.4 Evolutionary Programming ( EP)

• 8.1 Evolutionary algorithms in general
• 8.2 Genetic Algorithms
• 8.3 Evolution Strategies
• 8.4 Genetic Programming
• 8.5 Evolutionary Programming

Introduction

Evolutionary algorithms are mainly used for optimization or search. Specific problems that are solved with EA, are extremely diverse: for example, the development of sensor networks, stock market analysis or RNA structure prediction. Even with problems about the nature of which there is only little knowledge, you can find satisfactory solutions. This is due to the characteristics of their natural tooth.

In biological evolution, the genes of organisms are naturally occurring mutation exposed, thus genetic variability arises. This mutation can be positive, negative or no effect on heirs themselves. Since it comes between successful individuals for reproduction ( recombination) species can be long periods of time to a present selection pressure to adapt (eg, climate change or the development of an ecological niche ). This simplified presentation is idealized in the computer science and artificially recreated in the computer. The quality of a candidate solution is explicitly calculated with a fitness function so that different candidates are comparable.

In practice, for example in the form of a car door can be optimized so that the aerodynamic drag is minimized. The properties of a potential solution are thereby stored in the computer as a genome. Common problem representations are genomes of binary or real numbers or a sequence of known elements ( in combinatorial problems such as traveling salesman ).

The strong simplifications that are made in comparison to the evolution, present a problem in terms of the exploration of evolutionary biology issues with EA Results will can not be easily transferred to the more complex nature.

Expiration

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

The various EA differ in the selection of the operators ( recombination, selection, ... ) from each other. They also differ in different problem representation, the corresponding fitness function or additional steps. Recombination does not necessarily have to take place, since the individuals can reproduce asexually. EA are often combined with artificial neural networks or local search. Depending on the particular application resulting advantages and disadvantages in relation to specific operators or concepts.

Components

Evolutionary algorithms differ from each other mainly in the respective genetic representation, the fitness function and the genetic operators used: mutation, recombination and selection.

Mutation and recombination are the search operators of evolutionary algorithms with which the search space is explored. Its application to solution candidates can guarantee no improvement, however, the search process is replaced by the selection of a direction that leads to the global optimum in case of successful conception. While completely new areas of the search space can be opened up with the mutation operator, which allows recombination especially the merging of successful schemes ( building block hypothesis). So a successful search is based on the combination of both properties. The success of a Rekombinationsoperators depends on the nature of the fitness landscape. The more local optima has the fitness landscape, the more likely generates the recombination of two individuals who are on a local optimum, between a descendant in the valley. Mutation of this property, the fitness landscape is almost independent.

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

Theoretical foundations

No- free -lunch theorem

The no- free -lunch theorem, the optimization states that all optimization strategies are equally effective, if the set of all optimization problems is considered. Under the same circumstances also not an evolutionary algorithm is inherently better than another. This can only be the case if the set of problems is limited. That's what is done necessarily in practice. An EA must therefore exploit problem knowledge (eg through the choice of a particular mutation strength ). Thus, if two EA compared, then this constraint is implied.

Schema set

The schema set by John H. Holland is commonly seen as an explanation of the success of genetic algorithms. He says simplifies that short bit pattern with above average fitness quickly spread in a generation, which is evolved by a genetic algorithm. Thus statements about the long-term success of a genetic algorithm can be made.

Virtual alphabets

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

Areas of application

The areas in which evolutionary algorithms are used in practice, are virtually unlimited, ranging from the industry on research to art ( evolutionary art ).

Economy

EA will be used for verification and optimization of prototypes. For example, the speed of microprocessors, the power consumption of mobile phones or the reusability of products ( recycled ) to be optimized. General or sensor networks also in the design of telecommunications networks, infrastructure. In the financial world are analyzed with EA stock markets, game theoretic analyzes and agent-based simulations designed and portfolios for maximum profit and minimum risk optimized. Even for the optimization of farms they are used to test long-term effects, to develop management strategies or virtually non- executable to simulate experiments.

Research

Especially in molecular biology, where incurred enormous amounts of data (Big Data) and relationships can not be detected without computer support, sequence analysis, sequence alignment, the creation of phylogenetic trees, protein structure prediction, search for coding regions or the visualization of large data be used with evolutionary algorithms.

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

Art and Music

With the help of evolutionary algorithms complex structures or sequences of notes can be designed, the aesthetic effect on people. This is partly automated and often what they feel with human interaction, with the EA people make the decision to be beautiful.

History

George Friedman designed in 1956 for his master's thesis at the University of California, Los Angeles, a machine that should develop with the principle of natural selection circuits, but this machine was never built. Even artificial life was explored early with EA. The Italian Barricelli developed in 1954 a concept represented by the figures being " live " on a two-dimensional lattice and formed by mutation and reproduction to the new generation. He showed that the formation of self-replicating structures, ie structures that copy themselves into the next generation. With respect to machine learning wrote the British computer scientist Alan Turing in 1950:

"One must experiment with teaching one machine and see how well they learn. [ ... ] There is an obvious connection between this process and evolution [ ...] One may hope, however, that this process is faster. "

Early 1950s suggested the British statistician George Box to optimize the production in chemical factories, by varying with massive trial and error parameters such as temperature or chemical compositions and the potential improvements are analyzed by hand to thereafter vary with the improvements found again. Although the decision makers were not at first excited to experiment on a current production, the concept that baptized Box Evolutionary operation used until the early 1960s in several chemical factories to increase productivity was. Many practical problems they went into the episode with evolutionary algorithms were formed especially the evolution strategy in Europe ( Ingo Rechenberg and Hans- Paul Schwefel ) and the genetic algorithm ( John H. Holland ) in the USA out, the latter being the up today is the most popular approach and the concept of genetic algorithm often generalizing for all EA will be used. However, this has no practical significance for the selection of a specific concept. At the latest with the rapidly increasing availability of computing power, there were evolutionary algorithms in all imaginable fields again, where they were used for the optimization and search. In particular, even in art and music, as well as in the study of artificial life ( Avida ).

Today, not only the original concepts are strongly fused together, but created many other approaches and mixing concepts. EA represent important tools for industry and research

Types of Evolutionary Algorithms

The problem of the optimization problem is a problem, and an objective function space containing possible solutions given. The difference between the problem space of the application and the search space of the algorithm is that an EA can be a solution differently in order to process it better and play them back later in its original form (genotype -phenotype mapping, artificial embryogenesis ). This especially makes sense to when the representation of a possible solution can be significantly simplified and need not be processed in its complexity in memory. Different Evolutionary algorithms differ mainly in the following properties (see also the introductory sequence diagram):

• Search space (eg, binary numbers, real numbers, tree structures)
• Search operators (such as mutation and recombination)
• Fitness assignment and selection on the basis of the objective function
• Way be involved in the previous generations in the selection with ( parental generation ein-/ausschließen )
• Relationship between the search space and the problem space (genotype -phenotype mapping)

Classic versions

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

Genetic algorithms ( GA)

Genetic algorithms have been known primarily through the work John H. Holland. They use binary problem representation and therefore usually require a genotype -phenotype mapping. This means that represented binary solution candidates must be converted first in order to be evaluated with the fitness function. Because of this property they are the biological model of evolutionary algorithms all the next. The genetic material of natural organisms is similar in format to binary numbers into four nucleic acids. On this basis, natural mutation and recombination occur. However, the appearance (phenotype ) is not the genetic material itself, but arises from it by a multi-step process. The principle of genotype -phenotype mapping is analogous to a simplified form. The binary representation is useful for fast processing in computers. In the course of research in the field of EA itself has not been shown a clear advantage over other methods this.

The selection of the propagating individuals takes place at GA with fitness -proportional selection, reproduction itself by n-point crossover. And recombination of more than two parents genomes is possible and in some cases leads to better results. The mutation in GA you can vividly imagine, because the genomes are composed of individual bits inverted, can be duplicated or deleted ( all sequences). A theoretical investigation of the convergence behavior of genetic algorithms provides the schema set by John H. Holland.

Evolution Strategies ( ES)

Evolution strategies are direct problem representations ( eg, real numbers ). Problem and search space are thus identical. This has complex problems means that the evolution strategy can not explore the entire problem space when classical crossover operators are used (virtual alphabets ). ES primarily use mutation as a search operator and in some cases no recombination. The mutation represents an addition of a value of normal distribution, the variance (mutation thickness) is not constant. Since the algorithm with increasing solution quality converges (Scheme set), it is advantageous to adapt the variance. Thus it can be ensured that the ES seeks its targets in ever finer increments. For the adjustment, two methods have been established.

• Adaptive adjustment ( 1/5-Erfolgsregel ): The 1/5-Erfolgsregel states that the ratio of the successful mutations (that is mutations that result in an improvement of the adjustment ) should be about one-fifth to all mutations. If the quotient is larger, the variance of mutations should be increased with a smaller ratio should be reduced.
• Self-adaptivity: Each individual has an additional gene for the mutation while starch itself, this is not possible in biology, but the evolution in the computer finds a suitable variation in this way, without limitation, humans.

Genetic Programming (GP )

The goal of genetic programming is the creation of structures to transform a given input to a specified output (computer programs, circuits, or mathematical functions). The solution candidates are represented by trees.

The problem of symbolic regression a particular function is sought (eg, as a polynomial ). Where are couples, each with a value and the corresponding value. It is therefore known as the unknown function maps values ​​. With GP tree structures evolve that mimic the symbolic function most accurately.

A basic work on Genetic Programming wrote John Koza. He also recognized the opportunity to solve symbolic regression with GP. In the research of GP, this problem was often used as a benchmark test.

Evolutionary Programming ( EP)

Similar to the GP structures how to search computer programs, but which are not represented by trees but by finite automata. Only the numerical properties of the machine are varied, their structure is fixed. We are looking exclusively through mutation, recombination does not occur. Some individuals are considered different species, so to speak. Evolutionary programming has been little developed after its creation.