基于隶属云模型蚁群算法与LK搜索的TSP求解  

Improved ant colony algorithm based on membership cloud models

作　　者：张煜东[1] 吴乐南[1] 王水花[1] 韦耿[1] 颜俊[1] 朱庆[1] 

机构地区：[1]东南大学信息科学与工程学院,南京210096

出　　处：《计算机工程与应用》2011年第14期46-55,共10页Computer Engineering and Applications

基　　金：国家自然科学基金 No.60872075;国家高技术研究发展计划(863)(No.2008AA01Z227);高等学校科技创新工程重大项目培育资金项目(No.706028);江苏省自然科学基金(No.BK2007103)~~

摘　　要：提出一种求解TSP的算法,采用"问题无关的进化算法与问题相关的局部搜索相结合"的策略。采用基于云模型的蚁群算法来产生足够好的解;改进传统的LK算法,新加入5种搜索删除集与添加集元素的准则,以此细化搜索。将该算法用于求解TSPLIB中不同类型、城市数从48到33810内变化的TSP,比较该学派与其他学派算法的偏离率与运行时间,结果均显示该算法更优,有效求解了TSPLIB中的非对称TSP、哈密尔顿圈问题。This paper proposes a novel method,which combines the problem-independent evolution algorithm and problem- dependent local search,to solve TSP.This method adopts an improved ant colony algorithm based on the cloud model to gen- erate high-quality solutions,and improves the traditional LK algorithm by addition of 5 new criterions to refine the element searching in the deletion set and the addition set.Experiments on different types and city numbers ranged from 48 to 33,810 show that the proposed method is superior to algorithms not only within this school but also among other schools in re- spect of the gap and computation time.Besides,the application to asymmetric TSP and Hamilton cycle problem also demon- strate the efficacy and efficiency of the proposed method.

关 键 词：隶属云 蚁群算法 LK算法 旅行商问题 非对称旅行商问题 哈密尔顿圈问题 

分 类 号：TN911.73[电子电信—通信与信息系统]