用于求解TSP问题的遗传算法比较研究

徐瑞超

(陕西国防工业职业技术学院机械工程学院, 西安710300)

引言

旅行商问题(Traveling Salesman Problem，TSP)源于18世纪Euler提出的旅行骑士问题，也称货郎担问题。它是一个描述起来简单，但处理起来却十分困难的组合优化问题。该问题可以简单地叙述为：一位商人准备去n座城市推销产品，需要找到一条巡回路径，使路经每一座城市之后，回到出发城市的路径最短。一些实际应用问题经过简单处理都可以转化成旅行商问题模型。如：快递配送线路[1]、灾害应急调度[2]、车辆路径规划[3]等方面的问题，经过简化处理后，都可以转化为旅行商问题的数学模型。

在小规模TSP问题的求解中，通常用到穷举法[4]、分支限界法[5]和动态规划法[6]等传统算法，但是当n较大时，这些传统的基于搜索的确定性算法就不能完美地解决问题。大规模的TSP问题复杂度大幅度增加，依靠传统算法不能解决，那么就需要一些新的算法。针对大规模TSP问题的比较好的算法有蚁群算法[7-8]、模拟退火算法[9]、启发搜索式算法[10]和遗传算法(GA)[11-13]等，另外还有一些混合的智能算法[14]。

目前，科学工作者在应用遗传算法(GA)解决大规模TSP问题方面做了大量的研究，取得了许多成果。刘世清[15]等分析了混合遗传算法、粗粒度遗传算法和两阶段遗传算法等改进遗传算法的基本原理、参数设置、遗传算子的操作方法及其各自的优缺点等。孙文彬[13]等借助交叉与小角操作优化TSP路径，将遗传算法进行并行化处理，通过增加遗传多样性来提高了TSP求解质量，结果显示该法优于最邻近法、插入法等。文艺[16]等引入选择因子，提出一种改进的交叉算子和基于种群相似度的更新策略，加快了收敛速率，取得了较好的结果。本文综合比较了部分匹配交叉算子、顺序交叉算子的遗传算法在TSP问题中的应用，提出了一种基于贪心交叉算子的改进型遗传算法，并对三种算子的优化过程与优化路径进行了数值模拟，分析了各自的优缺点。

1 旅行商问题

基于图论知识来看，TSP问题实质上就是在一个带权完全无向图中，找一个权值最小的Hamilton圈，具体可描述为：

记V=(C,E)为赋权无向图，如图1 所示。其中：C={1,2,3...n}为顶点集；E为边集，任意两顶点之间的距离为dij。已知dij>0，i,j∈C，设

(1)

则TSP问题的数学模型可表示成线性规划形式：

(2)

其中：S表示C的所有非空子集，|S|表示集合S中所含有的图V中顶点的个数。约束条件一，保证了旅行商从顶点i出来一次；约束条件二，保证了旅行商从顶点i进去一次；约束条件三，保证了旅行商在顶点集的所有子集中不会形成回路。于是满足上面三个约束条件的解就构成了一条Hamilton回路。图1 中包含四个顶点(c1、c2、c3、c4)的e1e2e3e4路径即为最优路径。

图1 赋权无向图

2 遗传算法

2.1 编码

对于包含有n座城市的TSP问题，给每座城市赋予一个特定编号，那么TSP问题的解空间就是由多个n座城市编号组成的全排列。例如，9座城市依次编号为1、2、3、4、5、6、7、8、9，如此7→5→9→8→4→3→2→6→1→7就表示一条巡回路径(染色体)，即表示商人从城市7出发顺序经过城市5、9、8、4、3、2、6、1，最后回到城市7。

2.2 适应度函数

选用巡回路径长度的倒数作为遗传算法的适应度函数，如下所示。适应度函数的值越大，表明此路径越优。

即：

(3)

2.3 选择算子

轮盘赌选择操作算子是基本遗传算法中的成员，它的基本思想是个体适应度值越高，被选中的概率也越高，被进行遗传操作的概率也就越大，换言之轮盘赌选择算子是依据概率进行选择，操作简单但因此也具有很大的不确定性。

2.4 交叉算子

经典GA的交叉算子一般使用单点交叉算子，但由于遗传算法求解TSP问题具有特殊性，以及本文中采用的编码方法限制了任意染色体(个体)中不允许有重复的基因码出现，因此若应用单点交叉算子进行操作会导致大概率产生非法染色体。故此，本文选择部分匹配交叉算子和顺序交叉算子这两个基本交叉算子，以及改进后的贪心交叉算子。

2.5 变异算子

经典GA的变异算子一般使用基因位变异算子。基于TSP问题的特殊性，本文应用逆转进化变异算子。

逆转进化变异算子要求在选择的一个父代个体中，随机选取(产生)两个逆转点，进而将逆转点之间的中间段调换位置。例如，针对父个体A随机产生两个逆转点4和7：

A:(7 5 9 | 8 4 3 2 | 6 1)

逆转得到子代个体为：

A′:(7 5 9 | 2 3 4 8 | 6 1)

变异后的个体若适应度高于父个体的适应度值则保留下来，若低于父个体适应度值，则继续保留父个体。

2.6 参数设置

在求解问题时，参数设置一般凭借经验进行取值。本文中，种群大小取100，终止迭代次数取100，交叉概率取0.9，变异概率取0.05，代沟取1.0。

3 仿真实验

3.1 三种算子的仿真优化

应用基本遗传算法对TSP问题进行求解，得到三种交叉算子求解问题规模为30座城市的TSP问题，实验数据见表1，种群大小=100，交叉概率=0.9，变异概率=0.05，代沟=1.0。

图2 (a)～2(c)依次是部分匹配交叉算子、顺序交叉算子和贪心交叉算子求解规模为30座城市的TSP问题优化过程。

图3 (a)～3(c)依次是部分匹配交叉算子、顺序交叉算子和贪心交叉算子求解规模为30座城市的TSP问题最优解巡回路径。

表1 三种交叉算子求解实验数据

图2 优化过程图

图3 最优解巡回路径图

从表1可知：贪心交叉算子求得最优解情况最好，部分匹配交叉算子次之，顺序交叉算子最差；从算法运行时间上看，贪心交叉算子运行时间最长，部分匹配交叉算子次之，顺序交叉算子最短。

从图2 可知：贪心交叉算子算法收敛速度最快，部分匹配交叉算子次之，顺序交叉算子最慢。

图3 展现了三种交叉算子最优解巡回路径的长短，从中可知贪心交叉算子最优解巡回路径无交叉，路径最短，部分匹配交叉算子次之，顺序交叉算子巡回路径最长。

3.2 不同参数设置对算法的影响

3.2.1种群规模

种群是遗传算法操作的基本对象，种群的大小影响着其多样性、算法的运行时间等。本节设置不同的种群大小来对利用不同交叉算子求解进行仿真。

图4 (a)～4(c)依次是部分匹配交叉算子、顺序交叉算子和贪心交叉算子在求解问题规模为30座城市的TSP问题时，在不同种群设置下的10次仿真实验的最优解分布图。

图4 仿真实验最优解分布图

从图4 可知：

(1) 随着种群规模的增大，三种交叉算子所求最优解都有变好的趋势。以部分匹配交叉算子为例：在求解30座城市时最优解从28502下降到25014。

(2) 随着种群规模的增大，三种交叉算子10次仿真最优解平均值呈下降趋势。

(3) 随着种群规模的增大，三种交叉算子最差解及算法运行时间呈上升趋势。

(4) 种群规模的变化对部分匹配交叉算子的影响最大，对顺序交叉算子和贪心交叉算子的影响较小。

因此可以得到如下结论：

(1) 在算法运行时间要求不高时，增大种群数量，可以改善进化过程中种群多样性，防止算法早熟，提升算法进化能力。

(2) 应用部分匹配交叉算子时，种群规模取值应不低于问题规模的2倍，不高于问题规模的3～4倍。

(3) 应用顺序交叉算子时，在求解小规模问题时，种群数可略小于问题规模的2倍。

3.2.2迭代次数

目前尚未找到合适的数学方法作为遗传算法运行的终止条件，普遍采用设置迭代次数来控制算法的运行和终止。本节设定不同的迭代次数(100,200,500)，分别用部分匹配交叉算子、顺序交叉算子和贪心交叉算子来求解不同规模(30座、50座、70座城市)的TSP问题，仿真结果见表2～表4，其种群大小=100，交叉概率=0.9，变异概率=0.05，代沟=1.0。

表2 部分匹配交叉算子不同迭代次数实验数据

表3 顺序交叉算子不同迭代次数实验数据

表4 贪心交叉算子不同迭代次数实验数据

从表2～表4可知：

(1) 随着迭代次数增加，三种算子最优解都呈现变好的趋势，算法收敛性都明显提高。

(2) 随着迭代次数增加，三种算法的运行时间均增长，其中贪心交叉算子的运行时间增长最猛。

由此可以得到如下结论：

(1) 迭代次数改变对部分匹配交叉算子影响最大，顺序交叉算子次之，贪心交叉算子最小。

(2) 贪心交叉算子的算法复杂度最高，部分映射交叉算子次之，顺序交叉算子最低。

(3) 迭代次数的设定应伴随着问题规模的变化而变化，若随意设置只会增加算法运行时间，还有可能导致算法退化。

3.2.3交叉概率

交叉算子是遗传算法中最重要的成员，它除了自身影响算法外，控制它作用大小的交叉概率在算法中也起着举足轻重的作用。本节对问题规模为30座城市的TSP问题在四种不同大小交叉概率下进行求解。

图5 (a)～5(c)依次是部分映射交叉算子、顺序交叉算子和贪心交叉算子在四种不同概率下的10次仿真实验所得最优解分布图。

图5 不同概率下的最优解分布图

从图5 可知：

(1) 部分匹配交叉算子随着交叉概率的减小，其最好解呈变坏趋势，但均值和方差都呈下降趋势；而最差解及算法运行时间变化不大。

(2) 部分匹配交叉算子在交叉概率0.9时求得最优解一次。

(3) 顺序交叉算子随着交叉概率减小，其最好解及其均值、方差都呈变好(下降)趋势；而最差解及算法运行时间变化不大。

(4) 顺序交叉算子在交叉概率为0.7时求得最优解一次。

(5) 贪心交叉算子在交叉概率为0.85、0.8、0.7时，其最好解均未变化，但在交叉概率为0.9时最好解由15824降到15695；最差解变化不大，但算法运行时间较其他两种算子有所变化(变小)。

(6) 贪心交叉算子在交叉概率为0.85、0.8、0.7时均取得最优解，但交叉概率为0.8时取得最优解二次且最早。

因此可以得到如下结论：

(1) 交叉概率对部分匹配交叉算子影响最大，顺序交叉算子次之，贪心交叉算子最小。

(2) 为了降低贪心交叉算子的算法复杂度，可适当降低交叉概率，同时其算法会更收敛。

(3) 应用部分匹配交叉算子时，交叉概率应设置大一点，但这样也会导致搜索空间移动得厉害，因此需要将算法多运行几次，以求得最优解。

(4) 对于在遗传操作中保证子代优于父代个体的能力来说，贪心交叉算子的作用最强，顺序交叉算子次之，部分匹配交叉算子最弱。

3.2.4变异概率

变异算子在遗传算法中起着避免算法过早收敛、保证种群多样性的作用，因此变异概率对算法的影响也不容忽视。本节对问题规模为30座城市的旅行商问题在三种不同大小变异概率(0.1,0.05,0.01)下，分别应用部分映射交叉算子、顺序交叉算子和贪心交叉算子进行TSP问题求解，结果分别见表5～表7，其迭代次数=100，种群大小=100，交叉概率=0.9，变异概率=(0.1,0.05,0.01)，代沟=1.0。

表5 部分匹配交叉算子不同变异概率实验数据

表6 顺序交叉算子不同变异概率实验数据

表7 贪心交叉算子不同变异概率实验数据

从表5～表7可知：

(1) 对于部分匹配交叉算子，变异概率为0.05时，最好解为25277最好；对于顺序交叉算子，变异概率为0.01时，最好解为25981最好；对于贪心交叉算子，交叉概率为0.1和0.01时，最好解为15695最好。

(2) 随着变异概率降低，部分匹配交叉算子和顺序交叉算子最优解方差都表现出先高后低，而贪心交叉算子反而是先低后高。

因此可以得出如下结论：

(1) 贪心交叉算子不易陷入局部最优，更具有全局搜索能力。

(2) 变异概率对贪心交叉算子影响最小，对部分匹配交叉算子次之，对顺序交叉算子最大。

3.2.5代沟

轮盘赌选择算子的选择思想是个体的适应度越高，被选择进行遗传操作的可能性就越大。这就导致了如果某代种群中最佳的适应度高于其他个体的适应度，则将会被大量的选择，使种群多样性降低，导致算法求得局部最优解。同时，应用基本遗传算法求解TSP问题时，等同于默认子代个体的适应度高于父代个体适应度，明显这是不一定正确的。为了弥补上述算法缺陷，引入代沟，即整个种群在每一代中没有被完全复制，体现了自然界中存在的父代个体与子代个体互相竞争的关系。

本节对问题规模为30座城市的TSP问题在代沟为1.0和0.9的设置下进行了求解。

相同参数下部分匹配交叉算子、顺序交叉算子和贪心交叉算子在有无代沟下的最优解分布图分别如图6 (a)～6(c)所示。

图6 不同代沟下的最优解分布图

从图6 (a)～6(c)可知：

(1) 部分匹配交叉算子和顺序交叉算子在加入代沟后，求得的最优解更好。以顺序交叉算子为例：30座城市的最好值从26 689降到15 175。

(2) 贪心交叉算子在加入代沟后，求得的最优解变化不明显。

(3) 三种算子在加入代沟后，从最好值均值、方差以及最差解均值、方差的角度都显示出算法收敛性大幅提升。

因此可以得出以下结论：

(1) 代沟对遗传算法的影响非常明显。

(2) 代沟对贪心交叉算子的影响不大，因此可以认为贪心交叉算子可以大概率保证所产生的子代优于父代。

(3) 加入代沟可以提高贪心交叉算子的收敛速度。

(4) 加入代沟可以提升部分匹配交叉算子和顺序交叉算子的综合性能。

4 结论

在分析研究规模为30城的TSP问题的基础上，对比了部分匹配交叉算子、顺序交叉算子以及贪心交叉算子遗传算法的求解质量和求解效率。结论如下：

(1) 从求得最优解的质量比较：贪心交叉算子最优，部分匹配交叉算子次之，顺序交叉算子最差。

(2) 从算法的复杂性比较：贪心交叉算子复杂度最高，部分映射交叉算子次之，顺序交叉算子最低。

(3) 从算法的收敛性比较：贪心交叉算子最强，顺序交叉算子次之，部分映射交叉算子最弱。

(4) 从算法的收敛速度比较：贪心交叉算子最快，部分映射交叉算子次之，顺序交叉算子最慢。

(5) 基于贪心交叉算子的遗传算法在TSP问题中具有高效性，且比普通优化算法具有更好的鲁棒性。