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

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

2、 Michigan 大学的 Holland 教授于 1969年提 出,后经 DeJong、Goldberg 等人归纳总结,形成一种新的全 局优化搜索算法 1。所谓遗传算法来源于达尔文的进化论、魏茨曼的物种选 择学说和孟德尔的群体遗传学说。遗传算法是模拟自然界生 物进化过程与机制求解极值问题的一类自组织、自适应人工 智能技术 2 ,其基本思想是模拟自然界遗传机制和生物进化 论,引用了随机统计理论而形成的。在求解过程中,遗传算 法从一个初始变量群体开始, 一代一代地寻找问题的最优解, 直至满足收敛判据或预先设定的迭代次数为止。它是一种迭 代式算法,是一种过程搜索最优解的算法,具有坚实的生物 学基础

3、。遗传算法广泛应用于自动控制、计算科学、模式识别、 工程设计、智能故障诊断、管理科学和社会科学等领域,适 用于解决复杂的非线性和多维空间寻优问题。2 遗传算法的基本原理及特点2.1 遗传算法的基本原理遗传算法是一种基于自然选择和群体遗传机理的搜索算 法,它模拟了自然选择和自然遗传过程中发生的繁殖、杂交 和突变现象。在利用遗传算法求解问题时,问题的每个可能 的解都被编码成一个“染色体”,即个体,若干个个体构成 了群体(所有可能解,通过适应度函数给每个个体一个数 值评价,淘汰低适应度的个体,选择高适应度的个体参加遗 传操作,这些个体经过交叉和变异算子进行再组合生成下一 代新的种群。这一群新个体由于

4、继承了上一代的一些优良性 状,因而在性能上要优于上一代,这样逐步朝着更优解的方 向进化。因此,遗传算法可以看作是一个由可行解组成的群 体逐代进化的过程。 3遗传算法的基本流程描述如图1所示。 图 1 遗传算法基本流程2.2 遗传算法的特点遗传算法利用了生物进化和遗传的思想, 不同于枚举法、 启发式算法、搜索算法等传统的优化方法,具有如下特点 4: (1自组织、自适应和智能性。遗传算法消除了算法设 计中最大的障碍,即需要事先描述问题的全部特点,并说明 针对问题的不同特点,算法应采取的措施。直接处理的对象 是参数编码集,而不是问题参数本身。它可用来解决复杂的 非结构化问题,具有很强的鲁棒性。(2搜

5、索过程中使用的是基于目标函数值的评价信息, 搜索过程既不受优化函数连续性的约束,也没有优化函数必 须可导的要求。·38· 计算机与信息技术 软件纵横(3 易于并行化, 可降低由于使用超强计算机硬件所带 来的昂贵费用。(4 算法基本思想简单,运行方式和实现步骤规范, 便于具体使用。3 遗传算法的理论与技术研究遗传算法的研究主要包括三个领域 5 :遗传算法的理论 与技术;用遗传算法进行优化;用遗传算法进行分类系统的 机器学习。 其中, 遗传算法的理论与技术研究主要包括编码、 交叉运算、变异运算、选择运算以及适应度评价等问题。本 文限于篇幅,仅就遗传算法的理论与技术研究进行探讨。

6、 3.1 编码机制在许多问题求解中,编码是遗传算法中首要解决的问题, 对算法的性能有很重要的影响。 常见的编码方法有如下几种 6:1 二进制编码由Holland最初提出,遗传算法中最常用的一种编码方 法。 它采用最小字符编码原则, 特点是编/解码操作简单易行, 利于交叉、变异操作的实现,也可以采用模式定理对算法进 行理论分析。但二进制编码用于多维、高精度数值问题优化 时,不能很好地克服连续函数离散化时的映射误差;不能直 接反映问题的固有结构,精度不高,个体长度大、占用内存 多。2 格雷码编码为了克服二进制编码在连续函数离散化时存在的不足, 人们提出了用格雷码进行编码的方法,它是二进制编码的变

7、形。 假设有一个二进制编码为 121-m m x x x x X =, 其对应的 格雷码为 121-m m y y y y Y =,则=+i 1i i mm x x y x y i=m-1,m-2,2,1格雷码不仅具有二进制编码的一些优点,而且能够提高 遗传算法的局部搜索能力。3 编码该方法适合于遗传算法中表示范围较大的数,使遗传算 法更接近问题空间,避免了编码和解码的过程。它便于较大 空间的遗传搜索,提高了遗传算法的精度要求;便于设计专 门问题的遗传算子;便于算法与经典优化方法的混合作用, 改善了遗传算法的计算复杂性,提高了运算效率。4 十进制编码该方法利用十进制编码控制参数,缓解了“组合爆

8、炸” 和遗传算法的早熟收敛问题。5 符号编码染色体编码串中的基因值取一个仅有代码含义而无数值含义的符号集,这些符号可以是数字也可以是字符。非数值 编码的优点是在遗传算法中可以利用所求问题的专门知识及 相关算法。对于非数值编码,问题的解和染色体的编码要注 意染色体的可行性、染色体的合法性和映射的惟一性。符号 编码的主要优点是便于在遗传算法中利用所求问题的专门知 识及相关算法。 3.2 适应度函数遗传算法在进化搜索中基本上不利用外部信息,仅以适 应函数为依据, 利用群体中每个个体的适应度值来进行搜索。 因此适应函数的选取至关重要,直接影响遗传算法的收敛速 度以及能否找到最优解。 7在遗传算法中,适

9、应度是描述个体性能的主要指标,根 据适应度的大小对个体进行优胜劣汰。对于求解有约束的优 化问题时,一般采用罚函数方法将目标函数和约束条件建立 成一个无约束的优化目标函数,然后再将目标函数作适当处 理,建立适合遗传算法的适应度函数。将目标函数转换成适应度函数一般应遵循两个原则: (1 适应度必须非负。(2 优化过程中目标函数的变化方向应与群体进化过 程中适应度函数变化方向一致。在使用遗传算法求解具体问题时,适应度函数的选择对 算法的收敛性以及收敛速度的影响较大,针对不同的问题需 根据经验或算法来确定相应的参数。 3.3 遗传操作遗传操作的任务是根据个体的适应度对其施加一定的操 作, 从而实现优胜

10、劣汰的进化过程。 从优化搜索的角度而言, 遗传操作可使问题的解逐代地优化,逼近最优解。选择是在适应度评估的基础上,从群体中选择优良的个 体,并淘汰劣质个体的操作。适应度越大的个体,被选择的 可能性就越大。常用的选择方法有: 1 轮盘赌选择法又称为适应度比例法,是目前遗传算法中最基本也是最 常用的选择方法。个体的适应度值越大,它被选中的概率就 越高,体现了“适者生存”这一自然选择原理。被选中的个 体被放入配对库中,随机地进行配对,以进行下面的交叉操 作。2局部选择法在局部选择法中,每个个体处于一个约束环境中,称为 局部邻集(而其它选择方法中视整个种群为个体之邻集, 个体仅与其临近个体产生交叉,该

11、邻集的定义由种群的分布 结构给出,邻集可被当作潜在的交配伙伴。3 最佳个体保存法把群体中适应度最高的个体不进行配对交叉而直接复制 到下一代。这样做的好处是保证了进化过程中某一代的最优 解不被交叉和变异操作所破坏。但会使局部最优的遗传基因 急速增加,而使进化停滞于局部最优解,即这种方法影响了 遗传算法的全局搜索能力。因此,最佳个体保存法通常不单 独使用。4 竞争法个体的选择公式为f m = maxf i, f j,即随机地选取两 个个体,对其适应值进行比较,大的被选中,小的被自然淘 汰;如果两个个体的适应值相同,则任意选取其中的一个。 被选中的个体放入配对库中。重复此过程,直至配对库中包 含N

12、个个体为止。这种方法既保证了配对库中的个体在解空 间中有较好的分散性,同时又保证了加入配对库中的个体具 有较大的适应值。5 排序选择法首先根据各个体的适应度大小进行排序,然后基于所排 序号进行选择。交叉是指把两个父代个体的部分结构加以替换重组而生 成新个体的操作。交叉的目的是为了能够在下一代产生新的 个体,就象人类社会的婚姻过程。通过交叉操作,遗传算法 的搜索能力得以飞跃性的提高。交叉是遗传算法获取新优良 个体的最重要手段。交叉操作是按照一定的交叉概率(也称交叉率在配对 库中随机地选取两个个体进行的。交叉的位置也是随机确定 的。交叉算子分为以下几种:1 单点交叉又简称为简单交叉,即在个体串中随

13、机地选定一个交叉 点, 两个个体在该点前或后进行部分互换, 以产生新的个体。 2 多点交叉多个个体无重复随机地选择,在交叉点之间的变量间续 地相互交换,产生两个新的后代。3 均匀交叉是通过设置屏蔽字来决定新个体的基因如何继承父代个 体中相应的基因。变异就是以很小的变异概率Pm随机地改变群体中个体 的某些基因的值。变异操作的基本过程是:对于交叉操作中 产生的后代个体的每一基因值, 产生一个 0, 1 之间的伪随 机数rand,如果rand < Pm,就进行变异操作。变异本身是一种局部随机搜索,与选择、交叉算子结合 在一起,就能避免由于选择和交叉算子而引起的某些信息的 永久性丢失,保证了遗传

14、算法的有效性,使遗传算法具有局 部的随机搜索能力;同时使得遗传算法保持群体的多样性, 以防止出现未成熟收敛。因此,变异操作是一种防止算法早 熟的措施。几种常用的变异操作如下:1基本位变异对个体编码串以变异概率Pm随机指定某一位或某几位 基因进行变异操作。2均匀变异也叫一致变异,分别用符合某一范围内均匀分布的随机 数,以某一较小的概率来替换个体编码串中原有基因值。均 匀变异操作特别适合应用于遗传算法的初期运行阶段,它使 得搜索点可以在整个搜索空间内自由地移动,从而可以增加 群体的多样性,使算法能够处理更多的模式。3二元变异需要两条染色体参与,通过二元变异操作后生成两条新 个体中的各个基因分别取原

15、染色体对应基因值的同或/异或。 它改变了传统的变异方式,有效地克服了早熟收敛,提高了 遗传算法的优化速度。4高斯变异在进行变异时用一个均值为、 方差为2的正态分布的 一个随机数来替换原有基因值。 其操作过程与均匀变异类似。 4 结束语遗传算法的理论与技术研究主要包括编码、交叉运算、 变异运算、选择运算等遗传操作以及适应度评价等问题。本 文就遗传算法的理论与技术研究的诸方面进行了探讨。 遗传算法是一个十分活跃的研究领域,遗传算法的研究 正在从理论的深度、技术的多样化以及应用的广度不断地探 索,朝着计算机拥有甚至超过人类智能的方向努力。参考文献1 HOLLAND J H. Adap tation

16、in natural and artificial systems M .Ann Arbor: University ofMichigan Press, 1975 2 张文修,梁怡.遗传算法的数学基础M .西安:西 安交通大学出版社,2000(下转第 43页换。算法 2:设计 GF (28 上的 4×4级的 Hadamard MDS矩 阵。Step1、 从 有 限 域 (82GF 中 选 取 4个 非 零 元 素0123, , , i i i i a a a a 且满足 222201231i i i i a a a a +=;Step2、生成 Hadamard 矩阵 01231032

17、23013210i i i i i i i i i i i i i i i i a a a a a a a a H a a a a a a a a =; Step3、 验证 H 是否为 MDS 矩阵; 如果 H 为 MDS 矩阵,则输出 H ;否则返回 Step1重新选取。在 有 限 域GF (28 (生 成 多 项 式 为(8651p x x x x x =+上,我们通过编程生成了若干个4×4的自对偶的 MDS 矩阵,列举 3个如下:=, 13473174247137431H =251H =。 参考文献1 Biham E. Shamir A. Differential crypta

18、nalysis of DES-like CryptosystemsJ. Journal of Cryptology. 1991(4 : 3-722 Lai X, Massey J L, Murphy S. Markov Ciphers and DifferentialCryptanalysisC.AdvancesinCryptology-Eurocrypt, 91, LNCS 547. 1991. 17-383 Masayuki Kanda , Youichi Takashima , Tsutomu Matsumoto, et al. A Strategy for constructing Fast Round Functions with Practical Security Against Differential and Linear Cryptanalysis, SAC98, LNCS 1556. 1999. 264-2794 Bon Wook Koo, Hwan Seok Jang, and Jung Hwan Song,Constructin