基于变异和启发式选择的蚁群优化算法

方霞，席金菊

湖南文理学院计算机科学与技术学院，湖南常德 415000

基于变异和启发式选择的蚁群优化算法

方霞，席金菊

湖南文理学院计算机科学与技术学院，湖南常德 415000

蚁群算法是一种较好地解决组合优化问题的新型进化算法，是继模拟退火、遗传算法、禁忌搜索等之后的又一启发式智能优化算法。20世纪90年代初期，它由意大利学者M.Dorigo等人首先提出[1]，并成功应用于求解TSP、二次分配、图着色、车辆调度、集成电路设计及通信网络负载等问题[2-5]。

由于蚁群算法具有良好的鲁棒性、正反馈、分布式及并行计算等特点，所以受到学者们的广泛关注，蚁群算法的理论框架页日趋成熟。但是随着问题规模n上升，蚁群算法暴露出收敛速度慢，计算时间长，易于过早陷入局部最优，难以满足实际需求的不足。针对这些问题，王颖提出了自适应蚁群算法[6]，黄国锐使用信息素扩散等办法来提高全局搜索能力和搜索速度[7]，丁建立等提出了GAAA算法融合遗传算法和蚁群算法的各自优点，来取长补短[8]。结合信息素的更新和搜索机制的改进是目前优化蚁群算法的集中方略，如文献[9]提出分段优化策略加速解的构造；文献[10]通过视觉反馈与行为记忆加快局部收敛；文献[11]进行启发式修正来加速收敛；文献[12]通过不同的蚂蚁种群构造解的多样性，使得收敛平衡。文献[13-14]分别对于蚁群算法进行了综述以及各项参数对于算法的影响。这些改进蚁群算法都进一步提高了算法的收敛速度，改进了求解质量，这些学者的研究都在一定程度上改善了蚁群算法的性能，但是收敛速度慢、求解质量和求解效率的矛盾等问题仍然是制约蚁群算法广泛应用特别是在较大规模优化问题中应用的主要瓶颈。因此，本文从一些经典TSP问题出发，提出了一种基于变异和启发式选择的蚁群优化算法（ACO algorithm based on Mutation Features and Selected Heuristic，MFSHACO）。首先利用较优路径中城市相互之间的邻接特点，产生较好的初始解，极大提高了算法的效率，在不同阶段进行变异，既提高了变异效率，也改进了变异质量，在一些经典TSP问题上新算法表现出很好的性能。

1 TSP问题描述

已知n个城市及各城市之间的距离，求一条经过各城市一次且仅一次的最短回路。图论描述为G=(V,A)，V={v1,v2,…,vn}是n个城市的顶点集，vi,vj∈V}是V中各顶点相互连接组成的弧集，已知各城市间的距离dij，求一条最短的Hamilton回路，即在点集V= {v1,v2,…,vn}中，对n个城市遍历且只遍历一次的最短封闭曲线。本文算法采用具备dij=dji特征的TSP问题进行探讨。

2 基本蚁群算法

常规蚁群算法求解TSP问题描述：

将m只蚂蚁随机放置在n个城市上，设初始时刻城市之间每一条边上信息素τs(0)=const，const是一个常量，tabuk是禁忌表，用来记录蚂蚁k所遍历城市节点，初始时刻是第一个城市节点，随着tabuk进化作动态调整，凡是写入禁忌表tabuk中城市节点，蚂蚁不允许再遍历该城市节点。当n个城市节点都写入禁忌表tabuk中，表示蚂蚁完成一次循环。当本次循环完成后，禁忌表tabuk被清空，该蚂蚁又可以重新自由地进行选择。在路径搜索过程中，蚂蚁根据各条路径上的信息量及路径的启发信息来计算状态转移概率。如果(t)＜p0（0＜p0＜1，为转移概率门槛值），在t时刻，蚂蚁k在城市i选择城市j的转移概率(t)按公式（1）来求解：

其中τij(t)表示t时刻在节点i和节点j路径上的信息素。蚂蚁k(k=1,2,…,n)在运动过程中，根据各条路径上的信息素的浓度决定转移方向；(t)表示在t时刻蚂蚁k从节点i转移到节点j的概率；dij(i,j=1,2,…,n)表示节点i和节点j之间的距离，ηij为能见度启发因子，表示目标点的能见度，它与距离因子dij成反比，ηij=1/dij；allowedk={1,2,…,n}表示蚂蚁k下一步允许选择的城市，转移概率成正比。

经过n个时刻，蚂蚁完成一次循环，各路径上信息量根据公式（2）调整：

Δτij(t,t+1)表示本次循环中路径(i,j)的信息素的增量，计算方法根据计算模型而定，本文算法采用蚁周系统模型（Ant Cycle System）：

Lk是节点i与j之间的距离。基本的蚁群算法有两个基本缺陷：搜索时间过长和容易陷入局部解。新算法采用MMAS（最大最小蚂蚁系统，MAX-MIN Ant System）在很大程度上克服了这两个缺陷，取得了良好的结果。

3 MFSHACO算法

3.1 MFSHACO算法原理

3.1.1 紧邻信息优先机制

大量的实验表明，实际优化回路中城市i的邻接节点仅仅是离城市i较近的有限几个城市，结合视觉能见度分析，可以有选择地进行，由此提出紧邻信息优先机制：蚂蚁k以当前节点i为中心，按照距离路径长短dij的非递减排序，选取一定数量的节点作为有限的能见城市，作为下一个节点j的可选范围，具体数量可以根据情况动态设定，也可简单设定有限视觉数量为w=n/r，r=1,2,…,20（r的值根据问题规模n的大小进行适当调整），即从w个节点中找出还未经过的节点加入禁忌表tabuk。

算法根据dij距离矩阵信息进行排序得到一个n行w列的有序矩阵，以及对应的城市编号信息矩阵。则在t时刻蚂蚁k在当前节点，至多需要检测编号信息矩阵中w个节点与禁忌表中信息进行比较，从而亦能降低可行节点的数目，随之可行节点的转移概率计算量也大大下降，总体时间复杂度由O(mn2)变为O(w·mn)，而w是一个相对稳定的常量，不会随着问题规模n的增长而增长，亦可记为O(mn)，蚁群算法的计算速度大大提高，同时初始解的蚂蚁群较好，排除了出现大量较差解的可能。

大量的实例计算可以发现，蚁群算法选择下一个城市时，往往是选择最近的几个，也就是从allowedk所列的城市中，仅选择符合dij较小的几个城市。随着每一只蚂蚁走完大半路径后，备选城市越来越少，很有可能被迫从一个边区跳跃至另一个边区，出现路径交叉，产生较差的解，影响整个蚁群算法的搜索效率。最明显的情况就是每一只蚂蚁搜索到最后两三个城市时，这几个城市间距又很远，蚂蚁已经无法进行更多的选择，出现这种情况主要是因为ACS中蚂蚁选择路径是没有考虑所有剩下城市的布局，这就出现了选择的冲突。从ACS的搜索过程中，查看一些蚂蚁历经的城市连线，绝大部分都不可避免地存在这个问题，而到目前为止尚无合适的解决方案。本文算法采用变异策略解决该冲突。

3.1.2 变异机制

新算法采用变异策略解决该冲突：当w个备用节点均和禁忌表tabuk相冲突时，则突破w个视觉范畴，转向全部的节点数据来和禁忌表检测，找到合理的节点作为下一节点。一般这时找到的节点不能得到较好的解，为了保证寻找到较优的解，随即采用一定的概率进行变异，变异时只对路径后面发生冲突的部分采用2-opt变异，同时检测以防止出现路径交叉的现象，得到比较理想的解。变异策略如下：

其中c为变异次数，一般取为(n+1)/8，t为当前发生冲突时在当前搜索路径中所处的位置，n为路径长度。

在所有蚂蚁进行一次周游完成以后，全局也进行一次2-opt变异，充分利用其简洁高效的特点，使每一轮能得到较好解，有效提高收敛速度，期望得到全局最优解。

3.1.3 启发式选择调整

在基本蚁群算法中，启发式信息在指导蚂蚁的路径搜索方面会产生一定的影响，但是随着搜索过程的不断深入，较好路径上的信息素累积越来越多，启发式信息的影响程度越来越弱；在算法后期，启发式信息对搜索过程的影响已经微乎其微。因此，为了更加有效地利用启发式信息，本文在算法后期通过动态调整启发式信息来保证算法快速收敛于最优解。

信息素指数β采用模拟退火法进行调整。蚁群完成一次周游后得到路径长度的最短路径Lbest和平均路径长度LAver，β值根据如下公式进行计算：

其中nc为当前迭代数，初始β为一指定常量β0。

相较于文献[10]中DEAHACO算法定义的路径期望值PExpect进行当前路径调整，算法计算数据大大下降，时间复杂度也相应降低。

3.2 MFSHACO算法步骤

步骤1初始化m,α,β0,ρ,Q,NC,w，计算得到紧邻矩阵信息D_sort，R_sort。

步骤2随机选择每只蚂蚁的初始位置。

步骤3开始周游，首先根据紧邻矩阵信息并按照公式（1）找到下一个城市节点；如果紧邻节点发生冲突成为不可选，则突破紧邻矩阵的限制，在全部可选范围处理，同时记忆当前位置t，该蚂蚁周游完成后随即进行变异操作。

步骤4所有蚂蚁周游一次完成后，进行变异操作。

步骤5根据公式（2）～（4）更新信息素浓度τij，采用了MMAS算法。

步骤6计算本次周游得到的最短路径Lbest和最长路径Lworst，根据公式（5）更新β值。

步骤7判断是否达到指定的迭代次数NC或者所求的解在最近若干代中无明显改进，若是，则结束迭代，输出最后的优化结果；否则转步骤2。

4 实验分析

为了探索改进算法的各项性能指标，将MFSHACO算法应用于TSPLIB数据集（http：//elib，zib，de/pub/mp-testdata/tsp/tsplib）中eil51实例，结合Matlab编程实验环境，实验中使用的参数均通过验证确认。

4.1 MFSHACO算法性能比较

设置参数Q=100，τmax=10，τmin=0.1。在每种情况运行10次，每次最大迭代次数NC为100的实验数据结果基础上，得到的平均数据如表1所示。

表1 改进算法加入变异和启发式选择机制的优化结果

从表1中数据可以看出：改进蚁群算法MFSHACO在求得最优解和收敛速度上有明显优势，算法通过引入合理的变异机制和进行启发式选择可以大大提高算法的收敛性能，在求解质量方面都得到明显改善，说明MFSHACO算法是有效又实用的。

为了验证该算法的有效性，根据不同的紧邻信息数据w，表2为应用于eil51实例在不同参数下得到的实验统计结果。由表2可知将变异机制、启发式选择机制、MMAS算法等融合之后算法在全局搜索能力和收敛速度方面得到了较好的平衡，整个程序的计算速度得到了大幅提升，随着问题规模的上升，可以更好地体现其优越性。

表2 MFSHACO算法解决eil51实例不同参数下的实验结果

4.2 MFSHACO算法收敛性分析

图1为MFSHACO算法应用到eil51实例所得到的一个最优路径模拟仿真和收敛效果图。具有MFSHACO算法的一般特征，算法参数为：m=n=51，Q=100，α=2，β0= 3，ρ=0.1，NC=100，横坐标表示算法的迭代次数，纵坐标表示当前路径的长度。收敛曲线分别为每次迭代所得到的最短路径长度和平均路径长度。

图1 MFSHACO算法在eil51实例上的收敛性

由实验收敛效果图可以看出，MFSHACO算法在运行初期急速收敛，迭代至10～25次时能够接近于最优解，而基本MMAS算法大约需要迭代2 500次以后才收敛，经过多次实验，参考表2中的数据，根据参数选择设置的不同，达到收敛所需进化代数最小值略有差异，但是相较于基本蚁群算法，无论时间复杂度，还是收敛效果方面，本文MFSHACO算法都是一种高效的求解TSP问题的蚁群优化算法。

5 结束语

针对传统蚁群算法初始较好解产生困难、计算搜索时间长、收敛速度慢、易于停滞等特点，本文提出了MFSHACO算法，该算法采用节点之间的紧邻信息，动态进行启发式的选择，能够合理有效地产生较好的初始解，避免了大范围搜索，并且能够极大提高算法的计算速度。同时充分采用局部和全局变异策略，指导算法加速收敛，使得变异结果的质量有较大改善。实验数据表明，MFSHACO算法不仅能够获得高质量优化解，而且收敛速度大幅提升，整体运行时间大幅下降，特别随着问题规模n的增大，有很强的实用意义。本文各种参数的选择主要依靠经验，后期将针对不同的变异策略和组合参数之间的关系进行深入研究。

[1]Dorigo M，Maniezzo V，Colorni A.Ant system：optimization by a colony of cooperating agents[J].IEEE Trans on Systems，Man and Cybernetics，1996，26（1）：29-41.

[2]常智勇，杨建新，赵杰，等.基于自适应蚁群算法的工艺路线优化[J].机械工程学报，2012，48（9）：163-169.

[3]潘杰，王雪松，程玉虎.基于改进蚁群算法的移动机器人路径规划[J].中国矿业大学学报，2012，41（1）：108-113.

[4]于宏涛，高立群.容量受限工厂选址问题模型及贪婪蚁群算法求解[J].东北大学学报：自然科学版，2011，32（12）：1688-1691.

[5]冀俊忠，黄振，刘椿年.基于变异和信息素扩散的多维背包问题的蚁群算法[J].计算机研究与发展，2009，46（4）：644-654.

[6]王颖，谢剑英.一种自适应蚁群算法及仿真研究[J].系统仿真学报，2002，14（1）：31-33.

[7]黄国锐，曹先彬，王煦法.基于信息素扩散的蚁群算法[J].电子学报，2004，32（5）：865-868.

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

[9]冀俊忠，黄振，刘椿年，等.基于多粒度的旅行商问题描述及其蚁群优化算法[J].计算机研究与发展，2010，47（3）：434-444.

[10]郭禾，程童，陈鑫，等.一种使用视觉反馈与行为记忆的蚁群优化算法[J].软件学报，2011，22（9）：1994-2005.

[11]刘全，陈浩，张永刚，等.一种动态发挥率和启发式修正的蚁群优化算法[J].计算机研究与发展，2012，49（3）：620-627.

[12]张晓伟，李笑雪.新型的双种群蚁群算法[J].计算机工程与应用，2011，47（13）：39-41.

[13]Hu Yurong，Ding Lixin，Xie Datong.The setting of parameters in an improved Ant Colony Optimization algorithm for feature selection[J].Journal of Competational Information Systems，2012，8（19）：8231-8238.

[14]Hu Xiayun，Zhu Yanfei.Researches and applications of ant colony algorithm[C]//Proc of the 2nd International Conference on Computer Application and System Modeling.Paris：Atlantis Press，2012：859-862.

FANG Xia,XI Jinju

School of Computer Science and Technology,Hunan University of Arts and Science,Changde,Hunan 415000,China

There are some shortcomings in the traditional ant colony algorithm as the algorithm costs too much time to get an optimal solution and easily falls into a stagnation behavior.To solve these problems,this paper puts forward a new ant colony algorithm based on mutation features and selected heuristic.The new algorithm uses the basic characteristics between the adjacent nodes in the optimal path,avoiding the large scope searching.It can get better initial solutions and greatly reduces the time complexity of the algorithm.It also uses the selected heuristic to accelerate the convergence process.With the 2-exchanged method, the mutation strategy not only enhances the mutation efficiency,but also improves the mutation quality.Combined with classic TSP instances,the MFSHACO algorithm shows good performance.

ants colony system;Traveling Salesman Problem（TSP）;mutation;selected heuristic

为了解决传统蚁群算法求解TSP问题的求解时间较长、易于局部收敛的问题，提出了一种基于变异和启发式选择的蚁群优化算法。利用较优路径中城市相互之间的邻接特点，避免了大范围搜索求解，使得能具有较好的初始解，将算法的时间复杂度大大降低；同时为了加快算法的收敛速度，对于路径的启发式选择进行重新定义；引入变异机制，充分利用2-交换法简洁高效的特点，既提高了变异效率，也改进了变异质量。实验结果证明，在一些经典TSP问题上新算法表现出很好的性能。

蚁群算法；旅行商问题（TSP）；变异；启发式选择

A

TP301；TP18

10.3778/j.issn.1002-8331.1306-0238

FANG Xia,XI Jinju.Ant colony algorithm based on mutation features and selected heuristic.Computer Engineering and Applications,2013,49（24）：24-27.

湖南省教育厅项目（No.09C704）。

方霞（1972—），女，高级实验师，主要研究方向：计算机应用，智能控制与优化；席金菊（1965—），女，教授，主要研究方向：计算机应用。E-mail：yufangxia@163.com

2013-06-21

2013-08-05

1002-8331（2013）24-0024-04

CNKI出版日期：2013-10-14http://www.cnki.net/kcms/detail/11.2127.TP.20131014.1655.003.html