Difference between revisions 32757262 and 32820376 on zhwiki

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

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

(contracted; show full):模式的阶数和定义距描述了模式的基本性质。
* [[模式定理]] 在遗传算子选择、交叉和变异的作用下，具有阶数低、长度短、平均适应度高于群体平均适应度得模式在子代中将以指数级增长。
===积木块假设===
* 阶数低、长度短和适应度高的模式称为[[积木块]]。
:[[积木块假设]]：阶数低、长度短、适应度高的模式（积木块）在遗传算子作用下，相互结合，能生成阶数高，长度长、适应度高的模式，可最终生成全局最优解。
:与积木块一样，一些好的模式在遗传算法操作下相互拼搭、结合，产生适应度更高的串，从而找到更优的可行解，这正是积木块假设所揭示的内容。


===在线交互式演示与学习===
英国[[格拉斯哥大学]]在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/ 欧洲软计算中心网站]。⏎
⏎
=== 特点 ===
遗传算法在解决优化问题过程中有如下特点：

* 遗传算法在适应度函数选择不当的情况下有可能收敛于局部最优，而不能达到全局最优。
* 初始种群的数量很重要，如果初始种群数量过多，算法会占用大量系统资源；如果初始种群数量过少，算法很可能忽略掉最优解。
* 对于每个解，一般根据实际情况进行编码，这样有利于编写变异函数和适应度函数(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/ 欧洲软计算中心网站]。⏎
⏎
== 适用的问题 ==

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

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

== 遗传算法的不足之处 ==
遗传算法作为一种优化方法，它存在自身的局限性:
(contracted; show full)* [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:人工智能应用]]