4
#4楼 得分：0回复于：2003-04-16 11:12:10
starfish 版竹的遗风：
发信人: starfish (金盆洗手，退隐江湖), 信区: Algorithm
标 题: 遗传算法
发信站: 南京大学小百合站 (Wed Apr 2 13:57:13 2003)
遗传算法（Genetic Algorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传
机制）演化而来的随机化搜索方法。它是由美国的J.Holland教授1975年首先提出，其主要
特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和
更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应
地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优
化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键
技术之一。
1.遗传算法与自然选择
达尔文的自然选择学说是一种被人们广泛接受的生物进化学说。这种学说认为，生物要生存
下去，就必须进行生存斗争。生存斗争包括种内斗争、种间斗争以及生物跟无机环境之间的
斗争三个方面。在生存斗争中，具有有利变异的个体容易存活下来，并且有更多的机会将有
利变异传给后代；具有不利变异的个体就容易被淘汰，产生后代的机会也少的多。因此，凡
是在生存斗争中获胜的个体都是对环境适应性比较强的。达尔文把这种在生存斗争中适者生
存，不适者淘汰的过程叫做自然选择。它表明，遗传和变异是决定生物进化的内在因素。自
然界中的多种生物之所以能够适应环境而得以生存进化，是和遗传和变异生命现象分不开的
。正是生物的这种遗传特性，使生物界的物种能够保持相对的稳定；而生物的变异特性，使
生物个体产生新的性状，以致于形成新的物种，推动了生物的进化和发展。
遗传算法是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。它的思想源于生
物遗传学和适者生存的自然规律，是具有“生存＋检测”的迭代过程的搜索算法。遗传算法
以一种群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空间进行高效
搜索。其中，选择、交叉和变异构成了遗传算法的遗传操作；参数编码、初始群体的设定、
适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内容。
作为一种新的全局优化搜索算法，遗传算法以其简单通用、鲁棒性强、适于并行处理以及高
效、实用等显著特点，在各个领域得到了广泛应用，取得了良好效果，并逐渐成为重要的智
能算法之一。
2.遗传算法的基本步骤
我们习惯上把Holland1975年提出的GA称为传统的GA。它的主要步骤如下：
编码：GA在进行搜索之前先将解空间的解数据表示成遗传空间的基因型串结构数据，这些串
结构数据的不同组合便构成了不同的点。
初始群体的生成：随机产生N个初始串结构数据，每个串结构数据称为一个个体， N个个体
构成了一个群体。GA以这N个串结构数据作为初始点开始迭代。
适应性值评估检测：适应性函数表明个体或解的优劣性。不同的问题，适应性函数的定义方
式也不同。
选择：选择的目的是为了从当前群体中选出优良的个体，使它们有机会作为父代为下一代繁
殖子孙。遗传算法通过选择过程体现这一思想，进行选择的原则是适应性强的个体为下一代
贡献一个或多个后代的概率大。选择实现了达尔文的适者生存原则。
交换：交换操作是遗传算法中最主要的遗传操作。通过交换操作可以得到新一代个体，新个
体组合了其父辈个体的特性。交换体现了信息交换的思想。
变异：变异首先在群体中随机选择一个个体，对于选中的个体以一定的概率随机地改变串结
构数据中某个串的值。同生物界一样，GA中变异发生的概率很低，通常取值在0.001~0.01之
间。变异为新个体的产生提供了机会。
GA的计算过程为：
选择编码方式
产生初始群体
计算初始群体的适应性值
如果不满足条件 {
选择
交换
变异
计算新一代群体的适应性值
}
3.遗传算法的特点
遗传算法作为一种快捷、简便、容错性强的算法，在各类结构对象的优化过程中显示
出明显的优势。与传统的搜索方法相比，遗传算法具有如下特点：
搜索过程不直接作用在变量上，而是在参数集进行了编码的个体。此编码操作，
使得遗传算法可直接对结构对象（集合、序列、矩阵、树、图、链和表）进行操作。
搜索过程是从一组解迭代到另一组解，采用同时处理群体中多个个体的方法，降
低了陷入局部最优解的可能性，并易于并行化。
采用概率的变迁规则来指导搜索方向，而不采用确定性搜索规则。
对搜索空间没有任何特殊要求（如连通性、凸性等），只利用适应性信息，不需要
导数等其它辅助信息，适应范围更广。
4.遗传算法的研究历史与现状
遗传算法研究的兴起是在80年代末和90年代初期，但它的历史起源可追溯至60年代
初期。早期的研究大多以对自然系统的计算机模拟为主。如Fraser的模拟研究，他提出了和
现在的遗传算法十分相似的概念和思想。Holland和DeJong的创造性研究成果改变了早期遗
传算法研究的无目标性和理论指导的缺乏。其中，Holland于1975年出版的著名著作 < <自然
系统和人工系统的适配> > 系统地阐述了遗传算法的基本理论和方法，并提出了对遗传算法的
理论研究和发展极为重要的模式理论。这一理论首次确认了结构重组遗传操作对于获得隐并
行性的重要性。
同年，DeJong的重要论文 < <遗传自适应系统到的行为分析> > 将Holland的模式理论与他的计
算实验结合起来，并提出了诸如代沟等新的遗传操作技术。可以认为，DeJong所作的研究工
作是遗传算法发展过程中的一个里程碑。
进入80年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门
的课题。尤其是遗传算法的应用领域也不断扩大。目前遗传算法所涉及的主要领域有自动控
制、规划设计、组合优化、图象处理、信号处理、人工生命等。可见，遗传算法的应用研究
已从初期的组合优化求解拓展到了许多更新。更工程化的应用方面。
--
凤凰台上凤凰游，凤去台空江自流。
吴宫花草埋幽径，晋代衣冠成古丘。
三山伴落青天外，二水中分白鹭洲。
总谓浮云能蔽日，长安不见使人愁。
