MMAS-EC算法求解旅行商问题  

MMAS-EC algorithm for solving traveling salesman problem

作　　者：李哲[1] 夏立[1] 庄浩俊[2] 董红生[3] 

机构地区：[1]海军工程大学电气与信息工程学院 [2]中国人民解放军91656部队 [3]中国人民解放军92665部队

出　　处：《计算机工程与应用》2011年第9期41-44,47,共5页Computer Engineering and Applications

摘　　要：针对蚁群算法在求解旅行商问题容易出现搜索精度不高的问题,提出一种结合排出算法的最大-最小蚁群系统算法(MMAS-EC)。算法采用全局寻优和局部搜索结合的策略,利用寻优效果较好的最大-最小蚁群系统指导全局搜索方向,同时引入排出算法来探索局部解空间,并采用2-opt操作减小了排出算法对初始位置的依赖,提高了解的稳定性。仿真实验表明:结合了排出算法的最大-最小蚁群系统算法与标准蚁群算法相比,在时间开销增加较小的情况下,取得了质量更高的解。One of the problems encountered when ant colony optimization is applied to traveling salesman problem is that sometimes this algorithm results in a lower performance.According to this problem,a new Max-Min Ant System combining with Ejection Chains is presented（MMAS-EC）.A new strategy based on global search and neighborhood search is used in this algorithm.Firstly,Max-Min Ant System which performs effectively in ant colony optimization is used to guide the global search.Then Ejection Chains（EC） is introduced to exploit the neighborhood space.Because the results generated by ejection chains depend on their original state,2-opt operation is adopted,which can help avoid instability of results.Theorems and simulations show that the new MMAS-EC outperforms traditional MMAS algorithm with less time increased in all the instances.

关 键 词：蚁群优化算法 旅行商问题 排出算法 最大-最小蚁群系统 

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