Computer Engineering and Applications ›› 2010, Vol. 46 ›› Issue (26): 49-52.DOI: 10.3778/j.issn.1002-8331.2010.26.017

• 研究、探讨 • Previous Articles     Next Articles

Improved culture ant colony optimization method for solving TSP problem

GU Jun-hua,FAN Pei-pei,SONG Qing-zeng,LIU En-hai   

  1. School of Computer Science and Engineering,Hebei University of Technology,Tianjin 300130,China
  • Received:2009-12-15 Revised:2010-03-23 Online:2010-09-11 Published:2010-09-11
  • Contact: GU Jun-hua

改进的求解TSP问题文化蚁群优化方法

顾军华,范培培,宋庆增,刘恩海   

  1. 河北工业大学 计算机科学与软件学院,天津 300130
  • 通讯作者: 顾军华

Abstract: Based on cultural algorithm,an improved Ant Colony Optimization algorithm(ACO) for Traveling Salesman Problem(TSP) has been proposed.In the improved algorithm,the population space and the belief space of cultural algorithm are redesigned.This algorithm uses double evolutionary mechanisms and the Max-Min Ant System(MMAS) to build the population space,and adopts 3-OPT cross operation for the current optimal solution in the beliefs pace.As the result of this double evolutionary mechanisms,the population space gets higher efficiency of evolution.The simulation results show that the improved algorithm is more effective than Ant Colony Optimization algorithm(ACO) and Cultural Ant Colony Algorithm(CACS),which has faster convergence speed and greater accuracy.

Key words: cultural algorithm, cultural ant colony algorithm, Max-Min Ant System(MMAS), Traveling Salesman Problem(TSP), 3-OPT algorithm

摘要: 在文化算法基础上提出了一种改进的用于求解TSP问题的蚁群优化算法。改进算法采用新的双层进化机制对文化算法的种群空间与信念空间进行了重新设计,用最大最小蚁群系统(MMAS)构建种群空间,在信念空间中对当前最优解进行改进的3-OPT交叉变换操作,由于采用了这种双层进化机制,种群空间获得了更高的进化效率。通过仿真实验结果表明,改进算法比传统的蚁群算法(ACO)、文化蚁群算法(CACS)效果更好,收敛速度更快,精确度更高。

关键词: 文化算法, 文化蚁群算法, 最大最小蚁群系统, 旅行商问题, 3-OPT算法

CLC Number: