摘要
针对传统的蚁群算法在解决旅行商问题时(traveling salesman problem,TSP)存在着收敛速度慢、容易陷入局部最优等问题,提出了一种结合竞争交互策略和淘汰重组机制的异构多蚁群算法。建立一个异构多种群系统,算法采用竞争交互策略,根据不同时期各种群的汉明距离来自适应的调节交互周期;并利用竞争系数来差异化匹配交互对象,经过匹配后的交互对象之间通过最优解和信息素矩阵进行交互,通过该机制实现了算法收敛速度和多样性的平衡。算法采用了淘汰重组机制,会定期对寻优能力差的种群进行淘汰与重组,以加快算法的求解精度。采用多组不同规模的TSP算例进行仿真实验,结果表明,该算法在提高求解精度和收敛速度方面表现更优。
The traditional ant colony algorithm has many problems in convergence and diversity when solving the traveling salesman problem(TSP).Therefore,this paper proposes a heterogeneous multi-ant colony algorithm that combines the competitive interaction strategy and the eliminating-reconstructing mechanism(CEACO)to overcome these shortcomings.Firstly,the algorithm uses a competitive interaction strategy,which adjusts the interaction period adaptively according to the Hamming distance of different groups in different periods.Competition coefficients are adopted to differentiate matching interaction objects for interaction.The matched objects interact with each other through the optimal solution and pheromone matrix.This mechanism achieves a balance between algorithm convergence speed and diversity.Secondly,the algorithm uses the eliminating-reconstructing mechanism,which periodically eliminates and reconstructs the poor-searching populations to improve the solution accuracy of the algorithm.Finally,several groups of simulation experiments prove that the algorithm outperforms other methods in improving the solution accuracy and convergence speed.
作者
冯晨
游晓明
刘升
Feng Chen;You Xiaoming;Liu Sheng(Shanghai University of Engineering Science,Shanghai 201620,China)
出处
《系统仿真学报》
CAS
CSCD
北大核心
2024年第1期232-248,共17页
Journal of System Simulation
基金
国家自然科学基金(61673258,61075115)
上海市自然科学基金(19ZR1421600)。
关键词
蚁群算法
异构多种群
竞争交互
淘汰重组
旅行商问题
ant colony optimization(ACO)
heterogeneous multiple population
competitive interaction
eliminating-reconstructing
traveling salesman problem
