双编码改进遗传算法求解旅行商问题

王 玉，谭代伦

(西华师范大学数学与信息学院，四川 南充 637009)

0 引言

旅行商问题(Traveling Salesman Problem，TSP)是一个经典的组合优化问题，其求解难度被证明是NP难问题[1]。在现实生活中，TSP问题广泛应用于货物零件加工顺序[2]、汽配件喷涂顺序[3]、仓储系统拣货路径规划[4]、光伏板清洁[5]等领域。

TSP问题于1959年被Dantzing等人提出[6]，被国内外众多专家学者研究，并用于测试算法效率[7]，目前已有大量研究成果。早期，求解TSP问题主要是精确型算法，如P.M.E.Shutler[8]基于分支定界算法思想，提出新的分支规则，将次梯度优化计算的最小生成树的标准下界作为算法下界，再从另一个角度去考虑最后几棵树的大部分边，使决策树的节点数增长幂为2，减少了解决TSP问题所需要的决策节点总数，降低了问题的复杂度。G.Carpaneto[9]基于子路径巡回消除方法，从三个方面对分支定界算法进行了改进，提出了一种广度优先分支定界算法，促进了成本矩阵的更新，加快了运算速度。精确算法的研究具有很强的理论意义，但只适用于求解小规模TSP问题。

自20世纪80年代以来，基于启发式规则的智能优化算法[10]兴起并被快速应用于求解TSP问题，如遗传算法[11-12]、模拟退火算法[13]、蜂群算法[14]、蚁群算法[15]、萤火虫算法[16]、粒子群算法[17]等，它们普遍具有快速搜索和求解能力，对规模更大的TSP问题也有明显效果。其中，以达尔文进化论、孟德尔遗传变异理论、模式理论为基础的遗传算法[18]逐渐受到重视，它是一种自适应全局优化的概率搜索算法，具有较强的鲁棒性、并行性，容易与其他算法结合等优点，但也存在交叉算子不易操作、容易过早收敛而陷入局部最优、收敛速度慢等缺点。为克服遗传算法存在的缺点，许多专家学者对遗传算法进行了不同的改进。陈斌等[18]引入深度强化学习思想，分离遗传算法的交叉和变异操作，将其作为智能体(agent)的动作空间，训练agent控制交叉和变异操作，把控种群进化方向。李利杰等[19]在交叉算子中融入贪婪思想，引入2opt算子和稳定状态选择机制改进算法，增强了算法的局部搜索能力，提高了算法的效率。徐佳等[20]优化适应度函数和初始种群，引入生物信息基因序列对比用于交叉算子，采用逆转算子对个体变异，使算法加快收敛速度，提高求解精度。刘海等[21]针对传统遗传算法求解TSP问题的交叉操作存在的部分缺点，构造了一种新的交叉算子，改善了算法性能。张立毅等[22]借鉴搜寻者优化算法的模糊思想与近邻策略改进变异算子，采用启发式策略设计一种反转算子，提高算法的执行效率和收敛性。刘荷花等[23]根据种群个体的多样性和分布情况，提出了计算算法截止代数的方法，再在算法中加入初始化信息并改进交叉算子，提高了算法的精确性。

综上，现有文献对遗传算法的改进主要是从遗传算子入手来改善算法性能。遗传算法求解TSP问题时交叉算子不易操作，其主要原因在于基于路径节点的序列编码方案要求个体染色体基因是不可重复的，为此，提出一种双编码改进遗传算法(Double Coding Improved Genetic Algorithm， DCIGA)。算法中，再引入一种可重复自然数编码作为第二种基因编码方案，主要作用于交叉环节，使得基因的遗传交叉不需修复，可任意设计交叉规则，从而大幅增强种群质量和多样性，提升算法性能。此外，算法还采用了多种交叉算子、变异算子轮流使用的策略，使得经交叉和变异后的个体得到不同程度的遗传进化效果，增强了算法搜索寻优能力。通过实验仿真，结果表明DCIGA算法是高效可行的。

1 TSP问题及数学模型

一般地，TSP问题可描述为：一个旅行商需要拜访n个城市，城市之间的距离是已知的，若旅行商对每个城市必须拜访且只拜访一次，求旅行商从某个城市出发并最终回到起点的一条最短路径[24]。

记n个城市序号构成集合为N={1，2，…，n}，旅行商拜访完n个城市所经过的回路记为

P={p1→p2→…→pn→p1}

(1)

其中pi∈N，pi≠pj(i≠j)，i=1，2，…，n.

若城市之间的距离矩阵为D=(dij)n×n，则TSP问题的数学模型可表示为

(2)

其中f(P)表示旅行商行走路线的总路径长度。

2 传统遗传算法

遗传算法(Genetic Algorithms，GA)是由J.Holland教授在20世纪70年代提出的，通常被称为传统遗传算法或标准遗传算法[18]。它模拟和借鉴了自然界生物进化过程中基因的遗传、交叉与突变等现象，从算法上设计了对种群个体的选择、交叉、变异这三个主要环节，被保留和遗传的个体是经过适应性评估为优的个体，从而体现生物界“适者生存、优胜劣汰”的机制，按此不断迭代和进化，直到满足某种收敛条件为止[25]。

遗传算法是一种具有全局优化能力的概率搜索算法，通用性高、并行性和鲁棒性强，已被成功运用于求解TSP问题[3]，其基本步骤为：

Step1 确定基因编码方案，设置算法参数。基因编码方案是根据优化问题的可行解特点而设计的编码结构和取值，其TSP问题通常取基于路径节点的不重复序列编码。算法参数主要包括种群规模、迭代次数、交叉概率、变异概率等。

Step2 初始化种群，即按基因编码方案的要求和种群规模的大小生成一组个体。

Step3 利用适应度函数评估种群个体的优劣。其中，适应度函数通常基于优化问题的目标函数进行构造。

Step4 选择操作，即根据个体的适应度大小，按一定策略优选出足够数量的个体构成子代种群。个体适应度越好，被选中的概率就越大。常用的选择策略有轮盘赌策略、精英策略、排序优选策略等。

Step5 交叉操作，即将子代种群的个体继续随机配对，根据交叉概率进行基因随机交换，使个体有机会获得更多优良基因，从而增强子代种群的多样性，保持较强的搜索寻优能力。

Step6 变异操作，即随机选择一些子代个体，根据变异概率对个体的某些基因位进行改变，使其突变为新的个体，进而扩大搜索寻优范围。

Step7 重复Step3—Step6，直到遗传进化操作达到迭代的终止条件。

传统遗传算法具有通用性的算法框架，步骤清楚，各个环节允许自行设计，但是也存在收敛速度慢，或收敛过早而陷入局部最优等缺点[18]。因此，针对上述各个步骤进行改进，一直是提升算法性能的主要方向。

3 双编码改进遗传算法

遗传算法求解TSP问题时，其基因编码方案最常用的是以各城市组成的路径节点序列编码，其优点是直观，对应性强，便于计算个体适应度。缺点是个体之间如果直接进行交叉操作，很容易导致两个个体出现重复的基因或基因缺失，从而变成非法个体。文献[26]提出了一种与路径节点序列编码具有一一映射关系的可重复自然数编码，为此本文在传统遗传算法基础上引入这种新编码方案，提出双编码改进遗传算法(DCIGA)。在交叉环节采用这种新编码方案，在变异环节仍使用路径节点序列编码方案，将选择操作放在变异之后，并且选择之前先将父代种群、交叉后的种群和变异后的种群进行合并排序和精英优选，以加快收敛速度，下面具体说明本文算法的各个步骤。

3.1 双编码方案

这里，双编码方案是指在算法中同时采用路径节点序列编码和一种可重复自然数编码。

路径节点序列编码就是与式(1)相对应的编码，它通常用不重复的自然数编码来表示。实际编码时可以去掉式(1)末尾处的起点城市号。例如，当n=6时，以下两个序列都是合法的编码：

P1={2，5，3，1，4，6}，P2={3，2，5，6，4，1}

可重复自然数编码在文献[26]中被提出，其基本思想是将路径节点序列编码唯一映射为可重复自然数编码，如下：

(3)

其映射规则为：qi等于P中值为i的码(记为pk)的左边比该值小的码的个数。

为便于码的生成与转换，令

(4)

则qi的计算公式为

(5)

例如，将上述编码P1映射为Q1的结果为：

P1={2，5，3，1，4，6}→Q1={5，1，3，1，0，0}

在Q1中q6=5是因为在编码P1中码6的左边比它小的码的个数为5个，其余数字也是类似得来。同理，编码P2的映射码Q2={3，2，2，0，0，0}.

分析映射码Q，可以发现它具有以下特征：

q1≡0，0≤qi

因此，映射码Q还可以去掉q1位，并表示为：

Q={qn-1，…，q2，q1，0≤qi≤i}

(6)

综上，编码Q既可根据式(4)～(5)从编码P映射得到，也可根据式(6)直接随机生成。因此，第二种编码方案具有映射规则简单、生成方式灵活、码可重复等特点，在遗传算法求解旅行商问题时可利用价值较高。为方便遗传算法调用，下面给出这两种码相互转换的算法。

算法1：PToQ(编码P转换为编码Q)

Input：城市数n，编码P={pn，pn-1，…，p2，p1}.

Output：编码Q={qn-1，…，q2，q1}.

1.InitializeQ

2.Fori=1 ton-1 do

3. Searchpk=i+1 inP

4. Calculateqiby using formula (4)

5. StoreqitoQ

6.End for

算法2：QToP(编码Q转换为编码P)

Input：城市数n，编码Q={qn-1，…，q2，q1}.

Output：编码P={pn，pn-1，…，p2，p1}.

韦兰认为，在外部制度环境和内部道德秩序发生不连续性时，道德主体将有可能突破规则和传统，拒绝外在制度的约束，形成道德焦虑。在城市化和逆城市化交互作用的今天，众多村民要么告别熟悉的家园环境，背井离乡去城市寻梦；要么怀揣着寻找机遇的美好愿望，成为新一代返乡农民工创造商机。他们面临陌生的外部环境、快速流动的人群和变动不居的习俗规范，约束人的道德秩序和道德行为也在发生转变，属于外部因素的道德观念和道德标准影响着个体，能够形成一种新形势下的道德观和道德秩序。道德失去了制度环境的外在效力，也使得他律将以一种全新的面貌得以呈现。

1.SetP=[1]

2.Fori=1 ton-1 do

3.s=i+1

4. Ifqi=0

5.insertsto the left ofP(1)

6.Else

7.insertsto the right ofP(qi)

8.End if

3.2 种群初始化和适应度函数

按照DCIGA 算法的设计思路，遗传进化将按“交叉--变异--选择”的顺序完成，期间只在交叉环节使用可重复自然数编码，其余环节仍使用路径节点序列编码，这样个体适应度计算和变异操作都不受影响。由于编码转换远比交叉操作本身的复杂性低，因此利用两次码转换完成一轮交叉操作，对遗传进化操作是值得的。

为此，本文算法的初始种群是基于路径节点序列编码(末尾不含返回起点)进行初始化。例如，当城市数n=6时，种群中的每一个个体的基因编码就是由自然数1～6的随机不重复排列构成的一个序列编码。

适应度函数的任务是对种群个体的优劣进行评估。对 TSP问题，旅行商的回路越短则个体越优，因此本文算法取目标函数(2)式为算法的适应度函数，即对种群的任意个体P，其适应度为

(7)

3.3 交叉算子

遗传算法的交叉算子试图保留更多的优良基因，提高个体适应度。由3.1节可知，第二种编码的基因是可以重复的，可以更灵活地设计交叉算子。对此，本文算法设计的交叉策略是基于第二种编码轮流选取以下三种算子对种群个体进行交叉操作：

(1)两点交叉，即随机产生两个基因点，将两个个体对应位置的基因进行交换。

(2)片段交叉，即随机产生两个基因点，将两个个体中介于这两个基因点之间的基因片段进行整体交换。

(3)一致交叉，即对两个个体的每一个对应基因点，按交叉概率进行交换。

上述三种交叉算子，对个体优良基因的改造程度逐次加重，对交叉后新个体适应度的影响依次加大。轮流运用它们，可以合理控制种群基因的进化程度，使算法的交叉效果更显著。

在执行上述交叉算子前，需要先调用编码转换的“PtoQ”算法，将路径节点序列编码P转换为可重复自然数编码Q；交叉操作结束后，再调用“QtoP”算法，将编码Q再转换为编码P。

3.4 变异策略

在遗传算法中，变异算子主要用于维持种群的多样性，保证算法的局部寻优能力，尤其是遗传进化后期其作用更为重要。由于3.3节设计的交叉算子对种群个体的交叉作用比较显著，起到了部分进化的作用，为避免破坏交叉效果，本文算法的变异策略是直接针对父代种群轮流选取以下四种变异算子之一对种群个体进行变异操作：

(1)基因换位：将待变异个体中某两个随机位置处的基因直接进行交换。

(2)基因倒序：将待变异个体中某个随机的基因片段倒序放置。

(3)基因右移：将待变异个体中某个随机的基因片段循环右移一次。

(4)基因左移：将待变异个体中某个随机的基因片段循环左移一次。

上述四种变异算子都能对个体基因产生较明显的影响，引起旅行商路径的变化，从而增加种群的多样性。因此，综合运用它们会使算法的变异效果更好。

3.5 选择算子

通过选择算子，遗传算法可以朝着理想解的方向进化。传统的选择算子，如轮盘赌策略、锦标赛策略等，充分体现了遗传算法的“优胜劣汰”机制，但在个体进化效率不高的情形下收敛速度较慢，甚至出现收敛过早的早熟现象。

考虑到上述因素，本文算法的交叉算子和变异算子都是直接对父代种群进行操作，均能使个体得到更充分的进化，因此选择算子的设计主要借鉴了精英个体选择思想。具体做法是将父代种群、交叉后的子代种群和变异后的子代种群进行合并，计算合并后的种群个体适应度值按升序排列，选取排名前N(种群规模)个个体直接作为下一代种群。

上述选择算子在变异操作后执行，相较于传统的选择算子，该选择算子合并了父代和子代种群进行选择，让遗传的各个环节中进化比较充分的个体都能被选择出来遗传到下一代中，因而其遗传进化的收敛速度将更快。

4 算法流程图

综上，DCIGA算法求解TSP问题的流程图如图1所示。

图1 DCIGA算法流程图

5 实验仿真与分析

为测试DCIGA算法的性能和有效性，下面从三个方面进行实验仿真与分析。首先对DCIGA算法双编码方案和传统遗传算法单编码方案的种群质量和多样性进行比较，然后将DCIGA算法与其他遗传算法、其他智能启发式算法在求解效果等方面进行比较。

5.1 实验准备

实验硬件环境为Intel Core i5-7200U CPU/4GB，操作系统为windows10，编程环境为matlab2019a。实验数据选自TSPLIB数据集，包括oliver30、att48、eil51、berlin52、st70、pr76、rat99七个算例。对前两个算例，DCIGA算法的种群规模和迭代次数设置为N=30、G=400；对后五个算例，DCIGA算法的种群规模和迭代次数设置为N=50、G=800。算法所需的交叉概率和变异概率均设置为Pc=0.8，Pm=0.1。

5.2 DCIGA与GA的种群比较

与传统遗传算法(GA)相比， DCIGA算法主要是引入了第二种编码，补足和增强了种群个体染色体基因的交叉能力。下面通过实验比较和分析DCIGA算法相比GA算法在种群质量和多样性上的差异和提升。

为评估种群质量，取种群个体适应度的平均值为衡量指标(记为AVGR)。对TSP问题，AVGR值越小，意味着种群个体的平均适应度越小，即旅行商路径更短，含有优良基因的个体更多，因此种群质量就更高。为评估种群的多样性，取种群中个体之间基因不相同个数的平均值为其衡量指标(记为CH)[1]。CH值越大，则种群中不同个体相同基因的含量越少，个体的差异性越明显，所代表的旅行商路径不相同的程度越大，因此种群的多样性更丰富，进而有利于更大范围内的搜索寻优。

AVGR和CH指标的计算公式如下：

(8)

(9)

其中N为种群规模，fiti是种群第i个体的适应度值，H(P1，P2)表示个体P1与P2对应位置基因值不同的个数。

对上述选取的七个算例，实验记录DCIGA算法与GA算法在运行同一个算例相同迭代次数下种群的AVGR值和CH值，再将算法在相同实验环境重复运行20次，计算出AVGR和CH指标的平均值，结果如表1所示。

从表1可以看到，相比GA算法，DCIGA算法对七个算例在种群质量和多样性上都有比较明显的改善。在种群质量上，七个算例的AVGR指标值平均下降幅度为21%，下降幅度最少的是算例att48，约为13%；下降幅度最大的是算例rat99，达到37%。在种群多样性上，七个算例的CH指标值平均提升幅度为148%，提升幅度最少的是算例rat99，约为98%，提升幅度最大的是算例oliver30，达到258%。

综合来看，采用双编码方案，增强遗传算法的交叉操作后，对改善种群质量和提升种群多样性均有比较明显的效果，为算法搜索寻优奠定了良好的基础。

表1 种群质量和多样性比较

5.3 DCIGA与其他改进遗传算法结果对比

DCIGA算法是在传统遗传算法基础上改进的，为验证该算法与其他改进遗传算法的性能，将DCIGA算法与GA算法、混合遗传算法(Hybrid Genetic Algorithm，HGA)[27]和改进遗传算法(Improve the Genetic Algorithm，IGA)[18]进行比较。

实验数据仍选取5.1节中所述七个算例，各个算法在相同实验环境中分别独立运行20次，记录并统计求解结果的最好最优解(Best)、平均值(AVG)、偏差率(Dr)、方差(PD)，将其作为算法的比较指标。 其中偏差率和方差的计算公式为：

(10)

(11)

式中，Opt为TSPLIB数据集提供的最优解。

实验结果如表2所示，当所求得的最优解优于Opt时，表中指标偏差率(Dr)和方差(PD)就用“*”表示。从表2可以看到，DCIGA算法在给定算法参数下能求得比另外三种改进遗传算法更好的最优解，当TSP问题规模较小时(算例oliver30、att48)，DCIGA算法还可以求得比TSPLIB数据集所给最优解更好的结果，其中oliver30算例的优化幅度达到了9.76%。从最优解平均值(AVG)来看，前六个算例的求解结果均优于另外三种改进遗传算法，并且多次运行时的方差(PD)值也更小，表明DCIGA算法的稳定性和鲁棒性都更强。对算例rat99，虽然IGA算法和HGA算法的平均值(AVG)和方差(PD)略优于DCIGA算法，但在最好最优解(Best)上，DCIGA算法的表现要更优，体现了它具有更强的全局搜索寻优能力。此外，DCIGA算法的所有算例最优解平均值都优于GA算法最好最优解，优化幅度约为17%～34%，且城市规模越大，两者之间差距越大。从偏差率(Dr)来看，DCIGA算法的平均偏差率低于其他算法的平均偏差率，表明DCIGA算法求解TSP问题的精度更优。

表2 4种改进遗传算法实验结果对比

综合来看，DCIGA算法优于其他的改进遗传算法，具有良好的求解性能和寻优效果，能够较好的求解TSP问题，对中小规模TSP问题的求解性能更为突出。

5.4 DCIGA与其他启发式算法结果对比

为进一步验证DCIGA算法的性能，本节将DCIGA算法与最近领域算法(The Nearest Neighborhood Algorithm，NN)[28]、模拟退火算法 (Simulated Annealing，SA)[18]、双向扩展差额结合算法(Two Directions Moving With Difference Algorithm，TDMDA)[29]、蚁群算法(Ant Colony Optimization，ACO)[30]等启发式算法的求解结果进行对比，本文中的DCIGA算法仍然在前述给定参数和实验环境下运行，如表3所示。

表3 DCIGA算法与启发式算法实验结果对比

从表3可以看到，DCIGA算法在最好最优解(Best)和最优解平均值(AVG)上都要优于其他四种启发式算法，表明该算法的整体求解性能要优于其他启发式算法，算法稳定性和全局寻优能力更强。图2为表3中DCIGA算法对3组算例所求得的最好最优解(Best)所对应的最优路径图。

(a)att48 (b)eil51 (c)pr76

6 结束语

本文在遗传算法的通用框架下，针对经典的旅行商(TSP)问题，引入一种基因可重复的编码方案，使得遗传算法设计交叉算子时更灵活和方便，既避免了非法编码个体的产生，也大大增强了种群的质量和多样性，相比算法中增加的编码转换所耗费的时间，实验表明这种做法是值得的。此外，本文还将多种交叉算子、变异算子轮流选择，作用于不同的个体，也增强了算法的局部寻优能力，特别是在迭代后期，有利于算法避免早熟，跳出局部最优。这些改进思路对促进遗传算法的运用和发展都有积极意义，和遗传算法的其他策略相结合，甚至可以进一步有效求解中大规模TSP问题，将来可以为生产实践提供更多决策依据。