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

A seagull optimization algorithm for solving TSP

作　　者：程亚南 王晓峰[1,2] 刘凇佐 刘子琳 张九龙 CHENG Yanan;WANG Xiaofeng;LIU Songzuo;LIU Zilin;ZHANG Jiulong(School of Computer Science and Engineering,North Minzu University,Yinchuan 750021,China;The Key Laboratory of Images and Graphics Intelligent Processing of State Ethnic Affairs Commission,North Minzu University,Yinchuan 750021,China)

机构地区：[1]北方民族大学计算机科学与工程学院,宁夏银川750021 [2]北方民族大学图像图形智能处理国家民委重点实验室,宁夏银川750021

出　　处：《现代电子技术》2022年第7期112-116,共5页Modern Electronics Technique

基　　金：国家自然科学基金资助项目(62062001);国家自然科学基金资助项目(61762019);国家自然科学基金资助项目(61862051);国家自然科学基金资助项目(61962002);北方民族大学重大专项资助(ZDZX201901);北方民族大学校级科研一般项目(2019XYZJK05);宁夏自然科学基金项目(2020AAC03214,2020AAC03219,2019AAC03120,2019AAC03119)。

摘　　要：旅行商问题(TSP)是典型的NPC问题,目的是对所有城市遍历一遍求路径最短,旅行商问题易于描述、易于理解,但是求解极其困难。从确定性算法到智能优化算法该问题的求解有了很大的进步。海鸥算法是近年来提出的一种新型智能优化算法,该算法对于求解组合优化问题具有良好的效果,基于海鸥算法的基本原理,采用轮盘赌方法进行初始化,近邻矩阵限制搜索空间范围,利用交叉操作指导算法的搜索顺序,攻击过程中使用概率选择交换、逆序、插入等技术不断对海鸥的路径进行优化,并结合2-opt算子增强算法的局部搜索能力,提出了一种求解TSP问题的改进海鸥算法。最后,对提出的改进算法进行数值实验,将实验结果和近年的改进算法进行对比,实验结果表明,该算法有效且求解质量得到了很好的提高。The travelling salesman problem(TSP)is a typical NPC problem that aims to minimize the path traversing all cities.It is easy to describe and understand TSP,but it is very difficult to carry out the TSP solution.The TSP solution has made great progress with the development from deterministic algorithm to intelligent optimization algorithm.The seagull optimization algorithm(SOA)is a new intelligent optimization algorithm proposed in recent years,which has good effect for solving combinatorial optimization problems.In the improved algorithm,the basic principle of the SOA is taken as the basis,the Roulette method is used for the initialization,the nearest neighbor matrix is used to limit the search space and the crossover operation is used to guide the search order of the algorithm.During the attack,probability selection exchange,reverse order,insertion and other technologies are used to continuously optimize the path of seagulls.In combination with the 2-opt operator,the local search ability of the algorithm is enhanced.On the basis of the above,an improved SOA for TSP is proposed.Finally,numerical experiments were carried out to contrast the experimental results with the improved algorithms in recent years.The experimental results show that the proposed algorithm is effective and its solution quality is improved.

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

分 类 号：TN911.1-34[电子电信—通信与信息系统]