一种求解TSP问题的协同进化算法

魏士伟

摘 要：传统的遗传算法GA在求解TSP问题时容易出现早熟和陷入局部最优等现象。为此本文提出了一种基于协同进化的遗传算法（CEGA）用于解决GA算法的缺陷。该算法通过定义个体的适应度值和个体间的差异度值，将适应度值高和差异度大的个体分别放入2个不同的子群体。在进化过程中这2个子种群相互协同进化，既保证了种群向最优解的方向移动，又保持了种群的多样性。实验结果表明，本文所提出的算法在解决TSP问题时，具有收敛速度快、容易跳出局部最优等特点，相较其他GA算法具有更好的性能。

关键词： 遗传算法;进化算法;TSP;协同进化;资源调度

【Abstract】 The traditional Genetic Algorithm （GA） is more prone to be of premature convergence and fall into local optimums when solving TSP problems. In order to overcome these defects， a new Co-Evolution based Genetic Algorithm （CEGA） is proposed is this paper. By defining the fitness value of individuals and the difference value between individuals， this new algorithm puts individuals with high fitness values into a sub-population and put individuals with large differences into another sub-population. These two sub-populations coevolves with each other during the evolution process， which not only ensures the movement of the whole population towards the optimal value， but also maintains the diversity of the population. The experimental results show that the algorithm proposed in this paper has characteristics of fast convergence and being easy to jump out of local optimums when solving TSP problems. The research demonstrates that the proposed algorithm has better performance than other GA algorithms.

【Key words】  Genetic Algorithm; evolutionary algorithm; TSP; Co-Evolution; resource scheduling

1 概述

旅行商問题（Traveling Salesman Problem，TSP）是图论中一个著名的组合优化问题。现实世界很多行业中的优化问题，如快递配送线路安排、飞机航线安排、应急灾害调度、车辆路径规划、印制电路的制作、卫星位置的调整、人类基因排序、晶体结构分析和数据串聚类等[1-3]，都可以归纳为TSP问题。因此，研究求解TSP问题的高效算法具有十分重要的意义。

求解TSP问题的传统算法通常有穷举法[4]、分支限界法[5]和动态规划法[6]等。然而，TSP已被证明是一个NP完全问题，随着问题规模的扩大，所需的计算时间呈指数级增加，依靠这些传统算法求解TSP问题已经变得不可能。针对大规模TSP问题，一些进化算法显示出其独特的优越性。例如，蚁群算法[7-8]、模拟退火算法[9]、启发搜索式算法[10]、遗传算法 （GA）以及一些混合智能算法[11-14]等。 特别是遗传算法，模拟了生物进化论的自然选择的机理和遗传学的生物进化过程，能够使生物群体不断地向好的方向进化，从而搜索到最优解。由于具有良好的全局最优解搜索能力、隐含的并行计算能力和灵活的应用方式，在解决大规模复杂问题时遗传算法（GA）已经成为近期吸引学界高度关注的进化算法。例如，陈林等人[11]利用贪婪思想产生初始种群，通过改进的遗传算法来加快寻优速度，从而优化遗产算法的质量和寻优效率。姜群等人[12]通过动态调整种群的交叉和变异概率控制了进化过程，以便使遗传算法获得更好的性能。孙文彬等人[13]针对遗传算法求得的解质量不高等缺陷，设计了一种基于遗传算法的多策略优化求解方法来处理TSP问题，并取得了良好效果。张玉州等人[14]通过组合局部搜索算子集合并将其嵌入遗传算法，从而形成混合遗传算法来求解TSP问题。

这些改进的遗传算法在研究TSP问题时，一定程度上都表现出良好的性能。然而，随着问题规模的进一步扩大，遗传算法依然会出现早熟收敛、容易陷入局部最优等问题。为此，本文提出一种基于协同进化的遗传算法，来改善算法易于早熟收敛的缺陷，强化搜索全局最优解的能力。实验结果表明新提出的算法在解决TSP问题时具备良好的性能。

2 TSP问题描述及求解模型

具体的个体选择策略为，将群体分为2个子群体subpopA和subpopB，各子群体中的个体数量各占群体总数的1/2。接着即需确定subpopA中的个体，可使用轮盘赌的方式将适应度值高的个体选择进来，待subpopA一旦确定后，就可以根据subpopA中的每个个体从种群中查找出和其差异度最高的个体而组成subpopB， 从而完成个体的选择。

3.3 协同进化技术

选择出来的个体分别组成了2个子群体subpopA和subpopB，通过各个子群体的内部的交叉变异操作可以生成下一代新的种群个体。同时，子种群subpopA和subpopB之间也可以通过相互的交叉和变异操作，即通过协同进化的方式产生下一代种群新个体，对此进化方法可详述如下。

（1）子种群subpopA和子种群subpopB各自的独立进化。对于每个子群体，分别以随机的方式从子种群中选择1/3popsize个个体，其后以概率Pc进行两两交叉操作，接着又以概率Pm进行变异操作从而生成新的个体，再将其放入下一代群体中。

（2）子种群subpopA和子种群subpopB的协同进化。从subpopA子种群中随机选择1/6popsize个个体，从subpopB中选择同样数目的个体，并以概率1进行交叉操作，后续则以概率Pm进行变异操作从而生成新的个体，再将其放入到下一代群体中。

采用这种协同进化技术可以让个体在向最优解靠近的同时，还能保持种群的多样性，防止种群随着进化代数的增加过早出现早熟现象，并且各个子种群之间通过相互交叉变异更有可能产生出更优的解，从而找到最优解。下一节将给出协同进化算法的详细描述。

3.4 协同进化算法的详细描述

综合前述研究后可得，多精英协同进化遗传算法MECGA的基本思想如算法1所示。

算法1 协同进化算法

Step 1 令进化代数t=0，设置的种群大小popsize、交叉概率Pc、变异概率Pm的初始值， 并进行种群初始化操作生成初始化种群POP（t）;

Step 2 对POP（t）中的个体根据式（8）计算适应度值， 以轮盘赌的方式从中选择1/2popsize个个体组成子群体subpopA;

Step 3 对subpopA中的每个个体，根据公式（9）找出POP（t）中与之差异度最大的个体并将其放置于subpopB中。

Step 4 从subpopA中随机选择1/3popsize个体，并以概率Pc进行交叉操作，生成的新个体再以Pm概率进行变异操作，然后将其插入到下一代种群POP（t+1）中;

Step 5 从subpopB中随机选择1/3popsize个体，并以概率Pc进行交叉操作，生成的新个体再以Pm概率进行变异操作，然后将其放入种群POP（t+1）中;

Step 6 从subpopA中随机选择1/6popsize个体，并让其与从subpopB中选择出的相同数目的个体进行交叉操作，新生成的个体将以概率Pm进行变异操作，再将其放置于下一代群体POP（t+1）中。

Step 7 判断群体POP（t）中最优个体的适应度值是否大于下一代群体POP（t+1）中最优个体的适应度值（精英保留策略），若不大于，则将其放置于POP（t+1）。

Step 8 令t=t+1。

Step 9 判断是否满足终止条件，若是，则结束;否则，转到 Step 2。

4 实验与结果分析

为了验证协同进化算法在解决TSP问题时的良好性能，研究将其与传统的GA算法、带有精英保留策略的遗传算法GAE做了实验对比和分析。本研究中，进行实验验证和分析时的部分参数取值详见表1。

实验在标准的测试集TSPLIB数据库（http：//elib.zib.de/pub/mp-testdata/tsp/tsplib/tsp/index.html）中选择了6个数据集进行测试。针对文中选定的3种对比算法运算求得的最短哈曼顿路径的实验结果见表2。

從表2中可以看出，GA和GAE算法求得的最短路径的长度值相差不多，而且受到所处理问题规模的限制，这2种算法都容易陷入局部最优解而缺乏跳出局部机制能力，由其求得的结果并不理想。 而CEGA算法由于设计了精英种群和普通协同进化的思想，既可以保持向最优解不断靠近的压力，又保持了种群的多样性，具备跳出局部最优的能力，所求解的质量要好很多。在此基础上研究又发现，对于所有的测试案例，CEGA算法的结果总是好于GA算法和GAE算法的结果。特别是att48.tsp测试数据集，CEGA算法求得的最短路径长度只有GA算法和GAE算法的50%左右。

为了进一步验证本文所提出的算法的寻找最优解的性能，分别在att48.tsp和berlin52.tsp数据集上对比分析3种对比算法的进化过程。如图1和图2所示。

从图1、图2中可以看出，随着进化代数的推进，GA和CGA算法在进化的前期都能引导种群不断向最优解的方向移动，所求的最小值也在不断下降，但是在进化的后期（种群大概进化到60代以后），这种下降的趋势越来越不明显，几乎丧失了进一步寻优的能力。而CEGA算法却表现出较好的进化态势，群体寻找到的最优值随着进化代数的逐渐演进而不断向最优解靠近，即使到进化的后期，这种趋势也十分明显。分析可知，这一结果即得益于CEGA算法的良好设计，由于将群体分为2个子种群，一个子种群中的个体具有较高的适应度值，而另一个子种群具有较高的差异度值，这些子种群之间又相互协同进化，使得种群既有向最优解前进的驱动力，又能够保持种群的多样性，从而使群体具备了跳出局部最优解的能力。 至此，图1、图2中的结果可以看出，无论是最终求得的解的质量，还是求解过程中的进化趋势，CEGA算法都优于GA和GAE算法。

此外，关于本文提出算法CEGA在att48.tsp数据集和berlin52.tsp数据集上求得的旅行线路图，即哈曼顿路径，见图3和图4。

5 结束语

传统遗传算法在解决TSP这一NPC问题时容易出现早熟和陷入局部最优等问题。为此，本文提出了一种基于种群协同进化的遗传算法CEGA。该算法将种群中的个体依据适应度值和定义的差异度值分到了2个子种群中，一个子种群中的个体具有较高的适应度值，而另一个子种群中的个体具有较大的差异度值。在进化过程中，这2个子种群相互协作，共同进化，使种群既能够向靠近最优解的方向移动，又能保持种群的多样性。算法具有了易于跳出局部最优解的能力。为了验证所提出的算法的性能，研究则在TSPLIB数据库中的测试集上进行了多组实验。实验结果表明，CEGA算法在解决TSP问题时，其所求得的解的质量总是好于GA算法和GAE算法，而且在跳出局部最优解的能力方面有着良好表现，算法的稳定性也更高。

参考文献

[1]申艳光， 张玲玉， 刘永红. 基于混合遗传算法的物流路径优化方法研究[J].计算机技术与发展， 2018， 28（3） ：192-196.

[2]吴新胜， 姜婷， 赵梦超， 等. 基于群智能混合算法的应急物流路径优化研究[J]. 四川理工学院学报（自然科学版）， 2018， 31 （4） ：68-73.

[3]唐健， 史文中， 孟令奎. 基于遗传算法的时相关动态车辆路径规划模型[J]. 武汉大学学报（信息科学版）， 2008， 33 （8） ：875-879.

[4]许玲. 优化穷举法求旅行商问题的近似最优解[J]. 微型机与应用， 1998（10）：20，33.

[5]陈涛， 张思发. 分支限界法求解实际TSP问题[J]. 计算机工程与设计， 2009， 30（10）：2431-2434.

[6]来学伟. 动态规划法在TSP问题中的应用[J]. 吉林化工学院学报， 2017， 34（3）：65-67.

[7]王宝生， 屈宝存. 蚁群算法在求解TSP问题中的改进研究[J]. 电子设计工程， 2014，22（22）：14-18，21.

[8]康岚兰， 李康顺. 蚁群算法在求解TSP问题上与遗传算法的对比研究[J]. 计算机系统应用， 2008， 17（10）：60-63.

[9]周君， 贾昆霖. 求解旅行商路径规划问题的改进模拟退火算法[J]. 电子科技， 2017， 30（7）：62-64，68.

[10]邓志刚， 何琦， 肖媛娥， 等. 一种基于TSP问题的启发式搜索算法研究[J]. 科技广场， 2010（9）：29-31.

[11]陈林， 潘大志. 改进遗传算法解决TSP问题[J]. 智能计算机与应用， 2016， 6（5）：17-19，23.

[12]姜群， 晏雨. 改進的遗传算法在TSP问题中的应用[J]. 重庆理工大学学报（自然科学）， 2012，26（9）：96-99.

[13]孙文彬， 王江. 一种基于遗传算法的TSP问题多策略优化求解方法[J]. 地理与地理信息科学， 2016， 32（4）：1-4.

[14]张玉州， 梅俊， 徐廷政. 一种求解TSP问题的混合遗传算法[J]. 安庆师范大学学报（自然科学版）， 2018，24（3）：77-81.