基于改进蚁群算法在TSP 问题中的应用

刘子墨

（首都经济贸易大学管理工程学院，北京 100070）

蚁群算法从大自然中诞生，是寻优问题中一种优秀的解决策略[1]。最初是由DORⅠGO 等[2]首次向世人介绍了蚁群算法。由于蚂蚁的移动是随机的，当种群规模达到一定程度时，蚁群算法需要很长时间才能找到较优的解决方案。因此，GAMBARDELLA 等[3]又对经典的AS 算法进行了改进，提出了一种更为通用的算法“Ant-Q System”。针对蚁群算法易过早停滞的缺陷，1997 年，STUTZLE 等[4]提出了MAX-MⅠN Ant System，为其中每条边可允许拥有的跟踪信息素的量设置了范围限制。而后GAMBARDELLA 等[5]提出了HAS，在HAS 的迭代中，利用蚂蚁获取的每个解，对局部进行检测，寻找局部最优，从而提升解的品质。如今，蚁群算法已频繁出现在专业学术会议上，许多关于蚁群算法的论文也被发表在Nature、Generation Computer System等专业的学术刊物上，许多计算机学者对其研究十分热切。

针对蚁群算法的缺陷，国内的研究人员也有着不同的解决策略，其中吴庆洪等[6]提出将突变机制应用于蚁群算法中，提高算法收敛速率；王颖等[7]提出针对参数的自适应调整，解决不易求得全局最优的不足；李擎等[8]利用蚁群算法易于与其他方法结合的特点，结合粒子群与蚁群，改进了信息素的更新策略，对性能进行了一定的提升。

1 相关理论与技术基础

1.1 ACO 算法

1.1.1 ACO 算法简述

对ACO 算法的具体过程进行参数设置，设τij为0，蚂蚁数目为m。第k（k=1，2，…，m）只的每一步选择由信息素浓度决定，其状态转移概率为，计算公式为：

其中，ak={1，2，…，n}－tabuk为下一次可选择的所有城市的集合，tabuk则是蚂蚁k当前已经过的城市，它会随着ACO 算法的运行而有一定变化。i代表蚂蚁当前所位于的城市，j为集合tabuk中的一员，为蚂蚁k由城市i转移至下一个城市j的概率，为蚂蚁从城市i去往j的期望程度，τij为路径（i，j）上的信息素轨迹强度。由公式1 可知，与[τij（t）]α[ηij（t）]β的关系成正比例，因此当蚂蚁进行路径的选择时会优先挑选信息素浓度较高的城市进行转移[9]。

1.1.2 ACO 算法优点与缺陷

ACO 算法作为仿生算法，继承了蚂蚁行为的诸多特点，有以下几点优点：①本质并行性。多个蚂蚁个体可位于多点同时进行搜索，相当于多项代理的分布式系统，具有较高的算法运行效率。②易与其他算法相结合。以ACO 算法为基础，引入其他算法的优秀机制与之进行互补，可进一步提升算法质量。③强鲁棒性。ACO 算法只需进行很小的改动便能使用在其他方面，有助于拓宽使用领域范围。

ACO 算法作为新生代仿生算法，仍有着一些缺陷，主要有：①不易取得最优解。由于ACO 算法的特性，信息素在运行时较易集群在个别路段上，从而陷入局部最优。②求解时间长。构造解的过程需要很大的计算量，当待解决问题需要构造的可行解数目增多时，蚂蚁寻找最优解所需要的时间将会变长。③参数的设置理论不足。ACO 算法的性能与关键参数息息相关，目前还没有对参数的设置给出严密的理论认证，多依赖实验经验而定[10-11]。

1.2 GA 算法

1.2.1 GA 算法简述

GA 算法由HOLLAND 在1975 时首次提出，该算法参照的是达尔文的“优胜劣汰” 进化论原则。在遗传算法的实现过程中，通过计算适应度函数所获取的结果可较为直观地判断出种群个体（染色体）适应度的强弱程度，从而决定它们的存留[12]。

1.2.2 遗传算法步骤

遗传算法步骤如下。

步骤1：初始化种群。设置参数，选择合适的编码方式，产生非固定数据并进行组合来获取初始种群。

步骤2：计算适应度值。使用适应度函数获取值后，选择后续操作个体。

步骤3：执行交叉运算。

步骤4：执行变异运算。

步骤5：判断是否能够结束，若满足条件则输出结果，否则回到步骤2，最终得出最优解。

1.3 TSP 问题

TSP 问题指有N个城市，由初始位置出发，遍历每一个城市，不能重复，且最终回到原来出发点的问题，同时需找到在过程中所付出的代价最小，即最短的路径。TSP 问题虽然描述起来并不困难，但是要获取其精确的解却并不是一件容易的事情，单是其所有可行路径就有（n－1）！/2 条，学术界将其称为NP-Hard问题[13-14]。

TSP 是NP 完全问题，若一种算法在对解决TSP应用而言表现良好，则通常在解决其他的应用上也可以获得不错的结果，因此以TSP 问题来验证算法的改进是否有效是比较可靠的[15-16]。

2 ACO-GA 混合算法及其在TSP 中的应用

2.1 ACO-GA 混合算法

2.1.1 ACO-GA 混合算法原理

ACO-GA 混合算法将ACO 算法和GA 算法进行结合，每进行一次迭代，最差蚂蚁个体就会被最好染色体所取代，替换后的解影响了信息素矩阵，从而影响最后所求最优解。同时，在迭代过程中融入轮盘赌算法，让适应值与个体选中概率成正比。

2.1.2 ACO-GA 混合算法步骤

ACO-GA 混合算法步骤如下。

步骤1：初始化算法参数。将Nc（迭代次数）置0，初始化τij和Δτij，对m、ρ、α、β、Q、Ncmax等参数赋值，设置启发值和信息素矩阵。

步骤2：初始化种群。编码并产生随机数据并进行组合来生成初始种群，初始化染色体。

步骤3：执行染色体选择、变异、交叉、解码操作。

步骤4：解空间的构建。将m个蚂蚁分配到n个城市，并根据状态转移概率对未经过的城市进行计算，并在其中选择算得的概率最大的城市逐步进行下一步的转移，该过程持续至蚂蚁遍历完所有的城市为止。最终每个成员都遵循规则获取了一条路径，在路径表中实现更新路径。

步骤5：如果蚁群的搜索未完成，那么就跳转到步骤4，继续进行循环搜索。

步骤6：执行染色体选择操作。

步骤7：进行总路程的计算，使用最好染色体取代最差蚂蚁，更新信息素矩阵。

步骤8：当Nc≥Ncmax，即算法循环迭代次数已到达设定的最大值，终止条件已满足，则循环结束并输出计算结果；否则，跳转至步骤3。

2.2 改进算法在TSP 问题中的应用

2.2.1 仿真实验

本文从通用TSPLⅠB 库中选取了eil51、rand75、eil76、pr152、bier127 等10 个实例，算例名称即为城市数目，分别对ACO 算法和ACO-GA 混合算法的性能进行测试，对比分析ACO 与ACO-GA 混合算法的仿真实验结果。

ACO 算法参数设置：α=1，β=3，ρ=0.4，m=城市数，Q=100，迭代次数为200。

ACO-GA 混合算法的参数设置：α=1，β=3，ρ=0.4，m=城市数，Q=100，Pc=0.6，Pm=0.02，迭代次数为200。

每组测试案例独立运行20 次，选择其中最佳优化路线，即20 次寻优中求解出的距离最短的一次。

2.2.2 测试结果与分析

分别对ACO 算法和ACO-GA 混合算法的数据进行整理，保留4 位小数，结果如表1 和表2 所示。

表2 ACO-GA 混合算法在TSP 问题中的实现

3 实验结果分析

运行时间对比。ACO-GA 混合算法和ACO 算法的运行时长均随着城市问题量的扩大而扩大。当城市规模较小、循环次数相同时，2 种算法在运行时间上并未有明显差距。但当测试数据达到并超过eil51 时，ACO-GA 混合算法的求解速度体现了明显优势，且随规模增大，优势更加明显。

最优解对比。ACO-GA 混合算法整体上获取的最优解值较ACO 算法好。

最差解对比。从表1、表2 可知，ACO 算法获得的最差解大于ACO-GA 混合算法，且与最优解差异较大。表明ACO-GA 混合算法较均匀，寻优效果较好。