HOME

TheInfoList



OR:

Evolutionary algorithms (EA) reproduce essential elements of the biological evolution in a computer algorithm in order to solve "difficult" problems, at least approximately, for which no exact or satisfactory solution methods are known. They belong to the class of metaheuristics and are a
subset In mathematics, a Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they a ...
of population based bio-inspired algorithms and
evolutionary computation Evolutionary computation from computer science is a family of algorithms for global optimization inspired by biological evolution, and the subfield of artificial intelligence and soft computing studying these algorithms. In technical terms ...
, which itself are part of the field of
computational intelligence In computer science, computational intelligence (CI) refers to concepts, paradigms, algorithms and implementations of systems that are designed to show " intelligent" behavior in complex and changing environments. These systems are aimed at m ...
. The mechanisms of biological evolution that an EA mainly imitates are
reproduction Reproduction (or procreation or breeding) is the biological process by which new individual organisms – "offspring" – are produced from their "parent" or parents. There are two forms of reproduction: Asexual reproduction, asexual and Sexual ...
,
mutation In biology, a mutation is an alteration in the nucleic acid sequence of the genome of an organism, virus, or extrachromosomal DNA. Viral genomes contain either DNA or RNA. Mutations result from errors during DNA or viral replication, ...
, recombination and selection. Candidate solutions to the
optimization problem In mathematics, engineering, computer science and economics Economics () is a behavioral science that studies the Production (economics), production, distribution (economics), distribution, and Consumption (economics), consumption of goo ...
play the role of individuals in a population, and the fitness function determines the quality of the solutions (see also loss function).
Evolution Evolution is the change in the heritable Phenotypic trait, characteristics of biological populations over successive generations. It occurs when evolutionary processes such as natural selection and genetic drift act on genetic variation, re ...
of the population then takes place after the repeated application of the above operators. Evolutionary algorithms often perform well approximating solutions to all types of problems because they ideally do not make any assumption about the underlying fitness landscape. Techniques from evolutionary algorithms applied to the modeling of biological evolution are generally limited to explorations of microevolutionary processes and planning models based upon cellular processes. In most real applications of EAs, computational complexity is a prohibiting factor. In fact, this computational complexity is due to fitness function evaluation. Fitness approximation is one of the solutions to overcome this difficulty. However, seemingly simple EA can solve often complex problems; therefore, there may be no direct link between algorithm complexity and problem complexity.


Generic definition

The following is an example of a generic evolutionary algorithm: # Randomly generate the initial
population Population is a set of humans or other organisms in a given region or area. Governments conduct a census to quantify the resident population size within a given jurisdiction. The term is also applied to non-human animals, microorganisms, and pl ...
of individuals, the first generation. # Evaluate the fitness of each individual in the population. # Check, if the goal is reached and the algorithm can be terminated. # Select individuals as parents, preferably of higher fitness. # Produce offspring with optional crossover (mimicking
reproduction Reproduction (or procreation or breeding) is the biological process by which new individual organisms – "offspring" – are produced from their "parent" or parents. There are two forms of reproduction: Asexual reproduction, asexual and Sexual ...
). # Apply
mutation In biology, a mutation is an alteration in the nucleic acid sequence of the genome of an organism, virus, or extrachromosomal DNA. Viral genomes contain either DNA or RNA. Mutations result from errors during DNA or viral replication, ...
operations on the
offspring In biology, offspring are the young creation of living organisms, produced either by sexual reproduction, sexual or asexual reproduction. Collective offspring may be known as a brood or progeny. This can refer to a set of simultaneous offspring ...
. # Select individuals preferably of lower fitness for replacement with new individuals (mimicking
natural selection Natural selection is the differential survival and reproduction of individuals due to differences in phenotype. It is a key mechanism of evolution, the change in the Heredity, heritable traits characteristic of a population over generation ...
). # Return to 2


Types

Similar techniques differ in genetic representation and other implementation details, and the nature of the particular applied problem. *
Genetic algorithm In computer science and operations research, a genetic algorithm (GA) is a metaheuristic inspired by the process of natural selection that belongs to the larger class of evolutionary algorithms (EA). Genetic algorithms are commonly used to g ...
– This is the most popular type of EA. One seeks the solution of a problem in the form of strings of numbers (traditionally binary, although the best representations are usually those that reflect something about the problem being solved), by applying operators such as recombination and mutation (sometimes one, sometimes both). This type of EA is often used in
optimization Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criteria, from some set of available alternatives. It is generally divided into two subfiel ...
problems. * Genetic programming – Here the solutions are in the form of computer programs, and their fitness is determined by their ability to solve a computational problem. There are many variants of Genetic Programming: ** Cartesian genetic programming ** Gene expression programming ** Grammatical evolution ** Linear genetic programming ** Multi expression programming * Evolutionary programming – Similar to evolution strategy, but with a deterministic selection of all parents. *
Evolution strategy Evolution strategy (ES) from computer science is a subclass of evolutionary algorithms, which serves as an optimization (mathematics), optimization technique. It uses the major genetic operators mutation (evolutionary algorithm), mutation, recomb ...
(ES) – Works with vectors of real numbers as representations of solutions, and typically uses self-adaptive mutation rates. The method is mainly used for numerical optimization, although there are also variants for combinatorial tasks. **
CMA-ES Covariance matrix adaptation evolution strategy (CMA-ES) is a particular kind of strategy for numerical optimization. evolution strategy, Evolution strategies (ES) are stochastic, Derivative-free optimization, derivative-free methods for numerical ...
** Natural evolution strategy * Differential evolution – Based on vector differences and is therefore primarily suited for numerical optimization problems. * Coevolutionary algorithm – Similar to genetic algorithms and evolution strategies, but the created solutions are compared on the basis of their outcomes from interactions with other solutions. Solutions can either compete or cooperate during the search process. Coevolutionary algorithms are often used in scenarios where the fitness landscape is dynamic, complex, or involves competitive interactions. * Neuroevolution – Similar to genetic programming but the genomes represent artificial neural networks by describing structure and connection weights. The genome encoding can be direct or indirect. * Learning classifier system – Here the solution is a set of classifiers (rules or conditions). A Michigan-LCS evolves at the level of individual classifiers whereas a Pittsburgh-LCS uses populations of classifier-sets. Initially, classifiers were only binary, but now include real, neural net, or S-expression types. Fitness is typically determined with either a strength or accuracy based
reinforcement learning Reinforcement learning (RL) is an interdisciplinary area of machine learning and optimal control concerned with how an intelligent agent should take actions in a dynamic environment in order to maximize a reward signal. Reinforcement learnin ...
or
supervised learning In machine learning, supervised learning (SL) is a paradigm where a Statistical model, model is trained using input objects (e.g. a vector of predictor variables) and desired output values (also known as a ''supervisory signal''), which are often ...
approach. * Quality–Diversity algorithms – QD algorithms simultaneously aim for high-quality and diverse solutions. Unlike traditional optimization algorithms that solely focus on finding the best solution to a problem, QD algorithms explore a wide variety of solutions across a problem space and keep those that are not just high performing, but also diverse and unique.


Theoretical background

The following theoretical principles apply to all or almost all EAs.


No free lunch theorem

The no free lunch theorem of optimization states that all optimization strategies are equally effective when the set of all optimization problems is considered. Under the same condition, no evolutionary algorithm is fundamentally better than another. This can only be the case if the set of all problems is restricted. This is exactly what is inevitably done in practice. Therefore, to improve an EA, it must exploit problem knowledge in some form (e.g. by choosing a certain mutation strength or a problem-adapted coding). Thus, if two EAs are compared, this constraint is implied. In addition, an EA can use problem specific knowledge by, for example, not randomly generating the entire start population, but creating some individuals through
heuristics A heuristic or heuristic technique (''problem solving'', '' mental shortcut'', ''rule of thumb'') is any approach to problem solving that employs a pragmatic method that is not fully optimized, perfected, or rationalized, but is nevertheless ...
or other procedures. Another possibility to tailor an EA to a given problem domain is to involve suitable heuristics, local search procedures or other problem-related procedures in the process of generating the offspring. This form of extension of an EA is also known as a memetic algorithm. Both extensions play a major role in practical applications, as they can speed up the search process and make it more robust.


Convergence

For EAs in which, in addition to the offspring, at least the best individual of the parent generation is used to form the subsequent generation (so-called elitist EAs), there is a general proof of
convergence Convergence may refer to: Arts and media Literature *''Convergence'' (book series), edited by Ruth Nanda Anshen *Convergence (comics), "Convergence" (comics), two separate story lines published by DC Comics: **A four-part crossover storyline that ...
under the condition that an optimum exists. Without loss of generality, a maximum search is assumed for the proof: From the property of elitist offspring acceptance and the existence of the optimum it follows that per generation k an improvement of the fitness F of the respective best individual x' will occur with a probability P > 0. Thus: :F(x'_1) \leq F(x'_2) \leq F(x'_3) \leq \cdots \leq F(x'_k) \leq \cdots I.e., the fitness values represent a monotonically non-decreasing
sequence In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is cal ...
, which is bounded due to the existence of the optimum. From this follows the convergence of the sequence against the optimum. Since the proof makes no statement about the speed of convergence, it is of little help in practical applications of EAs. But it does justify the recommendation to use elitist EAs. However, when using the usual panmictic population model, elitist EAs tend to converge prematurely more than non-elitist ones. In a panmictic population model, mate selection (see step 4 of the generic definition) is such that every individual in the entire population is eligible as a mate. In non-panmictic populations, selection is suitably restricted, so that the dispersal speed of better individuals is reduced compared to panmictic ones. Thus, the general risk of premature convergence of elitist EAs can be significantly reduced by suitable population models that restrict mate selection.


Virtual alphabets

With the theory of virtual alphabets, David E. Goldberg showed in 1990 that by using a representation with real numbers, an EA that uses classical recombination operators (e.g. uniform or n-point crossover) cannot reach certain areas of the search space, in contrast to a coding with binary numbers. This results in the recommendation for EAs with real representation to use arithmetic operators for recombination (e.g. arithmetic mean or intermediate recombination). With suitable operators, real-valued representations are more effective than binary ones, contrary to earlier opinion.


Comparison to other concepts


Biological processes

A possible limitation of many evolutionary algorithms is their lack of a clear genotype–phenotype distinction. In nature, the fertilized egg cell undergoes a complex process known as
embryogenesis An embryo ( ) is the initial stage of development for a multicellular organism. In organisms that reproduce sexually, embryonic development is the part of the life cycle that begins just after fertilization of the female egg cell by the male ...
to become a mature
phenotype In genetics, the phenotype () is the set of observable characteristics or traits of an organism. The term covers the organism's morphology (physical form and structure), its developmental processes, its biochemical and physiological propert ...
. This indirect
encoding In communications and Data processing, information processing, code is a system of rules to convert information—such as a letter (alphabet), letter, word, sound, image, or gesture—into another form, sometimes data compression, shortened or ...
is believed to make the genetic search more robust (i.e. reduce the probability of fatal mutations), and also may improve the evolvability of the organism. Such indirect (also known as generative or developmental) encodings also enable evolution to exploit the regularity in the environment. Recent work in the field of artificial embryogeny, or artificial developmental systems, seeks to address these concerns. And gene expression programming successfully explores a genotype–phenotype system, where the genotype consists of linear multigenic chromosomes of fixed length and the phenotype consists of multiple expression trees or computer programs of different sizes and shapes.


Monte-Carlo methods

Both method classes have in common that their individual search steps are determined by chance. The main difference, however, is that EAs, like many other metaheuristics, learn from past search steps and incorporate this experience into the execution of the next search steps in a method-specific form. With EAs, this is done firstly through the fitness-based selection operators for partner choice and the formation of the next generation. And secondly, in the type of search steps: In EA, they start from a current solution and change it or they mix the information of two solutions. In contrast, when dicing out new solutions in Monte-Carlo methods, there is usually no connection to existing solutions. If, on the other hand, the search space of a task is such that there is nothing to learn, Monte-Carlo methods are an appropriate tool, as they do not contain any algorithmic overhead that attempts to draw suitable conclusions from the previous search. An example of such tasks is the proverbial ''search for a needle in a haystack'', e.g. in the form of a flat (hyper)plane with a single narrow peak.


Applications

The areas in which evolutionary algorithms are practically used are almost unlimited and range from industry, engineering, complex scheduling, agriculture, robot movement planning and finance to research and art. The application of an evolutionary algorithm requires some rethinking from the inexperienced user, as the approach to a task using an EA is different from conventional exact methods and this is usually not part of the curriculum of engineers or other disciplines. For example, the fitness calculation must not only formulate the goal but also support the evolutionary search process towards it, e.g. by rewarding improvements that do not yet lead to a better evaluation of the original quality criteria. For example, if peak utilisation of resources such as personnel deployment or energy consumption is to be avoided in a scheduling task, it is not sufficient to assess the maximum utilisation. Rather, the number and duration of exceedances of a still acceptable level should also be recorded in order to reward reductions below the actual maximum peak value. There are therefore some publications that are aimed at the beginner and want to help avoiding beginner's mistakes as well as leading an application project to success. This includes clarifying the fundamental question of when an EA should be used to solve a problem and when it is better not to.


Related techniques and other global search methods

There are some other proven and widely used methods of nature inspired global search techniques such as * Memetic algorithm – A hybrid method, inspired by Richard Dawkins's notion of a meme. It commonly takes the form of a population-based algorithm (frequently an EA) coupled with individual learning procedures capable of performing local refinements. Emphasizes the exploitation of problem-specific knowledge and tries to orchestrate local and global search in a synergistic way. * A cellular evolutionary or memetic algorithm uses a topological neighbouhood relation between the individuals of a population for restricting the mate selection and by that reducing the propagation speed of above-average individuals. The idea is to maintain genotypic diversity in the population over a longer period of time to reduce the risk of premature convergence. * Ant colony optimization is based on the ideas of ant foraging by pheromone communication to form paths. Primarily suited for
combinatorial optimization Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the set of feasible solutions is discrete or can be reduced to a discrete set. Typical combina ...
and graph problems. * Particle swarm optimization is based on the ideas of animal flocking behaviour. Also primarily suited for numerical optimization problems. * Gaussian adaptation – Based on information theory. Used for maximization of manufacturing yield, mean fitness or average information. See for instance Entropy in thermodynamics and information theory. In addition, many new nature-inspired or methaphor-guided algorithms have been proposed since the beginning of this century. For criticism of most publications on these, see the remarks at the end of the introduction to the article on metaheuristics.


Examples

In 2020,
Google Google LLC (, ) is an American multinational corporation and technology company focusing on online advertising, search engine technology, cloud computing, computer software, quantum computing, e-commerce, consumer electronics, and artificial ...
stated that their AutoML-Zero can successfully rediscover classic algorithms such as the concept of neural networks. The computer simulations '' Tierra'' and '' Avida'' attempt to model macroevolutionary dynamics.


Gallery

File:Two-population EA search (2).gif, A two-population EA search over a constrained Rosenbrock function with bounded global optimum File:Two-population EA search (3).gif, A two-population EA search over a constrained Rosenbrock function. Global optimum is not bounded. File:Estimation of Distribution Algorithm animation.gif, Estimation of distribution algorithm over Keane's bump function File:Two population EA animation.gif, A two-population EA search of a bounded optima of Simionescu's function


References


Bibliography

* Ashlock, D. (2006), ''Evolutionary Computation for Modeling and Optimization'', Springer, New York, doi:10.1007/0-387-31909-3 . * Bäck, T. (1996),
Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolutionary Programming, Genetic Algorithms
', Oxford Univ. Press, New York, . * Bäck, T., Fogel, D., Michalewicz, Z. (1999), ''Evolutionary Computation 1: Basic Algorithms and Operators'', CRC Press, Boca Raton, USA, . * Bäck, T., Fogel, D., Michalewicz, Z. (2000), ''Evolutionary Computation 2: Advanced Algorithms and Operators'', CRC Press, Boca Raton, USA, doi:10.1201/9781420034349 . * Banzhaf, W., Nordin, P., Keller, R., Francone, F. (1998), ''Genetic Programming - An Introduction'', Morgan Kaufmann, San Francisco, . * Eiben, A.E., Smith, J.E. (2003), ''Introduction to Evolutionary Computing'', Springer, Heidelberg, New York, doi:10.1007/978-3-662-44874-8 . * Holland, J. H. (1992),
Adaptation in Natural and Artificial Systems
', MIT Press, Cambridge, MA, . * Michalewicz, Z.; Fogel, D.B. (2004), ''How To Solve It: Modern Heuristics''. Springer, Berlin, Heidelberg, , doi:10.1007/978-3-662-07807-5. * * * Price, K., Storn, R.M., Lampinen, J.A., (2005)
''Differential Evolution: A Practical Approach to Global Optimization''
Springer, Berlin, Heidelberg, , doi:10.1007/3-540-31306-0. * Ingo Rechenberg (1971), ''Evolutionsstrategie - Optimierung technischer Systeme nach Prinzipien der biologischen Evolution'' (PhD thesis). Reprinted by Fromman-Holzboog (1973). * Hans-Paul Schwefel (1974), ''Numerische Optimierung von Computer-Modellen'' (PhD thesis). Reprinted by Birkhäuser (1977). * Hans-Paul Schwefel (1995),
Evolution and Optimum Seeking
'. Wiley & Sons, New York. * Simon, D. (2013)
''Evolutionary Optimization Algorithms''
, Wiley & Sons, * Kruse, Rudolf; Borgelt, Christian; Klawonn, Frank; Moewes, Christian; Steinbrecher, Matthias; Held, Pascal (2013)
''Computational Intelligence: A Methodological Introduction''
Springer, London. , doi:10.1007/978-1-4471-5013-8. *


External links


An Overview of the History and Flavors of Evolutionary Algorithms
{{DEFAULTSORT:Evolutionary Algorithm Cybernetics Evolution Optimization algorithms and methods