一种求解TSP问题的海鸥算法

摘要：

旅行商问题(TSP)是典型的NPC问题,目的是对所有城市遍历一遍求路径最短,旅行商问题易于描述、易于理解,但是求解极其困难.从确定性算法到智能优化算法该问题的求解有了很大的进步.海鸥算法是近年来提出的一种新型智能优化算法,该算法对于求解组合优化问题具有良好的效果,基于海鸥算法的基本原理,采用轮盘赌方法进行初始化,近邻矩阵限制搜索空间范围,利用交叉操作指导算法的搜索顺序,攻击过程中使用概率选择交换、逆序、插入等技术不断对海鸥的路径进行优化,并结合2-opt算子增强算法的局部搜索能力,提出了一种求解TSP问题的改进海鸥算法.最后,对提出的改进算法进行数值实验,将实验结果和近年的改进算法进行对比,实验结果表明,该算法有效且求解质量得到了很好的提高.

关键词：海鸥算法、旅行商问题、路径优化、轮盘赌初始化、2-opt算子、局部搜索、求解质量

所属期刊栏目：45

分类号：TN911.1-34

资助基金：国家自然科学基金;国家自然科学基金;国家自然科学基金;国家自然科学基金;北方民族大学重大专项;宁夏自然科学基金项目;宁夏自然科学基金项目;宁夏自然科学基金项目;宁夏自然科学基金项目;北方民族大学校级科研一般项目

在线出版日期：2022-04-18（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：112-116