郭文强 杜正毅
融合动态邻域搜索机制的蚁群系统算法*
郭文强 杜正毅
(新疆财经大学信息管理学院,新疆 乌鲁木齐 830012)
针对蚁群算法收敛速度慢,容易陷入局部最优解等问题,提出一种融合动态邻域搜索机制的蚁群系统(DNS-ACS)算法。首先,在蚁群系统算法的基础上,引入2-opt算子进行局部搜索,加快算法收敛速度;然后,动态调整邻域搜索范围和信息素更新规则,使其跳出局部最优,避免早熟现象;最后,利用本文提出的DNS-ACS算法对16个经典TSP算例进行仿真模拟,并与其他算法进行对比实验。实验结果表明,DNS-ACS算法的求解精度明显提高,证明了该算法的有效性。
蚁群算法;旅行商问题;动态邻域搜索;信息素更新
旅行商问题(travelling salesman problem, TSP)是指给定一系列城市和每两座城市之间的距离,求解访问每座城市一次并回到起始城市的最短回路,是一类标准的组合离散优化问题[1],也是一个NP难问题。
TSP有精确算法和启发式算法2种求解方法。其中,精确算法包括切割平面法、动态规划法、分支定界法[2]等,该类方法可有效求得TSP的最优解,但需要指数时间,不适用于大规模的TSP;启发式方法包括蚁群优化算法(ant colony optimization, ACO)[3]、帝国竞争算法[4]、模拟退火法[5]、猫群算法[6]、禁忌搜索算法[7]、粒子群优化算法[8]、人工蜂群算法[9]等,该类算法能够在有限的时间内得到问题的满意解,是解决TSP的常用方法。
蚁群算法是具有代表性的群智能算法之一[10],由DORIGO Marco于1992年提出,并将其应用于解决TSP,取得较好效果。之后,各国学者不断优化……