3 总第 235 期 2009 年第 5 期 计算机与数字工程 Comp uter & Digital Engineering Vol. 37 No. 5 6　　　　 一种改进的抑制早熟收敛的遗传算法 (徐州师范大学计算机科学与技术学院1) 　徐州 　221116) (中石化管道储运公司徐州信息中心2) 　徐州 　221008) 巩 　固1) 　郝国生1) 　杨 　帆2) 摘 　要 　针对遗传算法运算速度低 、容易陷入局部最优值 、早熟收敛等缺点 ,提出了遗传算法算子的一些改进策略 ,对 遗传算法的选择 、交叉 、变异算子以及操作方法进行了改进 ,采用最佳保留选择策略 ,改进后的交叉与变异操作 ,使算法始终 保持了种群的多样性 ,同时也提高了寻优最终结果的精确性 。实验表明改进的遗传算法有效的改善了遗传算法的缺点 ,改 进后的算法明显优于传统的遗传算法 ,该算法具有良好的有效性和可行性 。 关键词 　遗传操作 　改进方法 　早熟收敛 　全局最优 　遗传算子 中图分类号 　TP181 Ge netic Algorit h m wit h I mp rove d Ge netic Op eration of Supp ressi ng Pre mat ure Conve rge nce Gong Gu1) 　Hao Guos he ng1) 　Ya ng Fan2) ( College of Comp uter Science and Tech nology , Xuzhou N or mal U niversit y1) , Xuzhou 　221116) ( Xuzhou Inf or mation Ce nter , B ranch of Sinop ec PS TC2) , Xuzhou 　221008) 　　Abs t rac t 　In resp ect t hat t he ge netic algorit hm’s disadva ntages of arit h metic sp eed lowly , running int o local op timum easily a nd so on , t he p ap er describes how t o imp rove t he ge netic algorit h m on t he selecting , crossing , mutating op erat or , and op eration met hod wit h t he multi op erat or crossed a nd mutated as well as adap ts mutation. The imp roved st rategies w hich reserve some elitist ge nes ca n reduce useless crossover eff ectively and t hus t he converge nce sp eed and t he search ca p abilit y are greatly imp roved w he n t he elitist reserved ge netic algorit hm t hat keeps best st rategies comp ared wit h t he ge netic algorit hm. Exp erimentation s hows t hat t he s hortage is meliorated by t his imp roved ge netic algorit h m , a nd t he im p roved algorit h m is sup erior t o t he t raditional ge netic algorit hm a nd has good validit y a nd f easibilit y. Ke y w ords 　ge netic op eration , imp rove ment met hods , p remat ure converge nce , global op timum , genetic op erat ors Clas s Nu m ber 　TP181 1 　引言 遗传算法 GA ( Genetic Algorit hms) 是以 Dar win 的生物进化论为基础而创建的 ,是基于进化论 中的优胜劣汰 、自然选择 、适者生存和物种遗传的 思想来搜索求解空间的最优解 。由于遗传算法在 求解优化复杂问题上的巨大潜力使得此算法已经 在许多领域得到了应用 ,如组合优化 、人工生命 、神 经网络 、模糊控制 、机器学习 、系统识别等[ 1 ] 。 早熟收敛是遗传算法中的特有现象 ,整个群体 已收敛于一个随机的非优个体 ,而不一定是局部最 优解与全局最优解 ,因此很难预见它的发生 。早熟 收敛的本质特征是群体中的个体非常相似 ,种群多 样性急剧减少 。导致种群早熟收敛的因素主要有 群体规模 、选择压力 、遗传操作 、适应度函数 、初始 群体分布等 ,现有解决早熟收敛问题的方案也主要 收稿日期 :2009 年 2 月 19 日 ,修回日期 :2009 年 3 月 30 日 基金项目 :江苏省高校自然科学基础研究资助项目 (编号 :08 KJD420002) ;徐州师范大学校级项目 (编号 :08XBL14) 资助 。 作者简介 :巩固 ,男 ,硕士 ,讲师 ,研究方向 :数据挖掘 、决策分析 。郝国生 ,男 ,博士 ,研究方向 :智能计算 、演经博弈 。 杨帆 ,女 ,硕士 ,研究方向 :信息安全 ,网格计算 。 © 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net 

第 37 卷 (2009) 第 5 期 计算机与数字工程 7　　　　 针对以上各点[ 2 ] 。因此本文在遗传算法的基础上 , 分析和研究相应的交叉算子与变异算子 ,研究和改 进遗传操作方法来抑制算法的早熟收敛 ,最后通过 实验与其他改进算法进行比较 ,验证了本文算法在 抑制早熟收敛提出的改进方法的有效性 。 2 　遗传算法及改进 遗传算法的基本思想是首先确定问题的求解 空间 。对求解空间中的每个点 (即可行解) 进行编 码 ,即用一种编码方式表示这个空间点 (特定串称 为染色体 ,染色体上字符串称为基因) 。从求解空 间中任选 N 个点组成初始种群 ,计算出群体中每 个个体的适应度函数值 ,运用选择算子 ,使适应度 函数值高的个体具有更多的繁殖机会 ,再运用交 叉 、变异算子产生下一代群体 ,对新的群体进行评 价 ,若找到满足问题要求的最优解 ,输出最优解 ,算 法求解结束[ 2～3 ] ;否则从当前群体的适应度函数值 开始 ,重复上述过程 。通常遗传算法的设计是按以 下步骤进行的 : 1) 确定问题的编码方案 ;2) 确定适配值函数 ; 3) 算法参数的选取 ;4) 遗传算子的设计 ;5) 确定 算法的终止条件 。 2. 1 　编码 在 GA 的运行过程中 ,并不是直接对实际变量 进行操作 ,而是对实际变量按某种方式进行编码 , GA 的所有操作基于实际变量的编码 。编码方法 在很大程度上决定了 GA 进化的效率 。遗憾的是 , 目前并没有一套严密的指导理论与准则来帮助设 计编码方案 。在不同的应用场合已经提出了多个 编码方案 。如熟悉的二进制编码和浮点数编码 。 由二值符号集{0 ,1} 所组成的二进制符号串[ 1 ,4 ] 。 作为遗传算法的标准编码方式 ,二进制编码方案不 仅解码简单 ,适用性好 ,而且极易设计相应的交叉 和变异算子 。连续变量搜索的精度取决于染色体 的长度和变量的取值范围 。假设待求问题的变量 为实数 ,要用二进制编码 ,设染色体长度为 l , 变量 的取值范围为 [ a , b] , 则可用式 ( 1) 确定编码精度 δ: δ= ( b - a) / 2 l (1) 这种从二进制空间到连续空间的映射 ,会使某 些可能为最优的个体漏掉 。此外这种映射可能会 引入一些额外的非线性 ,从而导致问题比原问题更 难于求解 。二进制空间和问题本身的连续空间可 能会有所不同 ,二进制空间的微小扰动会引起连续 空间的剧烈的震荡 , GA 在二进制空间进行进化操 作 ,所搜索到的最优解未必是连续空间的最优解 。 浮点数编码是指个体的每一个基因均用指定 范围内的浮点数表示 。个体编码的长度取决于决 策变量的个数 。如果一个问题有两个决策变量 ,则 直接编码为[ x1 , x2 ] 。浮点数编码适合于数值优化 问题 ,尤其是连续变量优化问题 。需要注意的是 , 浮点数编码必须保证基因值在给定的范围内[5 ] 。 交叉和变异算子所产生的结果也必须保证在给定 区间内 。解码 ( decoding) 是编码的反向过程 , 指从 遗传子型到表现型的映射 。 2. 2 　适应度函数确立 适应度函数的设计应该遵循一定的原则 ,如 : 1) 单值 、连续 、非负 、最大化 ;2) 尽量保证计算 量最小 、通用性强 , 减少计算时间 ; 3) 适应度函数 值能够很好地反映个体间的优劣程度 。 最常见的适应度函数的调整方法是线性变换 法 ,其计算简单 、易于实现 ,并能很好地保持种群的 多样性 。在线性变换法中 ,若原来的适应度函数为 f ,变换后的适应度函数为 f′, 则线性变换可表示 为式 (2) 。 f′= a f + c (2) 式 (2) 中 , a 和 c 分别表示变换系数和常数项 , 并且 这两个参数是需要确定的 。确定的方式为 :确保原 适应度的平均值等于变换后的适应度平均值 ,同时 确保对适应度值最大的个体在下一代种群中的复 制数量进行有效的限制 ,即把变换后的适应度函数 的最大值设置为原适应度平均值的 k 倍 , k 是人为 指定的 。假设原来的适应度函数的平均适应度为 f av g ,最大适应度为 f max , 那么表示 a、c 的表达式 为 : a = ( k - 1) f av g f max - f av g , c = ( f max - k f av g ) f av g f max - f av g (3) 按照式 (3) 的系数进行线性变化时 , 当种群中 某些个体的适应度过低 ,即远远低于平均适应度值 时 ,变换后的适应度值可能为负 。这是不符合要求 的 ,这种情况下应该采用另一种形式的变换 , 即式 (4) 变换方式 。 f av g f min f av g (4) a = , c = f max - f av g f max - f av g 其中 f min表示最小适应度 。此外 , 幂变换法和指数 变换法等也是比较重要的适应度函数的调整方法 。 2. 3 　遗传参数设置 在运行遗传算法程序时 ,需要对一些参数作事 © 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net 

8　　　　 巩 　固等 :一种改进的抑制早熟收敛的遗传算法 第 37 卷 先选择 ,它们包括种群的大小 、染色体的长度 、交叉 率 、变异率 、最大进化代数等 ,这些参数对遗传算法 的性能都有很重要的影响[6 ] 。 n + 1 个个体 (其中 , n 为群体大小) 。采用这种方法 的优点是 ,进化过程中某一代的最优解可不被交叉 或变异操作所破坏 。 种群规模就是指群体中所包含的个体的数量 。 选择较大数目的初始种群可以同时处理更多的解 , 容易找到全局最优解 ,其缺点是增加了每次迭代的 事件 ;较小规模的种群虽然可以提高遗传算法的运 算速度 ,但是却降低了群体的多样性 , 有可能会引 起遗传算法的早熟现象 。 交叉概率 Pc 的选择决定了交叉操作的频率 , 频率越高 ,可以越快地收敛到最有希望的最优解区 域 。若 Pc 取值过大 ,它会破坏群体中的优良模式 , 导致过早收敛 , 对进化运算产生不利影响 ; 如果取 值过小 ,产生新的个体的速度又会变慢 。一般取值 0. 4～0. 9 。 变异概率 Pm 的选取一般受种群大小 、染色体 长度等因素影响 , 如果 Pm 取值较大 , 虽然能够产 生出较多的新个体 ,但是也有可能破坏掉很多较好 的模式 ,使得遗传算法的性能近似于随机搜索算法 的性能 ; 若 Pm 取值太小 , 则变异操作产生新个体 的能力和抑制早熟现象的能力就会较差 。 染色体长度主要取决于问题求解精度的要求 , 精度越高 ,染色体长度越大 ,搜索空间就越大 ,相应 地要求种群规模设置大一些 。文中算法设计的染 色体的长度可以由用户设定 。 2. 4 　遗传算子的改进与设计 遗传算子包括选择 ( Selection) 、交叉 ( Cro ss over) 和变异 ( Mutation) 三种基本形式 ,它们是在 模拟自然选择以及遗传过程中的繁殖 、交叉和突变 现象的基础上得到的 。 选择算子 ( selection operator) 对个体进行优胜 劣汰 。选择算子有时又称为再生算子 ( rep roduc tion operator) 。选择算子在避免基因损失 、提高搜 索速度和全局收敛方面有着举足轻重的作用 。选 择操作基于个体的适应值 。常用的选择方法有赌 轮方法 、排序方法和锦标赛方法等 。选择的目的是 把优化的个体 (或解) 直接遗传到下一代或通过配 对交叉产生新的个体再遗传到下一代 。选择操作 是建立在群体中个体的适应度评估的基础上的 。 选择算子采用精英个体保存方法 。该方法的 思想是把群体中适应度最高的个体不进行配对交 叉而直接复制到下一代中 。设第 T 代时 ,群体中 x ( t) 为最佳个体 。设 X ( t + 1) 为新一代群体 ,若 X ( t + 1) 中不存在 x ( t) ,则把 x ( t) 作为 X ( t + l) 中的第 交叉算子 ( Cro ssover operator) 是遗传算法区 别于其他进化算法的重要特征 ,它是指对两个相互 配对的染色体按某种方式相互交换其部分基因而 形成两个新的个体 。交叉运算在遗传算法中起到 了关键作用 ,是产生新个体的主要方法 。编码方式 对交叉方式的影响比较大 ,一般而言 ,不同的编码 方式其交叉方式不同 。对于二进制编码和格雷码 而言 ,交叉算子一般可分为一点交叉 、两点交叉 、多 点交叉 、一致交叉等 。 遗传操作的算法设计主要是遗传算子的设计 。 POX 遗传算子产生的全都是可行解 ,且能很好地 继承父代的优良特性[ 5～6 ] 。因此本文主要以 POX 算子为原型 ,在此基础上进行改进 ,作为本文的遗 传算子 。POX 算子的主要思想就是让染色体上的 部分基因保持原来的位置 ,剩下的基因采用另一条 染色体的排列顺序 。本文提出的算子使父代的两 条遗传的染色体各自保留优良的不同的基因组合 , 剩下的基因组合仍然用另一条染色体上的排列顺 序 。经过这样的改进 ,使得染色体可以到达的范围 更大 ,产生最优解的机会就变大了 ,使结果容易达 到最优解 。采用二进制编码的方式时 ,假设在算法 中基因段组合 101 是最佳基因段 。本文对遗传算 子的单点交叉设计如下 。 父代 : parent1 :10010011 | 011110011 101 parent2 :00 101101 | 111111 101100 则子代如下 : off sp ring1 : 00 101101 | 011110 101101 off sp ring2 : 10 101101 | 111111 101101 变异算子 ( Mutation operator) 有利于遗传算 法跳离搜索空间的一个固定区域 ,以搜索更广阔的 空间 。传统的遗传算法存在早熟问题 ,早熟是指进 化收敛于局部最优解 ,而不是收敛于全局最优解 。 为了解决算法的早熟问题 ,很好的变异算子的设计 是必须的 。文中变异算子改进的操作主要是基于 实现算法对最佳基因段组合的突变 。如前面所述 101 假设是最佳基因组合段 ,则子代突变如下 : off sp ring1’: 00101101 | 01 0110101101 off sp ring2’: 10101101 | 1 011 01101101 变异是增加群体多样性的搜索算子 ,交叉结束 后 ,交配池中的全部个体位串上的每位等位基因以 © 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net 

第 37 卷 (2009) 第 5 期 计算机与数字工程 9　　　　 概率 Pm 进行随机改变 , 从而每代大约发生 次变 异 。其中 N 为群体规模 , L 为串长 。 Pm 值过大 , 会破坏有用的模式而使解远离最优解 ,使算法变成 随机搜索 ; Pm 值过小 ,则不会产生新的基因块 。无 法使陷于超平面的解摆脱超平面 。Pm 取值一般在 0. 005～0. 01 之间 。就能随机 、独立地产生许多新 个体 ,从而使整个种群脱离早熟 。 2. 5 　算法的终止条件 最大进化代数是表示遗传算法运行结束条件 的一个参数 ,它表示遗传算法运行到指定的进化代 数之后就停止运行 ,并将当前群体中的最佳个体作 为所求问题的最优解输入 。一般的取值范围是 100～500 代 。至于遗传算法的终止条件 ,还可以 利用某种判定准则 ,当判定出群体已经进化成熟且 不再有进化的趋势时就可以终止算法的运行过程 。 本文采用的最大进化代数是 200 。采用终止条件 主要是由于遗传算法具有较大的随机性 。 3 　实验结果与分析 最优化问题是遗传算法经典应用领域 ,如函数 最优化 、组合最优化等 。函数最优化能有效 、直接 反映算法实际性能 。本文采用二进制对普通函数 编码 ,采用无最大值自然数编码方法对经典函数进 行编码优化测试 。 测试函数采用一个普通函数 (极大值问题) 、和 一个经典函数 (极小值问题) 的最优化问题 (opti mization p roblem) 来验证文中的算法思想 。普通 函数如下所示 。该函数在 ( - 1 ,2) 内有一最大值 0. 463618 。 objective f unction : f = 2 xsin (20 x) ×e - 2 x ( - 1 < x < 2) 表 1 是普通函数优化算法和基本遗传算法实 现时用户运行设置某一次的参数对照表 。 表 1 　算法运行结果与 GA 比较 运行 次数 种群 大小 染色体 长度 最大进 化代数 交叉 概率 变异 概率 1 2 3 4 5 80 32 30 30 28 30 20 20 20 18 160 140 140 160 130 0. 4 0. 01 0. 3 0. 02 0. 2 0. 01 0. 2 0. 01 0. 5 0. 01 最优解代数 GA 优化 GA 12 25 46 46 73 3 16 37 37 67 　　从表 1 中可以看出 ,在相同条件下 ,优化后的 算法比基本算法获取最优解的代数减少 。在实验 时平均收敛 、算法搜索等方面优化后的算法都有适 当提高 。 经典函数采用 Goldstein p rice f unction 。该函 数是一个多模函数 ,有许多极小值点 ,但只有一个 全局最小值 3 ,最优点 (0 , - 1) 。该函数的图形见 图 1 所示 。 图 1 　Goldstein p rice f unction 图形 p rice f unction : (其中 - 2 Goldstein 2) x1 , x2 F = (1 + ( x1 + x2 + 1) 2 ×( 19 - 14 x1 + 3 x2 1 - 2 ) ) ×(30 + (2 x1 + 3 x2 ) 2 ×(18 - 14 x2 + 6 x1 x2 + 3 x2 32 x1 + 12 x2 1 + 48 x2 - 36 x1 x2 + 27 x2 2 ) ) 优化算法采用无最大值自然数编码 ,编码长度 12 ,种群大小为 30 ,最大进化代数设为 60 。我们知 道 ,采用自然数编码是通过随机数来影响交叉与变 异操作 ,故交叉与变异区开度不大 ,可以采用离散 重组方法产生下一代 。测试结果与文献[ 7 ]及基本 算法对比见表 2 ,表 2 中数据是多次运行的平均 值 。 表 2 　算法运行结果与其它算法比较 比较名称 种群 大小 收敛 代数 收敛 时间/ s 全局收敛率 / ( %) 本文方法 30 文献[ 7 ]方法 72 16. 2 0. 79 98. 2 21. 33 1. 23 93 　　从表 2 可以看出 ,本文方法比文献 [ 7 ]在效率 上有较大的改进与提高 。种群大小 、收敛代数等可 以明显提高 ,文献[ 7 ]可以看出种群大小过大时反 而会造成遗传算法性能的下降 ,全局收敛率不高 。 算法在实际设计中 ,种群大小 、收敛率 、编码方案 、 操作算子等都有待进一步研究 。 4 　结语 基本遗传算法在收敛性和获取最优解时会出 现早熟现象 ,遗传操作算子会使基本遗传算法陷于 局部收敛 。本文提出了对遗传算子的改进方法 ,并 用实验验证了本文提出的算法思想 ,在一些性能上 (下转第 16 页) © 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net 

2 16　　　 金金宝等 :遗传编程在符号回归中的应用 2 2 2 第 37 卷 ( ( + x ( ( + x ( - 体为 ( + x ( ( co s ( - x x) ) ( - x x) ) ) x) x) ) x) ) , 化简后即为 x4 + x3 + x2 + x , 此 时的最佳适应度为 0. 00 , 所以该代的拟合函数完 全正确 。从 31 代继续运行下去 , 最优个体再度扩 张 ,如 32 代最优个体 ( + ( x x) ) ( + ( - ( + x x) x) ( % ( x + ( sin ( - x x) ) ) x) ) ) ( x x) ) x) x) ,尽管该最优个体的算法树扩张 ,但仍是正确 结果 ,化简即为 x4 + x3 + x2 + x 。图 4 为第 0 、1 、2 、 31 代最优个体的算法树 ,图 5 为第 0 、1 、2 、31 代最 优个体的函数图形 ,图 6 为各代适应度及个体长度 的变化 。 ( - ( ( + x ( 图 4 中可以看出在进化过程中 ,个体的算法树 长度明显变长 。图 5 描述了四个最佳个体的函数 曲线 ,可以看出在进化过程中 , 各代的最优个体跟 正确函数逐步逼近 , 一直进化到 31 代时找到正确 解 。图 6 描述了遗传编程运行 89 代中各个代的最 优适应度 ,平均适应度及个体的平均长度 (已缩小 50 倍) 的变化情况 。从图中可以看出 ,最优适应度 (上接第 9 页) 要优于 GA 算法 ,较好地避免了 GA 的早熟出现 , 提高了 GA 算法的效率 。文中同时和其它改进思 想算法作了比较 ,理论分析和实验的结果说明本文 对算法提出的改进方法有效提高了遗传算法的进 化效率 。如何更有效地应用于连续优化 、组合优化 问题是下一步的研究方向 。 参 考 文 献 [ 1 ]巩敦卫 , 郝国生 , 周勇 , 等. 交互式遗传算法原理 及其应用[ M ]. 北京 : 国防工业出版社 , 2007 [2 ]杨世达 ,李庆华 , 阮幼林. 改进遗传算法全局收敛 性分析[J ]. 计算机工程与设计 ,2005 ,26 (7) :695～697 [ 3 ]吴政 ,汪峰坤. 基于遗传算法的排课系 [J ]. 计算机 与数字工程 ,2008 ,36 (11) :29～32 [ 4 ]最优化问题全局寻优的混合遗传算法 [J ]. 力学学 报 , 2002 , 34 (3) : 469～474 在运行前期明显减小 ,于 31～40 代为零 ,以后又稍 有升高 。平均适应度在初期明显减小后 ,继续缓慢 降低 。个体的平均长度则在不断加大 ,这是由于多 次交叉及突变造成的 。 4 　结语 实验表明 ,遗传编程是一种相当有效的符号回 归方法 。它的优势源于其结构的灵活性 ,由于采用 树形结构 ,可以描述层次化的问题 , 克服了传统方 法中确定函数结构难的缺陷 。但是遗传编程在整 体水平还处在比较初步的阶段 。下一步的工作就 是改进遗传编程算法 ,使其在实际应用中达到更好 的效果 ,可以通过改进初始种群生成方法 , 改进复 制 、交叉操作方式或改进适应度计算方法等来降低 程序的复杂度 ,提高程序的收敛性 。 参 考 文 献 [1 ] Koza J R. Introduction to genetic programming [ M ]. Cambridge :MIT Press ,1994 [2 ]王正志 ,薄涛. 进化计算 [ M ]. 长沙 :国防科技大学 出版社 ,2000 [3 ]王小平 ,曹立明 ,顾绍元. 遗传程序设计及其在符 : 号回归问题中的应用 [J ] . 同济大学学报 , 2001 , (10) 1200～1204 [4 ] 吴勇 ,谷峰 ,唐俊. 遗传规划中近似函数的求解问 题[J ]. 微机发展 ,2003 ,13 (3) :59～60 [5 ] 陈国良. 遗传算法及其应用 [ M ] . 北京 :人民邮电 出版社 , 1996 [5 ] Tu Yu kuang , Yang J , Sun Ming ting , et al. Fast variable size block motion estimation for efficient H. 264/ AVC encoding [J ]. Signal Processing : Image Communica tion , 2005 , 20 (7) : 595～623 [6 ] Tomioka S. , Nisiyama S. , Ento T. Identification of electro magnetic mode excited by electron beam in waveguide using genetic algorithm[J ]. Advances in Contin uum Mechanics and Electromagnetics ,2004 : 251～260 [7 ] Falcao D M. Genetic algorithms applications in e lectrical distribution systems [ C ]. Proceeding of the 2002 Congress on Evolutionary Comp utation 2002 , CEC’022 , 2002 ,5 , 2 : 1063～1068 [8 ]Li Daw ,Wang Li. A Study on the Optimal Pop ula tion Size of Genetic Algorithm[ C ]. Proceedings of the 4th World Congress on Intelligent Control and Automation. Shanghai ,China : [ s. n. ] , 2002 :3019～3021 © 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net