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

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