摘要
ACA(Ant Colony Algorithm)是一种可以有效求解组合优化的TSP(Travelling Salesman Problem)问题的方法。然而,当TSP问题的规模较大时,该算法的求解性能将会明显减弱。本文针对大规模TSP问题提出一种基于聚类集成的蚁群算法IAPACA(Improved AP Ant Colony Algorithm)的求解方法。利用AP(Affinity Propagation)聚类对大规模旅行商问题进行处理,将大规模旅行商问题分为若干子问题,并对每个子问题用蚁群算法进行寻优。然后用改进的集成方案对子问题进行组合,得到问题的结果。最后进行TSPLIB标准库测试算例的实验仿真,实验结果表明,基于聚类集成的蚁群算法具有更好的求解效果。
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.
作者
叶家琪
符强
贺亦甲
叶浩
YE Jia-qi;FU Qiang;HE Yi-jia;YE Hao(College of Science and Technology,Ningbo University,Ningbo 315212,China;Faculty of Information Science and Engineering,Ningbo University,Ningbo 315211,China)
出处
《计算机与现代化》
2020年第2期31-35,共5页
Computer and Modernization
基金
国家自然科学基金面上项目(61875098)
浙江省大学生新苗人才计划项目(2018R405055)
国家大学生创新创业训练计划支持项目(201813277002)
关键词
大规模TSP问题
蚁群算法
AP聚类
集成方案
求解质量
large-scale TSP problem
ant colony algorithm
AP clustering
integration scheme
quality of solution
