蚁群算法求解tsp中的参数设置

《蚁群算法求解tsp中的参数设置》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、蚁群算法求解TSP中的参数设置　　摘要：蚁群算法在求解TSP中取得了较好的效果，但相对于遗传算法等优化方法，其缺少系统的理论指导，特别是参数的设置，通常是根据经验或反复试验来选取合适的参数值。本文在分析各参数对蚁群算法性能影响的基础上，采用均匀设计法对算法参数进行设置，并以TSP为例，利用MATLAB进行仿真。试验结果表明，采用均匀设计达到以较少的试验获得较好的参数组合，获得较好算法性能的目的。　　关键词：蚁群算法；参数设置；均匀设计　　中图分类号：TP18文献标识码：A文章编号：1009-3044（2016）22-0179-0

2、3　　Abstract：AntcolonyalgorithmhasgoodeffectinsolvingTravelingSalesmanProblem（TSP）.Butcomparedwiththegeneticalgorithmoptimizationmethod，ithaslesssystematictheoreticalguidance.Especiallyintheparametersettings，peopleusuallyselectappropriateparametervaluesbasedonexperien

3、ceortrial.Basedontheanalysisoftheparametersinfluenceontheperformanceofantcolonyalgorithm，inthispaper，theuniformdesignmethodisadoptedtosettheparameters，TSPistakenasanexample，MATLABisusedtosimulate.Theexperimentalresultsshowthatusinguniformdesigntoachievethebetterparam

4、etercombinationwithless6testandobtainthepurposeofbetteralgorithmperformance.　　Keywords：antcolonyalgorithm；parametersettings；uniformdesign　　1概述　　20世纪90年代，意大利学者DorigoM等人提出通过模拟自然界蚂蚁群体觅食行为的过程，来完成对问题求解的优化算法，即蚁群算法（AntColonyAlgorithm，ACA）[1]。蚁群算法最先被应用于解决旅行商问题（TravelingSales

5、manProblem，TSP），并取得了较理想的实验结果。　　蚁群算法的基本思想是在多个蚂蚁并行寻找的可行路径所构成的解空间中搜索最优解。这其中不可或缺的因素是信息素的释放，它具有正反馈机制，可以使搜索过程不断收敛，最终逼近最优解[2]。但蚁群算法的收敛性能对参数的初始化设置比较敏感。从蚁群搜索最短路径的机理不难看到，有关参数的选取直接影响到算法的收敛性和效率。选取合适的参数组合能够让算法收敛速度较快并避免陷入局部最优解。但由于蚁群算法参数组合数目多，各参数之间具有关联性，如何选取最优的参数组合使得蚁群算法的性能最佳，目前尚没有

6、严格理论的支持。通常都是根据经验或反复试验来选取合适的参数值。基于此，国内外许多学者在蚁群算法的参数分析和优化组合方面进行了大量的研究工作。DorigoM等对m，ρ，α，β，Q等主要参数做了初步的研究；BoteeHM[3]等用遗传算法来求出m，ρ，α，β6等参数的最优组合，但算法比较麻烦。段海滨等通过对参数选择原则的数字仿真实验分析，总结了一种"三步走"的有效方法来选择最优参数组合[4]。詹士昌[5]，叶志伟[6]、蒋玲艳[7]、徐红梅[8]等也在蚁群算法的参数选择方面进行了研究。　　本文对蚂蚁数目m、信息素挥发因子ρ、信息启发

7、式因子α、期望启发式因子β、信息素强度Q等重要参数进行研究，并采用均匀设计法[9]确定试验方案，获得算法参数设置的最佳组合。　　2蚁群算法的数学模型　　3基本蚁群算法的参数分析　　3.1蚂蚁数量m　　在TSP中，单只蚂蚁完成一次循环经过的路径是解空间中的一个解，m只蚂蚁完成一次循环则会产生一个子集。显然，m越大，子集越大，可以提高蚁群算法的全局搜索能力以及算法的稳定性，但m过大时，会导致路径上的信息素变化趋于平均，信息正反馈作用减弱，收敛速度减慢。反之，m越小，子集越小，特别TSP规模较大时，会使从未被搜索到的路径上的信息素浓度

8、趋近于0，虽然收敛速度加快，但会出现过早停滞现象。文献[7]提出：当m∈[0.6n，0.9n]时（n为城市规模），蚁群算法的求解性能较好。在段海滨的“三步走”策略中，认为当蚂蚁数目m约为城市规模n的2/3时，蚁群算法的全局收敛性和收敛速度都比较好。　　3.2信息