基于遗传算法求解TSP 问题的研究及Matlab 实现

杨锦涛， 赵春香， 杨成福

（云南师范大学信息学院， 昆明 650500）

0 引 言

TSP 问题、即巡回旅行商问题，是组合优化领域中的一个典型问题。 现实生活中的很多实际应用问题都可以简化为TSP 问题。 TSP 问题可以用图论描述为：已知带权完全图G， 求一条使得路径总和最小、且经过所有顶点的回路。 TSP 问题虽然描述简单、容易理解，但是求解是很困难的。 当问题的规模较小时，仅使用枚举法就能找到一条最优路径，但当城市数量较多时，即使用计算机也无法将解全部列举，要求出TSP 问题的最优解是不可能的。

遗传算法是一种自组织、自适应的全局寻优算法，因其潜在的并行性、较高的鲁棒性，在应用研究方面取得了很多可观的成果，被广泛应用于函数优化、组合优化、生产调度、自适应控制、图像处理、机器学习、数据挖掘、人工生命、遗传编程等领域。

1975 年，Holland［1］受生物学中生物进化和自然选择学说的启发，提出了著名的遗传算法。 2006年，何燕［2］对遗传算法进行改进，将其应用到车间调度领域。 2010 年，蒋波［3］将遗传算法应用于车辆路径优化问题，指出遗传算法求解该问题的优越性，并对其做出了改进，实验证明改进后的遗传算法能够有效解决此类问题。 2013 年，乔阳［4］将遗传算法和Ostu 图像分割法进行改进后结合在一起进行图像分割实验，得到了满意的结果。

遗传算法是模拟生物进化的过程发展而来的一种算法，从一定规模的解集（初始种群）开始，通过选择、交叉和变异，将适应度低的解（个体）淘汰掉，将适应度高的解（个体）保留下来，并产生新的解（个体），生成新的解集（种群），通过不断地迭代，使解集（种群）中的解（个体）越来越接近问题的最优解。 生物学和遗传算法概念之间的对应关系见表1。

表1 生物学和遗传算法概念对照Tab. 1 Comparison of biological and genetic algorithm concepts

本文针对TSP 问题构建完整的遗传算法体系，将求解TSP 问题几种常用的交叉算子和变异算子两两组合在一起，分别对具体的TSP 问题实例进行求解，从所得的最优解和求解的时间两方面对实验结果进行分析和总结，探究使用不同的交叉算子和变异算子时遗传算法求解对称式TSP 问题的效果［5］。

1 遗传算法求解TSP 问题

1.1 编码

编码是指按照一定的构造方法，将问题的可行解转变为遗传算法能直接处理的个体。 常用的编码方式有二进制编码、近邻编码、次序编码、路径编码［6］。

使用路径编码求解TSP 问题，不仅编码过程简单易操作，而且编码结果非常直观，即首先对城市进行编号，然后以城市编号作为城市的编码，因此本文选择使用路径编码方式对城市进行编码。

1.2 初始种群

一般地，初始种群采用随机方法生成，如果种群规模为M，则随机生成M个个体。

1.3 适应度函数

适应度函数用于对种群中的个体进行优劣程度的评价，由于算法在搜索最优解的过程中主要以个体的适应度作为依据，所以如果适应度函数构建不当，很可能导致算法的收敛速度缓慢、甚至无法收敛，即适应度函数直接决定着算法的收敛能力和寻优能力。

对于TSP 问题，适应度函数一般取路径总和的倒数，具体定义公式见如下：

其中，n表示城市的数量；T＝（t1，t2，…，tn） 为种群中的一个个体；d（ti，tj） 表示城市i到城市j的距离。 TSP 问题为最小值问题，由适应度函数可知，路径总和与个体适应度呈倒数关系。

1.4 遗传操作

1.4.1 选择算子

选择是用选择算子对个体进行筛选的过程，这一过程中，差的个体被保留下来的概率小，好的个体被保留下来的概率大，会使种群中的个体向最优解进化。 常用的选择算子有轮盘赌选择、最佳个体保存选择、锦标赛选择和排序选择［7］。

轮盘赌选择是TSP 问题求解最常用的选择算子，即使用适应度值计算出每个个体被选择的概率，并根据该概率值对种群中的个体进行选择。 本文也使用轮盘赌选择作为选择算子，并在轮盘赌的基础上添加最佳个体保存选择，即把种群中出现过的适应度值最高的个体保留下来，避免种群中优秀的个体在遗传操作中被淘汰或破坏。

1.4.2 交叉算子

个体交叉是为了实现种群的更新，而交叉算子是进行交叉的手段，定义了个体之间以怎样的方式交叉。 对于不同问题，由于编码方式的不同，交叉算子也有所不同。 对此拟做研究分述如下。

（1）部分匹配交叉（PMX）：首先采用随机方式在父体中确定2 个位置，由2 个位置确定一个交叉段，然后将2 个父体的交叉段进行交换，最后根据交叉段之间的映射关系消除子代中的重复基因。

（2）顺序交叉（OX）：首先从父体中随机选择2个位置，由2 个位置确定一个基因段，然后将父体A的该基因段复制到子代A’的对应位置，最后将父体B除父体A被选择的基因段之外的基因依次复制到子代A’ 的其余位置，同理可得到子代B’。

（3）循环交叉（CX）：首先将父体A的第一个基因复制到子代，然后在父体B中的相同位置查看基因，随后在父体A中找到该基因复制到子代的相同位置，并在父体B中查看相同位置的基因，重复此步骤，直到在父体B中找到的基因已经在子代中，停止循环，在父体B中找到剩余的基因，并按照顺序复制到子代中的剩余位置。

1.4.3 变异算子

变异操作的主要目的是维持种群多样性，在遗传算法后期，个体交叉产生新个体的能力弱，通过个体变异可以进一步产生新个体，扩大搜索空间。 接下来给出剖析论述如下。

（1）对换变异。 首先用随机方式在父体中确定2 个位置，然后交换这2 个位置上的基因。

（2）倒位变异。 用随机方式在父体中确定2 个位置，以确定一个基因段，然后将其进行逆序排列。

（3）插入变异。 用随机方式在父体中确定一个位置，以确定一个待插入的基因，再用随机方式确定2 个位置，以确定插入点，最后将待插入的基因放入插入点。

1.5 遗传算法求解TSP 问题具体步骤

根据上文选择的实现技术构建完整的遗传算法体系后，对TSP 问题实例进行求解的具体步骤如下：

Step 1获取城市数据，对城市进行编号。

Step 2初始化种群。

Step 3适应度评价。

Step 4执行选择操作，采用轮盘赌选择对个体进行筛选，选出足够数量的个体。

Step 5执行交叉操作，将选择操作中选出的个体两两组合作为父染色体，判断是否进行交叉，如果进行交叉，则按照选定的交叉算子进行交叉。

Step 6执行变异操作，将执行交叉操作后的每个个体作为父染色体，判断是否进行变异，如果进行变异，则按照选定的变异算子进行变异。

Step 7完成变异后，执行最佳个体保存策略，判断当前种群中的最优解是否优于历史最优解。 如果是，更新历史最优解，否则找出种群中最差的解，用最优解将其替换掉。

Step 8判断是否继续进行迭代，若是，回到Step3；否则，结束迭代，输出最优解。

将前述的3 种交叉算子和3 种变异算子两两组合在一起，共有9 种组合方式，见表2。 基于表2 中列出的9 种组合，重复对TSP 问题进行求解。

表2 9 组交叉算子和变异算子Tab. 2 9 sets of crossover and mutation operators

2 实验及结果分析

2.1 实验仿真

本文使用Matlab 实现上文构建的遗传算法，从TSPLIB 中选择测试样例进行具体分析。 TSPLIB 是包含对称旅行商问题、哈密顿回路问题、以及非对称旅行商问题的多种实例数据的文件库，数据规模多样。 本文在对每个测试样例进行求解时，改变算法的交叉算子和变异算子，进行多次重复的实验，从问题的最优解和求解时间两方面对几组交叉算子和变异算子求解TSP 问题的效果进行分析比较。

在完成算法的编程后，初步设置参数，对实例Oliver30 进行求解，根据实验结果对算法的参数进行调整，最终选定迭代次数G为500，交叉概率Pc为0.9，变异概率Pm为0.2，种群规模M根据待求解问题的规模来确定。 一般地，城市个数越多，种群规模越大，对30 个城市的实例Oliver30，种群规模取100。 用上述9 组交叉算子和变异算子分别对Oliver30 求解10 次的结果见表3。

表3 遗传算法求解Oliver30Tab. 3 Genetic algorithm for Oliver30

以文献［8］中求得的最优解423.74 作为参考值，从表3 可以看出第2 组、第5 组、第8 组交叉算子和变异算子的求解结果都比较接近参考最优解，且较稳定，说明参数设置较合理。 其中一次求解的收敛曲线如图1 所示，最优路线如图2 所示。 其中，以圆圈标记的点为路线起点，其与路线终点用虚线相连，其余路线用实线连接。

图1 Oliver30 收敛曲线Fig. 1 Convergence curve of Oliver30

图2 Oliver30 最优路线图Fig. 2 Optimal roadmap of Oliver30

2.2 实验结果

从TSPLIB 中选择测试样例进行求解，本文总共选择了5 个实例，分别是ulysses16、dantzig42、eil51、eil76、eil101，根据问题的规模为每个实例设置合适的种群规模（M）。 其中，ulysses16、dantzig42、eil51 实例的种群规模取100，eil76 实例的种群规模取150，eil101 实例的种群规模取200，分别用上述9组交叉算子和变异算子求解10 次，记录10 次求解结果的最好值（Best）、 平均值（AVR） 和偏差率（Dr），以及求解的平均时间（Time），这里的偏差率可由式（2） 来计算：

其中，Opt是TSPLIB 数据集提供的最优解。

实验结果见表4～表8。

表4 遗传算法求解ulysses16Tab. 4 Genetic algorithm for ulysses16

表5 遗传算法求解dantzig42Tab. 5 Genetic algorithm for dantzig42

表6 遗传算法求解eil51Tab. 6 Genetic algorithm for eil51

表7 遗传算法求解eil76Tab. 7 Genetic algorithm for eil76

表8 遗传算法求解eil101Tab. 8 Genetic algorithm for eil101

为了方便对比，将每个实例求解结果中的偏差率（Dr） 和求解的平均时间（Time） 分别统计在一起，由于实例ulysses16 问题规模小，坐标数据也容易处理，不管选择哪种交叉算子和变异算子，求解结果都很接近最优解，因此在进行偏差率的比较时不将其考虑在内，具体见表9、表10。

表9 偏差率对比Tab. 9 Deviation rate comparison

表10 求解平均时间对比Tab. 10 Comparison of average solving time

3 实验结论

根据上述实验结果，可以得出如下结论：

（1）表9 中的偏差率描述了采用不同的交叉算子和变异算子时，所求得的最优解与TSPLIB 中给出的最优解的差距，偏差率越小，说明算法求得的结果越接近最优解，算法的寻优能力越好。 从表9 中可以看出，第2 组数据总是小于第1 组和第3 组、第5 组数据总是小于第4 组和第6 组、第8 组数据总是小于第7 组和第9 组，这说明每种交叉算子和逆转变异组合在一起时，问题的求解结果总是比与对换变异和插入变异组合在一起时更接近最优解。 由此可知，遗传算法使用逆转变异作为变异算子时比选择对换变异和插入变异作为变异算子的寻优能力更强。

（2）表10 是采用每组交叉算子和变异算子求解每个实例10 次所花时间的平均值，所花的时间越少，说明算法的搜索速度越快，执行效率越高，由于变异操作比较简单，所以遗传算法的执行效率主要由交叉操作决定。 从表10 中可以看出，遗传算法采用顺序交叉和循环交叉时，即使采用不同的变异算子，所花的时间也基本相同，但是采用部分匹配交叉所花的时间会因为变异算子的不同而有所不同。 对于每一个实例，在得到的解的质量差别不大的情况下，遗传算法使用部分匹配交叉所花的时间最多，使用循环交叉所花的时间最少。

综上所述，对于比较简单的TSP 问题，由于使用遗传算法总能求得与最优解很接近的解，所以选择何种交叉算子和变异算子对算法的寻优能力影响不大，但是使用部分匹配交叉会花费比较多的时间，会导致算法的执行效率低，因此交叉算子选择循环交叉比较合适。 对于不是总能求得最优解的TSP问题，与对换变异和插入变异相比，使用逆转变异会使算法具有更强的寻优能力，找到的最优解更接近最优解，使用部分匹配交叉和顺序交叉会花费比循环交叉更多的时间，使算法的执行效率变低，而且找到的最优解也不会更优。

4 结束语

本文对几种常用的交叉算子和变异算子求解TSP 问题的效果进行了研究。 实验结果表明，在几种常用的交叉算子和变异算子中，选择循环交叉和逆转变异算法的执行效率最高，寻优能力最好，这能为遗传算法中交叉算子和变异算子的选择提供一定的参考，同时有利于设计出更好的交叉算子和变异算子，提高算法的性能。