基于聚类集成的蚁群算法求解大规模TSP问题

doi:10.3969/j.issn.1006-2475.2020.02.007

计算机与现代化

基于聚类集成的蚁群算法求解大规模TSP问题

(1.宁波大学科学技术学院，浙江宁波315212；2.宁波大学信息科学与工程学院,浙江宁波315211）

收稿日期:2019-06-02 出版日期:2020-03-03 发布日期:2020-03-03
作者简介:叶家琪（1998-），男，浙江温州人，本科生，研究方向：智能优化算法,E-mail: 770599628@qq.com；通信作者：符强（1975-），男，江西玉山人，副教授，博士，研究方向：集成电路设计自动化，智能优化算法,E-mail: fuqiang@nbu.edu.cn。
基金资助:
国家自然科学基金面上项目（61875098）；浙江省大学生新苗人才计划项目(2018R405055)；国家大学生创新创业训练计划支持项目(201813277002)

Ant Colony Algorithm Based on Clustering Integration for Solving Large-scale TSP Problems

(1. College of Science and Technology, Ningbo University, Ningbo 315212, China;
2. Faculty of Information Science and Engineering, Ningbo University, Ningbo 315211, China)

Received:2019-06-02 Online:2020-03-03 Published:2020-03-03

摘要/Abstract

摘要： ACA（Ant Colony Algorithm）是一种可以有效求解组合优化的TSP（Travelling Salesman Problem）问题的方法。然而，当TSP问题的规模较大时，该算法的求解性能将会明显减弱。本文针对大规模TSP问题提出一种基于聚类集成的蚁群算法IAPACA（Improved AP Ant Colony Algorithm）的求解方法。利用AP（Affinity Propagation）聚类对大规模旅行商问题进行处理，将大规模旅行商问题分为若干子问题，并对每个子问题用蚁群算法进行寻优。然后用改进的集成方案对子问题进行组合，得到问题的结果。最后进行TSPLIB标准库测试算例的实验仿真，实验结果表明，基于聚类集成的蚁群算法具有更好的求解效果。

关键词: 大规模TSP问题, 蚁群算法, AP聚类, 集成方案, 求解质量

Abstract: Ant Colony Algorithm (ACA) is a Travelling Salesman Problem (TSP) to effectively solve the combination optimization. However, with the increased scale of TSP, traditional ACA has failed to effectively solve a large-scale TSP. The paper proposes a solving method based on Improved AP Ant Colony Algorithm (IAPACA) for large-scale TSP. With the AP clustering, the TSP is divided into sub-problems, for which the optimal solution is sought. Then the consequence of the problem is acquired through combination of the sub-problems with improved scheme. Finally an experiment simulation for test calculating example from TSPLIB standard library is conducted. The experimental results show that IAPACA has better effect than that of the traditional ACA.

Key words: large-scale TSP problem, ant colony algorithm, AP clustering, integration scheme, quality of solution

中图分类号:

TP301

叶家琪1，符强1，2，贺亦甲1，叶浩1 . 基于聚类集成的蚁群算法求解大规模TSP问题[J]. 计算机与现代化, doi: 10.3969/j.issn.1006-2475.2020.02.007.

YE Jia-qi1, FU Qiang1,2, HE Yi-jia1, YE Hao1 . Ant Colony Algorithm Based on Clustering Integration for Solving Large-scale TSP Problems[J]. Computer and Modernization, doi: 10.3969/j.issn.1006-2475.2020.02.007.

参考文献

［1］赵莉,董玉民. 新型改进量子蚁群算法及其TSP应用［J］. 电脑知识与技术, 2017,13(35):214-216. 〖HJ0.68mm〗
［2］ LIN Y Y， ZHANG J. An application of ant colony optimization algorithm in TSP［C］// 2012 5th International Conference on Intelligent Networks and Intelligent Systems. 2012:61-64.
［3］张立毅,肖超,费腾. 基于细菌觅食的改进蚁群算法［J］. 计算机工程与科学, 2018,40(10):1882-1889.
［4］杨昌昊,张琢. 基本蚁群算法在解决TSP问题中参数选择的研究［J］. 网络安全技术与应用, 2018(5):26-28.
［5］许能闯. 基于改进蚁群算法的TSP问题研究［J］. 软件导刊, 2018,17(2):56-59.
［6］冯志雨,游晓明,刘升. 分层递进的改进聚类蚁群算法解决TSP问题［J］. 计算机科学与探索, 2019(8):1280-1294.
［7］杨从锐,钱谦,王锋,等. 改进的自适应遗传算法在函数优化中的应用［J］. 计算机应用研究, 2018,35(4):1042-1045.
［8］吴天羿,许继恒. 基于混合遗传算法的模糊需求车辆路径问题［J］. 解放军理工大学学报(自然科学版), 2014,15(5):475-481.
［9］ YU Y Y, CHEN Y, LI T Y. A new design of genetic algorithm for solving TSP［C］// 2011 4th International Joint Conference on Computational Sciences and Optimization. 2011:309-313.
［10］裴皓晨,娄渊胜,叶枫,等. 一种求解旅行商问题的改进混合粒子群算法［J］. 计算机与数字工程, 2018,46(2):218-221.
［11］ZHI X H, XING X L， WANG Q X, et al. A discrete PSO method for generalized TSP problem［C］// Proceedings of 2004 International Conference on Machine Learning and Cybernetics. 2004,4:2378-2383.
［12］易云飞,林晓东,蔡永乐. 求解旅行商问题的改进粒子群算法［J］. 计算机工程与设计, 2016,37(8):2195-2199.
［13］徐练淞,潘大志. 一种求解TSP问题的改进遗传蚁群算法［J］. 智能计算机与应用, 2017,7(3):34-36.
［14］袁亚博,刘羿,吴斌. 改进蚁群算法求解最短路径问题［J］. 计算机工程与应用, 2016,52(6):8-12.
［15］许凯波,鲁海燕,程毕芸,等. 求解TSP的改进信息素二次更新与局部优化蚁群算法［J］. 计算机应用, 2017,37(6):1686-1691.
［16］EWBANK H， WANKE P， HADI-VENCHEH A. An unsupervised fuzzy clustering approach to the capacitated vehicle routing problem［J］. Neural Computing & Applications, 2016,27(4):857-867.
［17］章宁,陈钦. 基于AUC及Q统计值的集成学习训练方法［J］. 计算机应用, 2019,39(4):935-939.
［18］〖JP3〗张恒山,高宇坤,陈彦萍,等. 基于群体智慧的簇连接聚类集成算法［J］. 计算机研究与发展, 2018,55(12):29-37.
［19］庞永明,钟才明,程凯. 基于聚类集成的蚁群优化与受限解空间的TSP算法［J］. 中国科学技术大学学报, 2016,46(9):780-787.
［20］ZHU Y, YU J, JIA C Y. Initializing K-means clustering using affinity propagation［C］// 2009 9th International Conference on Hybrid Intelligent Systems. 2009:338-343.
［21］ARORA P, VIRMANI D, VARSHNEY S. Substantiation of K-means and affinity propagation algorithm［C］// 2017 7th International Conference on Cloud Computing, Data Science & Engineering. 2017:82-85.
［22］朱红,丁世飞. 基于属性区分能力和AP聚类的属性粒化方法［J］. 计算机科学, 2015,43(2):95-97.
［23］李新春,郭欣欣. 基于可靠AP选择和深度置信网络的室内定位算法［J］. 计算机应用研究, 2018,35(8):2469-2473.

[1]	张雄, 潘大志, . 融合邻域搜索策略蚁群算法求解带时间窗口的车辆路径问题[J]. 计算机与现代化, 2022, 0(03): 98-102.
[2]	曲建波, 孙剑伟. 基于蚁群算法的导航卫星功率增强任务规划[J]. 计算机与现代化, 2021, 0(02): 104-108.
[3]	高月仁, 吴涛, 高峡. 基于蚁群算法优化的路由频率动态择径的研究[J]. 计算机与现代化, 2020, 0(12): 32-37.
[4]	李显良1,2，周庆平2，谭长庚3，谭焱良2，徐则阳2. 基于蚁群算法的城市体育设施优化选址[J]. 计算机与现代化, 2020, 0(03): 33-.
[5]	梁晶亮,黄军胜,白树军,王鹏,李睿. 基于蚁群算法的电力数据网络APT攻击预警模型[J]. 计算机与现代化, 2019, 0(01): 95-.
[6]	付永忠，潘云峰. 基于改进蚁群算法的垂直旋转式贴片机贴装顺序优化[J]. 计算机与现代化, 2017, 0(8): 17-.
[7]	张建恒，黄蔚，胡国超. 基于LDA模型和AP聚类的主题事件抽取技术[J]. 计算机与现代化, 2017, 0(12): 77-81+87.
[8]	凌云翔1,2,宋志远1,张世海1,马力2. 基于蚁群算法的高原地区车辆运输路径优化问题[J]. 计算机与现代化, 2016, 0(9): 77-82.
[9]	宋琪，敬超. 面向多核系统的蚁群最优化能耗调度算法[J]. 计算机与现代化, 2016, 0(6): 91-96.
[10]	蔡明，左勇安. 基于MapReduce的混合蚁群算法研究[J]. 计算机与现代化, 2016, 0(10): 6-.
[11]	雷玉梅. 基于改进遗传算法的大规模TSP问题求解方案[J]. 计算机与现代化, 2015, 0(2): 34-.
[12]	李媛祯，杨群，段汐. 基于均衡更新蚁群算法的飞机排序调度[J]. 计算机与现代化, 2015, 0(2): 57-.
[13]	蔡文哲，王斌君. 一种QoS平面蚁群路由算法的设计与实现[J]. 计算机与现代化, 2015, 0(12): 15-.
[14]	陈曼青1，武子荣1，崔伟宁1，常婷婷2. 改进蚁群算法在装备保障路径选择中的应用[J]. 计算机与现代化, 2015, 0(11): 113-117.
[15]	朱卫宵，祝前旺，陈康. 基于改进蚁群算法的海上编队传感器资源分配模型[J]. 计算机与现代化, 2014, 0(12): 15-18+22.

基于聚类集成的蚁群算法求解大规模TSP问题

Ant Colony Algorithm Based on Clustering Integration for Solving Large-scale TSP Problems

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价