遗传算法求解TSP问题的研究

摘要：主要立足于遗传算法的应用研究，完成了以下两个方面的工作：1）首先对遗传算法做必要的理论性阐述，讨论了遗传算法在应用开发中的实现；在此从基础上提出了一种用C语言描述该算法的简单实现过程。2）对遗传算法的主要应用领域及最新研究进展进行了简要的阐述；针对原有解决TSP问题的方法进行了介绍，论述了遗传算法在解决TSP问题的编码表示和遗传操作算子等方面的应用情况。

关键词：遗传算法；TSP；编码；算子；变异

中图分类号：TP301文献标识码：A文章编号：1009-3044(2011)26-6488-03

The Research of Solving TSP Based On Genetic Algorithm

WANG Ke

(Jinhua Tobacco Company Yongkang Branch, Jinhua 321300, China)

Abstract: The paper focuses on the application research of genetic algorithms, it has completed the following two aspects of the work: 1) First, making the necessary genetic algorithm theory expounded, discussing the implementation of genetic algorithm in the application development; presented a description of the algorithm realization of the simple process in C language; 2) The main applications and the latest research areas of genetic algorithms are briefly described; described the original method to solve the TSP, discussed the application that genetic algorithm solved TSP in the encoded representation and genetic operation operators and other aspects.

Key words: genetic algorithm; travelling salesman problem; encode; operator; mutation

遗传算法（Genetic Algorithm，简称GA）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。与传统的搜索算法(基于微分的搜索技术、枚举技术、和随机搜索技术)相比，遗传算法适合于非连续或非处处可微、非凸、多峰和带噪音等复杂优化问题的求解，在复杂问题求解中有着显著的优势[1]。

我们习惯上把Holland 1975年提出的GA称为传统的GA。它的主要步骤包括编码、初始群体的生成、适应性值评估检测、选择、交叉、变异。遗传算法的一般结构可描述如下：

begin

t0;

初始化P(t);

评估P(t);

while 不满足终止条件 do

begin

重组P(t)获得C(t);

评估C(t);

从P(t)和C(t)中选择P(t+1);

tt+1;

end

end

1 用遗传算法来解决巡回旅行商问题

巡回旅行商问题（Travelling Salesman Problem，简称TSP），也称为货郎担问题，是一个较古老的问题。几十年来出现了很多近似优化算法，如近邻法（nearest neighbor）、贪心算法（greedy algorithm）、最近插入法（nearest insertion）、最远插入法（farthest insertion）、双极小生成树法（double minimum spanning tree）等等。近年来，有很多解决该问题的较为有效的算法不断被推出，例如Hopfield神经网络方法、模拟退火方法以及遗传算法方法[2]。

1.1 TSP问题的描述与建模

TSP问题可以简单地描述成：已知n个城市之间的相互距离，现有一推销员必须遍访这n个城市，并且每个城市只能访问一次，最后有必须返回出发城市。如何安排她对这些城市的访问次序，可使其旅行路线的总长度最短？其数学描述如下：设有一城市集合C=｛C1, C2, …, Cn｝。其每对城市Ci,Cj ∈C间的距离为d(Ci,Cj)∈Z+。求一条经过C中每个城市正好一次的路径(Cπ(1), Cπ(2), …, Cπ(n))，使得

(1)

最小。这里(π(1), π(2), …,π(n))是(1, 2, …, n)的一个置换。若采用图论语言，TSP问题还可描述为：

设G=(V,A)是一个图，此处V是具有n个顶点的集合，A称为弧或边集；D=(d0)是与A关联的距离或费用矩阵。TSP就是要决定一条经过所有顶点正好一次(这样的回路称为一条路径或Hami1ton回路)且距离最短的回路。若对任意i , j∈V有dij=dji，则该问题称为对称的TSP；否则称为非对称TSP。若对任意的i, j, k∈V有dij+djk≥dik，则称费用矩阵满足三角不等式。当V∈R2且dij为i 和j间的直线距离时，该问题称为平面（或Euclid）TSP问题。此类问题的费用矩阵满足三角不等式。

非对称旅行商问题较难解，在本文中介绍利用遗传算法求解对称旅行商问题的方法[3]。

若对于城市V={v1, v2, v3, …, vn}的一个访问顺序为T=(t1, t2，t3, …, tn)，其中ti∈V(i=1, 2, 3，…, n)，且记tn+1=t1，则旅行商问题的数学模型为：

(2)

1.2 对TSP的遗传基因编码

在旅行商问题的各种求解方法中，描述旅行路线的方法主要有如下两类：

1) 巡回旅行商路线所经过的连接两个城市的路线顺序排列；

2) 巡回旅行路线所经过的各个城市的顺序排列。

大多数求解旅行商问题的遗传算法是一后者为描述方法的，它们都采用所遍历城市的顺序排列来表示各个个体的编码串，其等位基因为n个整数值或n个记号。

用遗传算法求解TSP问题，算法设计的重点在编码的表示，即回路的编码和遗传算子的设计方面。TSP的编码主要包括二进制表示、近邻（adjacency）表示、次序（ordinal）表示、路径（path）表示、矩阵表示和边（edge）表示等。由于二进制表示不自然且需要额外的修正算子以保证个体的合法性，在实际中很少使用。路径表示自然、直观，且易于加入启发式信息，是用得最多的一种表示策略[4]。

TSP搜索空间随着城市数n的增加而增大，所有的旅程路线组合数为(n-1)!/2。5个城市的情形对应120/10=12条路线，10个城市的情形对应3628800/20=181440条路线，100个城市的情形则对应有4.6663×10155条路线。在如此庞大的搜索空间中寻求最优解，对于常规方法和现有的计算工具而言，存在着诸多的计算困难。借助遗传算法的搜索能力解决TSP问题，是很自然的想法。但如果将一条旅程路线表示为一个n城市的排列，基于二进制编码的交叉和变异操作就不能适用，所以需要重新设计遗传操作，以适应这类遗传基因表示问题。

1.3 操作算子的设计与分析

1) 顺序表示

假定讲旅行商问题中所有城市所组成的一个列表记为W，给每个城市分配一个1～n之间的序号，将这个序号的排列也表示为W，即：

W=(v1,v2,v3,v4,v5,…, vn )

W=(1 2 3 4 5 …n)

用编码串:

T：12345678…n

来表示这样的一个城市遍历路线：从城市v1开始，依次经过城市v2、v3、v4、v5、…、vn，然后再返回到出发城市v1。

对于一个旅行商问题的城市列表W，假定对各个城市的一个访问顺序为T，T=(t1，t2，t3， …,tn),规定每访问完一个城市，就从城市列表W中将该城市去掉，则用第i（i=1, 2, 3, …, n）个所访问的城市ti在所有未访问城市列表就可表示具体访问哪个城市，如此这样直到处理完W中所有的城市。将全部gi顺序列在一起所得到的一个列表G=(g1g2g3…gn)就可以表示一条巡回路线，它即为一个个体基因。

2) 交叉算子的设计

旅行商问题对交叉算子的设计要求是：对任意两条巡回路线进行交叉操作之后，都能够得到另外两条新的并且具有实际意义的巡回路线。过去10年里，为换位表达设计了好几种交叉算子，如部分映射交叉（PMX）、顺序交叉（OX）、循环交叉（CX）、基于位置的交叉、基于顺序的交叉、启发式交叉等。

3) 变异算子的设计

旅行商问题对变异算子的设计要求是：对任意一个个体编码串进行变异操作后，所产生的新个体应该能对应于一条具有实际意义的巡回路线。如点位变异、逆转变异、对换变异、插入变异算子

2.4 基于遗传算法求解TSP问题的实现

现就基本的遗传算法框架，简要介绍其算法实现过程[4]。

2.4.1 编码与适应度函数

我们以n城市的遍历次序作为遗传算法的编码，由于在可行解群体的初始化、交叉操作及变异操作中均隐含TSP问题的合法性约束条件。故适应度函数取为哈密尔顿圈的长度的倒数(无惩罚函数)。

2.4.2 选择机制

开始，我们用随机方法产生初始化群。随着遗传算法的执行，我们保留M个较优的个体作为样本群体，以供选择；在每一代运算过程中，个体被选中的概率与其在群体中的相对适应度成正比。

2.4.3 交叉方法

我们选用的交叉方法与OX法有点类似，现介绍如下：

1) 随机在串中选择一个区域，如两父串及区域选定为：

A ＝ 1 2 | 3 4 5 6 | 7 8 9

B ＝ 9 8 | 7 6 5 4 | 3 2 1

2) 将B的区域加到A的前面或后面，A的区域加到B的前面或后面得到：

A' ＝ 7 6 5 | 4 1 2 3 4 5 6 7 8 9

B' ＝ 3 4 5 6 | 9 8 7 6 5 4 3 2 1

3) 在A'中自支配区域后依次删除与区相同的城市码、得到最终的两子串为：

A" ＝ 7 6 5 4 1 2 3 8 9

B" ＝ 3 4 5 6 9 8 7 2 l

与其它方法相比，这种方法在两父串相同的情况下仍能产生一定程度的变异效果，这对维持群体内一定的多样化特性有一定的作用，实验中也显示了较好的结果。

2.4.4 变异技术

由于在选择机制中采用保留最佳样本方式，为保持群体内个体的多样化，我们采取连续多次对换的变异技术，使可行解有较大的顺序排列上的变比。变异操作发生的概率取得比较小(1％左右)，一旦变异操作发生，则用随机方法产生交换次数K，对所需变异操作的串进行K次对换(对换的两码位也是随机产生的)。

2.4.5 “进化逆转”操作

引入“进化逆转”操作的主要目的是改善遗传算法的局部搜索能力。在针对TSP问题的遗传算法中，“逆转”是一种常见的“变异”技术。我们使用的“进化逆转”是一种单方向的(朝着改进的方向)和连续多次的“逆转”操作，即对于给定的串，若“逆转”使串(可行解)的适应度提高，则执行逆转操作．如此反复，直至不存在这佯的逆转操作为止。这一操作实际上使给定的串改良到它的局部极点，这种局部爬山能力与基本遗传其法的全局搜索能力相结合在实验中显示了较好的效果。

3 结论

按照上述算法编制的，群体规模定为100，交叉概率为0.95。变异概率为0.003，初始可行解群体由随机产生。结果表明：

1) 当n≤15时，随机样本实验表明，本算法可100％搜索到用穷举法求得的最优解。

2) 当15≤30时，我们对组样本进行了测试，结果表明本算法能收敛到一稳定的“最好解”（难以确认其最优性）；多次实验的误差结果为0。

鉴于TSP问题的特点，许多方法只能解决小规模TSP[5]。处理大规模TSP的一个自然的想法是：把整个网络分成若干区和层次，每个层次中的每个区作为一个小规模TSP，用现有算法求解；再把每一层视为每一区作为一点的又一个小规模TSP，如此逐区逐层求解；最后按某种区、层连接原则连接各区和层，便可得到大规模TSP的一个次优解。分区分层法的关链在于：① 如何分区分层；② 各区、层如何连接；③ 小规模问题采用何种算法。SA法在n

参考文献：

[1] Ansari N,Hou putational Intelligence for Optimization[M].Boston:Kluwer Academic Publishers,1997.

[2] Mitchell M.An introduction to genetic algorithms[M].Cambridge,MA:The MIT Press,1996.

[3] Kernighan B W,Picke R.The Practice of Programming[M].MA:Addison-Wesley Longman Inc,1999.

[4] 党建武,靳蕃.神经网络方法在解MTSP中的应用[J].电子学报,1998,26(5):59-63.

[5] 孙惠文,靳蕃.一种求解TSP的改进型遗传算法[C]//神经网络理论与应用研究'96,1996:286-289.