一种基于离散进化算法、采用特殊编码及创新优化策略的旅行商问题高效新方法
《Swarm and Evolutionary Computation》:An efficient new method for traveling salesman problem using discrete evolutionary algorithm with special encoding and novel optimization strategy
【字体:
大
中
小
】
时间:2026年02月03日
来源:Swarm and Evolutionary Computation 9.6
编辑推荐:
何一超|陈国新|王希昭|欧阳海滨|孟曼曼|陈菊河北地质大学信息与工程学院,中国石家庄市,050031摘要为克服现有进化算法解决旅行商问题时的局限性,本文提出一种基于群论优化算法和特殊编码的新的TSP求解方法。首先,提出了一种新的编码方法,使用特殊整数向量作为个体编码来表示TSP解
何一超|陈国新|王希昭|欧阳海滨|孟曼曼|陈菊河北地质大学信息与工程学院,中国石家庄市,050031摘要为克服现有进化算法解决旅行商问题时的局限性,本文提出一种基于群论优化算法和特殊编码的新的TSP求解方法。首先,提出了一种新的编码方法,使用特殊整数向量作为个体编码来表示TSP解,该方法被证明与使用排列表示TSP解完全等价。它解决了在使用进化算法求解TSP时无法运用基本数学运算构建进化方程的瓶颈问题。其次,通过限制每个分量的取值范围,提出了一种改进的随机变异算子,使得GTOA非常适合结合新编码方法求解TSP。第三,提出了一种新的优化方法——固定片段交换法,用于改善TSP解的结构。将FFEM与3-Opt相结合,可通过简单优化当前最优解大幅提升算法性能。最后,基于GTOA提出了离散进化算法IGTOA用于求解TSP。为验证IGTOA的效率,将其用于解决TSPLIB中的65个基准实例。根据计算结果,首先分析了结合FFEM与3-Opt的必要性,然后通过与7种最先进的TSP求解进化算法比较,表明IGTOA在获得最优解、稳定性以及求解速度方面都具有优异表现,更具竞争力。引言组合优化是计算机科学、运筹学和应用数学中的重要研究领域,已被广泛应用于路径规划、资源分配、物流调度、制造、装配规划、电力系统设计、不确定性下的优化问题以及时间依赖型优化等多个领域。在各种组合优化问题中,旅行商问题一直是一个备受关注的重要问题,其目标是在给定图中找到所有哈密顿回路中最短的回路。许多实际问题都可以转化为TSP或其变体,如物流运输、机器人路径规划、印刷电路板钻孔、作业车间调度、电信网络设计以及QUAV跟踪控制等,这些问题都可以在TSP框架内得到有效建模和求解。由于TSP属于强NP难问题,尽管其描述较为简单,但其计算复杂度却呈指数级增长。随着TSP实例规模的增大,确定性算法的运行时间会急剧增加,因此不适合用于快速解决实际应用中的大规模TSP问题。因此,目前关于TSP的研究主要集中在非确定性算法上,其核心目标是提出快速高效的非确定性算法来求解TSP。进化算法是一种典型的非确定性算法,由于其固有的隐式并行性和强大的全局搜索能力,已被广泛用于求解TSP。例如,姚等人将交叉和变异算子引入量子粒子群优化算法,提出了遗传量子粒子群优化算法,这是一种结合遗传算法与量子粒子群优化算法来求解TSP的方法。Gülcü等人提出了一种并行协作混合算法PACO-3Opt,将蚁群优化与3-Opt相结合。Mahi等人则结合PSO、ACO和3-Opt的特点,提出了PSO-ACO-3Opt混合算法来求解TSP。Khan等人提出了一种改进的人工蜂群算法,该算法包含了基于交换操作的八条更新规则以及K-opt操作。Zhong等人提出了一种混合离散人工蜂群算法,采用阈值接受准则作为接受规则。Osaba等人还提出了一种改进的离散水循环算法来求解TSP。近年来,利用进化算法求解TSP的研究依然活跃,研究人员提出了许多新方法。例如,Panwar等人提出了一种离散灰狼优化器,通过结合2-Opt和汉明距离来求解TSP。Saji等人提出了一种离散蝙蝠算法,该算法结合了基于Levy飞行的随机游走与蝙蝠运动机制,并引入了中性交叉算子以提高群体的多样性和收敛性。Ali等人提出了一种离散差分进化算法,该算法基于改进的映射机制、基于k-means的修复方法以及多种变异策略。Gunduz等人提出了一种名为DJAYA的离散Jaya算法,对初始解生成策略和更新规则进行了修改,同时整合了八种变换算子。Huang等人提出了一种基于启发式信息的离散 shuffled frog-leaping算法,该算法采用了利用最近邻信息的个体生成算子以及四种改进策略。Jati等人提出了一种离散科莫多算法,通过引入改进的边构建算子和专门的边破坏算子来求解TSP。此外,Xu等人还提出了一种离散差分创造搜索算法,整合了多种搜索策略。尽管在利用进化算法求解TSP方面已取得诸多成果,但通过分析不难发现,以下两个局限性已成为制约性能提升的瓶颈。首先,现有研究通常使用集合Π={π|π是{1,2,…,n}的排列}中的排列作为个体编码。虽然这种编码直观且易于评估,但由于排列的有效可行运算极为有限,且无法使用基本数学运算构建排列的进化方程,这就导致生成新个体的路径单一,难以实现算法性能的显著突破。其次,几乎所有研究都依赖2-Opt、3-Opt或其变体来提升算法性能。这种依赖不仅耗费大量计算资源,而且缺乏对新的有效策略的探索。迄今为止,还没有提出任何新策略来通过结合2-Opt或3-Opt来提升算法性能,这也是现有基于进化算法的问题求解方法性能未能显著提升的原因之一。群论优化算法是一种基于群直积Z[m1,m2,…,mn]={0,1,…,m1}×{0,1,…,m2}×?×{0,1,…,mn}的离散进化算法,其中mj≥1为整数,j=1,2,…,n。其进化方程中的群运算本质上是基本数学运算中的模n加法、减法和除法运算。因此,为克服上述局限性,本文提出了一种基于GTOA的有效的TSP求解新方法。首先,借鉴参考文献[37]中的方法,提出了一种适合求解TSP的特殊编码方法,即使用特殊整数向量,并给出了这种新编码与TSP路径之间的快速转换算法。然后,基于局部重组策略,提出了一种新的优化方法——固定片段交换法,用于改善解的结构。将该方法与3-Opt结合使用,可大幅提升TSP解的质量。本文的主要贡献如下:(1)提出了一种特殊的编码方法,使用离散域{0,1,…,n?1}×{0,1,…,n?2}×?×{0}中的元素作为个体编码来求解TSP。该方法不仅与使用集合Π中的排列表示TSP解完全等价,而且非常适合使用模n加法、减法和乘法等基本数学运算来构建进化方程。(2)提出了一种改进的反转和随机变异算子,使得GTOA非常适合使用{0,1,…,n?1}×{0,1,…,n?2}×?×{0}中的元素作为个体编码来求解TSP。(3)提出了一种新的优化方法——固定片段交换法。该方法不仅能改善TSP解的局部结构,而且与3-Opt结合使用时还能大幅提升算法性能。(4)提出了一种基于GTOA和新编码方法的离散进化算法IGTOA用于求解TSP。该算法被用于解决TSPLIB中的65个TSP基准实例,并与7种最先进的TSP求解进化算法进行了比较。比较结果表明,IGTOA具有更大的优势与竞争力。本文的其余部分安排如下:第2节介绍TSP的数学模型以及GTOA的基本原理。第3节首先提出了一种特殊的个体编码方法,并证明了其与使用排列表示TSP解的方法完全等价。接着,提出了一种改进的变异算子,以更好地适应新的编码方法。第三,提出了一种固定片段交换法,用于在与3-Opt结合使用时提升TSP解的质量。最后,提出了一种基于GTOA和新编码方法的离散进化算法IGTOA用于求解TSP。第4节首先给出了IGTOA解决TSPLIB中65个TSP实例的计算结果,然后分析了结合FFEM与3-Opt的必要性与有效性。最后,通过与7种最先进的TSP求解进化算法比较,验证了IGTOA的高效性与卓越竞争力。第5节对本文进行总结,并指出未来研究的方向。章节要点旅行商问题TSP可以这样描述:给定一组城市C={1,2,…,n},其中每个元素代表一个城市,以及一个距离矩阵D=(dij)n×n,其中dij表示城市i与城市j之间的欧几里得距离,i,j∈{1,2,…,n}且i≠j。目标是为商人设计一条路线,使其从一个城市出发,依次访问其余每个城市恰好一次,最后返回起始城市,使得总行驶距离最小。定义矩阵X=(xij)n×n,其元素为……TSP解的特殊编码方法由于GTOA是为离散空间{0,1,…,m1}×{0,1,…,m2}×?×{0,1,…,mn}上的组合优化问题设计的,其个体被编码为该空间中的整数向量,而这些向量无法直接表示TSP的解。此外,GTOA的进化算子是基于整数加法群中的模m运算构建的,这会导致个体中某些分量的值为0,从而无法直接表示TSP的路径(即{1}的排列)。基于仿真的比较与分析本节使用TSPLIB [46]中的65个实例来验证所提方法的有效性。所有计算都在一台配置如下的一台笔记本电脑(LAPTOP-ABED80EB)上进行:第13代Intel? Core? i9-13980HX处理器,2.20 GHz,16 GB内存(可用15.6 GB)。操作系统为Microsoft Windows 11。该算法是用C++编程语言实现的,并在Code::Blocks环境中进行编译。结论与未来工作本研究提出了一种新的编码方法,使用{0,1,…,n?1}×{0,1,…,n?2}×?×{0}中的整数向量来表示TSP解。该方法彻底克服了使用排列作为TSP解时无法运用模加法、模减法和模乘法等基本数学运算构建进化方程的缺陷。此外,还提出了一种新的优化方法FEEM,用于改善解的结构,它能大幅提升TSP解的质量。CRediT作者贡献声明何一超:撰写——初稿、方法论、形式分析、概念构思。陈国新:撰写——初稿、软件、数据整理。王希昭:指导、调研、概念构思。欧阳海滨:撰写——审稿与编辑、调研、形式分析。孟曼曼:可视化、验证、软件。陈菊:可视化、验证。利益冲突声明我们声明与任何可能不当影响我们工作的个人或组织不存在财务或个人关系,也不在任何产品、服务及/或公司中拥有可能被视为影响我们观点的专业或其他个人利益。致谢我们感谢主编及匿名审稿人的宝贵意见和建议,它们帮助我们大幅提升了这篇文章的质量。本文得到了河北省自然科学基金(F2020403013)和河北省高等教育科学研究专项任务(基础研究重点培育)(JCZX2026013)的支持。