求解较大规模TSP问题的改进蚁群算法

求解较大规模TSP问题的改进蚁群算法

作者：方霞 曹洁 张平凤

来源：《科技创新与应用》2016年第27期

摘 要：为了优化并提高传统蚁群算法求解较大规模TSP问题的计算速度，提出了一种基于有限视觉能见度机制的改进蚁群优化算法。采用初始解优化路径中节点间邻接特征，缩小可选范围搜索求解，算法时间复杂度由O（mn2）改进为O（mn），最后对可能的冲突问题给出变异解决方案。结合大规模TSP问题验证并加以完善，实验结果证明，新算法提高计算速度效果显著。

关键词：蚁群算法ACS；TSP；有限视觉能见度 引言

蚁群算法是继模拟退火、禁忌搜索、遗传算法等之后的一种新型解决组合优化问题的启发式智能优化算法。蚁群算法的优点在于：采用正反馈机制，有发现较好解的能力，具有很强的并行性和鲁棒性等。但是收敛速度慢，计算时间较长，易过早陷入局部最优，在求解连续优化问题上没有优势。针对这些问题，目前已有了一些改进的蚁群算法：

White T等提出了ASGA（ant system with genetic algorithm）算法加入了控制参数的调整，更加优化[2]，Stüzle T等提出了MMAS（max-min ant system）算法避免算法过早收敛于非全局最优解[3]，张纪会、王颖等提出了自适应蚁群算法来提高全局搜索能力和搜索速度[4-5]，丁建立等提出了GAAA（genetic algorithm-ant algorithm）算法融合遗传算法和蚁群算法的各自优点，来取长补短[6]，尚鲜连等提出了一种智能蚁群优化算法[7]，采用最近节点选择策略进行路径优化，但是未能结合较大规模TSP问题实现验证，未考虑处理实际使用中出现的特别情况。文章主要采用有限视觉能见度机制，结合大规模TSP实际应用中的特殊情况验证并进行完善，避免在大范围搜索求解，产生较好的初始蚂蚁群，极大提高计算速度，有效解决蚁群算法求解较大规模问题时的计算时间过长这一缺陷。 1 TSP问题

已知n个城市V={v1，v2，…，vn}和各城市之间的距离dij，寻找一条经过各个城市一次且仅一次的最短路径。

文章选取对称TSP为基础，即具备dij=dji特征的对称矩阵信息来探讨TSP问题，特别针对于较大n规模的TSP问题分析探讨。 2 传统蚁群算法

龙源期刊网 http://www.qikan.com.cn

初始随机将m只蚂蚁放置在n个城市上，设置两两城市间邻接边上初始信息素τs（0）=const（const为一个常量）；禁忌表tabuk记忆蚂蚁k已经遍历的城市节点，初始时刻是起始第一个城市节点，随着蚂蚁运动轨迹的变化动态调整，凡是已经遍历过的城市节点，蚂蚁不允许再遍历该城市节点。当n个城市节点全部都写入禁忌表tabuk中，得到一条优化路径。一次循环完成后，禁忌表tabuk置空，蚂蚁又可重新开始选择，重复上述过程得到不同路径。 在生成路径的过程中，蚂蚁根据当前所在位置城市i所对应邻接城市节点路径上各信息素及能见度启发信息来计算选取下一个节点的转移概率。规则如下：若pkij（t）

其中pkij（t）表示在t时刻蚂蚁k从节点i转移到节点j的转移概率；τij（t）表示t时刻在节点i和节点j路径上的信息素强度；ηij为能见度启发因子，表示目标城市节点的能见度，它与距离因子dij成反比，ηij=1/dij；α为信息启发因子，表示轨迹重要性；β为期望启发因子，表示能见度重要性，不同的数据环境需要根据情况来设置调整相应的α和β值。allowedk={1，2，...，n}表示蚂蚁k下一步可以选择的城市，与禁忌表tabuk对应。转移概率pkij（t）与ταij（t）ηβij（t）成正比。

当蚂蚁完成一次循环，得到相应的优化解之后，所有路径段上信息素需要根据公式（2）调整：

其中，Δτkij（t，t+1）表示蚂蚁k在时刻（t，t+1）释放在路径（i，j）上的信息素，路径越短，信息素释放的量就越多；Δτij（t，t+1）表示所有蚂蚁在本次循环中经过路径（i，j）时信息素的增量之和；信息素的衰减系数ρ决定蚁群算法的全局搜索能力及算法的收敛速度，设置系数ρ

3 改进蚁群算法

传统ACS中蚂蚁k从当前节点i选择下一个节点j时，需要将n-1个节点与禁忌表比较，时间复杂度为O（mn）2，再计算n-1个节点的转移概率，蚂蚁在选择下一节点之前需要考虑所有可能的节点集合，时间量也相应增大，对于较大规模的实际问题，搜索时间很长。 3.1 有限视觉能见度机制

无数实例表明，在最优解对应的优化回路中城市节点i的邻接点仅是离城市i较近的几个有限城市。为了优化选择，采用有限视觉能见度策略：以蚂蚁k所在当前节点i为中心，将蚂蚁k的所有可选邻接点优先顺序按距离路径非递减排列，设置w个节点作为有限可选范围，其中w=n/r，r=1，2，…，20（r的值根据问题规模n的大小进行适当调整）[8]。

算法设计一个n×w维有序矩阵，用来记录每一个节点对应的w个优先邻接城市节点编号信息矩阵。采用有限视觉能见度，t时刻蚂蚁k在节点i，仅需检测其所在编号信息矩阵中w个节点，并与禁忌表tabuk中节点信息进行比较，大大降低可行节点数目，同时转移概率计算量也随之下降，不计算总的迭代次数NC_max在内，时间复杂度由O（mn2）变为O（wmn），

龙源期刊网 http://www.qikan.com.cn

其中w是一个常数，不随问题规模n的变化而变化，所以亦可记为O（mn），改进蚁群算法计算速度极大提高，由于这种策略得到的蚂蚁群初始解较好，避免了过早收敛，出现较差解的可能。

3.2 冲突解决策略

蚂蚁k在选择下一个邻接点时，往往是选择几个距离最近的节点，即从allowedk所列表中，仅选择符合dij较小的几个城市。这种情况下采用ACS在求解大规模TSP时存在一个很大问题：在求解路径的后期，第i只蚂蚁走完大多数城市后，搜索到回路中最末尾几个城市时，剩下可选城市范围越来越窄，蚂蚁i已经无法进行更多的选择，这几个城市间距很远，极有可能出现路径交叉，从一个边界区域跳跃至另一个边界区域，产生较差的解，影响整个蚁群算法的搜索效率。从ACS的大量实例求解中，可以看到蚂蚁优化解，这个问题是一个突出矛盾，目前为止尚无好的解决方案。这种现象出现的主要原因是，ACS中蚂蚁选择路径时没有考虑剩下城市的整体布局，从而出现了这样的选择冲突。

新算法用于解决冲突解决策略采用变异机制：寻找路径后期，当w个邻接节点和禁忌表tabuk相冲突或者路径长度不能达到预期优化数据时，则转向全局节点数据检测，突破w个视觉范畴，找到合理的节点作为下一节点。同时为了保证寻找的解的优越性，采用一定的概率进行变异，比较变异前后可行解的差异，选择两者中较优解为调整后的结果。 4 实验数据

结合Matlab编程实验环境，实现了用传统蚁群算法ACS和改进蚁群算法解决较大规模TSP问题并仿真，以TSPLIB提供的a280和pr1002问题为例。设置参数α=2，β=3，在a280问题中蚂蚁数量m=50，近距离城市数量w=20，pr1002问题中设置蚂蚁数量m=300，近距离城市w=30。每种情况进行运行10次以上的试验运行，得到的平均数据结果如表1所示。 基于有限视觉范围和变异机制的改进蚁群算法在时间复杂度上有明显优势，大大提高了算法的计算能力，而且能够产生良好的蚁群初始解，问题规模越大，效果越显著。

图1为实验选取a280问题的改进算法运行结果仿真之一，在多次求解得到较好解的优化路径曲线和迭代进化曲线（平均路径长度和最短路径长度）。虽然与图2中目前已求得的a280问题次优路径曲线有一定差距，但是求解速度已不在同一级别上[8]。 5 结束语

针对传统蚁群算法产生初始较好解困难，计算搜索时间过长的特点，结合较大规模TSP问题，提出了有限视觉范围的机制，使得算法时间复杂度实现了质的飞跃，从二维变为了线性增长，由O（mn2）改进为O（mn），极大提高计算速度。对于较大规模的问题，这点非常必要也是非常重要的，实验数据表明，改进算法效率显著，可行有效。

龙源期刊网 http://www.qikan.com.cn

基于有限视觉能见度的改进算法经过变异机制完善，求解得到的较优解也并不逊色于传统ACS算法，虽然离TSPLIB提供的最优解还有一定差距，这也正是该算法的魅力所在，需要我们思考和不断探索更多更先进的方法来辅助完善。 参考文献

[1]Dorigo M， Maniezzo V， Colorni A. The ant system： optimization by a colony of cooperating agents[J].IEEE Trans. on Systems， Man and Cybernetics，1996，1（26）：29-41. [2]White T，Pagurek B，Oppacher F.ASGA：Improving the ant system by integration with genetic algorithms[R].Canada：Systems and Computer Engineering，Carleton University，1998. [3]Stützle T，Hoos H.Max-min ant system[J].Future Generation System，2000，16：889-914. [4]张纪会，高齐圣，徐心和.自适应蚁群算法[J].控制理论与应用， 2000，17（1）：1-3. [5]王颖，谢剑英.一种自适应蚁群算法及仿真研究[J].系统仿真学报， 2002，14（1）：31-33.

[6]丁建立，陈增强，袁著祉.遗传算法与蚁群算法的融合[J].计算机研究与发展，2003，40（9）：1351-1356.

[7]尚鲜连，陈静，姒茂新.改进的智能蚁群算法在TSP问题中的应用[J].计算机仿真，2009，26（12）：160-163.

[8]方霞，席金菊.基于变异和启发式选择的蚁群优化算法[J].计算机工程与应用，2013，49（24）：24-27.

龙源期刊网 http://www.qikan.com.cn

龙源期刊网 http://www.qikan.com.cn