求解TSP问题的文化蚁群优化算法  

A Cultural Ant Colony System for Solving TSP Problem

作　　者：刘升[1,2] 王行愚[1] 游晓明[2] 

机构地区：[1]华东理工大学信息科学与工程学院,上海200237 [2]上海工程技术大学管理学院,上海200065

出　　处：《华东理工大学学报（自然科学版）》2009年第2期288-292,共5页Journal of East China University of Science and Technology

基　　金：国家自然科学基金项目(60674089);“973”计划资助项目(2002CB312200);上海市重点学科建设项目(B504);上海工程技术大学基金项目(2008XY18)

摘　　要：将蚁群系统(Ant Colony System,ACS)纳入文化算法框架,提出了一种新的高效文化蚁群优化算法(Cultural Ant Colony System,CACS)。该计算模型包含基于蚁群系统的群体空间和基于当前最优解的信仰空间,两空间具有各自群体并独立并行演化。群体空间定期将最优解贡献给信仰空间,信仰空间采用随机2-OPT交换操作,对最优解进行变异优化;经演化后的解个体用来对群体空间全局信息素更新,帮助指导群体空间的进化过程,从而达到提高种群的多样性、防止早熟、降低计算代价的目的。针对典型的旅行商问题(TSP)进行对比实验,验证了所提出的算法在速度和精度方面优于传统的蚁群系统。A new efficient cultural ant colony system （CACS） is proposed by integrating ant colony system into cultural algorithm frame. The computing model consists of a ACS-based population space and a current-best-solution based belief space. Both the population space and the belief space have their own population, respectively, and evolve independently and parallel. The population space periodically contrib- utes the current-best-solution to the belief population, and the belief space continually evolves the current- best-solution by using 2-OPT random mutation. The evolved solution is then used to update global pheromone level in the population space and guide the evolutionary search so as to improve population diversity and avoid prematurity. The contrasting experiments on the typical traveling salesman problem （TSP） show that the proposed algorithm is better than standard ant colony system in speed and accuracy.

关 键 词：蚁群系统(ACS) 信息素 旅行商问题 文化算法 

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