| 基于隶属云模型蚁群算法与LK搜索的TSP求解 |
| |
| 引用本文： | 张煜东,吴乐南,王水花,韦耿,颜俊,朱庆.基于隶属云模型蚁群算法与LK搜索的TSP求解[J].计算机工程与应用,2011,47(14):46-55. |
| |
| 作者姓名： | 张煜东 吴乐南 王水花 韦耿 颜俊 朱庆 |
| |
| 作者单位： | 东南大学 信息科学与工程学院，南京 210096 |
| |
| 基金项目： | 国家自然科学基金,国家高技术研究发展计划(863),高等学校科技创新工程重大项目培育资金项目,江苏省自然科学基金 |
| |
| 摘 要： | 提出一种求解TSP的算法，采用“问题无关的进化算法与问题相关的局部搜索相结合”的策略。采用基于云模型的蚁群算法来产生足够好的解；改进传统的LK算法，新加入5种搜索删除集与添加集元素的准则，以此细化搜索。将该算法用于求解TSPLIB中不同类型、城市数从48到33 810内变化的TSP，比较该学派与其他学派算法的偏离率与运行时间，结果均显示该算法更优，有效求解了TSPLIB中的非对称TSP、哈密尔顿圈问题。
|
| 关 键 词： | 隶属云 蚁群算法 LK算法 旅行商问题 非对称旅行商问题 哈密尔顿圈问题 |
| 修稿时间： | |
Improved ant colony algorithm based on membership cloud models |
| |
| ZHANG Yudong,WU Lenan,WANG Shuihua,WEI Geng,YAN Jun,ZHU Qing.Improved ant colony algorithm based on membership cloud models[J].Computer Engineering and Applications,2011,47(14):46-55. |
| |
| Authors: | ZHANG Yudong WU Lenan WANG Shuihua WEI Geng YAN Jun ZHU Qing |
| |
| Affiliation: | School of Information Science & Engineering，Southeast University，Nanjing 210096，China |
| |
| Abstract: | 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. |
| |
| Keywords: | membership cloud ant colony algorithm Lin and Kemighan＇s algorithm traveling salesmen problem asymmetrictraveling salesman problem Hamiltonian cycle problem |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程与应用》浏览原始摘要信息 |
|
点击此处可从《计算机工程与应用》下载全文 |
