蚁群算法求解TSP中的参数设置
2016-10-31严小燕夏桂林
严小燕+夏桂林
摘要：蚁群算法在求解TSP 中取得了较好的效果，但相对于遗传算法等优化方法，其缺少系统的理论指导，特别是参数的设置，通常是根据经验或反复试验来选取合适的参数值。本文在分析各参数对蚁群算法性能影响的基础上，采用均匀设计法对算法参数进行设置，并以TSP为例，利用MATLAB进行仿真。试验结果表明，采用均匀设计达到以较少的试验获得较好的参数组合，获得较好算法性能的目的。
关键词：蚁群算法；参数设置；均匀设计
中图分类号：TP18 文献标识码：A 文章编号：1009-3044（2016）22-0179-03
Abstract：Ant colony algorithm has good effect in solving Traveling Salesman Problem（TSP）. But compared with the genetic algorithm optimization method， it has less systematic theoretical guidance. Especially in the parameter settings， people usually select appropriate parameter values based on experience or trial. Based on the analysis of the parameters influence on the performance of ant colony algorithm， in this paper， the uniform design method is adopted to set the parameters， TSP is taken as an example， MATLAB is used to simulate.The experimental results show that using uniform design to achieve the better parameter combination with less test and obtain the purpose of better algorithm performance.
Key words：ant colony algorithm； parameter settings； uniform design
1 概述
20世纪90年代，意大利学者Dorigo M等人提出通过模拟自然界蚂蚁群体觅食行为的过程，来完成对问题求解的优化算法，即蚁群算法（Ant Colony Algorithm， ACA）[1]。蚁群算法最先被应用于解决旅行商问题（Traveling Salesman Problem， TSP），并取得了较理想的实验结果。
蚁群算法的基本思想是在多个蚂蚁并行寻找的可行路径所构成的解空间中搜索最优解。这其中不可或缺的因素是信息素的释放，它具有正反馈机制，可以使搜索过程不断收敛，最终逼近最优解[2]。但蚁群算法的收敛性能对参数的初始化设置比较敏感。从蚁群搜索最短路径的机理不难看到，有关参数的选取直接影响到算法的收敛性和效率。选取合适的参数组合能够让算法收敛速度较快并避免陷入局部最优解。但由于蚁群算法参数组合数目多，各参数之间具有关联性，如何选取最优的参数组合使得蚁群算法的性能最佳，目前尚没有严格理论的支持。通常都是根据经验或反复试验来选取合适的参数值。基于此，国内外许多学者在蚁群算法的参数分析和优化组合方面进行了大量的研究工作。Dorigo M等对m，ρ，α，β， Q 等主要参数做了初步的研究；Botee H M [3]等用遗传算法来求出m，ρ，α，β等参数的最优组合，但算法比较麻烦。段海滨等通过对参数选择原则的数字仿真实验分析，总结了一种"三步走"的有效方法来选择最优参数组合[4]。詹士昌[5]，叶志伟[6]、蒋玲艳[7]、徐红梅[8]等也在蚁群算法的参数选择方面进行了研究。
本文对蚂蚁数目m、信息素挥发因子ρ、信息启发式因子α、期望启发式因子β、信息素强度Q等重要参数进行研究，并采用均匀设计法[9]确定试验方案，获得算法参数设置的最佳组合。
2 蚁群算法的数学模型
3 基本蚁群算法的参数分析
3.1蚂蚁数量m
在TSP中，单只蚂蚁完成一次循环经过的路径是解空间中的一个解，m只蚂蚁完成一次循环则会产生一个子集。显然，m越大，子集越大，可以提高蚁群算法的全局搜索能力以及算法的稳定性，但m过大时，会导致路径上的信息素变化趋于平均，信息正反馈作用减弱，收敛速度减慢。反之，m越小，子集越小，特别TSP规模较大时，会使从未被搜索到的路径上的信息素浓度趋近于0，虽然收敛速度加快，但会出现过早停滞现象。文献[7]提出：当m∈[0.6n， 0.9n]时（n为城市规模），蚁群算法的求解性能较好。在段海滨的“三步走”策略中，认为当蚂蚁数目m约为城市规模n的2/3时，蚁群算法的全局收敛性和收敛速度都比较好。
3.2 信息素挥发因子ρ
3.3 信息启发因子α和期望启发因子β
3.4 信息素强度Q
信息素强度Q是蚂蚁完成一次循环在所经过的路径上所释放的信息素总量。它使得算法在正反馈机制作用下以合理的速度搜索到全局最优解。Q越大，在蚂蚁已走过的路径上信息素浓度的累积越快，正反馈作用会占主导地位，算法收敛速度快。但由于TSP的规模不同，路径长度各不相同，Q的取值应与TSP的规模相对应，确保信息素总量更新在可控制范围内。
综上，蚁群算法中各参数的作用是紧密耦合的，参数设置组合直接影响着算法的性能。
4 参数设置
均匀设计是一种非常有效的多因素多水平试验设计优化方法，应用到蚁群算法的多参数设置中，值得一试。
按照表3，因素个数为5，选取均匀表
表4中括号内的数值表示初始参数的实际取值。对每个参数组合运行15次，每次运行的最大循环次数为500次，取15次试验的平均值和最优解所得的结果如表5所示。
从表5可以看出平均值最小为第9组（426.4738），最优解的最低值出现在第2组（424.6354）。另第5组也取得较优值。
分析以上3组参数组合，给出一组新的参数组合13：m=27，α=0.8，β=4.2，ρ=0.42，Q=1200。对第5组，第9组和第13组参数分别进行15次试验，将迭代次数设置为200，得出如表6所示的对比结果：
以上3组参数求出的最优解相同（425.649），第13组参数的平均值最优。结果如图1、图2、图3所示。
5 结束语
蚁群算法中各参数的设置直接影响着算法的性能，本文以ACS为例，采用均匀设计法结合各参数较好取值范围确定试验方案，通过MATLAB仿真试验，以较少的试验次数获得了较好的蚁群算法参数组合。
参考文献：
[1]Dorigo M， Maniezzo V， Colorni A. Ant system： optimization by a colony of cooperating agents.IEEE Transaction on Systems， Man， and Cybernetics-Part B， 1996， 26（1）：29-41.
[2]郁磊，史峰，王辉，等.MATLAB智能算法30个案例分析[M].2版.北京：北京航空航天大学出版社，2015：205-206.
[3]Botee H M，Bonabeau E. Evolving ant colony optimization. Advances in Complex Systems，1998，1（2）：149-159.
[4]段海滨. 蚁群算法原理及其应用[M]. 北京：科学出版社，2005.
[5]詹士昌，徐婕. 蚁群算法中有关参数的最优选择[J].科技同报，2003，19（5）：381-386.
[6]叶志伟，郑肇葆. 蚁群算法中参数α、β、ρ设置的研究[J].武汉大学学报，2004，29（7）：597-601.
[7]蒋玲艳，张军，钟树鸿.蚁群算法的参数分析[J].计算机工程与应用，2007，43（20）：31-36.
[8]徐红梅，陈义保，刘加光，王燕涛.蚁群算法中参数设置的研究[J].山东理工大学学报，2008，22（1）：7-11 .
[9]方开泰. 均匀设计与均匀设计表[M]. 北京：科学出版社，1994.
[10]黄永青，梁昌勇，张祥德. 基于均匀设计的蚁群算法参数设定.控制与决策[J]，2006，21（1）：93-96.
[11]Dorigo M， Gambardella L M. Ant colony system： a cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation， 1997， 1（1）：53-66.
