混合遗传算法解决单目标旅行商问题的研究

袁成林

（1.广西大学计算机与电子信息学院，广西 南宁 530004；2.广西医科大学基础医学院，广西 南宁530021）

遗传算法是一种基于进化策略的优化算法[1]，被广泛使用在组合优化问题中。但是遗传算法在解决问题的时候也有诸多不足，首先是在早期的搜索中常常丢失种群的多样性[2]。在单目标优化中，对于种群的适应性方面的研究很多，多样性保持方面常常用的手段是小生境方法。其次由于遗传算法的局部能力差，也有学者采用其他局部搜索算法来构造混合遗传算法[3]，这些方法对在种群适应性方面是有效的，但是在种群多样性方面却不足，对于有的优化问题来说，多样性保持对搜索最优解有着重要的作用。最后在旅行商问题中普通的交叉算子会破坏要交换的基因片段，针对这个问题本文提出了对应连通子图交叉(Corresponding Connected Subgraph Crossover,CCSC)，结合LK局部搜索和小生境等操作构造一种基于CCSC的混合遗传算法(CHGA)。通过几个实例的计算和对比表明，算法的设计是有效的，求解质量也有较大提高。

1 对应连通子图交叉

交叉算子是遗传算法中最重要的部分，既可以使个体发生变化，又能保留父体的优秀基因片段，使种群向着理想的方向进化。对于旅行商问题通常采取自然编码，即每个基因位对应一个城市的号码。例如1-2-3-4-5-6表示依次经过城市1到6最后回到1。这种编码容易理解，效率高。但是在这种编码方式下普通的交叉算法就不再适用了，因为可能产生没有意义的个体。图1中两条可用路径经过交叉操作以后，产生的1-1-5-6-3-6路径是没有意义的。为了解决这个问题，很多学者提出了适用于TSP的交叉算子，像顺序插入法，启发式交叉等，但是这些算法会打乱交叉片段中的基因位置因而不能保存父体的优秀基因片段。

图1 普通交叉操作产生的不可用路径

基于以上分析，本文提出一种新的交叉算子：对应连通子图交叉(CCSC)。这种交叉方法可以做到严格的交叉，即子代的基因都是从父代继承所得，所有基因片段都可以在两个父体中找到。CCSC通过合并两条父体路径，构造连通图G。对G中的对应连通子图进行搜索，然后进行交叉，交叉策略可以是：随机选择某个或若干个对应连通子图进行交换，还可以采用贪婪选择对每个对应连通子图进行多次搜索，找到最短个体，这几种方法时间复杂度都在O(n)之内，本文权衡算法效率和求解效果，决定采用随机选择若干个对应连通子图进行交换的交叉策略。明显可以看出若对应连通子图的个数大于等于1，CCSC就可以创造两个以上的后代个体。若有k个对应连通子图，则可以产生2k+1-2个个体，减2是因为有两个个体和父体是相同的。

对应连通子图：合并两条父体路径，构造连通图G，在G中，删除两条父体路径的重合边后，得到图G1，G1的某个连通子图中的节点在两条父体中均为连续的基因片段，此连通子图称为对应连通子图。

图2-2中的a-b-c-d,a-c-b-d和g-h-j-i-k,g-i-h-j-k就是两对对应连通子图：

图2 对应连通子图示意

寻找对应连通子图的流程如下：

（1）删除图G中两条路径重合的边。

（2）建立队列Q，把度为1的n个节点放在队头，设定计数器K=n。

（3）从队列的n+1个节点开始进行广度遍历，找出所有连通子图，把遍历过的点前移，记录连通子图结点个数ti，直至所有节点操作完成。

（4）对结点个数ti大于等于3的连通子图i，对其父体进行检查如果连通子图的节点在两父体中均为连续的基因片段，则该连通子图为一个对应连通子图g，记录g。

（5）如果符合要求的连通子图都已经搜索就退出程序，否则返回步骤4。

2 混合遗传算法CHGA的实现

2.1 选择算子

选择算子是算法中关键的一环，可以选择优秀个体进入下一代进行交叉和变异操作，本文采用的是轮盘赌法，根据个体的适应度进行选择，适应度越大个体被选择的概率就越大，并且可以保留少量适应度较差的个体，增加种群多样性。

2.2 变异和交叉算子

变异：本文采用两点随机交换的变异操作对种群进行扰动，跳出某些局部最优解。

交叉：本文采用第一节提出的对应联通子图交叉作为交叉算子。

2.3 小生境操作

经过轮盘赌选择等操作后，适应度大的个体更容易进入新种群，种群里就会出现很多一样或者很相似的个体，这样就会导致算法早熟，结果陷入局部最优解，所以本文引入小生境操作来保持物种多样性。

具体方法是：假设种群共有n个个体，首先计算个体i(i=1,2…n)和其他个体之间的小生境距离L(i,j)。在对个体i与其他所有个体的小生境距离L(i,j)求和，计算出个体i的小生境排序值循环这个步骤直到计算出所有si。升序排列si后，用随机产生的个体代替si最高的n个个体，算法的时间复杂度是O(n2)。

其中L(i,j)的求法是，假设TSP共有N个城市，取个体i的第k（k=1,2,3…N）个基因位城市i(k)，在个体j中找到城市i(k)的位置t，对i(k)和j(t)左右两边城市号做同或操作∶L(i,j)=i(k+1)⊙j(t+1)+ i(k+1)⊙j(t-1)+ i(k-1)⊙j(t+1)+ i(k-1)⊙j(t-1)。因为 0≤L(i,j)≤2，所以 0≤si≤2n。小生境排序值si越大说明个体i周围的个体越多。对种群的非精英个体进行小生境操作，起到了保留精英又增加种群多样性的作用。

2.4 局部搜索

在CHGA中局部搜索算法起着十分重要的作用。它可以使种群迅速向着希望的方向进化。它的另一个作用是使 CHGA算法的第一代开始就能够找到更多的对应连通子图，提高算法的效率，本文采用LK算法[4]作为局部搜索。

在本文中局部搜索的另一个作用是使算法的第一代开始就能够找到等多的对应连通子图(CCS)，通过实验测试 CCSC结合局部搜索算法可以产生的对应连通子图的大致个数，实验采用TSPLIB中的att532,nrw1379 和 u1817三个算例，用3-OPT，3-OPT和MO-LK算法对50个随即路径进行测试，平均实验结果如表1。通过实验发现2-OPT与CCSC结合在90%的情况下可以产生可用个体，也就是至少有一对对应连通子图而，结合3-OPT和LK算法的CCSC产生可用解的概率达到了将近100%。

表1 不同局部搜索找到的对应连通子图个数

3 算例实验

3.1 实验环境

为验证所设计算法的有效性，基于如下实验环境进行相关实验：联想台式机，其配置为：

（1）CPU：AMD 64 2X 4400+；

（2）内存：2 G DDR2；

（3）操作系统：Windows XP

程序以 VC++2008编写及编译，实验使用数据取自TSPLIB。算法各参数如表1所示。实验结果均为运行算法10次后计算得到的平均值、最优值以及最差值。

3.2 实验参数

表2 混合遗传算法算法的参数设置

3.3 实验结果

本文的算例采用 TSPLIB数据库中的 Att48、Eil51、Eil76、Kroa100、 Ch130 、Tsp225、Ch 150等6个测试对象，每个算例进行20次计算，结果取平均值，并与文献[5,6]进行了对比。具体数据如下：

表3 混合遗传算法算法的计算结果

图3 算例Eil51收敛情况

实验结果表明，本文所做改进效果明显。100以内规模的问题每次都可以计算出TSPLAB最优解，而且速度上相比文献所述也有优势。100以上问题在 20次实验中可以计算出TSPLAB最优解，而且平均值的误差也在1%以内。在下一步工作中，可以着力改善算法的计算速度，并且向更大规模的问题发起挑战。

[1] Holland John H. Adaptation in natural andartificial systems: an introductory analysis with applications to biology, control, and artificial intelligence[J]. USA: University of Michigan, 1975.

[2] 马良.旅行推销员问题的算法综述[J].数学实践与认识,2000,32(2):156-165.

[3] 葛继科,丘玉辉,等.遗传算法研究综述[J],计算机应用研究,2008,25(10): 2911-2917.

[4] Helsgaun K. General k-opt submoves for the Lin–Kernighan TSP heuristic[J]. Mathematical Programming Computation, 2009,1(2-3): 119-163.

[5] 孙凯,吴红星,王浩,丁家栋.蚁群与粒子混合算法求解TSP问题[J].计算机工程与应用,2012,48(34):60-63.

[6] 李哲,夏立,庄浩俊,董红生.MMAS_EC 算法求解旅行商问题[J].计算机工程与应用,2011,47(9):41-47.