蚁群算法在求解旅行商问题中的改进  

AN ANT COLONY ALGORITHM BASED IMPROVEMENT FOR TSP SOLUTIONS

作　　者：严小燕[1,2] 李旸[1] 夏桂林[2] 

机构地区：[1]安徽农业大学信息与计算机学院,安徽合肥230036 [2]巢湖学院计算机系,安徽巢湖238000

出　　处：《巢湖学院学报》2010年第6期21-24,共4页Journal of Chaohu University

摘　　要：蚁群算法是一种启发式优化算法,在求解旅行商问题等多种组合优化问题上有着优越性。但基本蚁群算法收敛速度慢,易于陷入局部最优解,导致停滞现象出现。针对算法的这些缺点,提出给各条边赋予不同的信息素初始量以加强算法初期信息素的作用,缩小算法的搜索范围;并在进行全局信息素更新时,对到目前为止的最优解、最差解和普通解采用不同的更新策略。实验结果表明,改进的蚁群算法在实验环境下,解决旅行商问题时的性能较基本蚁群算法有较好的表现。The ant colony algorithm is a heuristic algorithm.It has advantages on a variety of combinatorial optimization problems such as the TSP.However,basic ant colony algorithm may converge slowly and fall into local optimal solution easily,which leads to stagnation.to avoid these shortcomings of the algorithm,it is proposed that different initial amount of pheromone be given to different edges in order to enhance the effects of the pheromone in the early algorithm and narrow the algorithm search range;it is also the purpose to carry out the global pheromone update,the best solution,the worst solution and general solution with different update strategies.Experimental results show that improved ant colony algorithm has better performance in solving the TSP than the basic ant colony algorithm in experimental conditions.

关 键 词：蚁群算法 旅行商问题 信息素初始化 信息素更新 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]