遗传算法理论及技术研究综述

1、遗传算法理论及技术研究综述周听凌兴宏（1.哈尔滨理工大学计算机科学与技术学院，黑龙江哈尔滨150080；2. 苏州大学计算机科学与技术学院，江苏苏州215006）摘要本文首先阐述了遗传算法的主要特点和基本原理，随后对遗传算法的理论与技术研究的主体, 即编码机制、适应度评价以及选择、交叉、变异等遗传算子进行了探讨；比较分析了各种遗传操作方法的 优缺点和适用场合；对遗传算法的理论和技术做了初步研究综述。关键词 遗传算法；编码机制；遗传算子；适应度评价1引言遗传算法是模拟遗传选择和口然淘汰的生物进化过程的计算模型，由美国michigan大学的holland教 授于1969年提出，后经dejong.

2、goldberg等人归纳总结，形成一种新的全局优化搜索算法。所谓遗传算法來源于达尔文的进化论、魏茨曼的物种选择学说和孟徳尔的群体遗传学说。遗传算法足 模拟自然界生物进化过程与机制求解极值问题的一类自组织、自适应人工解能技术2，, 基木思想是模拟 h然界遗传机制和生物进化论，引用了随机统计理论而形成的。在求解过程中，遗传算法从一个初始变量 群体开始，一代一代地寻找问题的绘优解，直至满足收敛判据或预先设定的迭代次数为止。它是一种迭代 式算法,是一种过程搜索最优解的算法,具有坚实的生物学基础。遗传算法广泛应用于自动控制、计算科学、模式识别、工程设计、智能故障诊断、管理科学和社会科 学等领域，适用于解

3、决复杂的非线性和多维空间寻优问题。2遗传算法的基本原理及特点2.1遗传算法的基本原理遗传算法是一种基于口然选择和群体遗传机理的搜索算法，它模拟了自然选择和口然遗传过程中发生 的繁殖、杂交和突变现象。在利用遗传算法求解问题时，问题的毎个町能的解都被编码成一个“染色体”， 即个体，若干个个体构成了群体（所冇可能解），通过适应度函数给每个个体一个数值评价，淘汰低适应 度的个体，选择高适应度的个体参加遗传操作，这些个体经过交叉和变异算子进行再组合生成下-代新的 种群。这一群新个体由于继承了上一代的一些优良性状，因而在性能上要优于上一代，这样逐步朝着更优 解的方向进化。因此，遗传算法可以看作是一个由可行

4、解组成的群体逐代进化的过程。遗传算法的基本流程描述如图1所示。初始化群体“图1遗传算法基本流程2.2遗传算法的特点遗传算法利用了生物进化和遗传的思想，不同于枚举法、启发式算法、搜索算法等传统的优化方法， 具有如下特点：（1）自组织、自适应和智能性。遗传算法消除了算法设计中最大的障碍，即需要事先描述问题的全 部特点，并说明针对问题的不同特点，算法应采取的措施。直接处理的对象是参数编码集，而不是问题参 数本身。它可用来解决复杂的非结构化问题，具有很強的鲁棒性。（2）搜索过程中使川的是基于目标函数值的评价信息，搜索过程既不受优化函数连续性的约束,也 没有优化函数必须可导的要求。（3）易于并行化，可降

5、低由于使用超强计算机硕件所带來的昂贵费用。（4）算法基本思想简单，运行方式和实现步骤规范,便于具体使用。3遗传算法的理论与技术研究遗传算法的研究主要包括三个领域® :遗传算法的理论与技术；用遗传算法进行优化；用遗传算法进 行分类系统的机器学习。其中，遗传算法的理论与技术研究主要包括编码、交叉运算、变界运算、选择运 算以及适应度评价等问题。本文限于篇幅，仅就遗传算法的理论与技术研究进行探讨。3. 1编码机制在许多问题求解屮，编码是遗传算法中首要解决的问题，对算法的性能冇很重要的影响。常见的编码 方法冇如下儿种：1）二进制编码由holland®初提岀，遗传算法中最常川的一种编码

6、方法。它采用最小字符编码原则，特点是编/解码 操作简单易行，利于交叉、变异操作的实现，也可以采用模式定理对算法进行理论分析。但二进制编码用 于多维、高椿度数值问题优化时，不能很好地克服连续两数离散化时的映射谋差；不能直接反映问题的固 冇结构，精度不高，个体长度人、占用内存多。2) 格宙码编码为了克服二进制编码在连续函数离散化时存在的不足，人们捉出了用格雷码进行编码的方法，它是二进 制编码的变形。假设冇一个二进制编码为，其对应的格雷码为，则i=m-l, m-2, , 2, 1格雷码不仅具有二进制编码的一些优点，而且能够提高遗传算法的局部搜索能力。3) 编码该方法适介于遗传算法中表示范围较大的数，

7、使遗传算法更接近问题空间，避免了编码和解码的过程。 它便于较人空间的遗传搜索，提高了遗传算法的精度要求；便于设计专门问题的遗传算子；便于算法与经 典优化方法的混合作用，改善了遗传算法的计算复杂性，提高了运算效率。4) 十进制编码该方法利用十进制编码控制参数，缓解了 “组合爆炸”和遗传算法的早熟收敛问题。5) 符号编码染色休编码串中的基因值取一个仅冇代码含义而无数值含义的符号集，这些符号可以是数字也可以是字 符。非数值编码的优点是在遗传算法中可以利用所求问题的专门知识及相关算法。对于非数值编码，问题 的解和染色体的编码耍注憑染色体的可行性、染色体的合法性和映射的惟一性。符号编码的主耍优点是便 于

8、在遗传算法中利用所求问题的专门知识及相关算法。3.2适应度函数遗传算法在进化搜索中基本上不利川外部信息，仅以适应函数为依据，利川群体中每个个体的适应度值 來进行搜索。因此适应函数的选取至关重要，直接影响遗传算法的收敛速度以及能否找到故优解。在遗传算法中，适应度是描述个体性能的主要指标，根据适应度的大小对个体进行优胜劣汰。对于求解 有约束的优化问题时，一般采用罚函数方法将目标函数利约束条件建立成一个无约束的优化日标函数，然 后再将目标函数作适当处理，建立适合遗传算法的适应度函数。将h标函数转换成适应度函数一般应遵循两个原则：(1) 适应度必须非负。(2) 优化过程中h标函数的变化方向应与群体进化

9、过程中适应度函数变化方向一致。在使用遗传算法求解具体问题时，适应度函数的选择对算法的收敛性以及收敛速度的影响较大，针对不 同的问题需根据经验或算法來确定和应的参数。3.3遗传操作遗传操作的任务是根据个体的适应度对其施加一定的操作，从而实现优胜劣汰的进化过程。从优化搜索 的角度而言，遗传操作可使问题的解逐代地优化，逼近最优解。遗传操作包括以下选择、交义和变异三个基本遗传算子。选择和交义基本上完成了遗传算法的大部分搜 索功能，变开增加了遗传算法找到接近最优解的能力。3. 3. 1选择选择是在适应度评估的基础上，从群体中选择优良的个体,并淘汰劣质个体的操作。适应度越大的个体, 被选择的可能性就越大。

10、常用的选择方法冇：1) 轮盘赌选择法乂称为适应度比例法，是目前遗传算法中最基本也是最常川的选择方法。个体的适应度值越大，它被选 中的概率就越高，体现了 “适者生存”这一自然选择原理。被选中的个体被放入配对库中，随机地进行配 对，以进行下而的交叉操作。2) 局部选择法在局部选择法中，毎个个体处于一个约束环境中，称为局部邻集（而其它选择方法中视整个种群为个体 z邻集），个体仅与其临近个体产生交叉，该邻集的定义由种群的分布结构给出，邻集可被当作潜在的交 配伙伴。3）最佳个体保存法把祥体中适应度最高的个体不进行配对交义而直接复制到下一代。这样做的好处是保证了进化过程中某 一代的最优解不被交义和变异操作

11、所破坏。但会使局部最优的遗传基因急速增加，而使进化停滞于局部最 优解，即这种方法彩响了遗传算法的全局搜索能力。因此，最佳个体保存法通常不单独使用。4）竞争法个体的选择公式为f m = maxf i, f j,即随机地选取两个个体，对其适应值进行比较，大的被选 中，小的被自然淘汰；如果两个个体的适应值相同，则任懣选取其中的-个。被选中的个体放入配对库中。 垂复此过程，直至配对席屮包含n个个体为止。这种方法既保证了配对库中的个体在解空间中有较好的分 散性，同时又保证了加入配对库中的个体具冇较大的适应值。5）排序选择法首先根据各个体的适应度人小进行排序，然后基于所排序号进行选择。3. 3.2交义/基

12、因重组交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。交义的目的是为了能够在下 一代产生新的个体，就象人类社会的婚姻过程。通过交叉操作，遗传算法的搜索能力得以飞跃性的捉高。 交叉是遗传算法获取新优良个体的最重要手段。交叉操作是按照一定的交叉概率（也称交叉率）在配对库中随机地选取两个个体进行的。交叉的位置 也是随机确定的。交叉算子分为以下儿种：1）单点交叉又简称为简单交叉，即在个体串中随机地选定一个交叉点，两个个体在该点前或后进行部分互换，以 产生新的个体。2）多点交叉多个个体无重复随机地选择，在交义点之间的变量间续地相互交换，产生两个新的后代。3）均匀交叉是通过设置屏蔽字來决定

13、新个体的基因如何继承父代个体中相应的基因。根据研究对彖不同，还冇多种可选择的交叉方法，如顺序交叉、循环交叉、洗牌交叉、缩小代理交叉 等。3.3.3变异变异就是以很小的变异概率pm随机地改变郡体中个体的某些基因的值。变异操作的基木过程是：对于 交叉操作中产生的后代个体的每一基因值,产生一个0,1 之间的伪随机数rand,如果rand < pm,就进行变异操作。变异本身是一种局部随机搜索，与选择、交叉算子结合在一起，就能避免由于选择和交叉算子而引起 的某些信息的永久性丢失，保证了遗传算法的有效性，使遗传算法具有局部的随机搜索能力；同时使得遗 传算法保持群体的多样性，以阴止出现未成熟收敛。因此

14、，变异操作是一种防止算法早熟的措施。儿种常用的变异操作如下：1）基本位变界对个体编码串以变异概率pm随机指定某一位或某儿位基因进行变异操作。2）均匀变界也叫一致变异，分别川符合某一范围内均匀分布的随机数，以某一较小的概率来替换个体编码串中原 冇基因值。均匀变异操作特别适合应用于遗传算法的初期运行阶段，它使得搜索点可以在整个搜索空间内 自由地移动，从而可以増加群体的多样性，使算法能够处理更多的模式。3）二元变异需要两条染色体参与，通过二元变异操作后生成两条新个体中的各个基因分别取原染色体对应基因值 的同或/界或。它改变了传统的变界方式，有效地克服了早熟收敛，提高了遗传算法的优化速度。4) 高斯变

15、异在进行变界时用一个均值为u、方差为。2的正态分布的一个随机数來替换原有基因值。其操作过程 与均匀变异类似。4结束语遗传算法的理论与技术研究主耍包括编码、交叉运算、变界运算、选择运算等遗传操作以及适应度评 价等问题。本文就遗传算法的理论与技术研究的诸方面进行了探讨。遗传算法是一个十分活跃的研究领域，遗传算法的研究正在从理论的深度、技术的多样化以及应用的 广度不断地探索，朝着计算机拥有甚至超过人类卿能的方向努力。参考文献张文修，梁怡.遗传算法的数学基础m .西安：西安交通人学出版社，2000段玉储，贺家李.遗传算法及其改进j .电力系统及其h动化学报，1998, 10 (1) 葛继科，邱玉辉.遗传算法研究综述j .计算机应用研究，2008, 25 (10)日玄光男，程润传.遗传算法与工程设计m .北京：科学出版社，2000王小平，邢文训，王洪燕，1 holland j h. adap tation in natural