改进的遗传算法在最短路径中的应用

何国锋+刘宇红

摘要： 经典遗传算法通过模拟生物自然进化来进行求解，但往往面临局部最优以及不能事先确定遗传所需要的迭代次数。该文以两点间的最短路径为对象，通过分析经典遗传算法中存在的问题，提出了基于阈值比较法与借鉴交叉思想的变异方法两种思想，在最短路径问题求解中，与经典遗传算法结果进行比较分析，对相关参数进行调整，达到了预定的效果。

关键词： 最短路径；生物进化；遗传算法

中图分类号：TP301.6 文献标识码：A 文章编号：1009-3044（2017）25-0162-03

1 概述

遗传算法（Genetic Algorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。它由美国J.Holland教授1975年首先提出，把所有可能出现的解做为染色体生成种群，对种群进行模拟生物进化的遗传迭代操作，每代中选取对环境适应度大的个体进行种群的下一步迭代，从而在迭代的过程中找出最优解。最短路径就是在一点出发，到达目的点，找出距离最短的一条路径，即端到端的最短路径。在通信网络、数值优化、机器学习、模式识别、神经网络和模糊控制等方面都有着应用。

2 最短路径遗传算法实现

2.1 遗传算法的基本概念

染色体：在遗传算法中，染色体指某一问题的每一种解，染色体中的每一位编码都称为一个基因。

种群：所有的染色体集合称为一个种群，可以模拟生物进化进行遗传操作。

选择：通过一定的规则来选取染色体需要操作的位置，包括交叉和变异。

交叉：两个染色体交换部分基因。

变异：对染色体中某一位基因做特定操作。

适应度：生成的子代染色体对环境的适应程度。

2.2 最短路径遗传算法的实现

染色体的编码：对于一个给定的图如图1，因为是由11个节点组成的图，所以一个染色体由11个基因组成，每个基因上包含节点序号，和节点是否选中信息，将每个基因随机排列后组成一个码串[1]，这个码串就是一个染色体，如图2，是从1节点到11节点最短路径的染色体，其中灰色代表该节点未被选中，白色代表该节点被选中，该染色体代表的路径为1-5-10-6-8-11。

交叉操作：交叉的方法略有不同，主要目的是交换两条染色体的部分基因，产生具有新的个体。交叉时，随机产生两个数字m，n（假设m≤n），然后令染色体X的m至n基因座上的基因保持不动，其他位置的数字清空；从Y染色体的基因中从左至右选取与X染色体中m至n基因座上基因不同的基因，从左至右填入X染色体中，形成新的染色体X。同理可以得到新染色体Y [1-3]。图3为交叉过程图，其中m=3，n=5。

变异操作：将染色体上的某一位基因反转。图4为一染色体第8位基因变异前后基因排列圖。

3 算法的改进

3.1 借鉴“交叉”思想的“变异”

经典遗传算法经常会出现局部收敛现象，特别是适应度还没达到最大时，种群中的局部收敛的个体已经据非常多的数量，并会在选择操作时被大量选中遗传到下一代中去。同时，交叉过程也会出现大量相同个体相交叉，相同染色体交叉是不会产生新种类的个体的。同时，由于交叉操作互换的基因都是左右排列顺序未改变的，所以即便一条局部收敛值的染色体和另一条其他染色体交叉，产生的新个体也接近局部收敛的染色体，所以新生成的种群中这种局部收敛的染色体值越来越多，最后甚至占据整个种群，达到一个局部最优。

为了消除这种局部最优的出现，本文借助交叉的思想，在每次染色体交叉后，再对每条染色在一定概率下随机做两个基因的交换，这样就避免了相同染色体在交叉过程中很难改变的基因间的左右顺序，消除这种局部最优的产生。以下简称“交变”操作。图5为交变操作前后转基因排列图，对第4位与第6位基因交换位置。

3.2 基于阈值比较的收敛判断

遗传算法进行运算时，无法事先预测种群何时收敛，迭代数设的过小，很可能找不到最优解；迭代数设置的过大，时间消耗大，效降低。

本文提出了一种基于阈值比较来判断种群收敛的方法，将上一代中的最优个体lastbest与本代中最优个体currentbest做对比，如果lastbest优于currentbest，则说明本代最优解比上一代差，种群衰退，还需进化，将变量Flag清零；如果lastbest次于currentbest，说明种群还在进化中，变量Flag加1；如果lastbest等于currentbest，Flag保持不变。最后，如若Flag超过设定阈值Threshod，说明已经连续Threshod次的最优解是同一值，此时认为种群已经最优。伪代码如下：

上述方法虽然可能会出现局部最优解，但是在不采用阈值比较时也可能存在局部最优。因此，阈值的设定要根据算法能够容忍的最大迭代次N来设定，经过实验发现一般设为N/3比较合适。这样得到得解，即便是局部最优，也已经非常接近N次迭代得到的解，同时也保证了算法一直不收敛时可以完成N次的迭代，求出最后解。本文设计要求结合3.1中的改进方法使用，相互弥补，会达到更好的效果。

4 C程序仿真结果

4.1 仿真参数

利用程序对Map10和图Map11处理，其中Map10是含有10个节点的图，Map11是含有11个节点的图，基中矩阵4.1是第2节中图1的无向图。

4.2 借鉴“交叉”思想的“变异”方法测试

（1） 验证交变思想

图6和7分别为经典遗传算法对Map10和Map11求解最短路径输出文件记录截图。

x通过程序输出文件里的记录可以看出，当用经典遗传算法求Map10和Map11最短路径时，Map10可以找出最优解，而Map11找到了局部最优解，不过结果已经非常接近最优解。而通过观察各代的平均值可以看出平均值大致相等，说明整个种群已经达到一个局部稳定相似，通过普通交叉很难再形成更优的新物种，需要人为对其基因进行小幅度调整。endprint

图8和图9为引进“交叉”思想的“变异”方法后，再对Map10和Map11求最短路径的结果。

通过结果数据可以看出，通过引进这种类似于“交叉”思想的“变异”后，算法对两个图都找到了最优解。下面研究Pe选取不同值时对结果是否存在影响。

表1和表2分别为对Map10和Map11在Pe取值为0到1时第一次找到最优解的迭代次数记录，其中X表示未找到最优解，即产生了局部最优解。可以发现，除了Map11中Pe=0（即不引入交变操作）和Pe=0.1时未能找到最优解，其他测试情况均找到最优解。而Pe=0.1时经典遗传算法同样未找到最优解，说明引入交变思想不会阻碍找到最优解。

将表1，表2中数据绘制成如图10、图11的曲线图，可以直观的看出，Pe值的大小会对算法的收敛速度造成影响。在Pe值为0.2-0.3与0.6-0.8间，初次找到最优解的迭代次数最小。造成这种双凹陷的原因是当Pe值过小时，交变操作对算法的影响太小，算法基本上靠经典遗传算法来对结果进行控制；当Pe值过大时，对算法的影响又太大，打乱了种群中大部分染色体基因顺序，使收敛减缓。因此，选取合适的Pe值也会使算法更优，仿真里选取Pe=0.3。

4.3 改进点2判断收敛方法测试

图6、图7、图8和图9都是没有判断种群是何时收敛的，都是完成最大迭代次数（本实现中为200）后才输出结果。而对图8和图9输出记录文件查找发现，对于Map10和Map11分别在第8次和第18次迭代中就已经找出最优解，如图10和图11所示，其它180多次的迭代浪費了大量时间。

图12和图13是通过阈值比较法判断种群是否收敛后的结果，可以看出，算法分别在40次和50次迭代后找出最优解，避免了不必要的迭代。

5 结束语

通过前面仿真结果已经可以看出，改进的遗传算法在求最短路径的问题中取得了不错的效果，并且效率也有所提升。同时这种改进方法思想也适用于其他应用；另一方面，改进的遗传算法也不能完全抑制局部最优，要对各参数进行测试选取。总体来说，这种改进的遗传算法达到了预定的效果。下一步将继续完善算法，并在其他问题中测试。

参考文献：

[1] 康晓军，王茂才.基于遗传算法的最短路径问题求解[J].计算机工程与应用， 2008，44（23）：23.

[2] 张勇.实数遗传算法的改进研究[D].东北农业大学， 2014：13-14.

[3] 张书源，郭聪.基于遗传算法的最短路径问题及其MATLAB实现[J].交通世界（运输车辆），2009（6）：104-105

[4] 边霞，米良.遗传算法理论及其应用研究进展[J].计算机应用研究， 2010，27（7）：2427.

[5] 汪定伟，王俊伟，王洪峰.智能优化方法[M].高等教育出版社，2007：279-306.

[6] 徐综本.计算智能——模拟进化计算[M].北京：高等教育出版社，2005：1-101.

[7] 陈国良，王熙法，庄镇泉，等.遗传算法及其应用[M].北京：人民邮电出版社，2003：1-162.

[8] 贺毅朝，宋建民，张敬敏，等.遗传算法求解静态与动态背包问题的研究[J].计算机应用研究， 2014（32）.endprint