遗传算法的改进

遗传算法的改进 韩万林, 张幼蒂 ()1. 中国矿业大学 采矿工程系, 江苏 徐州 221008 摘要: 遗传算法是建立在遗传学与自然选择基础上的自适应搜索过程. 作为解决复杂问题的一种 有效手段, 遗传算法是目前人工智能和系统优化领域的热点研究课题. 但是, 在实际应用中, 简单 遗传算法存在着收敛速度慢和稳定性差等缺陷. 为克服这些问题, 在对遗传算法的基本要点进行 介绍的基础上, 对交换、突变和复制等算子以及操作过程进行了改进. 为了验证改进遗传算法的可 行性与有效性, 进行了多峰值函数的优化. 试验结果表明, 改进遗传算法提高了收敛速度和稳定 性. 关键词: 遗传算法; 多峰值函数优化; 改进 中图分类号: O 224 文献标识码: A 适应度函数1. 2 自 70 年 代 美 国 M ich igan U n ive r sity 的 Jo h n (教授提出遗传算法 , 简 在遗传算法中, 适应度是描述个体性能的主要 H o llan d gen e t ic a lgo r ithm ) 称 的概念体系以来, 遗传算法得到了各领域指标. 根据适应度的大小, 对个体进行优胜劣汰. 适 GA 学者的高度关注. 遗传算法仿效生物的进化与遗应度是驱动遗传算法的动力. 从生物学角度讲, 适 传, 根据“生存竞争”和“优胜劣汰”的原则, 借助复 应 度相当于“生存竞争, 适者生存”的生物生存能 制、交换、突变等操作, 使所要解决的问题一步步地 力, 在遗传过程中具有重要意义. 将优化问题的目 标函数与个体的适应度建立映射关系, 即可在群体 逼近最优解. 与其它优化方法相比, 遗传算法以单 一字符串的形式描述所研究的问题, 只需利用适应 进化过程中实现对优化问题目标函数的寻优. 将目 度函数值来进行优化计算, 而不需要函数导数等其 标函数转换成适应度函数一般应遵循两个原则: 一 它辅助信息, 特别适合解决其它科学技术无法解决 是适应度必须非负, 二是优化过程中目标函数的变 或难以解决的复杂问题, 如结构优化、非线性优化、 化方向应与群体进化过程中适应度函数变化方向 机器学习等, 是继专家系统、人工神经网络之后又 一致. 一受人青睐的人工智能新学科分支. 1. 3 群体初始化 群体初始化是指产生第一代一定数量的个体.1 , 31 遗传算法的基本要点 一般可先将优化问题的初始解转化为个体, 第一代 1. 1 编码群体中的其余个体随机产生. 研究表明, 群体的初 遗传算法的操作对象是字符串, 变量与个体间 始化影响遗传过程的收敛速度. 如果初始群体选择 恰当, 收敛速度较快. 否则, 收敛速度较慢, 甚至很的映射要通过编码来实现. 编码方法要求: 一是字 一般大于50, 而且初始 符串要反映所研究问题的性质; 二是应遵循字符串 难求得最优解. 群体规模 N 长度最短、模式阶次最高、模式数目最大等原则. 假 群体中要包含尽可能多的模式. 1. 4 遗传算子设有两种编码方法, 一种是二进制编码, 另一种是 进制编码. 从理论上可以证明, 当 > 2时用二进 k k 群体初始化以后, 后代群体的繁殖一般通过复 制编码来描述个体比用 进制编码能反映更多数 k 制、交换、突变等遗传算子的操作来进行. 目的基因模式, 因此遗传算法中常用二进制编码. ) 1复制 复制是将亲代的个体原封不动地传 收稿日期: 1999 07 01 () 的个体位串数为 , , 串 集中存在的模式 递到子代. 每代中的每一个个体, 按照其适应度函 H m H t 的个体位串的子集合的平均适应度为 数的大小决定它能够复制到下一代的概率. 通过复 属于模式 H () 制, 使得群体中的优秀个体数目不断增加, 整个进 , 全部个体位串集合的平均适应度为 , 则第 f H f 化过程朝着更优解的方向进行, 反映了“优胜劣汰” 的个体位串数的期望值为 + 1代的模式 tH 的原则. 复制概率 取0. 1, 0. 2.P r () ()m H , tf H + ) (. m H , t 1= H ) 2交换 复制虽然可以使可行解群体朝着最 - - () f 1 P c O H Pm - ( )l 1 优解方向移动, 但只能在现有群体内寻优, 它不能 该式是遗传算法的基本理论公式, 它说明所有长度 产生与亲代不同的个体. 在遗传算法中引入交换算 短、阶次低、平均适应度高于群体平均适应度的模 子, 每一代的各个个体之间按一定的概率交换其部 式在遗传算法中呈指数形式增长1相反, 凡是长度 长、阶次高、平均适应度低于群体平均适应度的模 分基因, 产生新的基因组合, 使各个解有机会交流 其优秀基因, 可望获得比亲代更好的解的结构. 执 式, 将呈指数形式消失1这个结论称为模式定理, 它 行交换的个体是随机选择的, 通常按给定的交换概 深刻地阐明了遗传算法中发生“优胜劣汰”的原因1 ( ) 率 取0. 5, 0. 8, 用轮盘算法按适应度大小选 P c 择被交换的个体. 交换点的选择也是随机的. 遗传算法的改进2 ) 3突变 复制和交换只能在现有的基因型的 虽然遗传算法已经取得了广泛的应用, 但存在 排列组合内寻找最优, 而不能产生新的基因型. 突 着收敛速度慢及算法稳定性差等缺陷. 为此, 在吸 变算子是对每个字符串的每一位按一定的概率由14, 5 收前人研究成果的基础上 , 对于遗传算法的求 变0或由0变1, 产生新的基因型, 扩大寻优范围. 突 解过程, 我们提出了如下改进措施与步骤:变个体的选择以及突变位置的确定, 都是采用随机 ) 1人工方法产生初始群体 先将优化问题的初0. 001, 0. 01. 取的方法产生. 突变概率 Pm 始解转化为个体, 然后在问 1. 5 终止条件 题的解空间中用人工方法产生初始种群的其它个 , 它通过 遗传算法是一种反复迭代的搜索方法 体, 使初始群体的个体模式阶次较高、模式数目较 多次进化逐渐逼近最优解而不是恰好等于最优解, 大, 具有多样性. 这样通过适当选择字符串长度和 因此需要确定其终止条件. 最常用的终止方法是规 群体规模, 可以在开始的几代内找到各极值点所在 定遗传的代次. 当目标函数是方差这一类有最优目 的区域, 加快搜索速度. 标值的问题时, 可采用控制偏差的方法实现终止. ) 2上代群体的处理一旦遗传算法得出的目标函数值与实际目标函数 对于上代群体, 计算其个体的适应度, 判别其 值之差小于允许值后, 算法终止. 终止条件也可通 是否满足终止条件. 如果满足终止条件, 停止遗传 过检查适应度的变化来实现. 如果群体平均适应度 操作, 输出最优解. 否则, 将上代群体全部放入中间 变化率和最优个体适应度变化率小于许可精度, 则 群体, 并对上代群体独立进行优选父代交换和大突可以认为群体处于稳定状态, 群体进化基本收敛, 变操作. 可结束群体进化过程, 否则继续群体的进化过程. ) 3优选父代交换 优选父代交换的主要思想 1. 6 模式定理 是指在进行交换操 在遗传算法中, 虽然复制、交换、突变等遗传算 作时, 提高父代的质量, 即选择较优的父代个体参子都是通过随机的方式来实现, 但从理论上讲, 遗 与交换. 具体过程是: 从上代群体中随机选取两个 传算法的群体进化过程是向优良个体逼近的过程, 个体, 然后比较其适应度, 保留适应度大的个体, 再 它 是 一 种 理 性 的 进 化 算 法. 70 年 代 初, Jo h n H o l2 从上代群体中随机选取两个个体, 同样保留适应度 教授提出了基因模式理论, 揭示了遗传算法 lan d 大的个体, 以保留下来的两个个体作为父代个体.的内在机制, 为遗传算法奠定了坚实的理论基础. 产生 0, 1 之间均匀分布的随机数 , 如果 < ,ssP c模式是指字符串中具有类似特征的子集, 通常 则两者进行交换, 将交换后的两个新个体加入到中 由二进制数0, 1 与通配符3 所构成的字符串来描 间群体, 否则直接将保留下来的两个个体加入到中 表示, 模式的阶次是指模式 述. 如果某一模式用 H () 间群体. 中已有明确含意的字符个数, 记为 ; 模式的 O H ) 长度是指模式中最前面和最后面两个具有明确含 4大突变操作 ()意的字符之间的距离, 记为 . 设第 代个体位理论上, 遗传算法的突变操作可以产生新个?H t 体, 使算法跳出“早熟”. 但为了保持算法的稳定性, 制到下一代群体, 否则个体 j 复制到下一代群体. 改进后遗传算法的基本流程如图1所示.突变操作的突变率通常取得很小, 单靠传统的突变 操作需要很多代才能变异出一个不同于其它个体 确定表示问题的字符串 的新个体. 大突变操作的思想是: 对上代群体, 以一 构造适应度函数 个远大于通常的突变概率的概率进行一次突变操 作, 并将突变后产生的新个体加入到中间群体. 大 人工方法产生初始群体 突变操作能够随机、独立地产生许多新个体, 从而 结束 能始终保持群体的多样性, 使群体脱离“早熟”. 计算适应度 )5 基于M e t ropo lis 判别准则的复制策略 结果 输出 对于中间群体, 运用基于 M e t ropo lis 判别 准 满足终止条件否 则的复制策略, 产生下一代群体. 基于 YM e t ropo lis N 判别准则的复制策略分为两步: 上代群体处理 优选父代交换 大突变操作 实施最优保留策略 将中间群体中性能最 a. 好的个体无条件地复制到下一代群体中, 这样就会 中间群体 保留中间群体中的最好解, 使遗传算法可以以概率 1收敛到全局最优解, 保证了算法的收敛. 基于M etropo lis判别准则的 复制策略产生下代群体 在 b. 实施M e t ropo lis 判别准则的复制策略 中间群体中随机选取个体 和 , 和 竞争进入下 i j i j 改进遗传算法的基本流程图 一代群体的准则采用 判别准则: 产生M e t ropo lis . 1 F igT h e f low ch a r t o f im p ro ved gene t ic a lgo r ithm (0, 1 之间均匀分布的随机数 s, 如果 s < = m in 1, 改进遗传算法的应用实例3 ((( ) ( ) ) ) ) (( ) ( ) exp - f i- f j ƒT 式中, f i, f j 分别 为验证改进遗传算法的性能, 我们采用 P e rcy ) 为个体 i 和 j 的适应度, T 为控制参数, 则个体 i 复 6 7 的目标函数 和 的目标函数 , 进 F 1 Sch afe r F 2 F 3 行实验. , , 具有多峰值点, 它们如表1所示.F 1 F 2 F 3 采用的目标函数 表1 1Table The targe t f un c t ion s 函 数 表 达 式 参数范围 个体长度 优化阈值 2 2 x + x 1 2 () ( ) ( ) - 10 , 10 22 3 F : f x =+2 co s 20Πx co s 20Πx +1 12 2 2 2 2 s in x + x - 0. 5 1 2 - 100 , 100 22 1 () 0. 5 - F : f x =2 2 22() 1 + 0. 001 x + x ] 1 2 2 2 2 2 0. 25 2 0. 1( ) () ( ( ) ) : = + [ 50 + + 1- 100 , 100 22 0. 994 F 3f x x 1x 2sin x 1 x 2 0. 0. 200代还未优化到目标函数的阈值, 则该次优化失 简单遗传算法的 = 100, c = 65, P m = N P 败, 将两种算法在50次中失败的总数作为衡量算法 改进遗传算法的 = 50, c = 0. 65, m = 0. 15. 01. N P P 稳定性的 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 . 实验结果如表2所示. 从实验结果我 我们分别利用简单遗传算法和改进遗传算法对表1 中的3个目标函数进行优化, 以优化50 次作为一次 们可以看到, 改进遗传算法较简单遗传算法不但在 实验, 将优化到目标函数的优化阈值所需要的平均 收敛速度上有60%, 130% 的提高, 而且算法的稳 定性也有显著的提高. 数作为衡量算法收敛速度的标准. 如果算法繁殖 表2 实验结果 2 Table The exper im en t re sults 简单遗传算法 改进遗传算法 改进率% ƒ函数 平均进化代数 未收敛次数 平均进化代数 未收敛次数 收敛速度 81. 9 15 51. 7 6 58. 4 F 1 70. 6 4 30. 8 0 128. 5 F 2 F 78. 4 3 35. 9 0 90. 5 3 P re ss, 1975. 88, 105. 结论4 . , 2 Go ldbe rg D EGene t ic a lgo r ithm s in sea rch op t i2 简单遗传算法的操作过程, 随机产生的初始群 [. : m iza t io n and m ach ine lea rn ing M N ew Yo rkA d2 体性能较差, 优良个体和劣质个体经受相同的交换 2,, 1989. 59d iso n W e sley P ub lish ing Com p any Inc和突变, 容易造成优良个体的破坏, 收敛速度慢, 算 308. 法稳定性差. 改进后的遗传算法, 人工方法产生的 云庆夏, 黄光球, 王占权. 遗传算法和遗传规划 [.M 3 初始群体性能较好, 将上代群体全部保留到中间群 北京: 冶金工业出版社, 1997. 21, 57.体, 对上代群体独立进行优选父代交换和大突变操 王占权. 进化算法的研究及其应用 [. 沈阳: 东北大 D 作. 这样, 中间群体既保留了上代群体, 又保留了上 4 学资源与土木工程学院, 1999. 代群体经过交换和突变产生的新个体, 使中间群体 在保护优良个体不受破坏的基础上, 又保持了群体 马钧水, 刘贵忠, 贾玉兰. 改进遗传算法搜索性能的大5 ( ) 变异 操 作 [. 控 制 理 论 与 应 用, 1998, 15 3: 404,J 的多样性. 最后运用基于 判别准则的 M e t ropo lis 复制策略产生下一代群体, 一方面保证中间群体中 407. 的最优个体进入下一代, 另一方面在接受优化解 , , . P e rcy P C Yo h H an P aoCom b ina to r ia l op t im iza2 6 外, 有限度地接受劣质解, 保证了群体的多样性和 t io n w ith u se o f gu ided evo lu t io na ry sim u la ted an2 算法的收敛. 实例证明, 改进后的遗传算法提高了 ( ) ,[ . , 1995, 2 6 : 290nea ling J IE E E T ran s o n N N 收敛速度和算法的稳定性. 295. 参考文献: . Sch affe r J DA study o f co n t ro l p a ram e te r s affec t ing 7 o n line p e rfo rm ance o f gene t ic a lgo r ithm s fo r func t io n [. : . . op t im iza t io n A inSanM a teoP ro co f th e T h ird . [ . :In te rna t Co nfo n Gene t ic A lgo r ithm s C CA 1 A dap ta t io n in na tu ra l and a r t if ic ia l sy s2 H o lland J. 1989. 51, 60. [.: tem s M A nn A rbo rU n ive r sity o f M ich igan Im p ro vem en t o f Gen e t ic A lgo r ithm 22, H an W an lin Zh an g Yo u d i ( ), , , 221008, D ep a r tm en t o f M in ing E ng inee r ingCUM T X uzho uJ iang su C h ina A bstra c t: Gen e t ic a lgo r ithm , b a sed o n th e m ech an ism o f gen e t ic s an d n a tu ra l se lec t io n , is an adap t ive . , sea rch in g p ro cedu reA s a pow e rfu l app ro ach app lied to com p lex p ro b lem sgen e t ic a lgo r ithm is a ho t . , po in t fo r re sea rch o n th e f ie ld s o f a r t if ic ia l in te lligen ce an d sy stem op t im iza t io nH ow eve rsim p le gen e t2 . ic a lgo r ithm h a s d raw b ack s su ch a s slow co n ve rgen ce an d le ss stab ility in ac tu a l u se sT o o ve rcom e th e se , , p ro b lem sc ro sso ve rm u ta t io n an d rep ro du c t io n op e ra to r s a s w e ll a s th e p ro cedu re a re im p ro ved b a sed . o n in t ro du c t io n o f th e p r in c ip le sM u lt im o da l fu n c t io n op t im iza t io n is p e rfo rm ed to ve r ify th e fea sib ility . an d effec t iven e ssT h e exp e r im en t re su lt s show th a t co n ve rgen ce sp eed an d stab ility a re in c rea sed b y im 2 .p ro ved gen e t ic a lgo r ithm : ; ; Key word sgen e t ic a lgo r ithm m u lt im o da l fu n c t io n op t im iza t io nim p ro vem en t