Algorithm 版 (精华区)

发信人: Lerry (戒网·学习), 信区: Algorithm
标  题: 遗传算法（Genetic Algorithm）
发信站: 哈工大紫丁香 (2001年11月20日20:51:02 星期二), 站内信件

遗传算法（Genetic Algorithm）
——遗传算法（Genetic Algorithm，缩写为GA）是一种有效的解决最优化问题的方法。
它最先是由John Holland于1975年提出的。从那以后，它逐渐发展成为一种通过模拟自
然进化过程解决最优化问题的计算模型。
——最优化问题通常可归结为极大化问题，利用数字公式描述就写作：
——其中f（x）为目标函数，S为可行域，它们是由工程实际问题的具体条件决定的。
——利用遗传算法解最优化问题，首先应对可行域中的点进行编码（一般采用二进制编
码），然后在可行域中随机挑选一些编码组成作为进化起点的第一代编码组，并计算每
个解的目标函数值，也就是编码的适应度。接着就像自然界中一样，利用选择机制从编
码组中随机挑选编码作为繁殖过程前的编码样本。选择机制应保证适应度较高的解能够
保留较多的样本；而适应度较低的解则保留较少的样本，甚至被淘汰。在接下去的繁殖
过程中，遗传算法提供了交叉和变异两种算子对挑选后的样本进行交换。交叉算子交换
随机挑选的两个编码的某些位，变异算子则直接对一个编码中的随机挑选的某一位进行
反转。这样通过选择和繁殖就产生了下一代编码组。重复上述选择和繁殖过程，直到结
束条件得到满足为止。进化过程最后一代中的最优解就是用遗传算法解最优化问题所得
到的最终结果。
——从以上介绍可以看出，GA算法具有下述特点：
GA是对问题参数的编码组进行进货，而不是直接对参数本身。
GA的搜索是从问题解的编码组开始搜索，而不是从单个解开始。
GA使用目标函数值（适应度）这一信息进行搜索，而不需导数等其他信息。
GA算法使用的选择、交叉、变异这三个算子都是随机操作，而不是确定规则。
——实践表明，遗传算法解最优化问题的计算效率比较高、适用范围相当广。为了解释
这一现象，Holland给出了图式定理。所谓图式，就是某些码位取相同值的编码的集合。
图式定理说明在进化过程的各代中，属于适应度高、阶数低且长度短的图式的编码数量
将随代数以指数形式增长。另外，Holland还发现遗传算法具有隐含的并行计算特性。最
近的研究则表明，上述遗传算法经适当改进后对任意优化问题以概率1收敛于全局最优解
。
——将遗传算法用于解决各种实际问题后，人们发现遣传算法也会由于各种原因过早向
目标函数的局部最优解收敛，从而很难找到全局最优解。其中有些是由于目标函数的特
性造成的，例如函数具有欺骗性，不满足构造模块假说等等；另外一些则是由于算法设
计不当。为此，不断有人对遗传算法提出各种各样的改进方案。例如：针对原先的定长
二进制编码方案；提出了动态编码、实数编码等改进方案；针对按比例的选择机制，提
出了竞争选择、按续挑选等改进方案；针对原先的一点交叉算子，提出了两点交叉、多
点交叉、均匀交叉等算子；针对原先遗传算法各控制参数在进化过程中不变的情况，提
出了退化遗传算法、自适应遗传算法等。另外，针对不同问题还出现了分布式遗传算法
、并行遗传算法等等。
——近年来，随着对于遗传算法研究的不断深入完善，有越来越多的人认识了解了遗传
算法，并把它应用到越来越广泛的领域，例如机器学习、模式识别、图像处理、神经网
络、工业优化控制和社会科学等方面。特别是在解决旅行商问题、煤气管道的最优控制
、通信网络链接长度的优化问题、铁路运输计划优化、喷气式收音机涡轮机的设计、VL
SI版面设计、键盘排列优化等问题上遗传算法都取得了很大的成功。
——目前国际国内有关GA的研究热潮方兴未艾。除从1985年起每两年举办一届GA国际会
议外，还有MIT从1993年开始出版的《Evolutionary Computatio》和《Adaptive Behav
ior》两种杂志、IEEE从今年起出版的专门关于进化计算的汇刊。另外，各种AI类的杂志
不断出版有关进化计算的专辑。其它有关GA理论和工程应用的文章也在各种不同类型杂
志上不断涌现。国内有关GA的研究也正在不断深入地展开。

--
　　不在乎天长地久，就怕你从来没有！

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 天外飞仙]