对基本蚁群算法的改进及其在TSP中的应用

王晨旸，张玉茹

(哈尔滨商业大学 计算机与信息工程学院，哈尔滨 150028)

对基本蚁群算法的改进及其在TSP中的应用

王晨旸，张玉茹

(哈尔滨商业大学 计算机与信息工程学院，哈尔滨 150028)

在基本蚁群算法的基础上对转移概率计算公式进行了修正，自行定义了间接期望启发式并将其引入转移概率计算方法之中，减少信息素对蚂蚁选择路径的影响，增加蚁群算法执行过程中的路径多样性，弥补蚁群算法易收敛于局部最优解的不足，并通过旅行商问题验证了改进算法的可行性.

间接期望启发式；多样性；旅行商问题

旅行商(TSP)问题又称为货担郎问题，是一种典型的组合优化问题.旅行商从某一个城市出发，途径其余各个城市有且仅有一次，然后再回到出发城市，求走过的最短行程.在实际生活中，很多组合优化问题都可以转化为旅行商问题，它已经成为测试新算法性能的标准问题[1].

目前针对蚁群算法的改进方法主要有针对算法本身的优化和蚁群算法与其他算法融合的优化[2].本文通过自行定义间接期望启发式，对基本蚁群算法进行改进，针对蚁群算法易收敛于局部最优解的不足，改进蚁群算法本身，通过旅行商问题验证改进算法的可行性.

1 蚁群算法简介

蚁群算法最早由意大利学者Dorigo于1992年在论文中提出，其灵感来自于自然界中蚂蚁在寻找食物过程中寻找巢穴到食物之间最短路径的行为[3].

在初始时刻，m只蚂蚁随机放置于n个城市中，城市与城市之间路径上的信息素初始值相等，τij(0)=τ0设为信息素初始值，τ0为常数.其次，蚂蚁k(k=1,2,…,m)根据公式(1)计算得到的转移概率，选择下一座城市.

(1)

其中：τij为边(i，j)上的信息素；ηij=1/dij为从城市i转移到城市j的启发式因子；allowedk为蚂蚁k下一步被允许访问的城市集合.

为了让蚂蚁访问每个城市仅一次，采用禁忌表tabuk来记录蚂蚁k当前走过的城市.当m只蚂蚁都完成了一次周游，回到出发城市，分别计算每只蚂蚁在本次周游中所走过的n条边的总长度，并保存其中最短的长度，同时，更新各边上的信息素.首先是计算信息素随着时间的流逝挥发后路径上剩余的信息素量，其次考虑蚂蚁本次周游过程中在它们所经过的边上释放的信息素，其计算公式为：

τij=(1-ρ)τij

(2)

其中：ρ为信息素挥发系数，且0<ρ<1.

(3)

(4)

根据上式可知，蚂蚁构建的路径长度dij越小，则路径上各条边就会获得更多的信息素，则在以后的迭代中就更有可能被其他的蚂蚁选择.

蚂蚁完成一次遍历后，重置禁忌表，周游次数增加1，重新将m只蚂蚁随机放置在n个城市，准备下一次周游.

当蚂蚁周游次数达到预定大小时，停止循环，输出整个算法执行得到的最优路径及其长度.

2 蚁群算法的改进

蚁群算法是一种新型的群集智能算法，具有鲁棒性强，分布式计算，易于与其他算法结合的优点，但是也有易收敛于局部最优的不足[4].

首先，在基本蚁群算法中，算法的期望启发式ηij仅仅与蚂蚁当前所在城市i到下一个城市j之间的距离有关，对于蚂蚁转移到城市j之后，从城市j出发到达下一个城市x时面临的情况，当前正位于城市i的蚂蚁却不加以考虑.蚂蚁仅考虑一步(i到j)的转移，受当前这一步转移时较短路径距离的诱惑，忽视了第二步(j到x)转移时面临的路径过长的风险[5].如图1所示，从A点出发到B点，途中有两条路径可选，A→C→B或A→D→B，当蚂蚁位于A点时，AD的距离远小于AC的距离，蚂蚁很显然更倾向于选择AD这条路径，而当蚂蚁到达D点后，已不能回头只能继续向前达到B点，这段路总长是10，而最优路径A→C→B的长度只有8，蚂蚁在A点选择AD只能得到次优解，并非最优解.如果蚂蚁从A点出发时，已经预先知道CB和DB的长度，则会对选择AC还是AD做出更加合理的选择.

图1 蚂蚁移动示意图

基于以上两点考虑，本文自行定义了间接期望启发式并将其引入转移概率计算之中，来增加路径多样性，改善算法的寻优能力.当蚂蚁k在城市i选择下一个城市j时，既考虑城市i和城市j之间的距离因素dij，又考虑城市j所连接的其他城市(除城市i以外)到城市j的距离.定义zij为城市j到除城市i以外其他(n-2)个城市的距离的平均值，即

(5)

取υij=1/zij为城市i到城市j的间接期望启发式.取δ为间接期望启发式因子，其功能α,β与类似.在计算蚂蚁k在城市i到城市j的转移概率时，加入υij，则式(1)被修正为：

(6)

3 改进后算法的实现步骤

本文仅对式(1)进行了改进，对基本蚁群算法的整体结构和流程未加修改.改进后的蚁群算法实现步骤与基本蚁群算法相似.如图2所示，算法的执行步骤为：

Step1 初始化参数各项参数，α，β，δ，η，τ，ρ，Q，m,n,NC,NCmax.

Step2 将m只蚂蚁随机放置在n个城市.

Step3m只蚂蚁按照式(6)选择下一座城市，完成本次循环.

Step4 记录本次循环中最短的路径及其长度.

Step5按照式(2)、式(3)、式(4)更新各条路径上的信息素.

Step6 判断NC是否小于等于NCmax，如果满足条件，则NC=NC+1，并跳转至Step2；否则，停止循环，输出所有循环中最短的路径及其长度.

图2 改进算法的执行流程

4 算法仿真

本文采用的算法仿真硬件环境是CPU：I5-4200H，8 G内存，软件环境是Win7系统64位旗舰版，Matlab2014 R2014a.

本次仿真采用验证数据为eil51，其坐标如表1所示.

表1 eil51坐标数据

为了算法测试的严谨性，本文算法和基本蚁群算法参数统一设定为α=1，β=3，NCmax=500,ρ=0.5,Q=106,m=n=51.图3、4分别是基本蚁群算法和改进蚁群算法求解典型TSP问题数据模型eil51所得到的Matlab仿真结果.改进蚁群算法得到的最优解为429.7371，其路径为7、43、24、14、25、13、41、19、40、42、44、15、45、33、39、10、49、9、30、34、21、50、16、2、29、20、35、36、3、28、31、26、8、22、1、32、11、38、5、37、17、4、18、47、12、46、51、27、6、48、23.

图3 基本蚁群算法代码运行结果

图4 改进蚁群算法代码运行结果

如表2所示，在最大循环次数500次(循环次数达500次以上时两种算法均未出现更优解)的限制条件下，本文算法最终得到的最优路径优于基本蚁群算法求解的路径.由图3、4比较还可发现，在算法运行初期，即循环次数100次时，本文算法的寻优能力也强于基本蚁群算法.收敛更快，求解更优，是本文算法对比基本蚁群算法的两大优势.

与目前已知最优值相比，本文算法得到的最优路径仅有不到百分之一的差距，由此可见，本文针对基本蚁群算法的改进是有效的，可行的.

表2 最优路径比较

5 结 语

本文旨在针对基本蚁群算法本身进行算法改进，减轻蚁群算法天生的易收敛于局部最优解的特性，保持了算法原来的整体结构和优良特性.经过仿真验证，本文算法与基本蚁群算法在同样参数条件下，拥有更好的寻优能力.由于本文是在基本蚁群算法的基础上进行的改进，与之前研究者所改进的方向不同，所以本文提出的算法完全可以和之前研究者做出的改进方法相结合，实现进一步改进.此外，蚁群算法参数的最优组合一直是广大学者寻找的目标，本文算法引入了新的启发式及其因子，使得本文算法的参数组合更加多变，最优的参数组合也是下一步工作的重点之一.

[1] 李勇霞. 自适应蚁群优化算法[M].重庆：重庆大学数学与统计学院，2016.

[2] 宗德才, 王康康, 丁 勇. 蚁群算法求解旅行商问题综述[J]. 计算机与数字工程, 2014: 42(11): 2004-2013.

[3] 刘建芳. 蚁群算法的研究及其应用[M].重庆：重庆大学数学与统计学院, 2015.

[4] 胡 勇. 基于蚁群算法的物流配送车辆路径优化问题的研究.鞍山：辽宁科技大学，2016

[5] 张永强, 王晓东. 基于改进蚁群算法的旅游路线优化[J]. 纺织高校基础科学学报, 2016, 29(4): 570-576.

ImprovementofbasicantcolonyalgorithmanditsapplicationinTSP

WANG Chen-yang, ZHANG Yu-ru

(School of Computer and Information Engineering, Harbin University of Commerce, Harbin 150028, China)

Based on the basic ant colony algorithm, this paper modified the calculation formula of transition probability. The indirect expectation heuristic was defined and introduced into the calculation method of transition probability, which will reduce the effect of pheromone on ant selecting path and increase the path’s diversity of ant colony algorithm. It will make up the deficiency of ant colony algorithm in convergence to local optimal solution. Finally, the feasibility of the improved algorithm was verified by the traveling salesman problem in this paper.

indirect expectation heuristic; diversity; traveling salesman problem

2017-03-10.

王晨旸(1992-)，男，硕士，研究方向：信号检测与信息处理.

TP368

A

1672-0946(2017)05-0561-04