DOI: 10.11817/j.issn.1672-7207.2015.08.026

新型蚁群算法在TSP问题中的应用

张弛^{1, 2}，涂立²，王加阳¹

(1. 中南大学 信息科学与工程学院，湖南 长沙，410083；

2. 湖南城市学院 信息科学与工程学院，湖南 益阳，413000)

摘 要：

算法容易出现早熟和停滞现象，提出一种新型蚂蚁算法(new ant colony algorithm，NACA)，即将转移规则、全局信息素灾变规则和局部混合调整信息素规则。选择几个典型TSP问题进行实验。研究结果表明：新型蚂蚁算法一方面提高了算法种群的多样性，同时将轮盘赌算子利用到城市转移规则中，有利于提高算法的收敛速度；另一方面，将种群个体的差分信息应用于局部信息素更新规则中，有利于搜索全局解；最后灾变算子避免算法陷入局部最优，而达到全局最优。新型的蚁群算法具有更强的搜索全局最优解的能力以及更好的稳定性和收敛性，同时为解决其他优化问题提供新的思路。

关键词：

蚁群算法(ACA)；轮盘赌；信息素；差分演化；灾变；

中图分类号：TP18             文献标志码：A         文章编号：1672-7207(2015)08-2944-06

Application of self-adaptive ant colony optimization in TSP

ZHANG Chi^{1, 2}, TU Li², WANG Jiayang¹

(1. School of Information Science and Engineering, Central South University, Changsha 410083, China;

2. School of Information Science and Engineering, Hunan City University, Yiyang 413000, China)

Abstract: Considering that there exists precocious and stagnation behavior phenomenon about the traditional ant algorithm, a new ant colony algorithm(NACA) was proposed, i.e. the transition rule, convulsions rule of global pheromones and the  mixing adjustment rule of local pheromones were mixed. The results show that on one hand, NACA enhances genetic algorithms population diversity and at the same time the roulette operator is used in translative rules, whch is beneficial to improving the convergence speed. On the other hand, the individual differential information is used in the updated rule of local pheromones, which is good for searching the global solution. Finally, the cataclysm operator avoids falling into local optimum, and leads to reach the global optimum. NACA has stronger ability to search the global optimal solution and better stability and astringency. It also provides a new idea for solving other combinational optimization problems.

Key words: ant colony algorithm (ACA); roulette; pheromones; differential evolution; convulsions

TSP问题^[1]可以简单描述为：已知n个城市以及任意2个城市之间的距离，求1条经过V中所有城市1次且仅1次的闭合，使得总行程最小。TSP问题是著名的NP难题，在电路板布局、车辆调度等组合优化问题中有广泛应用^[2]。遗传算法(genetic algorithm, GA)^[3]对非线性复杂问题显示出很强的求解能力^[4]，因而被成功地应用于模式识别、智能控制等领域。但基本遗传算法(simple genetic algorithm, SGA)^[5]在解决一些复杂问题时，存在着早熟、收敛速度慢及优化精度低的缺陷。为克服基本遗传算法的这些缺陷，目前相关的研究工作主要集中在对编码方式、选择算子、变异算子等方面对基本遗传算法加以改进。蚁群算法(ant colony algorithm, ACA)是一种新的启发式算法^[6-12]，作为新的仿生进化算法是由Dorigo首先提出的^[6]。该算法模仿蚂蚁觅食时的行为，按照启发式思想，通过外激素的诱发作用逐渐收敛到问题的全局最优解。但蚁群算法存在一些缺陷，如需要较长的搜索时间。这是因为蚁群中多个个体的运动是随机的，虽然通过信息的交流能够向着最优路径进化，但当群体规模较大时，很难在较短时间内从杂乱无章的路径中找出1条较好的路径。针对这些缺陷，近些年来国内外学者对蚁群算法进行了多方面改进，目标就是为了在合理时间复杂度下尽可能提高蚁群衍在一定空间复杂度下的寻优能力，从而改善蚁群算法的全局收敛性，拓宽蚁群算法的应用领域。本文作者结合遗传算法、差分演化算法^[13-15]和蚁群算法的优点，在基本蚁群算法中提出一种新型的蚁群算法(new colony algorithm, NACA)，即将转移规则、全局信息素灾变搜索规则和局部混合调整信息素规则等。

1  新型的蚁群算法(NACA)

1.1  信息素τ的随机初始化

              (1)

其中：m为蚂蚁个数；L_mn为最近邻方法得到的路径长度。信息素被初始化成多样性、种群个体多样性，有利于求解全局最优解。

1.2  混合转移规则

轮盘赌算法在遗传算法选择算子中常用，为此将轮盘赌算法^[12]使用到城市转移规则中，适应度越大的个体被选中的概率越大，这样能使蚁群算法往好的方向进化，对提高解的质量有很大帮助。

  (2)

其中：q为第k个蚂蚁在第i个顶点到第 i+1个顶点之间的连线数目，即ij子区间个数；f_ij为第i个和第j个子区间所在解的适应度；为ij所有q个子区间所在解的和；γ为轮盘赌启发因子。

1.3  全局信息素灾变搜索规则

由于算法中以一定的概率选择相邻子区间中信息量最大的子区间，因此，信息量最大的子区间常常被选中，这使得新一代解的该分量值集中在这个子区间，容易发生停滞现象，陷入局部最优值。为了避免这种现象，将算法中全局信息素变更嵌入灾变算法^[16]：当种群适应值保持在一个稳定值一段时间后，全局信息素发生灾变，杀掉优秀的个体，这样才可能产生更优秀的物种。进行灾变时用灾变倒计数的概念。倒计数的长度取决于进化的速度，若进化速度越慢，则倒计数长度越长。若倒计数完毕还没有新的最优值，则认为局部搜索已经充分，就发生灾变。若若干次灾变后产生的个体的适应度与没灾变前的一样，则停止灾变。

灾变规则如下：

 (3)

其中：q_i为蚂蚁在第i个顶点到第 i+1个顶点之间的连线数目；为蚂蚁在本次循环中留在路径ij上的信息量；ρ为信息素数量。

衰减系数为第i个分量各子区间的平均信息量。其中：r代表位于0 和k_i之间的子区间；d为搜索方向控制系数，当个体适应度高于平均值时，采用负反馈机制搜索，此时d=-1，反之，采用正反馈机制搜索，此时d=1。

这样，当陷入局部最优解时，算法降低了选择高适应度的子区间概率，增加了选择适应度低的子区间概率，增加了候选解的多样性，避免了局部收敛。

1.4  局部混合调整信息素规则

首先采用传统方法局部更新信息素：

        (4)

其中：；d_min为蚂蚁全程搜索n个城市后最近2个城市之间的距离。

信息素变化采用差分演化算法的变异策略，其中“DE/rand/1”是一个经典的战略^[15]，DE/rand/1”按下面方式产生中间向量v_ij：

        (5)

式中： 为差分向量；m为蚂蚁数目；为城市i和j之间信息素最优解，在进化过程中它能够自适应地调整搜索方向和搜索步长；F为缩放因子。

局部混合调整信息素策略如下：

       (6)

差分演化算是一种快速的演化算法^[14-15]，它采用实数编码，并利用个体间的差分信息来引导搜索产生新个体，有很强的全局搜索能力。

2  NACA算法描述

本文提出的新型蚁群算法求解TSP问题的主要步骤如下。

Step 1：按式(2)初始化各条路径上的信息素量、种群数目(蚂蚁数目)m、信息启发式因子α、期望启发式因子β、轮盘赌启发因子γ和信息衰减系数ρ等。

Step 2：随机初始化种群。

Step 3：计算群体中各个个体的适应度。

Step 4：第k只蚂蚁按式(2)进行城市转移，从i城市进入下一城市j。将城市j写入该蚂蚁的禁忌表U_k，更新U_k。

Step 5：当第k只蚂蚁周游结束后，按式(4)，(5)和(6)局部混合更新此蚂蚁走过的所有路径上的信  息素。

Step 6：所有蚂蚁按Step 4和Step 5完成周游，进行全局更新信息素，同时更新周游次数计数器N_c，当达到设定值时结束。否则，重复Step 4。

Step 7：判断是否陷入局部最优。若陷入局部最优，则按式(3)进行全局信息素灾变搜索，将算法引入全局最优搜索。

Step 8：若蚁群全部收敛到1条路径，则循环结束，输出最优路径。

3  仿真实验及分析

为了检验本文新型的蚁群算法(NACA)的可行性和有效性，从通用TSPLIB^[16]中选取5个实例进行测试，同时选择ACGA和HGI-ACGA算法进行对照实验。参数的最优设置见文献[17]。表1所示为实验中使用的公共参数，其中，m为蚁群个数，α为信息素启发因子，β为路径启发因子；γ为轮盘赌启发因子，ρ为衰变因子，F为缩放因子，Q为局部信息素调节因子，N_c为迭代次数。

为测试NACA，ACGA^[18]和HGI-ACGA^[18]算法的求解速度、求解质量和鲁棒性。针对eli51实例，NACA，ACGA^[19]和HGI-ACGA^[19]算法最优值曲线对比如图1所示。从图1可见：NACA在第58次迭代得到全局最小值440，eil51全局最优解f_best为440，在给定的步骤内，NACA算法10次有7次得到全局最优解；HGI-ACGA在第162次迭代得到全局最小值453，eil51全局最优解f_best为453，在给定的步骤内，HGI-ACGA算法10次有3次得到全局最优解；ACAG在第148次迭代得到全局最小值463，eil51全局最优解f_best为463，在给定的步骤内，HGI-ACGA算法10次有1次得到全局最优解。针对berlin52实例，NACA与ACGA^[19]和HGI-ACGA^[20]算法最优值曲线对比如图2所示。从图2可见：NACA算法在第99次迭代得到全局最小值7 602，berlin52全局最优解f_best为7 602，在给定的步骤内，NACA算法10次有6次得到全局最优解；NACA算法在第99次迭代得到全局最小值7 602，berlin52全局最优解f_best为7 602，在给定的步骤内，NACA算法10次有6次得到全局最优解；HGI-ACGA算法在第210次迭代得到全局最小值为7 769，berlin52全局最优解f_best为7 769，在给定的步骤内，HGI-ACGA算法10次有3次得到全局最优解；ACAG在第158次迭代得到全局最小值8 020，eil51全局最优解f_best为8 020，在给定的步骤内，HGI-ACGA算法10次有2次得到全局最优解。从图1和图2可见：NACA算法的求解速度、求解质量及鲁棒性能都比ACGA和HGI-ACGA算法的优。

表1  公共参数的设置

Table 1  Public parameters setting

图1  eli51最优值曲线比较

Fig. 1  eli51 optimal value curve comparison

图2  berlin52最优值曲线比较

Fig. 2  Comparison of berlin52 optimal values

为了测试NACA算法的整体性能，采用ACA，ACGA，HGI-ACGA和NACA这4种算法分别对5个TSP进行10次测试，求出平均值、最优值、平均误差和最优解的次数，见表2。其中平均误差(其中，S_Ti为第i次的最短路径；S₀为已知最短路径；N^best是找到最优解的次数)。从测试结果可以看出：除Pr107问题之外，NACA算法在最优解、平均值性能方面都比其他3种算法的优。另一方面，NACA算法在所有的TSP测试中，最优解、平均值和平均误差σ都比其他3种算法的小，同时在所有TSP问题的10次测试中，NACA算法获得的最优解次数最多。从表2可见：NACA算法的整体性能与ACA，ACGA和HGI-ACGA这3种算法相比明显提高。

ACGA，HGI-ACGA和NACA算法求解eil51和berlin52问题的进化过程见图3和图4。从图3可见：算法NACA在10次测试中获得7次最优解，最优解为440，平均值为458，最劣解为538，平均相对误差为5.6%；算法ACGA在10次测试中获得1次最优解，最优解为463，平均值为499，最劣解为575，平均相对误差为8.6%；算法HGI-ACGA在10次测试中获得3次最优解，最优解为453，平均值为488，最劣解为538，平均相对误差为6.2%。从图3可见：除第7和第9次测试外，在其他8次测试中，算法NACA的求解质量都比ACGA和HGI-ACGA的高，同时，NACA算法的鲁棒性都比其他2种算法的优。

从图4可见：算法NACA在10次测试中获得6次最优解，最优解为7 602，平均值为7 892，最劣解为8 120，平均相对误差为1.6%；算法ACGA在10次测试中获得2次最优解，最优解为7 820，平均值为8 201，最劣解为8 340，平均相对误差为6.3%；算法HGI-ACGA在10次测试中获得3次最优解，最优解为7 769，平均值为7 989，最劣解为8 278，平均相对误差为2.2%。从图4还可见：除第8和第9次测试外，在其他8次测试中，算法NACA求解质量比其他3种算法的优；NACA算法最优解和最劣解都比其他2种算法的优；NACA算法的平均误差比ACGA和HGI-ACGA算法的低；NACA算法的健壮性能比CGA和HGI-ACGA算法的优。NACA在ACA，ACGA和差分演化算法(DE)的基础上考虑了优化遗传信息对ACA算法的影响，NACA利用种群多样性规则、种群个体差分信息引导算法进行全局搜索规则和全局信息素灾变规则引导算法避免局部收敛，所以，NACA算法在解的质量、速度和鲁棒性性能方面均得到提高。

表2  TSP实例测试结果

Table 2  Results of TSPinstance test

图3  3种算法求解eli51

Fig. 3  Three algorithms solutions to eli51

图4  3种算法求解berlin52

Fig. 4  Three algorithms solutions to berlin52

4  结论

1) 为了保证种群的多样性，避免算法陷入局部最优，将初始种群个体中的信息素τ进行随机初始化。

2) 精英策略能加快算法的收敛速度，将轮盘赌策略引入城市选择方法中，为此引入城市混合转移规则。

3) 当蚁群算法陷入局部最优时，采用全局信息素灾变搜索规则能有效克服算法陷入局部最优，达到全局最优。

4) 差分演化算法采用实数编码，利用个体间的差分信息来引导搜索产生新个体，有很强的全局搜索能力。将差分演化算法嵌入到信息素局部调整规则中，加快了算法的收敛速度。

5) 在寻优能力方面，NACA与 ACA，ACGA和HGI-ACGA 相比，NACA具有快速且高精度的求解能力，同时其健壮性能也明显提高，这表明新型蚁群算法(NACA)是有效的。

6) 该新型蚁群算法(NACA)可推广到其他连续空间的优化问题之中，为将蚁群算法应用于连续性优化问题提供了新的途径。但若蚁群算法中参数选取不当，则容易出现早熟停滞现象，因此，需对蚁群算法数学模型进行改进。                                                                                                                                                                        

参考文献：

[1] Garey M R, Graham R L, Johnson D S. Some NP-complete geomet ric problems[C]//Proc 8th Annu ACM Symp: Theory of Computing。 Washington, America, 1976: 10-22.

[2] Michalewicz Z, Fogel D B. How to solve it: ModernHeuristick[M]. BerlinHeidelberg: Springer, 2000: 58-78.

[3] Holland J H. Adaptation in nature and aritificial systems[M]. Massachusetts, USA: MIT Press, 1992: 12-72.

[4] 杨奇文, 姜金平, 张国红. 速度优化的遗传算法[J]. 软件学报, 2001, 1(2): 270-275.

YANG Qiwen, JIANG Jingping, ZHANG Guohong. Improving optimization speed for genetic algorithms[J]. Journal of Software, 2001, 1(2): 270-275.

[5] Goldberg D E. Genteic algorithms in search optimization and machine learning[M]. Massachusetts, USA: Addison-Wesley, 1989: 38-95.

[6] Stutzle T, Hoos H H. Max-min ant system[J]. Future Generation Computer Systems, 2000, 16(8): 889-914.

[7] 段海滨. 蚁群算法原理及其应用[J]. 北京: 科学出版社, 2006: 45-96.

DUAN Haibin. Principle and application of ant colony algorithm[J]. Beijing: Science Press, 2006: 45-96.

[8] 焦李成, 杜海峰, 刘芳, 等. 免疫优化计算,学习与识别[M]. 北京: 科学出版社, 2007: 93-104, 133-143.

JIAO Licheng, DU Haifeng, LIU Fang, et al. Immunological computation for optimization, learning and recognition[M]. Beijing: Science Press, 2007: 93-104, 133-143.

[9] 刘波, 刘蒙生. 采用基于模拟退火算法的蚁群算法求解旅行商问题[J]. 华中科技大学学报(自然科学版), 2009, 37(11): 26-30.

LIU Bo, LIU Mengsheng. The traveling salesman problem is solved with an ant colonyalgorithm based on the simulated annealing algorithm[J]. Journal of Huazhong University of Science and Technology (Natural Science Edition), 2009, 37(11): 26-30.

[10] 刘勇, 马欣, 申志兵. 基于改进蚁群算法的应急救援最优路径选择[J]. 工业安全与环保, 2009, 35(11): 56-57.

LIU Yong, MA Xin, SHEN Zhibing. Emergency relief optimal path selection based on improved ant colony algorithm[J]. Industrial Safety and Environmental Protection, 2009, 35(11): 56-57.

[11] 张晓玲, 黄力. 融入遗传算子的蚁群算法求解TSP问题[J]. 广西民族大学学报(自然科学版), 2009, 15(3): 81-86.

ZHANG Xiaoling, HUANG Li. Added genetic operators into ant colony algorithm to solve TSP problem[J]. Journal of Guangxi University For Nationalities (Natural Science Edition), 2009, 15(3): 81-86.

[12] 吴建辉, 章兢, 刘朝华. 基于蚁群算法和免疫算法融合的TSP问题求解[J]. 湖南大学学报(自然科学版), 2009, 36(10): 81-87.

WU Jianhui, ZHANG Jing, LIU Zhaohua. Based on fusion of ant colony algorithm and immune algorithm to solve TSP problem[J]. Journal of Hunan University (Natural Science), 2009, 36(10): 81-87.

[13] 敖友云, 迟洪钦. 多目标差分演化算法研究综述[J]. 计算机科学与探索, 2009, 3(2): 123-126.

AO Youyun, CHI Hongqin. A survey of multiobjective differential evolution algorithms[J]. Journal of Frontiers of Computer Science & Technology, 2009, 3(2): 123-126.

[14] 毕晓君, 李安宁. 差分演化算法的认知无线电决策引擎[J]. 智能系统学报, 2012, 7(6): 1-5.

BI Xiaojun, LI Anning. Cognitive radio decision engine based on improved binary differential evolution algorithm[J]. Transaction on Intelligent Systems, 2012, 7(6): 1-5.

[15] JIA Liyuan, HE Jianxin, ZHANG Chi, et al. Differential evolution with controlled search direction[J]. Journal of Central South University, 2012, 19(12): 3516-3522.

[16] TSPLIB[EB/OL]. [2007-07-23]. http//www.iwruni-hei-delbergde/ groups/comopt/software/TSPLIB95/.

[17] Dorigom M, Maiezzo V, Colorn I A. Ant system: Optimization by a colony of cooperation agents[J]. IEEE Transaction on Systems Man and Cybernetics: Part B, 1996, 26(1): 29-41.

[18] 徐金荣, 李允, 刘海涛. 一种求解TSP的混合遗传蚁群算法[J]. 计算机应用, 2008, 28(8): 2084-2088.

XU Jinrong, LI Yun, LIU Haitao. Hybrid genetic ant colony algorithm for traveling salesman problem[J]. Computer Applications, 2008, 28(8): 2084-2088.

[19] 将金良, 林广明, 欧阳森. 改进的灾变遗传算法及其在无功优化中的应用[J]. 华南理工大学学报(自然科学版), 2010, 38(3): 95-98.

JIANG Jinliang, LIN Guangming, OUYANG Sen. Improved cataclysmic genetic algorithm and its applicationof the reactive power optimization[J]. Journal of South China University of Technology (Science and Technology), 2010, 38(3): 95-98.

[20] 张广帅, 张煜东. 蚁群算法求解TSP综述[J]. 南京师范大学学报(工程技术版), 2014, 14(4): 39-42.

ZHANG Guangshuai, ZHANG Yudong. Survey on ant algorithm for the traveling salesman problem[J]. Journal of Nanjing, Normal University (Engineering and Technology), 2014, 14(4): 39-42.

(编辑  陈灿华)

收稿日期：2014-10-29；修回日期：2014-12-21

基金项目(Foundation item)：湖南省教育科学“十二五”规划课题(XJK014CGD013)，益阳市科技计划项目(2014JZ52)(Project(XJK014CGD013) supported by Hunan Education Science “Twelfth Five-year” Planning Program; Project (2014JZ52) supported by Science and Technology Planning Project of Yiyang City, Hunan Province)

通信作者：张弛，硕士，讲师，从事计算机图像处理和算法研究；E-mail：carol_zc@126.com

摘要：针对传统的蚂蚁算法容易出现早熟和停滞现象，提出一种新型蚂蚁算法(new ant colony algorithm，NACA)，即将转移规则、全局信息素灾变规则和局部混合调整信息素规则。选择几个典型TSP问题进行实验。研究结果表明：新型蚂蚁算法一方面提高了算法种群的多样性，同时将轮盘赌算子利用到城市转移规则中，有利于提高算法的收敛速度；另一方面，将种群个体的差分信息应用于局部信息素更新规则中，有利于搜索全局解；最后灾变算子避免算法陷入局部最优，而达到全局最优。新型的蚁群算法具有更强的搜索全局最优解的能力以及更好的稳定性和收敛性，同时为解决其他优化问题提供新的思路。