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

2022-05-13 13:35:38郭文强杜正毅
自动化与信息工程 2022年2期
关键词:优化信息

郭文强 杜正毅

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

郭文强 杜正毅

(新疆财经大学信息管理学院,新疆 乌鲁木齐 830012)

针对蚁群算法收敛速度慢,容易陷入局部最优解等问题,提出一种融合动态邻域搜索机制的蚁群系统(DNS-ACS)算法。首先,在蚁群系统算法的基础上,引入2-opt算子进行局部搜索,加快算法收敛速度;然后,动态调整邻域搜索范围和信息素更新规则,使其跳出局部最优,避免早熟现象;最后,利用本文提出的DNS-ACS算法对16个经典TSP算例进行仿真模拟,并与其他算法进行对比实验。实验结果表明,DNS-ACS算法的求解精度明显提高,证明了该算法的有效性。

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

0 引言

旅行商问题(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,取得较好效果。之后,各国学者不断优化……

登录APP查看全文

猜你喜欢
优化信息
超限高层建筑结构设计与优化思考
房地产导刊(2022年5期)2022-06-01 06:20:14
民用建筑防烟排烟设计优化探讨
关于优化消防安全告知承诺的一些思考
一道优化题的几何解法
由“形”启“数”优化运算——以2021年解析几何高考题为例
订阅信息
中华手工(2017年2期)2017-06-06 23:00:31
基于低碳物流的公路运输优化
现代企业(2015年2期)2015-02-28 18:45:09
展会信息
中外会展(2014年4期)2014-11-27 07:46:46
信息
建筑创作(2001年3期)2001-08-22 18:48:14
健康信息
祝您健康(1987年3期)1987-12-30 09:52:32