一种求解TSP问题的混合遗传算法

张玉州，梅海俊，徐廷政

(安庆师范大学计算机与信息学院，安徽安庆246133)

旅行商问题(TSP)是一类应用在组合优化和路径规划等领域中著名的NP-hard问题，由美国学者Dantzig于1954年提出[1]。因TSP问题广泛应用于如物流配送、智能交通控制、电路板钻孔等方面，所以近年来引发了众多学者的关注，并取得一系列的研究成果[2-3]。对于较小规模的TSP问题，精确算法能快速地取得最优解，但难以应对规模较大、结构较复杂的问题。于是学者提出在不能获得全局最优的情况下，寻找高质量的近似解来求解TSP问题的启发式算法，包括遗传算法（GA）[4-5]、粒子群算法、模拟退火算法、禁忌搜索算法、蚁群算法等以及此类算法的混合算法或改进算法[6-7]。在遗传算法中，通过产生高质量的初始解可以提高求解问题的速度，甚至改进最终解的质量[8]。因此，本文在遗传算法的种群初始化上采用生成二种初始解的策略，分别采用最近邻域（NN）算法[9]以及个体随机生成策略，既保证种群的多样性，也提高了初始解的质量。遗传算法虽然有较好的全局搜索能力，但是难以对局部空间进行搜索，导致进化后期搜索效率偏低，解质量不高。因此引入局部搜索算法可以较好地解决遗传算法的早熟收敛问题，从而提高解的质量。常用的局部搜索有k-opt（2-opt，3-opt等）以及Lin-Kernighan[10]（LK），旨在对局部进行优化，通过施展局部扰动改进一条路径，其算法优点是运算速度快，但缺陷是邻域的搜索不够彻底，这导致寻找的解更多是次优的。因此本文借鉴限量弧路由问题[11]中的单点插入算子（SI）、交换算子（Swap）两种局部搜索，并结合2-opt组成一种特有的局部搜索算子集合，以提高对邻域的搜索能力。

1 TSP问题的描述

TSP问题可定义为给定n个节点无向完全图G=(V，E，r)，要求在G中遍历所有的节点形成简单回路C，使C上所有边的权值和最小，其中V={1，2，…，n}是图的节点集，表示被访问的城市，E是连接V中两个不同顶点的边集，r为边的权值集合。其基于图论的旅行商问题的数学模型定义如下：

（1）式为目标函数，为旅行商所经路径长度的最小化，其中dij表示城市i到城市j的权重；（2）式与（3）式一起表示每个城市有且只有一次被旅行商经过；（4）式为旅行商在任何一个城市真子集中不能形成循环；（5）式表示决策变量的取值，xij=1表示旅行商已经遍历过的城市，xij=0则代表旅行商未曾经过该城市。

2 混合遗传算法

遗传算法是一种基于生物进化理论发展起来的广为应用的、高效的随机搜索与优化方法。通过随机编码策略产生初始群体，初始群体里个体定义为种群的染色体，每条染色体代表问题的解，这些染色体通过选择、交叉、变异算子进行反复迭代，最终得到问题的满意解。

2.1 编码

本文在TSP问题中采用顺序表示的编码方法，每一个数字代表一个城市，遍历所有的城市产生一条染色体即产生一个解。以8个城市为例，城市编码是1～8的数字，若生成的染色体为12345678，则表示从城市1出发依次经过城市2、3、4、5、6、7、8最终回到城市1的一条路径回路。

2.2 适应度函数

假设由n个城市构成的染色体为p1|p2|...|pn-1|pn，则此个体的适应度函数值：

其中，d(pi,pi+1)表示路径中相邻的城市i到城市i+1的距离。此适应度函数f表示旅行商遍历所有城市并回到起点城市所产生路径距离的倒数。适应度函数越大代表染色体品质越好，即总路径长度越短；反之则表示染色体品质越差，即总路径长度越长。

2.3 局部搜索算子

在算法选择策略期间，最优的染色体不进行交叉，在迭代次数有限的情况下，往往可以得到比较优秀的结果，但是也容易造成种群泛滥，导致算法早熟收敛。而当遗传算法采取合适的局部优化方法时，通过施展局部扰动改进一条路径，提升对邻域的搜索能力，可以使算法的性能得到较大幅度的提升。本文采用3种局部搜索策略形成一种特有的局部搜索算子集合，其中SI，Swap能够精细地对个体邻域进行搜索，并且利用2-opt的扰动过程增加搜索维度，这样不仅克服了算法对单一邻域的过分依赖，也扩大了局部搜索范围。具体的局部搜索算子如下：

（1）SI：在一条染色体中，将每个基因分别插入到所有路径的各个位置，寻找最优插入位置，获取邻域解，比较其与原解的适应度大小。若邻域解的适应度大于原解的适应度，则前者替换后者。

（2）Swap：在一条染色体中，将每个基因分别与所有路径中各个位置的基因进行互换，寻找最优交换位置，得到邻域解，对其与原解进行适应度比较，并进行与上述（1）相同方式的替换。

（3）2-opt：在一条染色体中，随机在此条染色体中选取一段区间，将该区间内所有的基因序列进行翻转，区间外的基因不做改动，直接复制到子代染色体中，倒置区间中的基因序列也复制到代染色体中，形成一邻域解，并按上述规则进行个体替换。

2.4 初始化种群

遗传算法中初始化种群的质量影响算法的全局性能，基本遗传算法随机生成的初始种群中染色体适应度低且算法效率低下。本文算法的种群初始化采用两种生成策略：最近邻域法、随机生成法。最近邻域法过程如下：

Step1：随机选择一个城市为起点城市，在剩余未旅行的城市中选择距离最近的城市作为第二个城市；

Step2：比较剩余未旅行的城市到当前城市的距离，选择距离最近的城市作为下一个城市；

Step3：重复Step2直到旅行完所有城市再回到起点城市，构成一条完整的路径，得到一个解。

因为最近邻域算法存在每一步决策的短视行为，所以将导致在构造路径的后阶段可能需要连接距离较远的城市才能构造成完整路径，这容易造成个体生成同质化的缺陷。鉴于此，本文采用随机生成法来提高初始化种群的多样性。最近邻域法相较随机生成法，产生的种群个体在初始时就保持较高的适应度，提高了算法的收敛速度。

2.5 选择算子

选择算子使用轮盘赌选择法，个体选择的概率与适应度大小成正比。假设种群规模为M，则个体被选择的概率为，其中fi为第i个个体的适应度，pri为第i个个体被选择的概率，得出选择概率后，于[0,1]区间产生一个均匀分布的随机数来选择个体进行下一步操作。为保证算法的收敛性，算法采用精英保留策略。

2.6 交叉算子

交叉算子采用顺序交差法(OX)，从父代A随机选一个编码子串，放到子代A′的对应位置；子代A′空余的位置从父代B中按照B中的顺序选取，但不能重复已经选取的编码。同理得到子代B′，由于很难直接找到适应问题的交叉概率Pc，需要通过经验值和反复实验来确定。交叉算子过程如下：

父代 A：875|193|0624，父代 B：583|470|9216经过交叉后得到：

子代 A′：584|193|7026，子代 B′：851|470|9362。

2.7 变异算子

变异算子主要为了维护种群的多样性，防止算法陷入局部最优，并对当前解的邻域作一定程度的搜索，本文采用多次对换变异算子。当变异概率小于Pm时，产生不大于城市数目的随机数r，染色体按照变异策略随机产生2个位置，进行r次2个位置间基因的交换。为了说明多次对换变异算子过程，假设r=1，即只进行一次对换变异，过程如下：父代（123456789）经变异后得到子代（127456389），变异概率Pm一般取值较小。

2.8 HGA的步骤描述

HGA具体步骤描述如下。

Step1采用2.4节所述方法生成初始种群pop，规模定义为scale，设置染色体交叉概率Pc、变异概率Pm和最大进化代数Tmax，评价种群各个体的适应度；

Step2令当前代数t=1；

Step3挑选当前代适应度最高的个体直接赋予子代，并依据2.5节的轮盘赌选择策略挑选scale-1个子代个体，得到过渡种群pop′；

Step4从种群pop′挑选适应度最高的个体Nmax，将其加入到新种群pop*；

Step5令个体生成次数k=1;

Step6从pop′选取个体：N1，N2，按照概率Pc进行交叉生成子个体M1，M2；

Step7对个体M1，M2按照变异概率Pm进行变异操作生成子个体K1和K2；

Step8对个体K1和K2按照2.3节所述SI、Swap、2-opt 3种局部搜索算子分别进行局部搜索操作，从而得到优秀邻域解，并插入到pop*中；

Step9 k=k+1；

Step10若k＜=scale/2-1，则转至Step6继续产生新的个体。若pop′尚存个体Nlast，则对其进行变异操作，并插入到pop*；

Step11对pop*所有个体进行局部搜索操作；

Step12以pop*更新种群pop；

Step13 t=t+1；

Step14若t＜=Tmax，则转Step3继续执行，否则结束算法。

3 实验结果及分析

本文采用Java语言对所提HGA进行实现，对TSPLIB中的测试样例进行计算，并对比GA、NN、双向扩展差额算法（TDMDA）[12]、分层融合算法（HFA）[13]以及HGA共5种算法的求解结果。其中GA是基本遗传算法；NN为典型的构建型算法；TDMDA是基于NN的改进的算法，主要区别为每次选择延伸方向的规则不同；HFA通过建立分层模型规避算法路径中不合理的边，从而得到较好的实验结果。实验环境：windows7系统，intel（R）Core（TM），i3-4160 CPU@3.60 GHz。

3.1 参数设置及测试样例

种群规模N=100，最大进化代数T=200，交叉概率Pc=0.5，变异概率Pm=0.085。为了验证算法的有效性，选取了TSPLIB样本案例库中规模有代表性的20个算例为测试数据，并且每个测试样例独立运行30次。

3.2 实验结果对比

（1）单个算例Att48

HGA对测试算例Att48的30次运行结果中，最优的路径长度为10 628，最差的路径长度为10 812，平均路径长度为10 678。算例Att48运行结果的最优路径示意图如图1所示。其余4种算法均未能达到最优路径，其中HFA相比能求得较好的结果，得出的最优结果为10 753。

图1 HGA算法得到的Att48最优路径轨迹图

（2）TSPLIB测试样例集运行结果

为了更好地说明算法的有效性，本文对所选取的20个测试样例分别采用5种算法求解，其结果如表1所示。

表1 5种算法求解20个TSP测试算例结果对比

表1中，算例名称为TSP的实例名称及其测试算例包含的城市数目；平均解和最优解分别表示算法的30次运行结果的平均质量和最优解质量，并且均用百分号表示，计算方式：（求解得路径长度-最优解路径长度）/最优解路径长度×100%，解质量的数值越低代表算法越优秀。5种算法GA、NN、TDMDA、HFA以及HGA算法都因为生成初始解解集的不同，使得每次实验得出的最优解都不相同，故而都为不确定性的算法，需要进行重复实验得出结果。

最优解方面。由表1可知在求得最优路径方面，HGA有明显的提升，城市数目不大于100的测试算例共有12个，其中有9个均求出最优解路径，其余3个最优解质量均不超过1%，说明本文算法在求得城市数目不大于100的TSP算例上，可以取得较好的结果甚至达到最优解。在剩下8个测试算例中，HGA算法有2个测试算例KroB150和KroA200的最优解质量略低于HFA算法，远远高于其余的3个算法。并且从表1中可以看出HGA算法最优解质量的平均值为最优，达到1.11%。5种算法的最优解质量对比折线

图2 5种算法最优解质量对比

通过实验仿真发现混合遗传算法在求解小规模TSP问题上的寻优能力具有较为明显的提高，比较5种算法的解质量，HGA算法在大部分TSP算例上优于其他4种算法，并且通过图2，图3可以直观地看出HGA算法在解质量方面一直趋于稳定状态，证明了本文算法的鲁棒性和有效性。

4 结论

局部搜索是求解组合优化问题的重要组成部分，当遗传算法引用合适的局部优化方法时，可以使算法的性能得到较大幅度的提升。本文基于SI、Swap以及2-opt 3种邻域搜索和遗传算法中2种初始解生成策略，提出一种混合遗传算法HGA。通过对TSPLIB中的20个测试样例进行计算，对比GA、NN、TDMDA、HFA以及HGA共5种算法的求解结果，验证了算法的有效性和稳定性。图如图2所示。

平均解质量方面。TSP为最小化问题，解的数值越低代表对应算法越优秀。GA的平均解质量数值最高，为61.10%，代表其算法性能最差；NN算法和TDMAA算法的平均解质量相近，分别为26.43%和27.72%；HFA算法的平均解质量提升明显，达到7.45%；本文提出的HGA算法相较其他算法有较为明显的优势，平均解质量为4.6%，说明本文算法在20个算例上，每次求出的结果与最优解路径相近，证明算法有较好鲁棒性。5种算法的平均解质量对比折线图如图3所示。

图3 5种算法平均解质量对比