-
题名一种求解TSP问题的海鸥算法
被引量:1
- 1
-
-
作者
程亚南
王晓峰
刘凇佐
刘子琳
张九龙
-
机构
北方民族大学计算机科学与工程学院
北方民族大学图像图形智能处理国家民委重点实验室
-
出处
《现代电子技术》
2022年第7期112-116,共5页
-
基金
国家自然科学基金资助项目(62062001)
国家自然科学基金资助项目(61762019)
+4 种基金
国家自然科学基金资助项目(61862051)
国家自然科学基金资助项目(61962002)
北方民族大学重大专项资助(ZDZX201901)
北方民族大学校级科研一般项目(2019XYZJK05)
宁夏自然科学基金项目(2020AAC03214,2020AAC03219,2019AAC03120,2019AAC03119)。
-
文摘
旅行商问题(TSP)是典型的NPC问题,目的是对所有城市遍历一遍求路径最短,旅行商问题易于描述、易于理解,但是求解极其困难。从确定性算法到智能优化算法该问题的求解有了很大的进步。海鸥算法是近年来提出的一种新型智能优化算法,该算法对于求解组合优化问题具有良好的效果,基于海鸥算法的基本原理,采用轮盘赌方法进行初始化,近邻矩阵限制搜索空间范围,利用交叉操作指导算法的搜索顺序,攻击过程中使用概率选择交换、逆序、插入等技术不断对海鸥的路径进行优化,并结合2-opt算子增强算法的局部搜索能力,提出了一种求解TSP问题的改进海鸥算法。最后,对提出的改进算法进行数值实验,将实验结果和近年的改进算法进行对比,实验结果表明,该算法有效且求解质量得到了很好的提高。
-
关键词
海鸥算法
旅行商问题
路径优化
轮盘赌初始化
2-opt算子
局部搜索
求解质量
-
Keywords
SOA
TSP
path optimization
Roulette initialization
2-opt operator
local search
solution quality
-
分类号
TN911.1-34
[电子电信—通信与信息系统]
-