Revision 33227829 of "遗传算法" on zhwiki

生物的进化（Evolution）过程主要是通过染色体之间的交叉和变异来完成的。基于对自然界中生物遗传与进化机理的模仿，针对不同的问题，很多学者设计了许多不同的编码方法来表示问题的可行解，开发出了许多种不同的遗传算子来模仿不同环境下的生物遗传特性。这样，由不同的编码（Coding）方法和不同的遗传算子就构成了各种不同的遗传算法。

遗传算法是模仿自然界生物进化机制发展起来的随机全局搜索和优化方法，它借鉴了达尔文的进化论和孟德尔的遗传学说。其本质是一种高效、并行、全局搜索的方法，它能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应的控制搜索过程以求得最优解。遗传算法操作使用适者生存的原则，在潜在的解决方案种群中逐次产生一个近似最优解的方案，在遗传算法的每一代中，根据个体在问题域中的适应度值和从自然遗传学中借鉴来的再造方法进行个体选择，产生一个新的近似解。这个过程导致种群中个体的进化，得到的新个体比原来个体更能适应环境，就像自然界中的改造一样。

'''遗传算法'''是[[计算机科学]]人工智能领域中用于解决[[最优化]]的一种搜索启发式[[算法]]，是[[进化算法]]的一种。这种启发式通常用来生成有用的解决方案来优化和搜索问题。进化算法最初是借鉴了[[进化生物学]]中的一些现象而发展起来的，这些现象包括[[遗传]]、[[突变]]、[[自然选择]]以及[[杂交]]等。

遗传算法广泛应用在生物信息学、系统发生学、计算科学、工程学、经济学、化学、制造、数学、物理、药物测量学和其他领域之中。

遗传算法通常实现方式为一种[[计算机模拟]]。对于一个最优化问题，一定数量的[[候选解]]（称为个体）的抽象表示（称为[[染色体 (遺傳演算法)|染色體]]）的[[种群]]向更好的解进化。传统上，解用[[二进制]]表示（即0和1的串），但也可以用其他表示方法。进化从完全[[随机]]个体的种群开始，之后一代一代发生。在每一代中，整个种群的[[适应度]]被评价，从当前种群中随机地选择多个个体（基于它们的适应度），通过自然选择产生新的生命种群，该种群在算法的下一次迭代中成为当前种群。

== 遗传算法的机理 ==

在遗传算法裡，优化问题的解被称为个体，它表示为一个变量序列，叫做[[染色體 (遺傳演算法)|染色体]]或者[[基因]][[字符串|串]]。染色体一般被表达为简单的字符串或数字串，不过也有其他的依赖于特殊问题的表示方法适用，这一过程称为编码。首先，算法[[随机函数|随机]]生成一定数量的个体，有时候操作者也可以对这个随机产生过程进行干预，以提高初始种群的质量。在每一代中，每一个个体都被评价，并通过计算[[适应度函数]]得到一个[[适应度]]数值。种群中的个体被按照适应度[[排序]]，适应度高的在前面。这里的“高”是相对于初始的种群的低适应度来说的。

下一步是产生下一代个体并组成种群。这个过程是通过选择和[[繁殖]]完成的，其中繁殖包括交配（crossover，在算法研究领域中我们称之为交叉操作）和突变（mutation）。选择则是根据新个体的适应度进行的，但同时并不意味着完全的以适应度高低作为导向，因为单纯选择适应度高的个体将可能导致算法快速收敛到局部最优解而非全局最优解，我们称之为早熟。作为折中，遗传算法依据原则：适应度越高，被选择的机会越高，而适应度低的，被选择的机会就低。初始的数据可以通过这样的选择过程组成一个相对优化的群体。之后，被选择的个体进入交配过程。一般的遗传算法都有一个交配概率（又称为交叉概率），范围一般是0.6~1，这个交配概率反映两个被选中的个体进行交配的[[概率]]。例如，交配概率为0.8，则80%的“夫妻”会生育后代。每两个个体通过交配产生两个新个体，代替原来的“老”个体，而不交配的个体则保持不变。交配父母的染色体相互交換，从而产生两个新的染色体，第一个个体前半段是父亲的染色体，后半段是母亲的，第二个个体则正好相反。不过这里的半段並不是真正的一半，这个位置叫做交配点，也是随机产生的，可以是染色体的任意位置。再下一步是[[突變]]，通过突變产生新的“子”个体。一般遗传算法都有一个固定的[[突变常数]]（又称为变异概率），通常是0.1或者更小，这代表变异发生的概率。根据这个概率，新个体的染色体随机的突變，通常就是改变染色体的一个字节（0变到1，或者1变到0）。

经过这一系列的过程（选择、交配和突变），产生的新一代个体不同于初始的一代，并一代一代向增加整体适应度的方向发展，因为最好的个体总是更多的被选择去产生下一代，而适应度低的个体逐渐被淘汰掉。这样的过程不断的重复：每个个体被评价，计算出适应度，两个个体交配，然后突變，产生第三代。周而复始，直到终止条件满足为止。一般终止条件有以下几种：
* 进化次数限制；
* 计算耗费的资源限制（例如计算时间、计算占用的内存等）；
* 一个个体已经满足最优值的条件，即最优值已经找到；
* 适应度已经达到饱和，继续进化不会產生适应度更好的个体；
* 人为干预；
* 两种或更多种的组合。

一个典型的遗传算法要求：
一个基因表示的求解域,
一个适应度函数来评价解决方案。

=== 算法 ===

:选择初始生命种群
:循环
::评价种群中的个体适应度
::以比例原則（分數高的挑中機率也較高）选择产生下一个种群（輪盤法[[:en:roulette wheel selection]]、競爭法[[:en:tournament selection]]及等級輪盤法Rank Based Wheel Selection）。不僅僅挑分數最高的的原因是這麼做可能收斂到局部的最佳點，而非整體的。
::改变该种群（交叉和变异）
:直到停止循环的条件满足

=== GA参数 ===
* 种群规模（P,population size）：即种群中染色体个体的数目。
* 字串长度（l, string length）
* 交叉概率（pc, probability of performing crossover）：控制着交叉算子的使用频率。交叉操作可以加快收敛，使解达到最有希望的最优解区域，因此一般取较大的交叉概率，但交叉概率太高也可能导致过早收敛。
* 变异概率（pm, probability of mutation）：控制着变异算子的使用频率，决定了遗传算法的局部搜索能力。
* 中止条件（termination criteria）

===模式定理===
* 定义1基于三值字符集(0,1,*}所产生的能描述具有某些结构相似性的0、1字符串集的字符串称作模式。
:引入模式后，我们可以看到一个串实际上隐含着多个模式，一个模式可以隐含在多个串中，不同的串之间通过模式而相互联系。遗传算法中串的运算实质上是模式的运算。因此，通过分析模式在遗传操作下的变化，就可以了解什么性质被延续，什么性质被丢弃，从而把握遗传算法的实质，这正是模式定理所揭示的内容。
* 定义2模式H中确定位置的个数称为该模式的阶数，记作o(H)。
:显然，一个模式的阶数越高，其样本数就越少，因而确定性越高。
* 定义3模式H中第一个确定位置和最后一个确定位置之间的距离称作该模式的定义距，记作б(H)。
:模式的阶数和定义距描述了模式的基本性质。
* [[模式定理]]在遗传算子选择、交叉和变异的作用下，具有阶数低、长度短、平均适应度高于群体平均适应度得模式在子代中将以指数级增长。
===积木块假设===
* 阶数低、长度短和适应度高的模式称为[[积木块]]。
:[[积木块假设]]：阶数低、长度短、适应度高的模式（积木块）在遗传算子作用下，相互结合，能生成阶数高，长度长、适应度高的模式，可最终生成全局最优解。
:与积木块一样，一些好的模式在遗传算法操作下相互拼搭、结合，产生适应度更高的串，从而找到更优的可行解，这正是积木块假设所揭示的内容。

=== 特点 ===
遗传算法在解决优化问题过程中有如下特点：

* 遗传算法在适应度函数选择不当的情况下有可能收敛于局部最优，而不能达到全局最优。
* 初始种群的数量很重要，如果初始种群数量过多，算法会占用大量系统资源；如果初始种群数量过少，算法很可能忽略掉最优解。
* 对于每个解，一般根据实际情况进行编码，这样有利于编写变异函数和适应度函数（Fitness Function）。
* 在编码过的遗传算法中，每次变异的编码长度也影响到遗传算法的效率。如果变异代码长度过长，变异的多样性会受到限制；如果变异代码过短，变异的效率会非常低下，选择适当的变异长度是提高效率的关键。
* 变异率也是一个重要的参数。
* 对于动态数据，用遗传算法求最优解比较困难，因为染色体种群很可能过早地收敛，而对以后变化了的数据不再产生变化。对于这个问题，研究者提出了一些方法增加基因的多样性，从而防止过早的收敛。其中一种是所谓''触發式超级变异''，就是当染色体群体的质量下降（彼此的区别减少）时增加变异概率；另一种叫''随机外来染色体''，是偶尔加入一些全新的随机生成的染色体个体，从而增加染色体多样性。
* 选择过程很重要，但交叉和变异的重要性存在争议。一种观点认为交叉比变异更重要，因为变异仅仅是保证不丢失某些可能的解；而另一种观点则认为交叉过程的作用只不过是在种群中推广变异过程所造成的更新，对于初期的种群来说，交叉几乎等效于一个非常大的变异率，而这么大的变异很可能影响进化过程。
* 遗传算法很快就能找到''良好''的解，即使是在很复杂的解空间中。
* 遗传算法并不一定总是最好的优化策略，优化问题要具体情况具体分析。所以在使用遗传算法的同时，也可以尝试其他算法，互相补充，甚至根本不用遗传算法。
* 遗传算法不能解决那些“大海捞针”的问题，所谓“大海捞针”问题就是没有一个确切的适应度函数表征个体好坏的问题，使得算法的进化失去导向。
* 对于任何一个具体的优化问题，调节遗传算法的参数可能会有利于更好的更快的收敛，这些参数包括个体数目、交叉率和变异率。例如太大的变异率会导致丢失最优解，而过小的变异率会导致算法过早的收敛于局部最优点。对于这些参数的选择，现在还没有实用的上下限。
* 适应度函数对于算法的速度和效果也很重要。

== 变量 ==

最简单的遗传算法将染色体表示为一个[[位|数位]]串，数值变量也可以表示成[[整数]]，或者[[实数]]（[[浮点数]]）。算法中的杂交和突变都是在字节串上进行的，所以所谓的整数或者实数表示也一定要转化为数位形式。例如一个变量的形式是实数，其范围是0～1，而要求的精度是0.001，那么可以用10个数位表示：0000000000表示0，1111111111表示1。那么0110001110就代表0.398。

在遗传算法里，[[精英选择]]是一种非常成功的产生新个体的策略，它是把最好的若干个个体作为[[精英政治|精英]]直接带入下一代个体中，而不经过任何改变。

通过[[并行计算]]实现遗传算法一般有两种，一种是所谓粗糙并行遗传算法，即一个计算单元包含一个种群；而另一种是所谓精细并行遗传算法，每一个计算单元处理一个染色体个体。

遗传算法有时候还引入其他变量，例如在实时优化问题中，可以在适应度函数中引入时间相关性和干扰。

== 在线交互式演示与学习课件 ==
英国[[格拉斯哥大学]]在1997年出版了一个遗传/进化算法的网上在线交互式演示Java小程序：the [http://userweb.eng.gla.ac.uk/yun.li/ga_demo/index.html '''EA_demo''']，以帮助进化计算的新手了解遗传算法的编码和工作原理，至今仍广泛使用，采用大学包括英国利物浦（Liverpool）大学、苏塞克斯（Sussex）大学、北安普顿（Northampton）大学，德国乌尔姆（Ulm）大学，瑞士日内瓦（Geneva）大学，西班牙格林纳达（Granada）大学，葡萄牙新里斯本（Nova de Lisboa）大学，美国加州大学戴维斯分校（UC Davies），加拿大卡尔加里（Calgary）大学，澳大利亚墨尔本皇家理工大学（RMIT），新加坡国立大学，台湾国立清华大学，上海交通大学，巴西PUCRS大学等。 

EA_demo允许用户直接在网页上一代一代地手动运行，以看遗传/进化算法是怎样一步一步操作的，亦可在背景中批次运行，以观察算法的收敛和染色体是否跳出局部最优。用户可以改变终止代数，群体规模，交配率，变异率和选择机制。也有其它自学课件收录于[http://geneticalgorithms.ai-depot.com/Applications.html AI中心网站]和[http://teaching.softcomputing.es/ 欧洲软计算中心网站]。

== 适用的问题 ==

遗传算法擅长解决的问题是[[组合最优化|全局最优化问题]]，例如，解决[[时间表安排]]问题就是它的一个特长，很多安排时间表的软件都使用遗传算法，遗传算法还经常被用于解决实际[[工程问题]]。

跟传统的[[爬山算法]]相比，遗传算法能够跳出局部最优而找到全局最优点。而且遗传算法允许使用非常复杂的适应度函数（或者叫做[[目标函数]]），并对变量的变化范围可以加以限制。而如果是传统的爬山算法，对变量范围进行限制意味着复杂的多的解决过程，这方面的介绍可以参看[[受限优化问题]]和[[非受限优化问题]]。

== 遗传算法的不足之处 ==
遗传算法作为一种优化方法，它存在自身的局限性：

（1）编码不规范及编码存在表示的不准确性。

（2）单一的遗传算法编码不能全面地将优化问题的约束表示出来。考虑约束的一个方法就是对不可行解采用阈值，这样，计算的时间必然增加。

（3）遗传算法通常的效率比其他传统的优化方法低。

（4）遗传算法容易出现过早收敛。

（5）遗传算法对算法的精度、可行度、计算复杂性等方面，还没有有效的定量分析方法。

== 改进的遗传算法 ==
尽管遗传算法有许多优点，也有许多专家学者对遗传算法进行不断研究，但目前存在的问题依然很多，如：

（1）适应度值标定方式多种多样，没有一个简洁、通用的方法，不利于对遗传算法的使用。

（2）遗传算法的早熟现象（即很快收敛到局部最优解而不是全局最优解）是迄今为止最难处理的关键问题，但可考虑自适应跟踪成熟度<ref name=APSO/>。

（3）快要接近最优解时在最优解附近左右摆动，收敛较慢。

遗传算法通常需要解决一下问题，如确定编码方案，适应度函数标定，选择遗传操作方式及相关控制参数，停止准则确定等。相应地，为改进简单遗传算法的实际计算性能，很多学者的改进工作也是分别从参数编码、初始群体设定、适应度函数标定、遗传操作算子、控制参数的选择以及遗传算法的结构等方面提出的。其基本途径概括起来主要有下面几个方面：

（1）改进遗传算法的组成成分或使用技术，如选用优化控制参数、适合问题特性的编码技术等。

（2）采用混合遗传算法（Hybrid Genetic Alogrithm），比如混用简单明了的粒子群算法<ref name=OLPSO/>。

（3）采用动态自适应技术，在进化过程中调整算法控制参数和编码精度，比如使用模糊自适应法<ref name=APSO/>。

（4）采用非标准的遗传操作算子。

（5）采用并行算法。

几种常见的改进遗传算法：

（1）分层遗传算法（Hierachic Genetic Alogrithm）;

（2）CHC算法;

（3）Messy遗传算法;

（4）自适应遗传算法（Adaptive Genetic Alogrithm）;

（5）基于小生境技术的遗传算法（Niched Genetic Alorithm）;

（6）并行遗传算法（Parallel Genetic Algorithm）;

（7）混合遗传算法：

①遗传算法与最速下降法相结合的混合遗传算法；

②遗传算法与模拟退火法相结合的混合遗传算法。

== 发展历史 ==

遗传算法由[[密歇根大学]]的[[约翰·霍兰德]]和他的同事于二十世纪六十年代在对[[细胞自动机]]（英文：cellular automata）进行研究时率先提出。在二十世纪八十年代中期之前，对于遗传算法的研究还仅仅限于理论方面，直到在[[匹兹堡]]召开了第一届[[世界遗传算法大会]]。随着计算机计算能力的发展和实际应用需求的增多，遗传算法逐渐进入实际应用阶段。1989年，[[纽约时报]]作者[[约翰·马科夫]]写了一篇文章描述第一个商业用途的遗传算法--[[进化者]]（英文：Evolver）。之后，越来越多种类的遗传算法出现并被用于许多领域中，[[财富杂志]]500强企业中大多数都用它进行时间表安排、数据分析、未来趋势预测、预算、以及解决很多其他组合优化问题。

== 应用领域 ==
[[File:JRCentralSeriesN700Nose.JPG|250px|thumb|[[N700]]列車“气动双翼”的獨特空氣動力造型車鼻；是遗传算法運算結果]]
* [[计算机自动設計]]（[[:en:Computer-automated_design|Computer-Automated Design]]）<ref name=CAutoD04/> <ref name=GA_SMC96/>
* [[工业工程]]与运作管理
* [http://eprints.gla.ac.uk/3817/1/IEEE3.pdf 无需调试的即插即用比例-积分-微分控制器]（[[PID控制器]]）
* [[物流]]系统设计
* 生产调度
* 制造系统控制
* 系统优化设计
* [[汽车设计]]，包括材料选择、多目标汽车组件设计、减轻重量等。
* [[机电一体化|机电系统]]设计。
* 分布计算机网络的[[拓扑结构]]。
* [[电路]]设计，此类用途的遗传算法叫做[[进化电路]]<ref name=GA_circuits01/>。
* [[电子游戏]]设计，例如计算平衡解决方案。
* [[人工智能|机器智能]]设计和[[机器人]]学习。
* [[模糊控制]]系统的训练<ref name=GA_fuzzy94/>。
* 移动通讯优化结构。
* 时间表安排，例如为一个大学安排不冲突的课程时间表。
* [[旅行推销员问题]]。
* [[神经网络]]的训练，也叫做神经进化。

== 相关技术 ==

[[遗传程序]]是[[约翰Koza]]与遗传算法相关的一个技术，在遗传程序中，并不是参数优化，而是计算机程序优化。遗传程序一般采用[[树 (图论)|树型结构]]表示计算机程序用于进化，而不是遗传算法中的列表或者数组。一般来说，遗传程序比遗传算法慢，但同时也可以解决一些遗传算法解决不了的问题。

[[交互式遗传算法]]是利用人工评价进行操作的遗传算法，一般用于适应度函数无法得到的情况，例如，对于图像、音乐、艺术的设计和“优化”，或者对运动员的训练等。

[[模拟退火]]是解决全局优化问题的另一个可能选择。它是通过一个解在搜索空间的随机变动寻找最优点的方法：如果某一阶段的随机变动增加适应度，则总是被接受，而降低适应度的随机变动根据一定的概率被有选择的接受。这个概率由当时的[[退火温度]]和适应度恶化的程度决定，而退火温度按一定速度降低。从模拟退火算法看，最优化问题的解是通过寻找最小能量点找到的，而不是寻找最佳适应点找到的。模拟退火也可以用于标准遗传算法里，只要把突变率随时间逐渐降低就可以了。

== 参见 ==
* [[演化策略]]
* [[遗传编程]]
* [[演化规划]]
* [[模拟退火]]
* [[禁忌搜索]]
* [[旅行推销员问题]]
* [[最优化]]
* [[交叉 (遗传算法)]]

== 参考文献 ==

{{Reflist|refs=

<ref name=APSO>
{{cite journal
|last1=Zhan
|first1=Zhi-Hui, et al
|title=Adaptive Particle Swarm Optimization
|journal=IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics
|year=2009
|volume=39
|issue=6
|pages=1362–1381
|doi=10.1109/TSMCB.2009.2015956
|url=http://eprints.gla.ac.uk/7645/1/7645.pdf
}}
</ref>

<ref name=OLPSO>
{{cite journal
|last1=Zhan
|first1=Zhi-Hui, et al
|title=Orthogonal learning particle swarm optimization
|journal=IEEE Transactions on Evolutionary Computation
|year=2009
|volume=15
|issue=6
|pages=832–847
|doi=10.1109/TEVC.2010.2052054
|url=http://eprints.gla.ac.uk/44801/1/44801.pdf
}}
</ref>

<ref name=CAutoD04>
{{cite journal
|last1=Li
|first1=Yun, et al
|title=CAutoCSD-evolutionary search and optimisation enabled computer automated control system design
|journal=International Journal of Automation and Computing
|year=2004
|volume=1
|issue=1
|pages=76–88
|doi=10.1007/s11633-004-0076-8
|url=http://eprints.gla.ac.uk/3818/1/IJAC_04_CAutoCSD.pdf
}}
</ref>

<ref name=GA_SMC96>
{{cite journal
|last1=Li
|first1=Yun, et al
|title=Genetic algorithm automated approach to the design of sliding mode control systems
|journal=International Journal of Control
|year=1996
|volume=64
|issue=3
|pages=721–739
|doi=10.1080/00207179608921865
|url=http://userweb.eng.gla.ac.uk/yun.li/ga_demo/
}}
</ref>

<ref name=GA_circuits01>
{{cite conference
|last1=Goh
|first1=Cindy
|last2=Li
|first2=Yun
|title=GA automated design and synthesis of analog circuits with practical constraints
|booktitle=Proceedings of the IEEE Congress on Evolutionary Computation 2001
|year=2001
|volume=1
|pages=170–177
|doi=10.1109/CEC.2001.934386
|url=http://userweb.eng.gla.ac.uk/yun.li/ga_demo/
}}
</ref>

<ref name=GA_fuzzy94>
{{cite conference
|last1=Ng
|first1=Kim Chwee
|last2=Li
|first2=Yun
|title=Design of sophisticated fuzzy logic controllers using genetic algorithms
|booktitle=Proceedings of the Fourth Congress on Evolutionary Computation (CEC)
|year=1994
|volume=3
|pages=1708–1712
|doi=10.1109/FUZZY.1994.343598
|url=http://userweb.eng.gla.ac.uk/yun.li/ga_demo/
}}
</ref>

}}

* Goldberg, David E (1989), ''遗传算法：搜索、优化和机器学习''，Kluwer Academic Publishers, Boston, MA.
* Goldberg, David E (2002), ''创新的设计：竞争遗传算法课程''，Addison-Wesley, Reading, MA.
* Harvey, Inman (1992), ''物种适应和遗传算法持续进行的基础''in 'Toward a Practice of Autonomous Systems: Proceedings of the First European Conference on Artificial Life', F.J. Varela and P. Bourgine（eds.）, MIT Press/Bradford Books, Cambridge, MA, pp. 346-354.
* Koza, John (1992), ''遗传算法：通过自然选择编写计算机程序''
* Michalewicz, Zbigniew (1999), ''遗传算法+数据结构=进化程序''，Springer-Verlag.
* Mitchell, Melanie,（1996），''遗传算法概论''，MIT Press, Cambridge, MA. 
* {{cite book | author=Poli, R., Langdon, W. B., McPhee, N. F. |year=2008 |title=A Field Guide to Genetic Programming | publisher=Lulu.com, freely available from the internet | isbn = 978-1-4092-0073-4}}
* Schmitt, Lothar M (2001), ''遗传算法理论''，Theoretical Computer Science (259), pp. 1-61
* Schmitt, Lothar M (2004), ''遗传算法理论（二）''，Theoretical Computer Science (310), pp. 181-231
* Vose, Michael D (1999), ''简单遗传算法：基础和理论''，MIT Press, Cambridge, MA.

== 外部链接 ==
* http://userweb.eng.gla.ac.uk/yun.li/ga_demo/ - 格拉斯哥大学的在线交互式演示与学习GA_demo
* http://cs.felk.cvut.cz/~xobitko/ga/ - 用Java语言编写的遗传算法在线介绍程序。
* [http://www-illigal.ge.uiuc.edu/IlliGAL 伊利诺斯遗传算法实验室] - 可以下载技术报告和程序源代码。
* [http://www.it-weise.de/projects/book.pdf Global Optimization Algorithms - Theory and Application]

[[Category:算法]]
[[Category:遗传算法]]
[[Category:最优化算法]]
[[Category:人工智能]]
[[Category:人工智能应用]]