1,569
个编辑
更改
跳到导航
跳到搜索
Moved page from wikipedia:en:Evolutionary algorithm (history)
此词条暂由彩云小译翻译，未经人工整理和审校，带来阅读不便，请见谅。
{{Artificial intelligence}}
In [[artificial intelligence]] (AI), an '''evolutionary algorithm''' ('''EA''') is a [[subset]] of [[evolutionary computation]],<ref name="EVOALG">{{cite article|last=Vikhar|first=P. A.|title=Evolutionary algorithms: A critical review and its future prospects|doi=10.1109/ICGTSPICC.2016.7955308|journal=Proceedings of the 2016 International Conference on Global Trends in Signal Processing, Information Computing and Communication (ICGTSPICC)|location= Jalgaon|year= 2016|pages=261-265|isbn=978-1-5090-0467-6}}</ref> a generic population-based [[metaheuristic]] [[optimization (mathematics)|optimization]] [[algorithm]]. An EA uses mechanisms inspired by [[biological evolution]], such as [[reproduction]], [[mutation]], [[genetic recombination|recombination]], and [[natural selection|selection]]. [[Candidate solution]]s 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.
In artificial intelligence (AI), an evolutionary algorithm (EA) is a subset of evolutionary computation, a generic population-based metaheuristic optimization algorithm. An EA uses mechanisms inspired by biological evolution, such as 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.
在人工智能(AI)中，进化算法(EA)是一种基于种群的元启发式优化算法进化计算的子集。Ea 使用生物进化启发的机制，如繁殖、变异、重组和选择。最佳化问题的候选解决方案扮演了种群中个体的角色，而适应度函数决定了解决方案的质量(参见损失函数)。在重复应用上述算子之后，种群的演化就发生了。
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.<ref name="VLSI">{{cite book|last=Cohoon|first=J|display-authors=etal|title=Evolutionary algorithms for the physical design of VLSI circuits|url= https://www.ifte.de/mitarbeiter/lienig/cohoon.pdf|journal=Advances in Evolutionary Computing: Theory and Applications|publisher= Springer, pp. 683-712, 2003|isbn=978-3-540-43330-9|date=2002-11-26}}</ref> 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{{Citation needed|date=June 2018}}; therefore, there may be no direct link between algorithm complexity and problem complexity.
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.
进化算法通常对所有类型的问题都能很好地执行近似解决方案，因为在理想情况下，它们不会对潜在的适应度场景做出任何假设。应用于生物进化建模的进化算法技术通常局限于微进化过程和基于细胞过程的规划模型的探索。在大多数实际应用中，计算复杂度是一个禁止因素。实际上，这种计算复杂性是由于适应度函数的计算。适应度逼近是克服这一困难的解决方案之一。然而，看似简单的 EA 可以解决常常是复杂的问题，因此，算法复杂度和问题复杂度之间可能没有直接的联系。
==Implementation==
Step One: Generate the initial [[population]] of [[individual]]s randomly. (First generation)
Step One: Generate the initial population of individuals randomly. (First generation)
第一步: 随机生成个体的初始种群。(第一代)
Step Two: Repeat the following regenerational steps until termination:
Step Two: Repeat the following regenerational steps until termination:
第二步: 重复以下重生步骤直到终止:
#Evaluate the [[Fitness function|fitness]] of each individual in the population (time limit, sufficient fitness achieved, etc.)
Evaluate the fitness of each individual in the population (time limit, sufficient fitness achieved, etc.)
评估群体中每个个体的适应性(时间限制，达到的足够适应性，等等)
#Select the fittest individuals for [[reproduce|reproduction]]. (Parents)
Select the fittest individuals for reproduction. (Parents)
选择最适合繁殖的个体。(家长)
# [[Breed]] new individuals through [[crossover (genetic algorithm)|crossover]] and [[mutation (genetic algorithm)|mutation]] operations to give birth to [[offspring]].
Breed new individuals through crossover and mutation operations to give birth to offspring.
通过交叉和变异操作繁殖新个体以产生后代。
# Replace the least-fit individuals of the population with new individuals.
Replace the least-fit individuals of the population with new individuals.
用新的个体取代人口中最不健康的个体。
==Types==
Similar techniques differ in [[genetic representation]] and other implementation details, and the nature of the particular applied problem.
Similar techniques differ in genetic representation and other implementation details, and the nature of the particular applied problem.
类似的技术在遗传表示和其他实现细节以及特定应用问题的性质上有所不同。
*[[Genetic algorithm]] – 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),<ref name=VLSI/> by applying operators such as recombination and mutation (sometimes one, sometimes both). This type of EA is often used in [[Optimization (mathematics)|optimization]] 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.
*[[Evolutionary programming]] – Similar to genetic programming, but the structure of the program is fixed and its numerical parameters are allowed to evolve.
*[[Gene expression programming]] – Like genetic programming, GEP also evolves computer programs but it explores a genotype-phenotype system, where computer programs of different sizes are encoded in linear chromosomes of fixed length.
*[[Evolution strategy]] – Works with vectors of real numbers as representations of solutions, and typically uses self-adaptive mutation rates.
*[[Differential evolution]] – Based on vector differences and is therefore primarily suited for [[numerical optimization]] problems.
*[[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]] or [[supervised learning]] approach.
==Comparison to biological processes==
A possible limitation{{According to whom|date=May 2013}} 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]] to become a mature [[phenotype]]. This indirect [[encoding]] 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.<ref>G.S. Hornby and J.B. Pollack. "Creating high-level components with a generative representation for body-brain evolution". ''[[Artificial Life (journal)|Artificial Life]]'', 8(3):223–246, 2002.</ref><ref>Jeff Clune, Benjamin Beckmann, Charles Ofria, and Robert Pennock. [http://www.ofria.com/pubs/2009CluneEtAl.pdf "Evolving Coordinated Quadruped Gaits with the HyperNEAT Generative Encoding"] {{Webarchive|url=https://web.archive.org/web/20160603205252/http://www.ofria.com/pubs/2009CluneEtAl.pdf |date=2016-06-03 }}. ''Proceedings of the IEEE Congress on Evolutionary Computing Special Section on Evolutionary Robotics'', 2009. Trondheim, Norway.</ref> Such indirect (a.k.a. generative or developmental) encodings also enable evolution to exploit the regularity in the environment.<ref>J. Clune, C. Ofria, and R. T. Pennock, [http://jeffclune.com/publications/Clune-HyperNEATandRegularity.pdf "How a generative encoding fares as problem-regularity decreases"], in ''PPSN'' (G. Rudolph, T. Jansen, S. M. Lucas, C. Poloni, and N. Beume, eds.), vol. 5199 of ''Lecture Notes in Computer Science'', pp. 358–367, Springer, 2008.</ref> Recent work in the field of [[artificial development|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.<ref>Ferreira, C., 2001. [http://www.gene-expression-programming.com/webpapers/GEP.pdf "Gene Expression Programming: A New Adaptive Algorithm for Solving Problems"]. ''Complex Systems'', Vol. 13, issue 2: 87–129.</ref>{{Synthesis inline|date=May 2013}}
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 to become a mature phenotype. This indirect encoding 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 (a.k.a. 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.
许多进化算法的一个可能的局限性是它们缺乏明确的基因型-表型区分。在自然界中，受精卵细胞经历一个称为胚胎发生的复杂过程，最终形成成熟的表型。这种间接编码被认为可以使遗传搜索更加健壮(即:。减少致命突变的可能性) ，也可能提高生物体的可进化性。这种间接的。生殖编码或发育编码也使进化能够利用环境中的规律性。最近在人工胚胎发生或人工发育系统领域的工作，试图解决这些问题。基因表达式编程成功地探索了一个基因型-表现型系统，其中基因型由固定长度的线性多基因染色体组成，表现型由多个表达树或不同大小和形状的计算机程序组成。
==Related techniques==
[[Swarm intelligence|Swarm algorithms]]{{clarify|reason=Why are swarm algorithms associated with evolutionary ones?|date=January 2018}} include
Swarm algorithms include
群算法包括
* [[Ant colony optimization]] – Based on the ideas of ant foraging by pheromone communication to form paths. Primarily suited for [[combinatorial optimization]] and [[graph theory|graph]] problems.
* The runner-root algorithm (RRA) is inspired by the function of runners and roots of plants in nature<ref>F. Merrikh-Bayat, "The runner-root algorithm: A metaheuristic for solving unimodal and multimodal optimization problems inspired by runners and roots of plants in nature", ''Applied Soft Computing'', Vol. 33, pp. 292–303, 2015</ref>
* [[Artificial bee colony algorithm]] – Based on the honey bee foraging behaviour. Primarily proposed for numerical optimization and extended to solve combinatorial, constrained and multi-objective optimization problems.
* [[Bees algorithm]] is based on the foraging behaviour of honey bees. It has been applied in many applications such as routing and scheduling.
* [[Cuckoo search]] is inspired by the brooding parasitism of the [[cuckoo]] species. It also uses [[Lévy flight]]s, and thus it suits for global [[optimization]] problems.
* Electimize optimization - Based on the behavior of electron flow through electric circuit branches with the least electric resistance.<ref>{{Cite journal|last=Khalafallah Ahmed|last2=Abdel-Raheem Mohamed|date=2011-05-01|title=Electimize: New Evolutionary Algorithm for Optimization with Application in Construction Engineering|journal=Journal of Computing in Civil Engineering|volume=25|issue=3|pages=192–201|doi=10.1061/(ASCE)CP.1943-5487.0000080}}</ref>
*[[Particle swarm optimization]] – Based on the ideas of animal flocking behaviour. Also primarily suited for [[numerical optimization]] problems.
==Other population-based [[metaheuristic]] methods==
*[[Hunting Search]] – A method inspired by the group hunting of some animals such as wolves that organize their position to surround the prey, each of them relative to the position of the others and especially that of their leader. It is a continuous optimization method<ref>{{cite journal |last1=Oftadeh |first1=R. |last2=Mahjoob |first2=M.J. |last3=Shariatpanahi |first3=M. |title=A novel meta-heuristic optimization algorithm inspired by group hunting of animals: Hunting search |journal=Computers & Mathematics with Applications |date=October 2010 |volume=60 |issue=7 |pages=2087–2098 |doi=10.1016/j.camwa.2010.07.049 }}</ref> adapted as a combinatorial optimization method.<ref>{{cite journal |author1=Amine Agharghor |author2=Mohammed Essaid Riffi |year=2017 |title=First Adaptation of Hunting Search Algorithm for the Quadratic Assignment Problem |journal=Europe and MENA Cooperation Advances in Information and Communication Technologies |volume=520 |pages=263–267 |doi=10.1007/978-3-319-46568-5_27 |isbn=978-3-319-46567-8|series=Advances in Intelligent Systems and Computing }}</ref>
*[[Adaptive dimensional search]] – Unlike nature-inspired metaheuristic techniques, an adaptive dimensional search algorithm does not implement any metaphor as an underlying principle. Rather it uses a simple performance-oriented method, based on the update of the search dimensionality ratio (SDR) parameter at each iteration.<ref>Hasançebi, O., Kazemzadeh Azad, S. (2015), "Adaptive Dimensional Search: A New Metaheuristic Algorithm for Discrete Truss Sizing Optimization", ''Computers and Structures'', 154, 1–16.</ref>
*[[Firefly algorithm]] is inspired by the behavior of fireflies, attracting each other by flashing light. This is especially useful for multimodal optimization.
*[[Harmony search]] – Based on the ideas of musicians' behavior in searching for better harmonies. This algorithm is suitable for combinatorial optimization as well as parameter optimization.
*[[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]].
*[[Memetic algorithm]] – A hybrid method, inspired by [[Richard Dawkins]]'s notion of a meme, it commonly takes the form of a population-based algorithm 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.
*Emperor Penguins Colony – A method inspired by the behavior of emperor penguins in their colony. The emperor penguins in the colony seek to create the appropriate heat and regulate their body temperature, and this heat is completely coordinated and controlled by the movement of the penguins.<ref>{{cite journal |last1=Harifi |first1=Sasan |last2=Khalilian |first2=Madjid |last3=Mohammadzadeh |first3=Javad |last4=Ebrahimnejad |first4=Sadoullah |title=Emperor Penguins Colony: a new metaheuristic algorithm for optimization |journal=Evolutionary Intelligence |date=25 February 2019 |volume=12 |issue=2 |pages=211–226 |doi=10.1007/s12065-019-00212-x }}</ref>
==Examples==
In 2020, [[Google]] stated their AutoML-Zero can successfully rediscover classic algorithms such as the concept of neural networks.<ref>{{cite news |last1=Gent |first1=Edd |title=Artificial intelligence is evolving all by itself |url=https://www.sciencemag.org/news/2020/04/artificial-intelligence-evolving-all-itself |accessdate=16 April 2020 |work=Science {{!}} AAAS |date=13 April 2020 |language=en |archive-url=https://web.archive.org/web/20200416222954/https://www.sciencemag.org/news/2020/04/artificial-intelligence-evolving-all-itself |archive-date=16 April 2020 |url-status=dead }}</ref>
In 2020, Google stated their AutoML-Zero can successfully rediscover classic algorithms such as the concept of neural networks.
2020年，谷歌宣布他们的 autol-zero 可以成功地重新发现经典算法，比如神经网络的概念。
The computer simulations ''[[Tierra (computer simulation)|Tierra]]'' and ''[[Avida]]'' attempt to model [[macroevolution]]ary dynamics.
The computer simulations Tierra and Avida attempt to model macroevolutionary dynamics.
Tierra 和阿维达的计算机模拟试图建立宏观进化动力学模型。
==Gallery ==
<ref>{{Cite journal |last1=Simionescu |first1=P.A. |last2=Beale |first2=D.G. |last3=Dozier |first3=G.V. |title=Constrained optimization problem solving using estimation of distribution algorithms |series=Proc. of the 2004 Congress on Evolutionary Computation - CEC2004|place=Portland, OR |pages=1647–1653 |year=2004 |doi=10.1109/CEC.2006.1688506 |url=http://faculty.tamucc.edu/psimionescu/PDFs/WCCI2004-Paper1361.pdf |access-date=7 January 2017}}</ref>
<ref>{{Cite book |last1=Simionescu |first1=P.A. |title=2006 IEEE International Conference on Evolutionary Computation |last2=Dozier |first2=G.V. |last3=Wainwright |first3=R.L. |chapter=A Two-Population Evolutionary Algorithm for Constrained Optimization Problems |series=Proc 2006 IEEE International Conference on Evolutionary Computation|place=Vancouver, Canada |pages=1647–1653 |year=2006 |doi=10.1109/CEC.2006.1688506 |chapter-url=http://faculty.tamucc.edu/psimionescu/PDFs/WCCI2006-Paper7204(1).pdf |access-date=7 January 2017|isbn=0-7803-9487-9 }}</ref>
<ref>{{cite book|last=Simionescu|first=P.A.|title=Computer Aided Graphing and Simulation Tools for AutoCAD Users|year=2014|publisher=[[CRC Press]]|location=Boca Raton, FL|isbn=978-1-4822-5290-3|edition=1st}}</ref>
<gallery>
<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 (2).gif|A two-population EA search over a constrained Rosenbrock function with bounded global optimum.
文件: 双种群 EA 搜索(2) . gif | 有界全局最优的约束 Rosenbrock函数上的双种群 EA 搜索。
File:Two-population EA search (3).gif|A two-population EA search over a constrained [[Rosenbrock function]]. Global optimum is not bounded.
File:Two-population EA search (3).gif|A two-population EA search over a constrained Rosenbrock function. Global optimum is not bounded.
文件: Two-population EA search (3) . gif | a Two-population EA search over a constrained Rosenbrock函数。全局最优不是有界的。
File:Estimation of Distribution Algorithm animation.gif|[[Estimation of distribution algorithm]] over [[Keane's function]]
File:Estimation of Distribution Algorithm animation.gif|Estimation of distribution algorithm over Keane's function
文件: 分布估计算法
File:Two population EA animation.gif|A two-population EA search of a bounded optima of [[Test_functions_for_optimization#Test_functions_for_constrained_optimization|Simionescu's function]].
File:Two population EA animation.gif|A two-population EA search of a bounded optima of Simionescu's function.
文件: Two population EA animation.gif | a Two-population EA search of a bounded optima of Simionescu’s function。
</gallery>
</gallery>
/ 画廊
== References ==
{{Reflist}}
==Bibliography==
* Ashlock, D. (2006), ''Evolutionary Computation for Modeling and Optimization'', Springer, {{ISBN|0-387-22196-4}}.
* Bäck, T. (1996), ''[https://books.google.com/books?id=htJHI1UrL7IC&printsec=frontcover#v=onepage&q&f=false Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolutionary Programming, Genetic Algorithms]'', Oxford Univ. Press.
* Bäck, T., Fogel, D., Michalewicz, Z. (1997), ''Handbook of Evolutionary Computation'', Oxford Univ. Press.
* 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.
* Holland, J. H. (1992), ''[https://books.google.com/books?id=5EgGaBkwvWcC&printsec=frontcover#v=onepage&q&f=false Adaptation in Natural and Artificial Systems]'', The University of Michigan Press, Ann Arbor
* Michalewicz Z., Fogel D.B. (2004). How To Solve It: Modern Heuristics, Springer.
* {{cite book |doi=10.1109/BICTA.2010.5645312 |chapter=Bin Packing/Covering with Delivery, solved with the evolution of algorithms |title=2010 IEEE Fifth International Conference on Bio-Inspired Computing: Theories and Applications (BIC-TA) |pages=298–302 |year=2010 |last1=Benko |first1=Attila |last2=Dosa |first2=Gyorgy |last3=Tuza |first3=Zsolt |isbn=978-1-4244-6437-1 }}
* {{cite book |author1=Poli, R. |author2=Langdon, W. B. |author3=McPhee, N. F. |year=2008 |title=A Field Guide to Genetic Programming |publisher=Lulu.com, freely available from the internet |url=http://cswww.essex.ac.uk/staff/rpoli/gp-field-guide/ |isbn=978-1-4092-0073-4 |access-date=2011-03-05 |archive-url=https://web.archive.org/web/20160527142933/http://cswww.essex.ac.uk/staff/rpoli/gp-field-guide/ |archive-date=2016-05-27 |url-status=dead }}{{self-published source|date=February 2020}}
* Price, K., Storn, R.M., Lampinen, J.A., (2005). [https://books.google.com/books?id=hakXI-dEhTkC&printsec=frontcover#v=onepage&q&f=false "Differential Evolution: A Practical Approach to Global Optimization"], Springer.
* [[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).
* Simon, D. (2013): [http://academic.csuohio.edu/simond/EvolutionaryOptimization Evolutionary Optimization Algorithms], Wiley.
* ''[https://books.google.com/books?id=yQVGAAAAQBAJ&printsec=frontcover#v=onepage&q&f=false Computational Intelligence: A Methodological Introduction]'' by Kruse, Borgelt, Klawonn, Moewes, Steinbrecher, Held, 2013, Springer, {{ISBN|978-1-4471-5012-1}}
* {{cite journal |last1=Rahman |first1=Rosshairy Abd. |last2=Kendall |first2=Graham |last3=Ramli |first3=Razamin |last4=Jamari |first4=Zainoddin |last5=Ku-Mahamud |first5=Ku Ruhana |title=Shrimp Feed Formulation via Evolutionary Algorithm with Power Heuristics for Handling Constraints |journal=Complexity |date=2017 |volume=2017 |pages=1–12 |doi=10.1155/2017/7053710 |doi-access=free }}
{{DEFAULTSORT:Evolutionary Algorithm}}
[[Category:Cybernetics]]
Category:Cybernetics
类别: 控制论
[[Category:Evolution]]
Category:Evolution
分类: 进化
[[Category:Evolutionary algorithms| ]]
[[Category:Optimization algorithms and methods]]
Category:Optimization algorithms and methods
类别: 优化算法和方法
<noinclude>
<small>This page was moved from [[wikipedia:en:Evolutionary algorithm]]. Its edit history can be viewed at [[进化算法/edithistory]]</small></noinclude>
[[Category:待整理页面]]
{{Artificial intelligence}}
In [[artificial intelligence]] (AI), an '''evolutionary algorithm''' ('''EA''') is a [[subset]] of [[evolutionary computation]],<ref name="EVOALG">{{cite article|last=Vikhar|first=P. A.|title=Evolutionary algorithms: A critical review and its future prospects|doi=10.1109/ICGTSPICC.2016.7955308|journal=Proceedings of the 2016 International Conference on Global Trends in Signal Processing, Information Computing and Communication (ICGTSPICC)|location= Jalgaon|year= 2016|pages=261-265|isbn=978-1-5090-0467-6}}</ref> a generic population-based [[metaheuristic]] [[optimization (mathematics)|optimization]] [[algorithm]]. An EA uses mechanisms inspired by [[biological evolution]], such as [[reproduction]], [[mutation]], [[genetic recombination|recombination]], and [[natural selection|selection]]. [[Candidate solution]]s 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.
In artificial intelligence (AI), an evolutionary algorithm (EA) is a subset of evolutionary computation, a generic population-based metaheuristic optimization algorithm. An EA uses mechanisms inspired by biological evolution, such as 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.
在人工智能(AI)中，进化算法(EA)是一种基于种群的元启发式优化算法进化计算的子集。Ea 使用生物进化启发的机制，如繁殖、变异、重组和选择。最佳化问题的候选解决方案扮演了种群中个体的角色，而适应度函数决定了解决方案的质量(参见损失函数)。在重复应用上述算子之后，种群的演化就发生了。
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.<ref name="VLSI">{{cite book|last=Cohoon|first=J|display-authors=etal|title=Evolutionary algorithms for the physical design of VLSI circuits|url= https://www.ifte.de/mitarbeiter/lienig/cohoon.pdf|journal=Advances in Evolutionary Computing: Theory and Applications|publisher= Springer, pp. 683-712, 2003|isbn=978-3-540-43330-9|date=2002-11-26}}</ref> 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{{Citation needed|date=June 2018}}; therefore, there may be no direct link between algorithm complexity and problem complexity.
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.
进化算法通常对所有类型的问题都能很好地执行近似解决方案，因为在理想情况下，它们不会对潜在的适应度场景做出任何假设。应用于生物进化建模的进化算法技术通常局限于微进化过程和基于细胞过程的规划模型的探索。在大多数实际应用中，计算复杂度是一个禁止因素。实际上，这种计算复杂性是由于适应度函数的计算。适应度逼近是克服这一困难的解决方案之一。然而，看似简单的 EA 可以解决常常是复杂的问题，因此，算法复杂度和问题复杂度之间可能没有直接的联系。
==Implementation==
Step One: Generate the initial [[population]] of [[individual]]s randomly. (First generation)
Step One: Generate the initial population of individuals randomly. (First generation)
第一步: 随机生成个体的初始种群。(第一代)
Step Two: Repeat the following regenerational steps until termination:
Step Two: Repeat the following regenerational steps until termination:
第二步: 重复以下重生步骤直到终止:
#Evaluate the [[Fitness function|fitness]] of each individual in the population (time limit, sufficient fitness achieved, etc.)
Evaluate the fitness of each individual in the population (time limit, sufficient fitness achieved, etc.)
评估群体中每个个体的适应性(时间限制，达到的足够适应性，等等)
#Select the fittest individuals for [[reproduce|reproduction]]. (Parents)
Select the fittest individuals for reproduction. (Parents)
选择最适合繁殖的个体。(家长)
# [[Breed]] new individuals through [[crossover (genetic algorithm)|crossover]] and [[mutation (genetic algorithm)|mutation]] operations to give birth to [[offspring]].
Breed new individuals through crossover and mutation operations to give birth to offspring.
通过交叉和变异操作繁殖新个体以产生后代。
# Replace the least-fit individuals of the population with new individuals.
Replace the least-fit individuals of the population with new individuals.
用新的个体取代人口中最不健康的个体。
==Types==
Similar techniques differ in [[genetic representation]] and other implementation details, and the nature of the particular applied problem.
Similar techniques differ in genetic representation and other implementation details, and the nature of the particular applied problem.
类似的技术在遗传表示和其他实现细节以及特定应用问题的性质上有所不同。
*[[Genetic algorithm]] – 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),<ref name=VLSI/> by applying operators such as recombination and mutation (sometimes one, sometimes both). This type of EA is often used in [[Optimization (mathematics)|optimization]] 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.
*[[Evolutionary programming]] – Similar to genetic programming, but the structure of the program is fixed and its numerical parameters are allowed to evolve.
*[[Gene expression programming]] – Like genetic programming, GEP also evolves computer programs but it explores a genotype-phenotype system, where computer programs of different sizes are encoded in linear chromosomes of fixed length.
*[[Evolution strategy]] – Works with vectors of real numbers as representations of solutions, and typically uses self-adaptive mutation rates.
*[[Differential evolution]] – Based on vector differences and is therefore primarily suited for [[numerical optimization]] problems.
*[[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]] or [[supervised learning]] approach.
==Comparison to biological processes==
A possible limitation{{According to whom|date=May 2013}} 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]] to become a mature [[phenotype]]. This indirect [[encoding]] 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.<ref>G.S. Hornby and J.B. Pollack. "Creating high-level components with a generative representation for body-brain evolution". ''[[Artificial Life (journal)|Artificial Life]]'', 8(3):223–246, 2002.</ref><ref>Jeff Clune, Benjamin Beckmann, Charles Ofria, and Robert Pennock. [http://www.ofria.com/pubs/2009CluneEtAl.pdf "Evolving Coordinated Quadruped Gaits with the HyperNEAT Generative Encoding"] {{Webarchive|url=https://web.archive.org/web/20160603205252/http://www.ofria.com/pubs/2009CluneEtAl.pdf |date=2016-06-03 }}. ''Proceedings of the IEEE Congress on Evolutionary Computing Special Section on Evolutionary Robotics'', 2009. Trondheim, Norway.</ref> Such indirect (a.k.a. generative or developmental) encodings also enable evolution to exploit the regularity in the environment.<ref>J. Clune, C. Ofria, and R. T. Pennock, [http://jeffclune.com/publications/Clune-HyperNEATandRegularity.pdf "How a generative encoding fares as problem-regularity decreases"], in ''PPSN'' (G. Rudolph, T. Jansen, S. M. Lucas, C. Poloni, and N. Beume, eds.), vol. 5199 of ''Lecture Notes in Computer Science'', pp. 358–367, Springer, 2008.</ref> Recent work in the field of [[artificial development|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.<ref>Ferreira, C., 2001. [http://www.gene-expression-programming.com/webpapers/GEP.pdf "Gene Expression Programming: A New Adaptive Algorithm for Solving Problems"]. ''Complex Systems'', Vol. 13, issue 2: 87–129.</ref>{{Synthesis inline|date=May 2013}}
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 to become a mature phenotype. This indirect encoding 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 (a.k.a. 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.
许多进化算法的一个可能的局限性是它们缺乏明确的基因型-表型区分。在自然界中，受精卵细胞经历一个称为胚胎发生的复杂过程，最终形成成熟的表型。这种间接编码被认为可以使遗传搜索更加健壮(即:。减少致命突变的可能性) ，也可能提高生物体的可进化性。这种间接的。生殖编码或发育编码也使进化能够利用环境中的规律性。最近在人工胚胎发生或人工发育系统领域的工作，试图解决这些问题。基因表达式编程成功地探索了一个基因型-表现型系统，其中基因型由固定长度的线性多基因染色体组成，表现型由多个表达树或不同大小和形状的计算机程序组成。
==Related techniques==
[[Swarm intelligence|Swarm algorithms]]{{clarify|reason=Why are swarm algorithms associated with evolutionary ones?|date=January 2018}} include
Swarm algorithms include
群算法包括
* [[Ant colony optimization]] – Based on the ideas of ant foraging by pheromone communication to form paths. Primarily suited for [[combinatorial optimization]] and [[graph theory|graph]] problems.
* The runner-root algorithm (RRA) is inspired by the function of runners and roots of plants in nature<ref>F. Merrikh-Bayat, "The runner-root algorithm: A metaheuristic for solving unimodal and multimodal optimization problems inspired by runners and roots of plants in nature", ''Applied Soft Computing'', Vol. 33, pp. 292–303, 2015</ref>
* [[Artificial bee colony algorithm]] – Based on the honey bee foraging behaviour. Primarily proposed for numerical optimization and extended to solve combinatorial, constrained and multi-objective optimization problems.
* [[Bees algorithm]] is based on the foraging behaviour of honey bees. It has been applied in many applications such as routing and scheduling.
* [[Cuckoo search]] is inspired by the brooding parasitism of the [[cuckoo]] species. It also uses [[Lévy flight]]s, and thus it suits for global [[optimization]] problems.
* Electimize optimization - Based on the behavior of electron flow through electric circuit branches with the least electric resistance.<ref>{{Cite journal|last=Khalafallah Ahmed|last2=Abdel-Raheem Mohamed|date=2011-05-01|title=Electimize: New Evolutionary Algorithm for Optimization with Application in Construction Engineering|journal=Journal of Computing in Civil Engineering|volume=25|issue=3|pages=192–201|doi=10.1061/(ASCE)CP.1943-5487.0000080}}</ref>
*[[Particle swarm optimization]] – Based on the ideas of animal flocking behaviour. Also primarily suited for [[numerical optimization]] problems.
==Other population-based [[metaheuristic]] methods==
*[[Hunting Search]] – A method inspired by the group hunting of some animals such as wolves that organize their position to surround the prey, each of them relative to the position of the others and especially that of their leader. It is a continuous optimization method<ref>{{cite journal |last1=Oftadeh |first1=R. |last2=Mahjoob |first2=M.J. |last3=Shariatpanahi |first3=M. |title=A novel meta-heuristic optimization algorithm inspired by group hunting of animals: Hunting search |journal=Computers & Mathematics with Applications |date=October 2010 |volume=60 |issue=7 |pages=2087–2098 |doi=10.1016/j.camwa.2010.07.049 }}</ref> adapted as a combinatorial optimization method.<ref>{{cite journal |author1=Amine Agharghor |author2=Mohammed Essaid Riffi |year=2017 |title=First Adaptation of Hunting Search Algorithm for the Quadratic Assignment Problem |journal=Europe and MENA Cooperation Advances in Information and Communication Technologies |volume=520 |pages=263–267 |doi=10.1007/978-3-319-46568-5_27 |isbn=978-3-319-46567-8|series=Advances in Intelligent Systems and Computing }}</ref>
*[[Adaptive dimensional search]] – Unlike nature-inspired metaheuristic techniques, an adaptive dimensional search algorithm does not implement any metaphor as an underlying principle. Rather it uses a simple performance-oriented method, based on the update of the search dimensionality ratio (SDR) parameter at each iteration.<ref>Hasançebi, O., Kazemzadeh Azad, S. (2015), "Adaptive Dimensional Search: A New Metaheuristic Algorithm for Discrete Truss Sizing Optimization", ''Computers and Structures'', 154, 1–16.</ref>
*[[Firefly algorithm]] is inspired by the behavior of fireflies, attracting each other by flashing light. This is especially useful for multimodal optimization.
*[[Harmony search]] – Based on the ideas of musicians' behavior in searching for better harmonies. This algorithm is suitable for combinatorial optimization as well as parameter optimization.
*[[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]].
*[[Memetic algorithm]] – A hybrid method, inspired by [[Richard Dawkins]]'s notion of a meme, it commonly takes the form of a population-based algorithm 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.
*Emperor Penguins Colony – A method inspired by the behavior of emperor penguins in their colony. The emperor penguins in the colony seek to create the appropriate heat and regulate their body temperature, and this heat is completely coordinated and controlled by the movement of the penguins.<ref>{{cite journal |last1=Harifi |first1=Sasan |last2=Khalilian |first2=Madjid |last3=Mohammadzadeh |first3=Javad |last4=Ebrahimnejad |first4=Sadoullah |title=Emperor Penguins Colony: a new metaheuristic algorithm for optimization |journal=Evolutionary Intelligence |date=25 February 2019 |volume=12 |issue=2 |pages=211–226 |doi=10.1007/s12065-019-00212-x }}</ref>
==Examples==
In 2020, [[Google]] stated their AutoML-Zero can successfully rediscover classic algorithms such as the concept of neural networks.<ref>{{cite news |last1=Gent |first1=Edd |title=Artificial intelligence is evolving all by itself |url=https://www.sciencemag.org/news/2020/04/artificial-intelligence-evolving-all-itself |accessdate=16 April 2020 |work=Science {{!}} AAAS |date=13 April 2020 |language=en |archive-url=https://web.archive.org/web/20200416222954/https://www.sciencemag.org/news/2020/04/artificial-intelligence-evolving-all-itself |archive-date=16 April 2020 |url-status=dead }}</ref>
In 2020, Google stated their AutoML-Zero can successfully rediscover classic algorithms such as the concept of neural networks.
2020年，谷歌宣布他们的 autol-zero 可以成功地重新发现经典算法，比如神经网络的概念。
The computer simulations ''[[Tierra (computer simulation)|Tierra]]'' and ''[[Avida]]'' attempt to model [[macroevolution]]ary dynamics.
The computer simulations Tierra and Avida attempt to model macroevolutionary dynamics.
Tierra 和阿维达的计算机模拟试图建立宏观进化动力学模型。
==Gallery ==
<ref>{{Cite journal |last1=Simionescu |first1=P.A. |last2=Beale |first2=D.G. |last3=Dozier |first3=G.V. |title=Constrained optimization problem solving using estimation of distribution algorithms |series=Proc. of the 2004 Congress on Evolutionary Computation - CEC2004|place=Portland, OR |pages=1647–1653 |year=2004 |doi=10.1109/CEC.2006.1688506 |url=http://faculty.tamucc.edu/psimionescu/PDFs/WCCI2004-Paper1361.pdf |access-date=7 January 2017}}</ref>
<ref>{{Cite book |last1=Simionescu |first1=P.A. |title=2006 IEEE International Conference on Evolutionary Computation |last2=Dozier |first2=G.V. |last3=Wainwright |first3=R.L. |chapter=A Two-Population Evolutionary Algorithm for Constrained Optimization Problems |series=Proc 2006 IEEE International Conference on Evolutionary Computation|place=Vancouver, Canada |pages=1647–1653 |year=2006 |doi=10.1109/CEC.2006.1688506 |chapter-url=http://faculty.tamucc.edu/psimionescu/PDFs/WCCI2006-Paper7204(1).pdf |access-date=7 January 2017|isbn=0-7803-9487-9 }}</ref>
<ref>{{cite book|last=Simionescu|first=P.A.|title=Computer Aided Graphing and Simulation Tools for AutoCAD Users|year=2014|publisher=[[CRC Press]]|location=Boca Raton, FL|isbn=978-1-4822-5290-3|edition=1st}}</ref>
<gallery>
<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 (2).gif|A two-population EA search over a constrained Rosenbrock function with bounded global optimum.
文件: 双种群 EA 搜索(2) . gif | 有界全局最优的约束 Rosenbrock函数上的双种群 EA 搜索。
File:Two-population EA search (3).gif|A two-population EA search over a constrained [[Rosenbrock function]]. Global optimum is not bounded.
File:Two-population EA search (3).gif|A two-population EA search over a constrained Rosenbrock function. Global optimum is not bounded.
文件: Two-population EA search (3) . gif | a Two-population EA search over a constrained Rosenbrock函数。全局最优不是有界的。
File:Estimation of Distribution Algorithm animation.gif|[[Estimation of distribution algorithm]] over [[Keane's function]]
File:Estimation of Distribution Algorithm animation.gif|Estimation of distribution algorithm over Keane's function
文件: 分布估计算法
File:Two population EA animation.gif|A two-population EA search of a bounded optima of [[Test_functions_for_optimization#Test_functions_for_constrained_optimization|Simionescu's function]].
File:Two population EA animation.gif|A two-population EA search of a bounded optima of Simionescu's function.
文件: Two population EA animation.gif | a Two-population EA search of a bounded optima of Simionescu’s function。
</gallery>
</gallery>
/ 画廊
== References ==
{{Reflist}}
==Bibliography==
* Ashlock, D. (2006), ''Evolutionary Computation for Modeling and Optimization'', Springer, {{ISBN|0-387-22196-4}}.
* Bäck, T. (1996), ''[https://books.google.com/books?id=htJHI1UrL7IC&printsec=frontcover#v=onepage&q&f=false Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolutionary Programming, Genetic Algorithms]'', Oxford Univ. Press.
* Bäck, T., Fogel, D., Michalewicz, Z. (1997), ''Handbook of Evolutionary Computation'', Oxford Univ. Press.
* 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.
* Holland, J. H. (1992), ''[https://books.google.com/books?id=5EgGaBkwvWcC&printsec=frontcover#v=onepage&q&f=false Adaptation in Natural and Artificial Systems]'', The University of Michigan Press, Ann Arbor
* Michalewicz Z., Fogel D.B. (2004). How To Solve It: Modern Heuristics, Springer.
* {{cite book |doi=10.1109/BICTA.2010.5645312 |chapter=Bin Packing/Covering with Delivery, solved with the evolution of algorithms |title=2010 IEEE Fifth International Conference on Bio-Inspired Computing: Theories and Applications (BIC-TA) |pages=298–302 |year=2010 |last1=Benko |first1=Attila |last2=Dosa |first2=Gyorgy |last3=Tuza |first3=Zsolt |isbn=978-1-4244-6437-1 }}
* {{cite book |author1=Poli, R. |author2=Langdon, W. B. |author3=McPhee, N. F. |year=2008 |title=A Field Guide to Genetic Programming |publisher=Lulu.com, freely available from the internet |url=http://cswww.essex.ac.uk/staff/rpoli/gp-field-guide/ |isbn=978-1-4092-0073-4 |access-date=2011-03-05 |archive-url=https://web.archive.org/web/20160527142933/http://cswww.essex.ac.uk/staff/rpoli/gp-field-guide/ |archive-date=2016-05-27 |url-status=dead }}{{self-published source|date=February 2020}}
* Price, K., Storn, R.M., Lampinen, J.A., (2005). [https://books.google.com/books?id=hakXI-dEhTkC&printsec=frontcover#v=onepage&q&f=false "Differential Evolution: A Practical Approach to Global Optimization"], Springer.
* [[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).
* Simon, D. (2013): [http://academic.csuohio.edu/simond/EvolutionaryOptimization Evolutionary Optimization Algorithms], Wiley.
* ''[https://books.google.com/books?id=yQVGAAAAQBAJ&printsec=frontcover#v=onepage&q&f=false Computational Intelligence: A Methodological Introduction]'' by Kruse, Borgelt, Klawonn, Moewes, Steinbrecher, Held, 2013, Springer, {{ISBN|978-1-4471-5012-1}}
* {{cite journal |last1=Rahman |first1=Rosshairy Abd. |last2=Kendall |first2=Graham |last3=Ramli |first3=Razamin |last4=Jamari |first4=Zainoddin |last5=Ku-Mahamud |first5=Ku Ruhana |title=Shrimp Feed Formulation via Evolutionary Algorithm with Power Heuristics for Handling Constraints |journal=Complexity |date=2017 |volume=2017 |pages=1–12 |doi=10.1155/2017/7053710 |doi-access=free }}
{{DEFAULTSORT:Evolutionary Algorithm}}
[[Category:Cybernetics]]
Category:Cybernetics
类别: 控制论
[[Category:Evolution]]
Category:Evolution
分类: 进化
[[Category:Evolutionary algorithms| ]]
[[Category:Optimization algorithms and methods]]
Category:Optimization algorithms and methods
类别: 优化算法和方法
<noinclude>
<small>This page was moved from [[wikipedia:en:Evolutionary algorithm]]. Its edit history can be viewed at [[进化算法/edithistory]]</small></noinclude>
[[Category:待整理页面]]