蚁群遗传混合算法在求解旅行商问题上的应用

卓雪雪 苑红星 朱苍璐 钱鹏

摘要：针对在求解旅行商问题时，蚁群算法易陷入局部最优，而遗传算法收敛速度慢等问题，将蚁群与遗传算法相结合：把蚁群算法每次迭代的结果作为遗传算法的初始种群，并且用遗传算法寻优结果更新蚁群算法的信息素。在用遗传算法处理问题的阶段，引入了两种新的交叉算子，并且提出混合交叉算子的新思想，算法的后期使用贪心搜索和2-opt局部优化算法，成功的避免了算法过早陷入局部最优解的问题，加快了算法的收敛速度。通过仿真，本算法与其他算法进行对比，寻优路径长度明显降低，在求解效率和求解质量上都有更好的效果。

Abstract： In solving the traveling salesman problem， ant colony algorithm is easy to fall into local optimum， and  genetic algorithm converges slowly. To overcome the problem， the Ant Colony Algorithm and the Genetic Algorithm were combined which uses the results of each iteration of the ant colony algorithm as the initial population of the genetic algorithms， and the pheromone of ant colony algorithm is updated by the optimization result of genetic algorithm. In the process of genetic algorithm， two new crossover operators were introduced and a new hybrid crossover operator scheme was proposed. To avoid the proposed algorithm falling into the local optimal solution and accelerate the convergence speed， the greedy search algorithm and the 2-opt local optimization algorithm are adopted in proposed hybrid algorithm. The simulation results show that the route path length is significantly reduced， and the proposed algorithm is more effective， compared with others algorithms.

關键词：蚁群算法;遗传算法;混合算法;TSP问题

Key words： ant colony algorithm;genetic algorithm;hybrid algorithm;TSP problem

中图分类号：TP301.6                                     文献标识码：A                                  文章编号：1006-4311（2020）02-0188-06

0  引言

最近几年，各类启发式智能优化算法在生产过程、车辆管理、数据挖掘乃至路径寻优等领域得到深入的研究与广泛的应用。蚁群算法[1-2]和遗传算法作为各类智能优化算法中的佼佼者，各具特色。蚁群算法（Ant Colony Algorithm，ACO）是模拟大自然中真实蚂蚁在寻找食物时群体间的相互协作行为，通过群体行为寻求最优结果。遗传算法（Genetic Algorithm，GA）是模拟生物进化论的自然选择和遗传学的生物进化过程，通过自然选择、优胜劣汰、适者生存的遗传机制来寻求最优结果。使用智能优化算法可以解决路径寻优领域中的一个经典问题——旅行商问题。

1  旅行商问题

旅行商问题（Traveling Saleman Problem，TSP）是一个典型的NP完全问题。求一条使得旅行商的行程最短的路径，可用以下数学模型表示：

若路径，满足函数f（L）的值最小，则路径L就是所求的最优路径。函数f（L）如下：

其中，ci为城市号，i=（1，2，…，n-1），c（i，j），j=（1，2，3，…，n），表示城市ci到城市cj的距离。若d（ci，cj）=d（cj，ci），则称为对称TSP问题[3]。

“旅行商问题”的应用非常广泛，如：在互联网环境中，如何更好地设置节点，以让信息更好地流动;在道路交通中，如何更合理更高效的规划道路，以减少拥堵;在物流运输中，如何更好地规划物流，以减少运营成本等。

鉴于TSP问题如此广泛的应用，近几年，很多学者进行了深入的研究。其中Abdulah Fajar在2009年使用聚类策略（Clustering Strategy）[4];M. A. H. Akhand在2013年使用速度试探粒子群算法（Velocity Tentative Particle Swarm Optimization）[5];Yingying Yu在2011年使用改进的遗传算法（Genetic Algorithm）[6];M. D. Arango and C. A. Serna 在2015年使用文化基因算法（Memetic Algorithm）[7];Yongsheng Pan在2014年使用分解交叉路径（Dismantling Cross Paths）[8]的方法;Haisheng Qin于2015年采用基于动态局部搜索（Dynamic Local Search）的蚁群算法[9];Vaisakh Shaj于2016年采用基于重组运算符（Recombination Operator）的边缘粒子群优化算法[10]来求解TSP问题。这些算法在收敛速度或全局搜索能力等方面仍有许多值得完善的地方。

针对其他学者研究中的不足，本文提出了一种新的蚁群遗传混合算法来求解旅行商问题。通过与其他算法的对比分析，本文提出的改进型蚁群遗传混合算法具有收敛速度快，搜索全局最优解能力强的优点。

2  蚁群遗传混合算法求解TSP

蚁群遗传混合算法（Ant Colony Genetic Hybrid Algorithm，ACGHA）将蚁群算法求得的结果作为遗传算法的初始种群，用遗传算法寻优结果更新蚁群算法的信息素。与单一的遗传算法和蚁群算法相比，该算法减少了遗传算法的寻优次数，加快了遗传算法的收敛速度，提高了蚁群算法的正反馈性和全局搜索能力，从整体上提高了算法的执行效率。改进的蚁群遗传混合算法求解TSP问题的流程图如图1所示。

具体步骤如下：

2.1 初始化

初始化信息素启发式因子α，期望值启发式因子β，信息素挥发系数ρ，信息素强度Q，每两个城市之间的距离d、信息素τ、启发式信息η，交叉率pc，变异率pm。

2.2 循环迭代

step1初始化禁忌表为空

step2将m只蚂蚁随机地分配在n个城市中

step3 確定状态转移方向

在每次迭代中，采用禁忌表来记录每只蚂蚁k（k=1，2，…，m）当前走过的城市。蚂蚁k根据各路径上的信息量和路径启发信息来计算状态转移概率，再根据状态转移概率和禁忌表来确定状态转移方向。依次执行m次，最终可求出m只蚂蚁一次遍历后的m条完整路径。

蚂蚁k在t时刻由城市i转移到城市j的状态转移概率p（t）为：

公式中，allowedk用以表示蚂蚁k在下一时刻允许选择的下一个城市。τij（t）表示t时刻，路径（i，j）上的信息素强度，并且路径上的信息素浓度越大，此路径被蚂蚁选择的概率也越大。ηij（t）表示启发式信息，反映蚂蚁对下一个城市的能见度，通常取值为1/dij，dij表示路径（i，j）之间的距离。α为信息素启发式因子，β为期望值启发式因子，这两个因子皆是预先设置的参数，用来控制启发式信息与信息素浓度作用的权重关系。

step4编码生成遗传算法的初始种群

在遗传算法的设计中，编码影响着整个算法的执行效率，因此它成为遗传算法要解决的首要问题。在TSP中，将城市按照被拜访的顺序组成编码。确定编码方式后，把蚁群算法中每只蚂蚁一次遍历后的完整路径作为遗传算法的初始种群（population）。

step5计算适应度

适应度（fitness）由适应度函数计算而来。适应度函数（fitness function）是问题中的全体对象与其适应度之间的一种对应关系。在TSP中，要寻找使目标函数f （L）取最小值时的个体。因此适应度函数选取目标函数的倒数，即f （k）=1/f （Lk）。可见，路径越短适应度越大。

step6执行选择算子

首先按照适应度由大到小的顺序对种群中的个体进行排序，然后通过选择算子对种群中的个体进行选择，最后得到遗传的父体。

在TSP中，按照1：1的比例，采用最优个体保存策略[11]和轮盘赌方法对种群中的个体进行选择。即首先适应度排序在前50%的个体一定被保存，然后对剩下50%的个体，计算每个个体适应度在整个种群适应度中被选择的概率和累计概率，最后通过随机数random （0

step7执行交叉算子

遗传算法中起核心作用的是交叉算子（crossover）。在TSP中，对种群中的个体，按照交叉概率pc进行交叉操作，产生下一代种群。本文引入两种新的交叉算子，并提出混合交叉算子的思想，分别叙述如下：

a）交叉算子1[6]

生成子路径L1的过程：

首先，从种群population中随机确定两个个体p、q作为子代路径的父体，随机确定一个交叉城市randcity作为子代路径的起点城市。

其次，计算父体p、q路径中城市randcity与下一个城市cp1、cq1的距离，记作dp1和dq1，接着分别计算城市cp1、cq1与城市cp1、cq1之后的城市cp2、cq2之间的距离，记作dp2和dq2，若dp1+r*dp2？燮dq2+r*dq2（0

最后，重复上面的步骤，直到父体中仅剩一个城市为止，直接加入路径L1。

生成子路径L2的过程与生成子路径L1的过程大致相同，不同之处是分别计算父体p、q路径中城市randcity与上一个城市和上上一个城市之间的距离之和在做比较，这里不再赘述。

按照上述方法选择不同的父体得出更多的子路径，然后把这些子路径组合在一起形成新种群newpopulation。在生成新种群的过程中需要注意的是：按照不同的方向分别生成两个子路径之后，在生成下一个路径的过程中所选择的父体不允许重复。

相比于其他交叉算子，该交叉算子使算法的收敛速度明显加快，且易于求出问题空间的最优解;但是，该交叉算子的时间复杂度稍微偏高，而且不利于开拓新路径，因此本文引入了交叉算子2[11]。

b）交叉算子2

首先，根据TSP中城市的数量，定义4个互不相同的随机数字作为交叉城市的城市编号。

其次，从种群population中随机确定两个个体p、q作为子代路径的父体。

最后，分别确定4个交叉城市所在父体染色体上的基因位置。保持父体染色体交叉点上的基因不变，其他基因按顺序兑换位置。这样就产生子代种群中的两个个体。

例如，两个父体分别如下（标有下划线加粗的数字代表交叉城市的城市编号）：

05 07 04 11 02 10 03 09 06 01 08

10 03 05 09 04 06 08 02 11 01 07

父体染色体交叉点上的基因不变，其他基因按顺序兑换位置后，产生的子代种群中的两个个体如下：

03 05 04 06 08 10 02 09 11 01 07

10 05 07 09 04 11 02 03 06 01 08

按照上面的三个步骤可以确定构成子代新种群newpopulation所需要的m个个体。同样地，在生成子代种群的过程中所选择的父体不允许重复。

相比于交叉算子1，该交叉算子有利于开拓新路径和搜索全局最优解，且该算子的时间复杂度较低，但算法的收敛速度相对较慢。

鉴于交叉算子1和交叉算子2的优缺点，根据实际问题的需要，本文提出混合交叉算子的新思想，使交叉算子1和2按比例进行交叉运算，使其优劣互补，有效的提高了整个算法的收敛速度和求解全局最优解的能力。

step8执行变异算子

变异（mutation）亦称为突变，就是改变染色体某个（些）位上的基因。主要的变异技术有逆转变异、位点变异、插入变异、对换变异等。本文在求解TSP中采用的变异方式为对换变异，即将随机选取的若干基因按照变异概率pm互换。

step9执行贪心搜索

为防止遗传算法过早陷入局部最优解，本文提出一种贪心搜索算法[12]，并按照一定的概率进行贪心搜索。首先，从种群中随机地选取一个个体p中的城市c作为旅行商当前所在的城市，并加入到新个体中;其次，搜索个体p中所有未加入到新个体中的城市，找到距离当前城市c最近的城市d，将d添加至新个体中并作为旅行商当前所在的城市;最后，按照这种方法，继续搜索个体p中所有未加入到新个体中的下一个城市，直到所有城市都加入到新个体中，这样便得到优化后的个体。

step10使用2-opt局部优化

2-opt局部优化[7]是防止遗传算法过早陷入局部最优的另一有效方法。本文按照一定的概率进行2-opt局部优化。该算法的思想是以边为基础，首先，从解当中任意拿出两条边，此时会将解拆成两个部分，如图2（a）中去掉边s23和s45，将其中一部分的路径反接回另一路径，如图2（b）所示;

其次，比较新路径与原路径的长度，把路径相对较短的解保留下来;最后，针对不同的边重复进行以上的步骤，便可得到局部优化的解。

step11更新信息素

随着时间的推移，信息素不仅会慢慢的积累，也会渐渐的挥发。为了避免一条路径被蚂蚁反复走过之后信息素无限的积累，导致残留信息素淹没启发信息，因此在遍历完n个城市一次之后，需要对信息素进行更新。t+1时刻路径（i，j）上的信息素按以下公式进行更新：

公式中，m是蚂蚁个数，ρ是信息素的挥发率（0<ρ<1），1-ρ代表信息素残留因子，Δτ（t）代表第k只蚂蚁在本次迭代中（t时刻）经过路径（i，j）后，对路径（i，j）上的信息素产生的增量。Lk代表第k只蚂蚁在本次迭代中所走过的路径长度，Q表示蚂蚁循环一周所释放的总信息量。

step12算法终止条件判断

若nc？燮maxNc且gene？燮maxGene，转到step5，若nc？燮maxNc且gene>maxGene，轉到step1，若nc>maxNc或遗传算法得出的结果满足本文要求的最优解，转到2.3。

2.3 输出结果

根据上述步骤得出的结果，输出最优路径。

3  仿真实验

基于上文提到的算法，采用C++语言编写程序进行仿真对比实验。实验环境为： Windows7系统，2G内存，Intel（R） Core（TM）2 Quad 2.50GHz CPU，Microsoft Visual Studio 2010平台。实验参数设置如下：种群规模m=20，α=2，β=3，ρ=0.7，Q=100，pc=0.7，pm=0.095，遗传算法最大进化代数maxGene=20，程序最大迭代次数maxNc=200。

①为说明本文算法在寻优结果上取得的良好效果，分别选用国际标准TSPLIB测试库[13]中的eil76、st70、eil51、c50、att48等实例进行模拟。算法连续运行10次，得到的实验数据对比如表1所示。

对比其他学者在TSP问题上的研究成果，可以得出，本文算法在寻优结果上有了很大的提升。其中，各实例寻优结果最短路径分别如图3至图11所示。

②本文提出的算法具有较快的收敛速度，以eil51实例为例。图12表示初始种群中的路径，Route Length=1493.44;图13表示第1次迭代后的最优路径，Route Length=492.993;图14表示最后1次迭代后的最优路径，Route Length=428.982。图15是eil51实例中，算法收敛过程迭代图。

由图12至图15可知，经过第1次迭代后便可从初始种群的Route Length=1493.44搜索到Route Length=492.993的良好路径;迭代不足200次即可搜索出Route Length=428.982的最好路径。结合算法收敛过程迭代图，可知本文算法不仅在寻优结果上有了很大的提升，而且具有较好的全局搜索能力和较快的收敛速度。

4  结论

本文提出的蚁群遗传混合算法将蚁群算法求得的结果作为遗传算法的初始种群，使人工智能蚁群的搜索代替传统遗传算法中随机的编码。用遗传算法寻优结果更新蚁群算法的信息素，使蚁群算法信息素的更新更具高效性，提高了算法的正反馈性。引入启发式混合交叉算子有效地提高了算法的收敛速度，算法的后期使用贪心搜索策略和2-opt局部优化算法有效的防止了解集陷入局部最优，从而提高了算法的全局搜索能力。仿真结果表明，改进的算法在解决TSP问题上具有较好的寻优能力。

參考文献：

[1]Maniezzo D， Dorigo M， Maniezzo V， et al. Ant System： An Autocatalytic Optimizing Process[J]. Clustering， 1991， 3（12）：340.

[2]Dorigo M， Maniezzo V， Colorni A. The Ant System： Optimization by a colony of cooperating agents[C]// IEEE Transactions on Systems， Man， and Cybernetics. 1996：29-41.

[3]Niendorf M， Kabamba P T， Girard A R. Stability of Solutions to Classes of Traveling Salesman Problems.[J]. Cybernetics IEEE Transactions on， 2015：1.

[4]Fajar A， Abu N A， Herman N S. Initial Result of Clustering Strategy to Euclidean TSP[C]// Soft Computing and Pattern Recognition， 2009. SOCPAR '09. International Conference of. 2009：13-18.

[5]Akhand M A H， Akter S， Rashid M A. Velocity Tentative Particle Swarm Optimization to solve TSP[C]// International Conference on Electrical Information and Communication Technology. 2014：1-6.

[6]Yu Y， Chen Y， Li T. A New Design of Genetic Algorithm for Solving TSP[C]// International Joint Conference on Computational Sciences & Optimization. IEEE Computer Society， 2011：309-313.

[7]Arango Serna M D， Serna Uran C A. A Memetic Algorithm for the Traveling Salesman Problem[J]. IEEE Latin America Transactions， 2015， 13（8）：2674-2679.

[8]Pan Y， Xia Y. Solving TSP by dismantling cross paths[C]// IEEE International Conference on Orange Technologies. IEEE， 2014.

[9]Qin H， Zhou S， Huo L， et al. A New Ant Colony Algorithm Based on Dynamic Local Search for TSP[C]// Fifth International Conference on Communication Systems and Network Technologies. IEEE， 2015：913-917.

[10]Vaisakh Shaj， P M Akhil， S. Asharaf. Edge-PSO：A Recombination Operator Based PSO Algorithm for Solving TSP[C]// 2016 International Conference on Advances in Computing， Communications and Informatics （ICACCI）. IEEE， 2016：35-41.

[11]Huang S C， Jiau M K， Lin C H. Optimization of the Carpool Service Problem via a Fuzzy-Controlled Genetic Algorithm[J]. IEEE Transactions on Fuzzy Systems， 2015， 23（5）：1698-1712.

[12]Lin S， Rong Y， Sun X， et al. Learning capability of relaxed greedy algorithms.[J]. IEEE Transactions on Neural Networks & Learning Systems， 2013， 24（10）：1598-1608.

[13]TSPLIB.http：//www.iwr.uni-heidelberg.de/groups/comopt/software/ TSPLIB95/. April， 2006.

[14]Hua Z， Chen J， Xie Y. Brain Storm Optimization with Discrete Particle Swarm Optimization for TSP[C]// International Conference on Computational Intelligence and Security. IEEE Computer Society， 2016：190-193.

[15]Pan Y， Xia Y. Solving TSP by dismantling cross paths[C]// IEEE International Conference on Orange Technologies. IEEE， 2014：121-124.

[16]Safae Bouzbita， Abdellatif El Afia， Rdouan Faizi， Mustapha Zbakh. Dynamic adaptation of the ACS-TSP local pheromone decay parameter based on the Hidden Markov Model[C]//2016 2nd International Conference on Cloud Computing Technologies and Applications （CloudTech）.IEEE， 2016：344-349.