融合动态邻域搜索机制的蚁群系统算法  

Ant Colony System Algorithm Combining Dynamic Neighborhood Search Mechanism

作　　者：郭文强[1] 杜正毅 GUO Wenqiang;DU Zhengyi(School of Information ManagementXinjiang University of Finance and Economics,Urumqi 830012,China)

机构地区：[1]新疆财经大学信息管理学院,新疆乌鲁木齐830012

出　　处：《自动化与信息工程》2022年第2期15-22,共8页Automation & Information Engineering

基　　金：国家自然科学基金项目(61941205);天山雪松项目(2020XS07)。

摘　　要：针对蚁群算法收敛速度慢,容易陷入局部最优解等问题,提出一种融合动态邻域搜索机制的蚁群系统(DNS-ACS)算法。首先,在蚁群系统算法的基础上,引入2-opt算子进行局部搜索,加快算法收敛速度;然后,动态调整邻域搜索范围和信息素更新规则,使其跳出局部最优,避免早熟现象;最后,利用本文提出的DNS-ACS算法对16个经典TSP算例进行仿真模拟,并与其他算法进行对比实验。实验结果表明,DNS-ACS算法的求解精度明显提高,证明了该算法的有效性。Aiming at the problems of slow convergence speed and easy to fall into local optimal solution of ant colony algorithm,an ant colony system(DNS-ACS)algorithm combining dynamic neighborhood search mechanism is proposed.Firstly,based on the ant colony system algorithm,the 2-opt operator is introduced for local search to speed up the convergence speed of the algorithm;Then,dynamically adjust the neighborhood search range and pheromone update rules to make it jump out of the local optimum and avoid premature phenomenon;Finally,the DNS-ACS algorithm proposed in this paper is used to simulate 16 classical TSP examples,and compared with other algorithms.Experimental results show that the accuracy of DNS-ACS algorithm is significantly improved,which proves the effectiveness of the algorithm.

关 键 词：蚁群算法 旅行商问题 动态邻域搜索 信息素更新 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]