基于成长机制的改进遗传算法及其应用.pdf

基于成长机制的改进遗传算法及其应用郝鹏（山西机电职业技术学院 基础部，山西 长治 046000）摘要:在简单遗传算法（SGA）的基础上，结合自然界物种进化中优胜劣汰的过程，引入所有个体向最优个体学习的基于成长机制的改进遗传算法（DGA）。通过设置个体的学习率来区分不同个体学习过程，根据个体成长之后的适应度值来判断是否选择进化，充分保证进化初期种群的多样性，进而优化了遗传算法的全局搜索能力。通过函数寻优以及 TSP 问题的仿真，充分验证了新算法在增强全局寻优方面的能力。关键词:改进遗传算法；成长机制；全局寻优中图分类号：TP31文献标识码：A文章编号：1008-9004（2023）03-099-03虽然遗传算法（Genetic Algorithm,GA）具有许多优点，可是当面对实际复杂多变的问题时还是存在以下的不足：（1）整体解空间的搜索能力很强，局部最优解的搜寻能力很差。据研究，遗传算法可以很快地到达最优解的 90%，但是要真正的到达最优解却要花费很长的时间；（2）容易出现早熟的现象。当种群规模较小时，如果进化初期出现适应度较高的个体，由于个别个体繁殖过快，往往会破坏种群额多样性，从而出现早熟的现象1。引入个体成长机制的 DGA 算法，通过实验探究，更有利于在进化初期保留种群的多样性，从而进一步增强算法的全局寻优能力。1 DGA引入成长机制的改进遗传算法从简单遗传算法（SGA）的实现过程可以看出，个体的基因是其是否进化的决定性因素，遗传算子中的交叉算子和变异算子都是对个体的基因进行改进2，以提高其适应度值，来保证最优解的搜寻。算子的实现机理是物种在进化过程中基因的交叉和变异3。由于交叉过程和变异过程的随机性，并不能保证经过算子作用之后的种群个体的适应度值一定得到了提高，由此得到的个体在选择算子的作用下会存在优秀个体的基因快速复制，种群多样性降低，容易陷入局部最优解。本文进一步结合物种进化的过程，提出了所有个体在进行进化选择之前都会通过向优秀个体学习来提高自身进化的几率，形成了个体成长机制的改进遗传算法即 Develop Genetic Algorithm,简称 DGA。其算法的主要流程如图 1：收稿日期：2022-08-25基金项目：山西机电职业技术学院立项课题（JWCL20010）作者简介：郝鹏（1988-），男，讲师，硕士，研究方向：应用数学、图形图像处理、数据挖掘。图 1增加成长算子 GA 的算法流程图2 成长算子的设计由于不同问题运用遗传算法的种群编码方式不同，因此成长算子需要分别设计。本文以多元函数寻优和旅行商问题（TSP）为例，设计了两种种群个体向优秀个体学习的成长算子。第 30 卷 第 3 期灾燥造援30 晕燥援3鄂州大学学报允燥怎则灶葬造 燥枣 耘扎澡燥怎 哉灶蚤增藻则泽蚤贼赠圆园23 年 5 月May 圆园23doi:10.16732/ki.jeu.2023.03.036鄂州大学学报第 30 卷可以看出函数本身是一个多峰类型函数，并且函数在 X1=X2=X3=X4=X5=时取得最小值-2，这里采用实数编码进行种群基因初始化和遗传进化，其中成长算子的实现原理为将个体 Pd比例的基因向最优个体的对应基因按照式（1）和式（2）进行靠近：仔22.1 多元函数寻优考虑多元函数：f（x）=-5sinx1sinx2sinx3sinx4sinx5-sin5x1sin5x2sin5x3sin5x4sin5x5+80 xi0.9，i=1,2,3,4,5Xij=Xij+p（Ximinj-Xij），XijXiminj（1）Xij=Xij+p（Xij-Ximinj），XijXiminj（2）其中 Xij表示第 i 个个体的第 j 个基因片段，Ximinj表示当前种群中最优个体的第 j 个基因片段。2.2 TSP 路径寻优以 14 个城市的 TSP 问题为例，直接以城市编号作为符号编码方式进行种群初始化和遗传进化，其成长过程见表 1：表 1成长算子示意图1.最优个体1 14 3 7 8 4 11 2 5 12 6 13 9 102.随机选取基因片段7 8 43.种群某个体11 13 5 2 7 12 9 6 14 3 4 1 10 84.将 2 中片段插入形成新个体11 13 5 2 7 12 9 6 14 3 8 1 10 43 实验仿真仿 真 环 境 为：Intel（R）Core（TM）i7-8700CPU3.2GHz window10 系统仿真软件为：Matlab2016a3.1 函数寻优为验证 DGA 算法效果，这里选择初始种群规模为 20，交叉概率 Pc=0.6,变异概率 Pm=0.01，成长学习率 Pd=0.2，总共进行 100 代的进化。经过 50次仿真之后取每一代最优解的平均值，最终得到SGA 和 DGA 的进化过程如图 2、图 3：图 2SGA 进化过程图 3DGA 进化过程SGA 和 DGA 取得最优解的代数、最优解如表 2：表 2SGA 和 DGA 效果比较最优解代数最优解SGA212.0216DGA172.0152可以看出，DGA 相较于 SGA 来说在多元函数寻优过程中能更快地寻找到更好的优解，由此可以说明成长机制可以有效地提高遗传算法的寻优效率。3.2 TSP 寻优3.2.1 14 个城市首先对 14 个城市的 TSP 问题进行了 SGA 和DGA 算法的模拟仿真，设置初始种群为 100，交叉概率 Pc=0.9,变异概率 Pm=0.05，代沟 P=0.9，成长学习率 Pd=0.2，共进行 200 代的仿真。各经过 50 次的模拟之后得出最优路径取平均值绘图如图 4，图 5：图 4SGA 模拟算法图 5DGA 模拟算法100第 3 期郝鹏：基于成长机制的改进遗传算法及其应用SGA 在平均迭代 60 次之后，DGA 在平均迭代 54 次之后，均取得了 14 个城市的最短路径为29.34059 如图 6，可以看出 DGA 相较于 SGA 在路径寻优中搜索效率有 10%的提升。图 6DGA 与 SGA 寻优中比较3.2.2 中国 34 个省会城市在对 34 个中国省会城市进行路径寻优时，设置初始种群为 100，交叉概率 Pc=0.9,变异概率Pm=0.05，代沟 P=0.09，成长学习率，共进行 10000代的仿真。各经过 50 次的模拟之后得出最优路径取平均值绘图如图 7、图 8：图 7SGA 最优路径平均值图 8DGA 最优路径平均值SGA 和 DGA 分别寻找的轨迹分别为图 9、图 10：图 9SGA 寻找轨迹图 10 DGA 寻找轨迹34 城市 TSP 问题 SGA 和 DGA 取得最优解的代数、最优解如表 3：表 3 TSP 问题中 SGA 与 DGA 求解结果比较最优解代数最优解SGA700019.1255DGA100518.0672可以看出当城市数量较多时，DGA 的寻优能力无论在效率上还是在结果上都要明显强于SGA，并且所获得的最优解与理论最优解是接近的，由此说明 DGA 算法是有效的。4 结语引入个体成长机制的 DGA 算法，相较于简单遗传算法来说，更有利于在进化初期保留种群的多样性，从而进一步增强算法的全局寻优能力。通过函数寻优、14 城市 TSP 问题以及 34 城市 TSP问题的测试，充分验证了算法的有效性，达到了改进算法的目的。在此基础上，如果将 SGA 中的交叉算子、变异算子均改为由个体适应度值确定的自适应概率，这样可以进一步改进算法的性能。参考文献：1刘洪杰,王秀峰.遗传多峰搜索J.系统工程学报,2000(4):321-0326.2史峰,王辉,郁磊,等.Matlab 智能算法 30 个案例分析M.北京：北京航空航天大学出版社,2011:19-21.3毕哓君.信息智能处理技术M.北京：电子工业出版社，2010:3-4.（责任编校：朱立文）101