更改

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]],<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.

在[[人工智能]]领域，演化算法是演化计算的子集<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> ，是一种基于群体的元启发式最优化算法。演化算法使用到了各种模拟[[生物演化]]机制的操作，比如繁衍、变异、重组、选择等。在群体中每一个个体都是问题的备选解，而适应度函数用于计算出每一个解的质量（亦即个体对于环境的适应度）。演化就是在不断在群体中进行繁衍、变异、重组、选择这些操作进而找出最优解的过程。

 

 

 

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 [[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.

演化算法通常会对各种优化问题得出很好的近似解，因为演化算法不会做出任何假设，对每一个问题都一视同仁。演化算法通常应用于求解最优化问题，在生物建模方面一般来说只会用在研究微观演化过程以及基于细胞过程的规划模型。在大多数演化算法的应用中，计算复杂度都是最大的障碍<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>。事实上，这种计算复杂度来源于[[适应度函数]]。简化适应度函数、计算近似的适应度，是克服这一障碍的方法之一。由于简单的演化算法也往往可以解决复杂的优化问题，因此，算法的复杂度应该与问题的复杂度没有直接关系。

 

 

 

Step One: Generate the initial [[population]] of [[individual]]s randomly. (First generation)

Step One: Generate the initial [[population]] of [[individual]]s 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 function|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 [[reproduce|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 (genetic algorithm)|crossover]] and [[mutation (genetic algorithm)|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 programming）：这种技术用于生成一段计算机程序，其适应度是这些计算机程序解决某计算问题的能力。

* 演化规划（Evolutionary programming）：与遗传规划类似，但其求解的计算机程序的结构是固定的，可以演化的是一些数值参数。

 

* 基因表达规划（Gene expression programming）：类似于遗传编程，基因表达规划同样以计算机程序群体来进行演化计算，但这种计算机程序虽然大小不同，却都编码在相同固定的线性染色体中。

*[[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.

* 演化策略（Evolution strategy）：这种技术以实数向量作为个体，而且使用了自适应的变异率。

 

* 差分演化（Differential evolution）：这种算法以向量的差为基础，因此特别适合数值最优化问题。

*[[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.

* 神经演化：类似于遗传规划，但是基因组表示的是人工神经网络的结构和连接权重，这种基因组编码可以是直接编码也可以是间接编码。

 

* 学习分类器系统（Learning classifier system）：这种技术的解是一组分类器（一组规则画着条件）。密歇根-学习分类器系统在个体层面进行演化而匹兹堡-学习分类器系统使用分类器集合群体来演化。最开始的时候这些分类器都是0-1编码的，如今包含实数、神经网络、或者S-expression。其适应度一般是分类器系统应用于强化学习或有监督学习时的准确率。

*[[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.

 

 

 

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{{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.

对于演化算法来说，一个可能的局限可能是缺少对基因型和表现型的明确区分。在大自然中，一个受精卵会历经一个成为胚胎发育的过程，然后成为一个成熟的表现型。自然选择以表现型而非基因型为选择标准。这种间接编码被认为可以使得演化过程更健壮（降低致命突变的概率），并提高器官的进化能力<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> 。这种间接编码还使得演化能够充分利用环境的规律<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>。最近有关人工胚胎学（artificial embryogeny）和人工发展系统（artificial developmental system）的工作也在寻求解决这一局限的方法。基因表达规划这一技术在基因型-表现型系统的探索中取得成功，其中基因型包括固定长度地线性多基因染色体，而表现型则包括了规模可变的多重表达式树或者计算机程序<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>。

==Related techniques==

==相关技术==

[[Swarm intelligence|Swarm algorithms]]{{clarify|reason=Why are swarm algorithms associated with evolutionary ones?|date=January 2018}} include

[[Swarm intelligence|Swarm algorithms]]{{clarify|reason=Why are swarm algorithms associated with evolutionary ones?|date=January 2018}} include

*[[Particle swarm optimization]] – Based on the ideas of animal flocking behaviour. Also primarily suited for [[numerical optimization]] problems.

*[[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>

*[[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>

*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>

*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==