更改

:"Short, low order, and highly fit schemata are sampled, [[crossover (genetic algorithm)|recombined]] [crossed over], and resampled to form strings of potentially higher fitness. In a way, by working with these particular schemata [the building blocks], we have reduced the complexity of our problem; instead of building high-performance strings by trying every conceivable combination, we construct better and better strings from the best partial solutions of past samplings.

:"Short, low order, and highly fit schemata are sampled, [[crossover (genetic algorithm)|recombined]] [crossed over], and resampled to form strings of potentially higher fitness. In a way, by working with these particular schemata [the building blocks], we have reduced the complexity of our problem; instead of building high-performance strings by trying every conceivable combination, we construct better and better strings from the best partial solutions of past samplings.

:“对短的、d低次序的和高度适合的模式进行取样、重组(交叉) ，并重新取样以形成具有潜在更高适合度的表示串。在某种程度上，通过使用这些特定的模式[构建块] ，我们降低了问题的复杂性; 我们不是通过尝试每一种可以想象的组合来构建高性能表示串，而是从过去采样的最佳部分解决方案中构建越来越好的表示串。

:“对短的、低次序的和高度适合的模式进行取样、重组(交叉) ，并重新取样以形成具有潜在更高适合度的表示串。在某种程度上，通过使用这些特定的模式[构建块] ，我们降低了问题的复杂性; 我们不是通过尝试每一种可以想象的组合来构建高性能表示串，而是从过去采样的最佳部分解决方案中构建越来越好的表示串。

Despite the lack of consensus regarding the validity of the building-block hypothesis, it has been consistently evaluated and used as reference throughout the years. Many estimation of distribution algorithms, for example, have been proposed in an attempt to provide an environment in which the hypothesis would hold. Although good results have been reported for some classes of problems, skepticism concerning the generality and/or practicality of the building-block hypothesis as an explanation for GAs efficiency still remains. Indeed, there is a reasonable amount of work that attempts to understand its limitations from the perspective of estimation of distribution algorithms.

Despite the lack of consensus regarding the validity of the building-block hypothesis, it has been consistently evaluated and used as reference throughout the years. Many estimation of distribution algorithms, for example, have been proposed in an attempt to provide an environment in which the hypothesis would hold. Although good results have been reported for some classes of problems, skepticism concerning the generality and/or practicality of the building-block hypothesis as an explanation for GAs efficiency still remains. Indeed, there is a reasonable amount of work that attempts to understand its limitations from the perspective of estimation of distribution algorithms.

尽管对于构件假设的有效性缺乏共识，但多年来它一直在被评测，并被作为参考。例如，已经有许多'''分布估计算法 estimation of distribution algorithms'''被提出，试图提供一个使假设成立的环境<ref>{{cite book|last1=Harik|first1=Georges R.|last2=Lobo|first2=Fernando G.|last3=Sastry|first3=Kumara|title=Linkage Learning via Probabilistic Modeling in the Extended Compact Genetic Algorithm (ECGA)|journal=Scalable Optimization Via Probabilistic Modeling|volume=33|date=1 January 2006|pages=39–61|doi=10.1007/978-3-540-34954-9_3|language=en|series=Studies in Computational Intelligence|isbn=978-3-540-34953-2}}</ref><ref>{{cite book|last1=Pelikan|first1=Martin|last2=Goldberg|first2=David E.|last3=Cantú-Paz|first3=Erick|title=BOA: The Bayesian Optimization Algorithm|journal=Proceedings of the 1st Annual Conference on Genetic and Evolutionary Computation - Volume 1|date=1 January 1999|pages=525–532|url=http://dl.acm.org/citation.cfm?id=2933973|isbn=9781558606111|series=Gecco'99}}</ref>。虽然在某些类别的问题上已经有了良好的结果，但是用构件假设来解释遗传算法有效性的普遍性和/或实用性仍然存在怀疑。事实上，有相当数量的工作试图从分布估计算法的角度来理解其局限性。

尽管对于构件假设的有效性缺乏共识，但多年来它一直在被评测，并被作为参考。例如，已经有许多'''<font color="#ff8000">分布估计算法 estimation of distribution algorithms</font>'''被提出，试图提供一个使假设成立的环境<ref>{{cite book|last1=Harik|first1=Georges R.|last2=Lobo|first2=Fernando G.|last3=Sastry|first3=Kumara|title=Linkage Learning via Probabilistic Modeling in the Extended Compact Genetic Algorithm (ECGA)|journal=Scalable Optimization Via Probabilistic Modeling|volume=33|date=1 January 2006|pages=39–61|doi=10.1007/978-3-540-34954-9_3|language=en|series=Studies in Computational Intelligence|isbn=978-3-540-34953-2}}</ref><ref>{{cite book|last1=Pelikan|first1=Martin|last2=Goldberg|first2=David E.|last3=Cantú-Paz|first3=Erick|title=BOA: The Bayesian Optimization Algorithm|journal=Proceedings of the 1st Annual Conference on Genetic and Evolutionary Computation - Volume 1|date=1 January 1999|pages=525–532|url=http://dl.acm.org/citation.cfm?id=2933973|isbn=9781558606111|series=Gecco'99}}</ref>。虽然在某些类别的问题上已经有了良好的结果，但是用构件假设来解释遗传算法有效性的普遍性和/或实用性仍然存在怀疑。事实上，有相当数量的工作试图从分布估计算法的角度来理解其局限性。

<ref>{{cite book|last1=Coffin|first1=David|last2=Smith|first2=Robert E.|title=Linkage Learning in Estimation of Distribution Algorithms|journal=Linkage in Evolutionary Computation|volume=157|date=1 January 2008|pages=141–156|doi=10.1007/978-3-540-85068-7_7|language=en|series=Studies in Computational Intelligence|isbn=978-3-540-85067-0}}</ref><ref>{{cite journal|last1=Echegoyen|first1=Carlos|last2=Mendiburu|first2=Alexander|last3=Santana|first3=Roberto|last4=Lozano|first4=Jose A.|title=On the Taxonomy of Optimization Problems Under Estimation of Distribution Algorithms|journal=Evolutionary Computation|date=8 November 2012|volume=21|issue=3|pages=471–495|doi=10.1162/EVCO_a_00095|pmid=23136917|s2cid=26585053|issn=1063-6560}}</ref><ref>{{cite book|last1=Sadowski|first1=Krzysztof L.|last2=Bosman|first2=Peter A.N.|last3=Thierens|first3=Dirk|title=On the Usefulness of Linkage Processing for Solving MAX-SAT|journal=Proceedings of the 15th Annual Conference on Genetic and Evolutionary Computation|date=1 January 2013|pages=853–860|doi=10.1145/2463372.2463474|isbn=9781450319638|series=Gecco '13|hdl=1874/290291|s2cid=9986768}}</ref>

<ref>{{cite book|last1=Coffin|first1=David|last2=Smith|first2=Robert E.|title=Linkage Learning in Estimation of Distribution Algorithms|journal=Linkage in Evolutionary Computation|volume=157|date=1 January 2008|pages=141–156|doi=10.1007/978-3-540-85068-7_7|language=en|series=Studies in Computational Intelligence|isbn=978-3-540-85067-0}}</ref><ref>{{cite journal|last1=Echegoyen|first1=Carlos|last2=Mendiburu|first2=Alexander|last3=Santana|first3=Roberto|last4=Lozano|first4=Jose A.|title=On the Taxonomy of Optimization Problems Under Estimation of Distribution Algorithms|journal=Evolutionary Computation|date=8 November 2012|volume=21|issue=3|pages=471–495|doi=10.1162/EVCO_a_00095|pmid=23136917|s2cid=26585053|issn=1063-6560}}</ref><ref>{{cite book|last1=Sadowski|first1=Krzysztof L.|last2=Bosman|first2=Peter A.N.|last3=Thierens|first3=Dirk|title=On the Usefulness of Linkage Processing for Solving MAX-SAT|journal=Proceedings of the 15th Annual Conference on Genetic and Evolutionary Computation|date=1 January 2013|pages=853–860|doi=10.1145/2463372.2463474|isbn=9781450319638|series=Gecco '13|hdl=1874/290291|s2cid=9986768}}</ref>

== Limitations ==

== 局限 ==

There are limitations of the use of a genetic algorithm compared to alternative optimization algorithms:

There are limitations of the use of a genetic algorithm compared to alternative optimization algorithms:

== Variants ==

== 变体 ==

=== Chromosome representation ===

=== 染色体表示 ===

{{main | genetic representation }}

{{main | genetic representation }}

The simplest algorithm represents each chromosome as a bit string. Typically, numeric parameters can be represented by integers, though it is possible to use floating point representations. The floating point representation is natural to evolution strategies and evolutionary programming. The notion of real-valued genetic algorithms has been offered but is really a misnomer because it does not really represent the building block theory that was proposed by John Henry Holland in the 1970s. This theory is not without support though, based on theoretical and experimental results (see below). The basic algorithm performs crossover and mutation at the bit level. Other variants treat the chromosome as a list of numbers which are indexes into an instruction table, nodes in a linked list, hashes, objects, or any other imaginable data structure. Crossover and mutation are performed so as to respect data element boundaries. For most data types, specific variation operators can be designed. Different chromosomal data types seem to work better or worse for different specific problem domains.

The simplest algorithm represents each chromosome as a bit string. Typically, numeric parameters can be represented by integers, though it is possible to use floating point representations. The floating point representation is natural to evolution strategies and evolutionary programming. The notion of real-valued genetic algorithms has been offered but is really a misnomer because it does not really represent the building block theory that was proposed by John Henry Holland in the 1970s. This theory is not without support though, based on theoretical and experimental results (see below). The basic algorithm performs crossover and mutation at the bit level. Other variants treat the chromosome as a list of numbers which are indexes into an instruction table, nodes in a linked list, hashes, objects, or any other imaginable data structure. Crossover and mutation are performed so as to respect data element boundaries. For most data types, specific variation operators can be designed. Different chromosomal data types seem to work better or worse for different specific problem domains.

最简单的算法将每个染色体表示为一个位串。通常，数值参数可以由整数表示，但也可以使用浮点表示。浮点表示是进化策略和进化规划的自然结果。实值遗传算法的概念已经提出，但实际上用词不当，因为它并不真正代表约翰 · 亨利 · 霍兰德在上世纪70年代提出的构件理论。这个理论不是没有支持，但是，基于理论和实验结果(见下文)。基本算法在比特级进行交叉和变异操作。其他变体将染色体视为指令表、链表中的节点、散列、对象或任何其他可以想象的数据结构的索引的数列。交叉和变异的执行是为了尊重数据元素的边界。对于大多数数据类型，可以设计特定的变化操作符。不同的染色体数据类型似乎对不同的特定问题域有更好或更坏的作用。

最简单的表示算法是将每个染色体表示为一个位串。通常，数值参数可以由整数表示，但也可以使用浮点表示。使用浮点数表示在进化策略和进化编程中更加自然。实值的遗传算法的概念已经提出，但实际上这个名词并不准确，因为它并不真正代表[[约翰·霍兰德_John_H_Holland|约翰·霍兰德]]在上世纪70年代提出的构件理论。不过这个理论并不是没有基于理论和实验结果(见下文)的证据支持。基本算法在二进制位（即'0101'）层面进行交叉和变异操作。其他变体将染色体视为指令表、链表中的节点、散列、对象或任何其他可以想象的数据结构的索引的数列。交叉和变异的执行是为了尊重数据元素的边界。对于大多数数据类型，可以设计特定的操作。不同的染色体数据类型似乎对不同的特定问题域有或更好或更坏的作用。

When bit-string representations of integers are used, Gray coding is often employed. In this way, small changes in the integer can be readily affected through mutations or crossovers. This has been found to help prevent premature convergence at so-called Hamming walls, in which too many simultaneous mutations (or crossover events) must occur in order to change the chromosome to a better solution.

When bit-string representations of integers are used, Gray coding is often employed. In this way, small changes in the integer can be readily affected through mutations or crossovers. This has been found to help prevent premature convergence at so-called Hamming walls, in which too many simultaneous mutations (or crossover events) must occur in order to change the chromosome to a better solution.

当使用整数的位串表示时，通常采用格雷编码。通过这种方式，整数中的微小变化很容易通过突变或交叉而受到影响。已经发现，这有助于防止所谓的汉明壁上的过早收敛，在汉明壁上必须发生太多的同时突变(或交叉事件) ，以便将染色体改变成一个更好的解决方案。

当使用位串表示整数时，通常会用道'''<font color="#ff8000">格雷编码 Gray coding</font>'''。通过这种方式，整数中的微小变化很容易通过突变或交叉而受到影响。已经发现，这有助于防止所谓的'''<font color="#ff8000">汉明壁 Hamming walls</font>'''上的过早收敛，使得不需要发生太多的同时突变(或交叉事件) ，即可令染色体变成一个更好的解。

Other approaches involve using arrays of real-valued numbers instead of bit strings to represent chromosomes. Results from the theory of schemata suggest that in general the smaller the alphabet, the better the performance, but it was initially surprising to researchers that good results were obtained from using real-valued chromosomes. This was explained as the set of real values in a finite population of chromosomes as forming a virtual alphabet (when selection and recombination are dominant) with a much lower cardinality than would be expected from a floating point representation.

Other approaches involve using arrays of real-valued numbers instead of bit strings to represent chromosomes. Results from the theory of schemata suggest that in general the smaller the alphabet, the better the performance, but it was initially surprising to researchers that good results were obtained from using real-valued chromosomes. This was explained as the set of real values in a finite population of chromosomes as forming a virtual alphabet (when selection and recombination are dominant) with a much lower cardinality than would be expected from a floating point representation.

其他方法包括使用实数数组代替位字符串来表示染色体。图式理论的结果表明，一般来说，字母表越小，表现越好，但最初令研究人员感到惊讶的是，使用实值染色体取得了良好的结果。这被解释为在有限的染色体群中形成一个虚拟字母表(当选择和重组占主导地位时)的一组真实值，其基数比浮点表示法预期的低得多。

其他方法包括使用实数数组代替位字符串来表示染色体。模式理论的结果表明，一般来说，可用字符集合越小，算法表现越好。但在起初研究人员感到惊讶，因为使用实值染色体也取得了良好的结果。这被解释为在有限的染色体群中形成一个虚拟可用字符集合(当选择和重组占主导地位时)的一组真实值，其基数比浮点表示法预期的低得多。<ref name=Goldberg1991>{{cite book|last=Goldberg|first=David E.|title=Parallel Problem Solving from Nature|chapter=The theory of virtual alphabets|journal=Parallel Problem Solving from Nature, Lecture Notes in Computer Science|year=1991|volume=496|pages=13–22|doi=10.1007/BFb0029726|series=Lecture Notes in Computer Science|isbn=978-3-540-54148-6}}</ref><ref name=Janikow1991>{{cite journal|last1=Janikow|first1=C. Z.|first2=Z. |last2=Michalewicz |title=An Experimental Comparison of Binary and Floating Point Representations in Genetic Algorithms|journal=Proceedings of the Fourth International Conference on Genetic Algorithms|year=1991|pages=31–36|url=http://www.cs.umsl.edu/~janikow/publications/1991/GAbin/text.pdf|accessdate=2 July 2013}}</ref>

====Other metaheuristic methods====

====其他元启发式方法====

====Other stochastic optimisation methods====

====其他复杂的最优化算法====

 

 

 

* The [[Cross-entropy method|cross-entropy (CE) method]] generates candidate solutions via a parameterized probability distribution. The parameters are updated via cross-entropy minimization, so as to generate better samples in the next iteration.

* The [[Cross-entropy method|cross-entropy (CE) method]] generates candidate solutions via a parameterized probability distribution. The parameters are updated via cross-entropy minimization, so as to generate better samples in the next iteration.

* Reactive search optimization (RSO) advocates the integration of sub-symbolic machine learning techniques into search heuristics for solving complex optimization problems. The word reactive hints at a ready response to events during the search through an internal online feedback loop for the self-tuning of critical parameters. Methodologies of interest for Reactive Search include machine learning and statistics, in particular [[reinforcement learning]], [[Active learning (machine learning)|active or query learning]], [[neural networks]], and [[metaheuristics]].

* Reactive search optimization (RSO) advocates the integration of sub-symbolic machine learning techniques into search heuristics for solving complex optimization problems. The word reactive hints at a ready response to events during the search through an internal online feedback loop for the self-tuning of critical parameters. Methodologies of interest for Reactive Search include machine learning and statistics, in particular [[reinforcement learning]], [[Active learning (machine learning)|active or query learning]], [[neural networks]], and [[metaheuristics]].

* [[Genetic programming]] 遗传编程

 

* [[Genetic programming]]

* [[List of genetic algorithm applications]]

* [[List of genetic algorithm applications]] 遗传算法应用

* [[particle filter|Genetic algorithms in signal processing (a.k.a. particle filters)]]

* [[particle filter|Genetic algorithms in signal processing (a.k.a. particle filters)]] 遗传算法在信号处理的引用（粒子过滤器）

* [[Propagation of schema]]

* [[Propagation of schema]]模式的传播

* [[Universal Darwinism]]

* [[Universal Darwinism]]泛达尔文主义

* [[Metaheuristics]]

* [[Metaheuristics]]元启发式

* [[Learning classifier system]]

* [[Learning classifier system]]学习分类器系统

* [[Rule-based machine learning]]

* [[Rule-based machine learning]]基于规则的机器学习

== References ==

== 引用 ==

{{Reflist|30em}}

{{Reflist|30em}}

== Bibliography ==

== 参考资料 ==

{{Refbegin}}

{{Refbegin}}

== External links ==

== 外部链接 ==

=== Resources ===

=== 资源 ===

* [https://web.archive.org/web/20160303215222/http://www.geneticprogramming.com/ga/index.htm] Provides a list of resources in the genetic algorithms field

* [https://web.archive.org/web/20160303215222/http://www.geneticprogramming.com/ga/index.htm] 遗传算法资源列表

* [https://www.staracle.com/general/evolutionaryAlgorithms.php An Overview of the History and Flavors of Evolutionary Algorithms]

* [https://www.staracle.com/general/evolutionaryAlgorithms.php 演化算法发展史概述]

=== Tutorials ===

=== 教程 ===

* [https://www2.econ.iastate.edu/tesfatsi/holland.gaintro.htm Genetic Algorithms - Computer programs that "evolve" in ways that resemble natural selection can solve complex problems even their creators do not fully understand] An excellent introduction to GA by John Holland and with an application to the Prisoner's Dilemma

* [https://www2.econ.iastate.edu/tesfatsi/holland.gaintro.htm Genetic Algorithms - Computer programs that "evolve" in ways that resemble natural selection can solve complex problems even their creators do not fully understand] An excellent introduction to GA by John Holland and with an application to the Prisoner's Dilemma

* [http://www.i4ai.org/EA-demo/ An online interactive Genetic Algorithm tutorial for a reader to practise or learn how a GA works]: Learn step by step or watch global convergence in batch, change the population size, crossover rates/bounds, mutation rates/bounds and selection mechanisms, and add constraints.

* [http://www.i4ai.org/EA-demo/ An online interactive Genetic Algorithm tutorial for a reader to practise or learn how a GA works]: Learn step by step or watch global convergence in batch, change the population size, crossover rates/bounds, mutation rates/bounds and selection mechanisms, and add constraints.

* [https://web.archive.org/web/20130615042000/http://samizdat.mines.edu/ga_tutorial/ga_tutorial.ps A Genetic Algorithm Tutorial by Darrell Whitley Computer Science Department Colorado State University] An excellent tutorial with much theory

* [https://web.archive.org/web/20130615042000/http://samizdat.mines.edu/ga_tutorial/ga_tutorial.ps A Genetic Algorithm Tutorial by Darrell Whitley Computer Science Department Colorado State University] An excellent tutorial with much theory

* [http://www.it-weise.de/projects/book.pdf Global Optimization Algorithms &ndash; Theory and Application]

* [http://www.it-weise.de/projects/book.pdf Global Optimization Algorithms &ndash; Theory and Application]

{{Authority control}}

{{Authority control}}

{{DEFAULTSORT:Genetic Algorithm}}

{{DEFAULTSORT:Genetic Algorithm}}