Evolutionary algorithm

Part of a series on the
Evolutionary algorithm
Chromosome Fitness function Genetic operator Crossover Mutation Selection Population model
Genetic algorithm (GA)
Chromosome Clonal selection algorithm Fly algorithm Genetic fuzzy systems Genetic memory Schema Promoter based GA
Genetic programming (GP)
Cartesian GP Linear GP Gene expression programming Grammatical evolution Multi expression programming
Differential evolution
Evolution strategy
Evolutionary programming
Related topics
Cellular EA Cultural algorithm Effective fitness Evolutionary computation Gaussian adaptation Grammar induction Evolutionary multimodal optimization Memetic algorithm Neuroevolution
v t e

Evolutionary algorithms (EA) reproduce essential elements of 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 are metaheuristics and population-based bio-inspired algorithms and evolutionary computation, which itself are part of the field of computational intelligence. The mechanisms of biological evolution that an EA mainly imitates are reproduction, mutation, recombination and selection. Candidate solutions to the optimization problem play the role of individuals in a population, and the fitness function determines the quality of the solutions (see also loss function). Evolution 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 microevolution (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.

(μ,λ)- and n function evaluations decreases only at a rate governed by the dimension. In particular, for Lipschitz-continuous black-box functions the worst-case error is of order ε−d. This exponential dependence on the dimension is an instance of the curse of dimensionality.

Like the no free lunch theorem, this result limits what can be guaranteed without additional problem structure, although the two results have different mathematical foundations. In the Lipschitz case, adaptivity or randomization does not in general remove the unfavorable worst-case dependence on dimension. Novak and Ritter also investigated global optimization based on hyperbolic cross points as a structured sampling approach.

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 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 x′ will occur with a probability 0"}}'>P>0. Thus:

Monte-Carlo methods

edit

EAs and Monte-Carlo methods 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

edit

Evolutionary algorithms are also widely used for problems with several conflicting objectives; this area is known as evolutionary multi-objective optimization (EMO).

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

edit

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 neighborhood 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 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 metaphor-guided algorithms have been proposed since the beginning of the 21st century. For criticism of most publications on these, see the remarks at the end of the introduction to the article on metaheuristics.

Examples

edit

In 2020, Google 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

edit

Vikhar, P. A. (2016). "Evolutionary algorithms: A critical review and its future prospects". 2016 International Conference on Global Trends in Signal Processing, Information Computing and Communication (ICGTSPICC). IEEE. pp. 261–265. doi:10.1109/ICGTSPICC.2016.7955308. ISBN 978-1-5090-0467-6. S2CID 22100336.
• 1 2 3 Mika, Marek; Waligóra, Grzegorz; Węglarz, Jan (2011). "Modelling and solving grid resource allocation problem with network resources for workflow applications". Journal of Scheduling. 14 (3): 291–306. doi:10.1007/s10951-009-0158-0. ISSN 1094-6136. S2CID 31859338.
• 1 2 "},"publisher":{"wt":"The conference is part of the Evo* series. The conference proceedings are published by Springer"},"access-date":{"wt":"2022-12-23"}},"i":0}}]}'/>"International Conference on the Applications of Evolutionary Computation". The conference is part of the Evo* series. The conference proceedings are published by Springer. Retrieved 2022-12-23.
• ↑ Tavares, Jorge; Machado, Penousal; Cardoso, Amílcar; Pereira, Francisco B.; Costa, Ernesto (2004). "On the Evolution of Evolutionary Algorithms". Genetic Programming. Lecture Notes in Computer Science. Vol. 3003. Springer. pp. 389–398. doi:10.1007/978-3-540-24650-3_37. ISBN 978-3-540-21346-8.
• ↑ Beyer, Hans-Georg; Schwefel, Hans-Paul (2002). "Evolution strategies – A comprehensive introduction". Natural Computing. 1 (1): 3–52. doi:10.1023/A:1015059928466.
• ↑ Ma, Xiaoliang; Li, Xiaodong; Zhang, Qingfu; Tang, Ke; Liang, Zhengping; Xie, Weixin; Zhu, Zexuan (2019), "A Survey on Cooperative Co-Evolutionary Algorithms.", IEEE Transactions on Evolutionary Computation, 23 (3): 421–441, Bibcode:2019ITEC...23..421M, doi:10.1109/TEVC.2018.2868770, S2CID 125149900
• ↑ Lehman, Joel; Stanley, Kenneth O. (2011-07-12). "Evolving a diversity of virtual creatures through novelty search and local competition". Proceedings of the 13th annual conference on Genetic and evolutionary computation. New York, NY, USA: ACM. pp. 211–218. doi:10.1145/2001576.2001606. ISBN 9781450305570. S2CID 17338175.
• ↑ Lienig, Jens; Brandt, Holger (1994), "An evolutionary algorithm for the routing of multi-chip modules", in Davidor, Yuval; Schwefel, Hans-Paul; Männer, Reinhard (eds.), Parallel Problem Solving from Nature — PPSN III, vol. 866, Berlin, Heidelberg: Springer, pp. 588–597, doi:10.1007/3-540-58484-6_301, ISBN 978-3-540-58484-1
• ↑ Leung, Yee; Gao, Yong; Xu, Zong-Ben (1997). "Degree of population diversity - a perspective on premature convergence in genetic algorithms and its Markov chain analysis". IEEE Transactions on Neural Networks. 8 (5): 1165–1176. doi:10.1109/72.623217. ISSN 1045-9227. PMID 18255718.
• ↑ Goldberg, David E. (1990), "The theory of virtual alphabets", in Schwefel, Hans-Paul; Männer, Reinhard (eds.), Parallel Problem Solving from Nature, Lecture Notes in Computer Science, vol. 496, Berlin/Heidelberg: Springer-Verlag, pp. 13–22, doi:10.1007/bfb0029726, ISBN 978-3-540-54148-6{{citation}}: More than one of |publication-date= and |date= specified (help)
• ↑ Hornby, Gregory S.; Pollack, Jordan B. (July 2002). "Creating High-Level Components with a Generative Representation for Body-Brain Evolution". Artificial Life. 8 (3): 223–246. doi:10.1162/106454602320991837. ISSN 1064-5462.
• ↑ Jeff Clune, Benjamin Beckmann, Charles Ofria, and Robert Pennock. "Evolving Coordinated Quadruped Gaits with the HyperNEAT Generative Encoding" Archived 2016-06-03 at the Wayback Machine. Proceedings of the IEEE Congress on Evolutionary Computing Special Section on Evolutionary Robotics, 2009. Trondheim, Norway.
• ↑ Fogel, David B.; Bäck, Thomas; Michalewicz, Zbigniew, eds. (2000). Evolutionary Computation 1. Bristol; Philadelphia: Institute of Physics Publishing. pp. xxx and xxxvii (Glossary). doi:10.1162/evco.1993.1.1.1. ISBN 978-0-7503-0664-5. OCLC 44807816.
• ↑ Gen, Mitsuo; Cheng, Runwei (1999-12-17). Genetic Algorithms and Engineering Optimization. Wiley Series in Engineering Design and Automation. Hoboken, NJ, USA: John Wiley & Sons, Inc. doi:10.1002/9780470172261. ISBN 978-0-470-17226-1.
• ↑ Mayer, David G. (2002). Evolutionary Algorithms and Agricultural Systems. Boston, MA: Springer US. doi:10.1007/978-1-4615-1717-7. ISBN 978-1-4613-5693-6.
• ↑ Chen, Shu-Heng, ed. (2002). Evolutionary Computation in Economics and Finance. Studies in Fuzziness and Soft Computing. Vol. 100. Heidelberg: Physica-Verlag HD. doi:10.1007/978-3-7908-1784-3. ISBN 978-3-7908-2512-1.
• ↑ Fogel, Gary; Corne, David (2003). Evolutionary Computation in Bioinformatics. Elsevier. doi:10.1016/b978-1-55860-797-2.x5000-8. ISBN 978-1-55860-797-2.
• 1 2 Eiben, A.E.; Smith, J.E. (2015). "Working with Evolutionary Algorithms". Introduction to Evolutionary Computing. Natural Computing Series (2nd ed.). Berlin, Heidelberg: Springer. pp. 147–163. doi:10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1. S2CID 20912932.
• ↑ Cotta, Carlos; Fernàndez, Antonio J. (2007), "Memetic Algorithms in Planning, Scheduling, and Timetabling", in Dahal, Keshav P.; Tan, Kay Chen; Cowling, Peter I. (eds.), Evolutionary Scheduling, vol. 49, Berlin, Heidelberg: Springer, pp. 1–30, doi:10.1007/978-3-540-48584-1_1, ISBN 978-3-540-48582-7
• ↑ Dorigo, Marco; Stützle, Thomas G. (June 2004). Ant Colony Optimization. Cambridge, Mass: MIT. ISBN 978-0-262-04219-2.
• ↑ Kjellström, Gregor; Taxén, Lars (1992), "Gaussian Adaptation, an Evolution-Based Efficient Global Optimizer", in Brezinski, Claude; Kulisch, Ulrich (eds.), Computational and Applied Mathematics. 1: Algorithms and Theory, Amsterdam: North-Holland, pp. 267–276, ISBN 978-0-444-89701-5, retrieved 2026-04-03
• ↑ Simionescu, P.A.; Dozier, G.V.; Wainwright, R.L. (2006). "A Two-Population Evolutionary Algorithm for Constrained Optimization Problems" (PDF). 2006 IEEE International Conference on Evolutionary Computation. Proc 2006 IEEE International Conference on Evolutionary Computation. IEEE. pp. 1647–1653. doi:10.1109/CEC.2006.1688506. ISBN 0-7803-9487-9. S2CID 1717817. Retrieved 7 January 2017.
• ↑ ISBN 978-0-19-509971-3.
• Bäck, T.; Foussette, C.; Krause, P. (2013), Contemporary Evolution Strategies. Natural Computing Series, Springer, Berlin, Heidelberg. doi:10.1007/978-3-642-40137-4. ISBN 978-0-3678-0637-8.
• Banzhaf, W., Nordin, P., Keller, R., Francone, F. (1998), Genetic Programming - An Introduction, Morgan Kaufmann, San Francisco, ISBN 978-0-262-08213-6.
• Michalewicz, Z.; Fogel, D.B. (2004), How To Solve It: Modern Heuristics. Springer, Berlin, Heidelberg, ISBN 978-3-642-42416-8, doi:10.1007/3-540-31306-0.
• Ingo Rechenberg (1973), Evolutionsstrategie: Optimierung technischer Systeme nach Prinzipien der biologischen Evolution. Frommann-Holzboog, Stuttgart-Bad Cannstatt, ISBN 978-3-7643-0876-6, doi:10.1007/978-3-0348-5927-1.
• Hans-Paul Schwefel (1995), Evolution and Optimum Seeking. Wiley & Sons, New York. ISBN 978-1-4471-5012-1, doi:10.1007/978-1-4471-5013-8.