遗传算法求解TSP问题的具体方法及其时间复杂性研究
-
遗传算法求解
TSP
问题的具体方法及其时间复
杂性研究
邢冲
(
上海交通大学计算机系
学号
5010339138)
摘要<
/p>
：
首先介绍遗传算法解决
TSP
问题的基因表示方法以及相应的几种交叉变异
方法。
然后研究不同的方法与参数设置对于路径最优解，
路径平均值以及所用处
理器时间的影响，主要研究方向是在尽可能短的时间内求出
TSP
问题的次优解。
得出结论：使用路径基因表示法，选择较大的变异率（<
/p>
0.3
左右），使用倒置变
异算法进行求
解，能够得到较好的次优值（处理器时间：
2000
，
100
个城市，大
致可以达到相距最优值
1%-2%
的效果），同时速度比较快。此研究针对那些只需
次优解，但对时间要求比较高的问题有一定指导意义。
关键字
:
遗传算法
TSP
联赛
排序
次优解
时间复杂度
引言：
TSP(Travelling
Salesman
Problem)
是一个著名的
NP
组合优化问题
.
旅
行商需要以尽可能少的路程遍历所有城市
,
回到出发点
.TSP
具有很大的
广泛性
,
无论是城市交通问题
,
航空问题
,
还是集成电路制造问题都需要解决
相应的
TSP
问题
.
对于
TSP
问题
,
穷举的时间复杂度为
N!(N
为城市数量
)
,
随着
N
增加时间以
指数级增加
,
对于如今的硬件技术这样的时间复杂度是难以接受的
.
而
利用遗传
算法
(GA)
求解
TSP
是个不错的选择
.GA
是一种模拟生命进化的算法
;
它利用适者
< br>生存的进化原则
,
通过演化逐步逼近问题的最优解
.
本文将讨论使用
GA
求解
TSP
问题的各种具体方法和及其参数设置的影响
.
1.
基因的表示方法
TSP
问题可以选择城市序列作为基因。首先对城市进行编号，比如
10
个城市
0
，
1
，……，
9
旅行序列：
4-1-2-3-0-5-9-8-7-6
则基因为（
4
，
1
，
2
，
3
，
0
，
5
，
9
，
8
，
7
，
6
）。这样的表示方法需要
解决交叉的问题，普通的交叉方法会引起不合理的基因，比如
父代一
:(0,1,2,3,4,5,6,7,8,9)
父代二
:(9,8,7,1,2,3,4,5,6,0)
子代的可能结果
:(
一点交叉
,
交叉位置假设
5)
(0,1,2,3,4,3,4,5,6,0)
(9,8,7,1,2,5,6,7,8,9)
这样的子代结果显然是不符合
TSP
问题要求的，
而且这样方法使得不合理基因在
子代中占绝对优势比例，为了解
决这一问题，尝试以下两种方法：
改变基因编码，
使用
Grefenst
ette
等提出的一种新的巡回路线编码
（以下简
称
G
法）。编码描述如下：
对于旅行商问题的城市列表
W
，假定对
各个城市的一个访问顺序为
T
：
T=(
T1,T2...Tn)
规
定
每
访
问
完
一
个
城
市
，
就
从
城
市
< br>列
表
W
中
将
该
城
市
去
掉
，
则
用
第
i(i=1,2,3...,n)
个所访
问的城市
ti
在所有未访问城市列表
W
-{t1,t2,...ti-1}
中的对应位置序号
gi(1
<=gi<=n-i+1)
就可表示具体访问哪个城市。
G=(
g1 g2
g3....gn)
就可表示一条巡回路线。
[1]
这样
编码交叉得出的就是合理基因，变异时只要保证
<
br>主要思想是首先按照两点交叉方法进行交换，然后根据两个基因交叉区域的
gi
得
到的也将是
合理基因。
特点：父代交叉点之前的性状得到继承，交叉点之后的性状丢失。
基因编码路径表达
:
就是上述提到的方法。
现在通过改变交叉和变异方法
来避
免不合理基因的产生。
交叉方法：
(Partially
Matched crossover)
。
映射关
系，修改相应城市编号，使得子代基因合理化。
特点：保留城市的绝对访问顺序。
(Ordered Crossover)
主要思想是从一个
父代中挑选一个子序列并保存另一个父代其它城市的相
应序列来构造子代。
特点：保留相对访问顺序。
(Cycle Crossover)
主要思想：两个父代之
间可能组成一些不相交的循环回路，交换其中几个循
环回路的城市编码就可产生新的基因
。
特点：保留城市的绝对位置。
变异方法：
1.
倒置：选择基因中的两个位置，颠倒两个位置中间的字串
如
（
0 1
2 3 |4 5 6 |7 8 9
）
倒置结果：（
0 1 2 3 |6 5 4| 7 8
9
）
2.
交
换：交换两个随即位置处的基因。
如
（
0 1 2 3 4 5 6 7 8
9
）
交换结果：（随即位置
1
和
5
）：（
0 5 2 3 4 1 6 7 8 9
）
3.
插入：随机选择一个城市插入一个随机位置。
如
（
0 1 2 3 4 5 6 7 8
9
）
插入结果：（随即选择位置
4
，随机插入位置
8
）：
如
（
0 1 2 3 5 6 7 8 4
9
）
2.
各种基因表示法的效果比较
变异率
:0.2
群体规模
:50
选择算法
:
排序选择
变异
:
路径编码使用倒置方法
,
而
G
法使用普通的随即改变
一位的方法
.
(
本实验的城市如无特
殊说明
,
即为分布在
9*9
矩形定点的
100
个城市，城市之
间的路径为平面上两点的直线距离，相邻两城市的发距离定义为一个单位
)
进化代
1000
3000
5000
10000
均值
:
121.8
108.16
106.6
106.46
PMX
最优值
:
118
105.8
104.5
104.14
处理器时间
:
925
2486
3995
7758
均值
:
120.05
106.87
106.46
105.79
OX
最优值
:
114.99
104.9
104.9
103.13
处理器时间
:
865
2350
3819
7477
-