论文导读:：本文将重点讨论该算法在求解中小规模旅行商问题时的性能。本文给出的二点组合算法就是一种环路改造算法。与经典的蚁群算法相比相比。
关键词：旅行商问题，二点组合算法，蚁群算法
1 引言
解旅行商问题(TravelingSalesman Problem,TSP)是一个著名的NP-Hard问题，由于该问题的实际模型在路径、网络、分配等优化问题中有着广泛的应用，故长期以来吸引着许多领域的研究人员采用各种方法对它进行求解[1-2]。它可以简单描述为:给出一条遍历给定的若干个城市中所有城市的最短路径[3]。目前，研究TSP问题主要采用启发式算法，环路改进算法就是一类典型的启发式算法，即通过比较目标解和局部最优解的优劣而逐步改变解[4-5]。
 本文给出的二点组合算法就是一种环路改造算法，其步骤是选取一条合法汉密尔顿环路，作为目标解，任取两个顶点删除与之相关的边，形成2至4个环路片断，对这些环路片断进行排列组合，尝试寻找更优的解替换目标解[6]。重复上述步骤，直到选定环路任意两点蚁群算法，目标解都无法进一步优化。与经典的蚁群算法相比相比，时间复杂度相等，但计算效率和计算误差性能皆优于后者[7-8]。本文将重点讨论该算法在求解中小规模旅行商问题时的性能，从而说明新算法的实用性。
2 二点组合算法性能分析
本节将以实际测试结果从多个不同侧面分析二点组合算法的时间复杂度、计算效率、计算误差等性能，测试全部采用随机起始环路进行计算，以保证试验性能不受初始环路的影响免费论文网。
2.1 实测数据的要求和环境
(1) 测试环境：联想开天4600 （CUP P4 1.7G，内存 256M）安装Window XP 2002操作系统。
(2) 测试内容：利用TSP-LIB中的数据实例，采用EUC_2D地图格式，结点范围为50-500，地图数量为40。
(3) 测试方法： 对40组不同地图，运行二点组合算法1000次（部分运行10000次），保留最好结果，称为最小解。距阵值为四舍五入求整。
(4) 误差计算方法：所有地图均提供通过证明的最佳解。
误差=（最小解-最佳解）/最佳解
2.2 计算精度分析
使用二点组合算法，对30组规模不同的TSP问题求解结果，最小解为计算1000次的结果，最优解目前已证明的最优解，计算时间的单位为毫秒，计算结果如表1所示。
结点数量与误差之间的关系如图1所示。根据图1可知，结点数量和误差不存在严格的正比关系。
如地图TS225，拥有顶点225个，计算误差为0%，而地图EIL101拥有顶点101个，误差却为1.6%。但是从整体趋势来看，顶点数量越大，获得误差也可能越大。
表1 二点组合算法结果表
|
No.
|
地图名
|
结点
|
最小解
|
最优解
|
误差
|
耗时(ms)
|
|
1
|
EIL51
|
51
|
427
|
426
|
0.23%
|
2640
|
|
2
|
BERLIN52
|
52
|
7542
|
7542
|
0.00%
|
3046
|
|
3
|
ST70
|
70
|
675
|
675
|
0.00%
|
4969
|
|
4
|
PR76
|
76
|
108159
|
108159
|
0.00%
|
6594
|
|
5
|
EIL76
|
76
|
540
|
538
|
0.37%
|
5562
|
|
6
|
RD100
|
100
|
7944
|
7910
|
0.43%
|
11141
|
|
7
|
KROE100
|
100
|
22079
|
22068
|
0.05%
|
11141
|
|
8
|
KROD100
|
100
|
21439
|
21294
|
0.68%
|
11000
|
|
9
|
KROC100
|
100
|
20749
|
20749
|
0.00%
|
11281
|
|
10
|
KROB100
|
100
|
22199
|
22141
|
0.26%
|
10843
|
|
11
|
KROA100
|
100
|
21282
|
21282
|
0.00%
|
11531
|
|
12
|
EIL101
|
101
|
639
|
629
|
1.59%
|
10203
|
|
13
|
LIN105
|
105
|
14379
|
14379
|
0.00%
|
13640
|
|
14
|
PR107
|
107
|
44303
|
44303
|
0.00%
|
13812
|
|
15
|
PR124
|
124
|
59030
|
59030
|
0.00%
|
20671
|
|
16
|
BIER127
|
127
|
118822
|
118282
|
0.46%
|
19375
|
|
17
|
CH130
|
130
|
6199
|
6110
|
1.46%
|
19453
|
|
18
|
PR136
|
136
|
98178
|
96772
|
1.45%
|
21578
|
|
19
|
PR144
|
144
|
58537
|
58537
|
0.00%
|
30000
|
|
20
|
CH150
|
150
|
6592
|
6528
|
0.98%
|
26188
|
|
21
|
PR152
|
152
|
73840
|
73682
|
0.21%
|
32750
|
|
22
|
U159
|
159
|
42080
|
42080
|
0.00%
|
33250
|
|
23
|
D198
|
198
|
15862
|
15780
|
0.52%
|
54922
|
|
24
|
KROB200
|
200
|
30300
|
29437
|
2.93%
|
48750
|
|
25
|
KROA200
|
200
|
29924
|
29368
|
1.89%
|
50078
|
|
26
|
TS225
|
225
|
126643
|
126643
|
0.00%
|
67843
|
|
27
|
TSP225
|
225
|
4018
|
3916
|
2.60%
|
64625
|
|
28
|
PR226
|
226
|
80571
|
80369
|
0.25%
|
78234
|
|
29
|
GIL262
|
262
|
2433
|
2378
|
2.31%
|
90375
|
|
30
|
PR264
|
264
|
49696
|
49135
|
1.14%
|
105140
|
结点数量-误差统计结果如表2所示。由表 2明确看出，随着顶点数量的增加蚁群算法，二点组合算法的误差将会有小幅度增加。顶点数在1-100范围内，平均误差为千分之一；顶点数在100-200范围内，平均误差为1%，顶点数在200-300范围内，平均误差为1.7%,所以可以得到结论：二点组合算法在平面地图顶点300以下，计算1000次就可以得到较好结果。
图1 结点数量-误差
表2 结点数量-误差
|
按顶点数分段
|
测试样本数
|
平均误差
|
|
1-100
|
11
|
0.18%
|
|
101-200
|
16
|
0.95%
|
|
201-300
|
7
|
1.73%
|
|
301-400
|
2
|
3.33%
|
|
400-500
|
4
|
2.89%
|
|
合计
|
40
|
1.19%
|
2.3 时间复杂度分析
根据表2绘制图2，由此图可以看出，随着地图顶点数的增加，消耗的时间也在增加。图中柱型图为消耗时间，曲线为顶点平方辅助线，由图可知，程序消耗时间随顶点增长速度比顶点平方辅助线增长速度略快一些。说明，单次运行二点组合算法的时间复杂度大于 免费论文网。
算法的时间复杂度证明：
根据二点组合算法的描述，可以知道，该算法在计算过程中，实际上就是给定一条随机汉密尔顿环路，不停修改其顶点连接次序，直至满足取任意两点都无法进行新的组合，得到更小解。
分析：(1) N点任取两点，根据排列组合公式，需要N×(N-1)次，所以时间复杂度为；
(2) 同地图假设有两条不同“汉密尔顿环路”，以按顶点交换进行相互转化，至多需要调整多少次？即使各个顶点的位置均不同，也仅需要N次。
结合上述分析和实验结果，估算“二点组合算法”的“时间复杂度”略大于。
图2 结点数量-误差
2.4 样本和误差关系
取地图TS255蚁群算法，将1000次计算结果，当作样本绘制图3进行分析。
图3 样本-误差
由图3可以看出，任意种子值得到的误差在0%-13%之间，同时可以看出任意种子值和计算误差无必然联系，也就是说使用二点组合算法进行运算，仅运算一次就求出最优解的可能性不大，运算次数越多，可能获得最优解的概率越大。同时也证明二点组合算法，因对解限制了严格的条件，所以求得解的误差本身就是在一定范围的。
继续以TS255做分析，取各阶段误差在1000次计算中命中次数绘制图4，同时取各阶段误差在10000次计算中命中次数绘制图5，分析两图可以得之，二点组合算法每次运算可能得到的误差分布并不是均匀的，而是呈现出正态分布的趋势，说明随着数据规模的增加，其最优解的求难难度也增大。
图4 样本数量-误差
图5 大样本数量-误差
3 算法性能比较
3.1 与蚁群算法的比较
由于在经典算法中，对中小规模的计算，蚁群算法的精度和效率较高，所以对二点组合算法和蚁群算法进行了误差、时间同机比较。测试结果如表3所示。
蚁群算法中参数：蚂蚁数10，计算代数1000。
经过比较可以看出，二点组合算法的平均误差仅有0.76%，而蚁群算法的平均误差为21.95%，计算速度同比提高8倍。所有地图中二点组合算法的结果都比蚁群算法消耗时间短，精度高。
表3 二点组合算法与蚁群算法
|
地图名
|
最优解
|
二点组合算法
|
蚁群算法
|
|
最小解
|
误差
|
耗时
|
最小解
|
误差
|
耗时
|
|
BERLIN52
|
7542
|
7542
|
0.00%
|
3046
|
8078
|
7.11%
|
33156
|
|
PR76
|
108159
|
108159
|
0.00%
|
6594
|
121696
|
12.52%
|
60328
|
|
RD100
|
7910
|
7944
|
0.43%
|
11141
|
9339
|
18.07%
|
97813
|
|
EIL101
|
629
|
639
|
1.59%
|
10203
|
790
|
25.60%
|
101797
|
|
CH130
|
6110
|
6199
|
1.46%
|
19453
|
7476
|
22.36%
|
153719
|
|
CH150
|
6528
|
6592
|
0.98%
|
26188
|
7584
|
16.18%
|
203531
|
|
U159
|
42080
|
42080
|
0.00%
|
33250
|
51119
|
21.48%
|
227483
|
|
D198
|
15780
|
15862
|
0.52%
|
54922
|
19539
|
23.82%
|
323766
|
|
TS225
|
126643
|
126643
|
0.00%
|
67843
|
164338
|
29.76%
|
436812
|
|
TSP225
|
3916
|
4018
|
2.60%
|
64625
|
5584
|
42.59%
|
450823
|
|
平均误差
|
0.76%
|
|
|
21.95%
|
|
3.2 最优解对比分析
最优解：经过证明的图中具有最小长度的汉密尔顿环路。以KROC100为例，最优解为20749。
利用二点组合算法计算20次蚁群算法，最小解21152，误差为1.94%。
(1:21152,2:21788,3:22139,4:21790,5:22213,6:21428,7:21757,8:21906,9:22424,10:21912,11:21470,12:21758,13:23599,14:21436,15:21886,16:22676,17:21917,18:21677,19:22399,20:22231)
将这20次的解，全部绘制一张网格，如图6所示，可以发现虽然最优解20次没有计算出来，但是最优解的所有边均在这张网格中免费论文网。
图6网格图
继续对网格分析，发现网格每条边被重新绘制的次数不同，最多被绘制了20次，表示在20次二点组合算法中，每个解均含有该边。可以发现明显的规律，被绘制的次数越多，代表是最优解的概率越大，本例中，被绘制超过17次以上边有65条，全部是最优解,占最优解的65%。详细情况请看表4。
根据图6可以分析出，该例中，仅需要计算20次，就可以将最优解边固定在221条边的范围内，甚至可以直接确定一半的最优解所包含的边。为进一步改进算法奠定了基础。（100个顶点的无向图，总包含边数为4950条，每个解含100条边）
表4 最优解概率
|
绘制次数
|
边数
|
最优解边数
|
概率
|
|
20
|
34
|
34
|
100.00%
|
|
19
|
13
|
13
|
100.00%
|
|
18
|
10
|
10
|
100.00%
|
|
17
|
5
|
5
|
100.00%
|
|
16
|
7
|
6
|
85.71%
|
|
15
|
4
|
4
|
100.00%
|
|
14
|
1
|
1
|
100.00%
|
|
13
|
5
|
4
|
80.00%
|
|
12
|
9
|
7
|
77.78%
|
|
11
|
5
|
3
|
60.00%
|
|
10
|
3
|
2
|
66.67%
|
|
9
|
4
|
1
|
25.00%
|
|
8
|
5
|
1
|
20.00%
|
|
7
|
4
|
1
|
25.00%
|
|
6
|
8
|
2
|
25.00%
|
|
5
|
7
|
1
|
14.29%
|
|
4
|
11
|
1
|
9.09%
|
|
3
|
14
|
2
|
14.29%
|
|
2
|
19
|
0
|
0.00%
|
|
1
|
53
|
2
|
3.77%
|
|
总计
|
221
|
100
|
45.25%
|
根据表4可以分析出，绘制次数越多的边，是最优解的概率越大，所以可以计算小数量的二点组合运算，确定最优解所包含边的范围，以大概率边为主干、以小概率边为辅助蚁群算法，进行汉密尔顿环路的遍历，从而解决更大规模的TSP问题。
3.3 测试结果总结
(1) 二点组合算法对中小规模精TSP问题，效果比较理想，100城市TSP问题，平均误差为0.18%，500城市TSP问题，平均误差为1.19%，随着旅行商问题规模的增大，计算精度有所降低；
(2) 二点组合算法的解样本呈正态分布。随机二点组合算法产生的解，找到较小和较大概率都不大，产生解接近平均值的概率较大。
(3) 二点组合算法在计算精度和时间复杂度上优于蚁群算法，二点组合算法的解可以做简单的交集操作，对降低启发集的规模有实际意义。
6 结束语
二点组合算法具有较强的理论价值，同时具有较强的实用价值，可以较好地完成中等规模的TSP问题，还适用于一系列的优化组合问题：如二次分配问题、大规模集成电路综合布线问题和车辆路径选择问题等。
参考文献:
[1]陈国良,王熙法,庄镇泉,王东生.遗传算法及其应用[M],人民邮电出版社,1996.
[2]玄光男,程润伟.遗传算法与工程优化[M]. 北京:清华大学出版社, 2004.
[3]Tsai Cheng-Fa, Tsai Chun-Wei, TsengChing-Chang. A new hybrid heuristic approach for solving large travelingsalesman problem[J]. Information Sciences, 2004, 166(1):67-81.
[4]邹鹏,周智,陈国良,顾钧.求解TSP问题的多级归约算法[J].软件学报, 2003,14(1):35-42.
[5]Helsgaun K. An effective implementationof the Lin-Kernighan traveling salesman heristic[J]. European Journal ofOperational Re-search, 2000, 126(1):106-130.
[6]Richard Warlimont. On the iterates ofEuler's function[J]. ArchMath, 2001 ,76:345-349.
[7]Ong H L. Worst-Case Analysis of TwoTraveling Salesman Heuristics[J]. Operations Res.1984:273-277.
[8]谢胜利,唐敏,董金祥.求解TSP问题的一种改进的遗传算法[J].计算机工程与应用, 2002,38(8): 58-62.
[9]许丽佳,蒲海波,蒋宏健.改进遗传算法的路径规划研究[J].微计算机信息, 2006,22(2): 251-253.
|
