当前位置：首页 > news >正文

2026年SEVC SCI2区，基于特殊编码和新颖优化策略的离散进化算法求解旅行商问题，深度解析+性能实测

news 2026/3/27 0:41:17

1.摘要

针对进化算法求解旅行商问题（TSP）中存在的编码和优化困难，本文提出了一种离散进化算法IGTOA，通过设计特殊整数向量编码表示TSP解，解决了传统排列编码难以进行数学运算的问题，并提出改进随机变异算子以适应新编码，引入固定片段交换方法（FFEM）结合3-Opt提升解的结构质量。

2.求解方法

编码方法

IGTOA采用 Grefenstette 编码方法（GEM），将 TSP 路径排列

π = [ π 1 , π 2 , … , π n ] ∈ Π \pi = [\pi_1, \pi_2, \dots, \pi_n] \in \Piπ=[π1,π2,…,πn]∈Π
映射为整数向量
G = [ g 1 , g 2 , … , g n ] ∈ Z [ n − 1 , n − 2 , … , 0 ] , G = [g_1, g_2, \dots, g_n] \in \mathbb{Z}[n-1, n-2, \dots, 0],G=[g1,g2,…,gn]∈Z[n−1,n−2,…,0],
其中
g 1 ∈ { 0 , … , n − 1 } , g 2 ∈ { 0 , … , n − 2 } , … , g n − 1 ∈ { 0 , 1 } , g n = 0. g_1 \in \{0, \dots, n-1\}, g_2 \in \{0, \dots, n-2\}, \dots, g_{n-1} \in \{0, 1\}, g_n = 0.g1∈{0,…,n−1},g2∈{0,…,n−2},…,gn−1∈{0,1},gn=0.
映射
μ : Π → Z [ n − 1 , n − 2 , … , 0 ] \mu: \Pi \to \mathbb{Z}[n-1, n-2, \dots, 0]μ:Π→Z[n−1,n−2,…,0]
为双射，满足
∣ Π ∣ = ∣ Z [ n − 1 , n − 2 , … , 0 ] ∣ = n ! |\Pi| = |\mathbb{Z}[n-1, n-2, \dots, 0]| = n!∣Π∣=∣Z[n−1,n−2,…,0]∣=n!

改进IRMO算子

由于编码向量Y = [ y 1 , y 2 , … , y n ] ∈ Z [ n − 1 , n − 2 , … , 0 ] Y=[y_1,y_2,\ldots,y_n]\in\mathbb{Z}[n-1,n-2,\ldots,0]Y=[y1,y2,…,yn]∈Z[n−1,n−2,…,0]中各分量满足y j ∈ y_j\inyj∈{ 0 , 1 , … , n − j } \{0,1,\ldots,n-j\}{0,1,…,n−j},且y n = 0 y_n=0yn=0，直接使用原有变异算子可能产生无效编码或降低效率。因此，本文提出改进随机变异算子 GIRMO，在变异概率P m P_mPm下对分量进行受限变异，使y j y_jyj始终保持在合法范围内，从而保证 Gref 编码有效并提升搜索效率，其时间复杂度为O ( n ) O(n)O(n)。

固定片段交换方法

固定片段交换方法（FFEM）将路径

π = [ π 1 , π 2 , … , π n ] \pi=[\pi_1,\pi_2,\ldots,\pi_n]π=[π1,π2,…,πn]

划分为num个固定长度片段，并为每个片段分配标识序列

I D = [ i d 1 , i d 2 , … , i d n u m ] ID=[id_1,id_2,\ldots,id_{num}]ID=[id1,id2,…,idnum]

随后随机选择两个不同标识并交换，重复n e ∈ [ 20 , 50 ] n_e\in[20,50]ne∈[20,50]次得到新的标识序列，再按该序列

重新拼接片段生成新路径

σ = [ σ 1 , σ 2 , … , σ n ] \sigma=[\sigma_1,\sigma_2,\ldots,\sigma_n]σ=[σ1,σ2,…,σn]

3-opt

局部搜索采用3-Opt，通过从当前路径中删除三条边并对剩余片段进行七种可能的重连来获得更短路径。将FFE与 3-Opt 结合：先对当前最优路径应用 FFEM 生成新路径，再仅对该路径执行一次 3-Opt 优化，从而在保持解质量提升的同时显著降低计算时间并提高算法整体求解效率。

3.结果展示

4.参考文献

[1] He Y, Chen G, Wang X, et al. An efficient new method for traveling salesman problem using discrete evolutionary algorithm with special encoding and novel optimization strategy[J]. Swarm and Evolutionary Computation, 2026, 101: 102306.