程荣

摘 要：旅行商问题是一个组合优化问题，具有重要的实际意义。而遗传算法是求解旅行商问题的典型算法之一。本文首先介绍了旅行商问题的定义以及它的研究背景、发展现状和常用算法。在此基础上，详细阐述了遗传算法原理。通过改进这些算子，改进了传统的遗传算法，提高了算法的效率，降低了它的时间及空间复杂度。本文使用路径总长度的倒数作为适应度函数，保证了解向着最优化方向发展。然后选择部分交叉算子来产生新个体，保证了迭代的效率。变异算子利用位点变异，使算法变得简单，易行。最后，使用MATLAB 语言进行编程，解决了城市数目分别为15和25时的两个实际问题。通过对这两个问题的收敛速度的对比、分析，总结了遗传算法求解旅行商问题的特点。

关键词：旅行商问题； 遗传算法； MATLAB

旅行商问题是优化组合问题研究中一个著名而经典的问题，它的研究价值也就不言而喻。在实际问题里，一个大家都熟知的例子就是利用机器给电路板钻孔的优化设计问题。此外旅行商问题的实际应用还体现在交通管理规划方面。交通管理的主要的目的是在复杂的地理网络结构中优化决定车辆的线路来减少交通费用。旅行商问题的应用例子还包括：设计安全，合理，有效率的交通网，从而减少交通拥堵；如何来规划出更好地物流线路，缩小运营界产生的成本，减少资源消耗等。

由于旅行商问题具有这么重要的实际意义，求解旅行商问题算法也就随之发展起来。最早的解决方法是线性规划，后来陆续产生了多种求解旅行商问题的算法。其中大致可以分为精确算法，近似算法，智能算法。精确算法：线性规划，动态规划，分支定界；近似算法包括：插入法，Clark& Wright算法，生成树算法，最近邻算法，概率算法等。近年来也出现了许多新的智能算法。像诸如模拟退火，蚁群算法以及遗传算法等等。

本文首先介绍了什么是旅行商问题，然后简单介绍了目前解决旅行商问题所用到的一些算法。之后详细介绍了什么是遗传算法，遗传算法的实现原理，以及遗传算法的构成。然后利用常用的MATLAB软件，使用遗传算法解决了几个实际问题。通过算法以及结果分析，找出遗传算法的优缺点，并进一步提出了改进的遗传算法。

1 旅行商问题

1.1 问题描述

旅行商问题，也叫货郎担问题，目的是求解最优线路，是一类经典的规划类问题。旅行商问题是指，一个旅行商，要去往n个不同的城市，需要每个城市都去，并且仅仅去一次，再回到最初的城市，形成一个环路，从众多可能路径中求解出一个最短的路径。

1.2 数学模型

我们将xij设定为决策变量。没有直接从城市i到达城市j的路线，我们将其赋值为xij=0。如果商人直接从城市i到达城市j，我们用xij=1来表示。我们在上述模型得到的5个式子中，第一个式子保障了路径之和最小，第二个和第三个式子分别保障从某个城市出来和进入都只是一次。而第四个式子则保障了走过的所有路径都没有回路。其中C表示集合C中元素个数。

2 算例分析

2.1 问题描述

一个旅行商人要从某一个城市出发，经过所有的城市，并且每个城市只能走一次。最终回到出发的城市，求解一个最短路径。

2.2 问题分析

1）编码方式。

我们这里使用十进制编码方式。把旅行商途经的城市的顺序序号作为遗传算法的编码。假设15 个城市的序号为1，2，…，15，那么它的任意一个全排列i1，i2，…，i15就是一个数据编码，表示一個染色体，每个染色体就代表一个解，不同解是靠染色体上不同的基因i决定的。

2）适应度函数。

由于旅行商问题的规划模型的目标函数是要求解最小值，所以适应度函数就用路径的总长度的倒数来表示。这样，符合了遗传算法的优胜略汰的搜索策略。

3）初始群体的产生。

随机生产一个大小为N且每条染色体上的基因长度都是的n初始种群，作为第一代个体。

4）选择过程。

我们需要构造一个∑f（xi）合适的隶属函数p=f（xi）∑f（xi）。然后计算出种群中每个遗传个体的适应度f（xi），从而得到种群中遗传个体适应度的和。那么我们就可以用来表示个体被选中的概率。

5）交叉过程。

首先设定交叉概率pc=0.9。其次，根据这一概率，选出要进行交叉操作的个体，并将它们两两配对。然后在染色体上1～n-1个基因编号之间随机地选出两个，之间的基因作为接下来将要进行交叉的对象。

6）变异过程。

进行完交叉操作后，以变异概率pm=0.2从群体中选出要进行变异的遗传个体。然后，随机地从1～n-1之间选择两个数作为变异点，将基因进行交换。

7）复制操作。

复制过程就是将适应度值打的个体直接复制到下一代，从而不至于丢掉性质较优的解。

2.3 问题求解结果

将程序放到MATLAB软件中执行，得到了如下结果：

2.3.1 城市数为15时的运行结果

（1）随机产生的初始解的路径总长度为4.7950e+004。

（2）迭代次数设置为c=100时的最优解路径的总长度为：2.5025e+004。

可以看出，迭代100次，产生了不错的优化效果。

但这是不是接近最终的最优解呢？下面我们又将迭代次数设置为了C=200，路径总长度为：2.4619e+004。

通过两结果进行比较知，迭代100次时基本上得到了近似最优解，而且迭代次数越多，得到的解越优。

2.3.2 城市数为25时的运行结果

（1）随机产生的初始解路径总长度1.1297e+005。

（2）迭代次数设置为c=100时的最优解路径总长度为46737e+004。

（3）迭代次数设置为C=300时路径总长度为：4.5038e+004。

容易看出，当城市的个数增加到25个时，迭代100次产生的结果与最优解的偏差还有点大，需要继续迭代。

继续进行迭代次数为500时的实验，路径总长度为： 44838e+004。这一结果接近200次迭代的解。也就是当迭代次数到200次时，为近似最优解。

2.4 结果评价

通过运用遗传算法对上面两个问题（城市数分别为15和25）求解结果可以看出，运用遗传算法能够求解旅行商问题。对于同一个问题，随着搜索次数的增多，所得到的解一般会在一定范围内波动，并且越来越好。但当增加到某一值时，函数的收敛会趋于平缓（这时可以认为达到了最优解）。通过15个样本城市和25个样本城市的迭代求解过程可以发现，当我们的样本数量比较多时，我们需要的循环搜索的次数就越多，求解完成需要的时间就越长。而且，通过上面的结果对比表我们可以发现，遗传算法求解过程中，初始解是随机产生的，对于每一次的求解，初始解的不同，问题收敛的情况也就不同，产生的最终解也不同。由此可见，遗传算法对初始解比较敏感，而且由于初始解是算法随机生成，不能人为控制，所以不容易把握。

参考文献：

[1]于莹莹，陈燕，李桃迎.改进的遗传算法求解旅行商问题[J].控制与决策，2014（8）：1483-1488.

[2]威廉·J·库克，J.Cook，郭凯声.旅行商问题[J].环球科学，2012（7）：19.

[3]章新华.遗传算法及其应用[J].火力与指挥控制，1997，18（4）：59-64.

[4]吉根林.遗传算法研究综述[J].计算机应用与软件，2004，21（2）：69-73.

[5]梁艳春，冯大鹏，周春光.遗传算法求解旅行商问题时的基因片段保序[J].系统工程理论与实践，2000，20（4）：7-12.

[6]周明，孙树栋.遗传算法原理及应用[M].国防工业出版社，1999.

[7]李敏强，徐博艺.遗传算法与神经网络的结合[J].系统工程理论与实践，1999，19（2）：65-69.