蚁群算法求解TSP中的参数设置.doc

蚁群算法求解TSP中的参数设置 　　摘要：蚁群算法在求解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