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

MMAS-EC algorithm for solving traveling salesman problem

针对蚁群算法在求解旅行商问题容易出现搜索精度不高的问题,提出一种结合排出算法的最大-最小蚁群系统算法(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.