一种适用于求解旅行商问题的新型算法性能分析_蚁群算法

1、一种适用于求解旅行商问题的新型算法性能分析_蚁群算法    论文导读:：本文将重点讨论该算法在求解中小规模旅行商问题时的性能。本文给出的二点组合算法就是一种环路改造算法。与经典的蚁群算法相比相比。 关键词：旅行商问题，二点组合算法，蚁群算法    1 引言 解旅行商问题(TravelingSalesman Problem,TSP)是一个著名的NP-Hard问题，由于该问题的实际模型在路径、网络、分配等优化问题中有着广泛的应用，故长期以来吸引着许多领域的研究人员采用各种方法对它进行求解1-2。它可以简单描述为:给出一

2、条遍历给定的若干个城市中所有城市的最短路径3。目前，研究TSP问题主要采用启发式算法，环路改进算法就是一类典型的启发式算法，即通过比较目标解和局部最优解的优劣而逐步改变解4-5。 本文给出的二点组合算法就是一种环路改造算法，其步骤是选取一条合法汉密尔顿环路，作为目标解，任取两个顶点删除与之相关的边，形成2至4个环路片断，对这些环路片断进行排列组合，尝试寻找更优的解替换目标解6。重复上述步骤，直到选定环路任意两点蚁群算法，目标解都无法进一步优化。与经典的蚁群算法相比相比，时间复杂度相等，但计算效率和计算误差性能皆优于后者7-8。本文将重点讨论该算法在求解中小规模旅行商问题时的性能，从而说明新算法

3、的实用性。 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、为四舍五入求整。 (4) 误差计算方法：所有地图均提供通过证明的最佳解。 误差=（最小解-最佳解）/最佳解 2.2 计算精度分析 使用二点组合算法，对30组规模不同的TSP问题求解结果，最小解为计算1000次的结果，最优解目前已证明的最优解，计算时间的单位为毫秒，计算结果如表1所示。 结点数量与误差之间的关系如图1所示。根据图1可知，结点数量和误差不存在严格的正比关系。 如地图TS225，拥有顶点225个，计算误差为0%，而地图EIL101拥有顶点101个，误差却为1.6%。但是从整体趋势来看，顶点数量越大，获得误差也可能越大。 表1 二点组合算法结果表    &

5、#160;     No.        地图名        结点        最小解        最优解        误差  &#

6、160;     耗时(ms)             1        EIL51        51        427     &#

7、160;  426        0.23%        2640             2        BERLIN52       

8、0;52        7542        7542        0.00%        3046             3  &

9、#160;     ST70        70        675        675        0.00%        4969

10、0;            4        PR76        76        108159        108159   &#

11、160;    0.00%        6594             5        EIL76        76      &#

12、160; 540        538        0.37%        5562             6        RD100

13、0;       100        7944        7910        0.43%        11141       &

14、#160;     7        KROE100        100        22079        22068        0.05%

15、0;       11141             8        KROD100        100        21439   

16、     21294        0.68%        11000             9        KROC100     

17、   100        20749        20749        0.00%        11281           &

18、#160; 10        KROB100        100        22199        22141        0.26%    

19、60;   10843             11        KROA100        100        21282      

20、0; 21282        0.00%        11531             12        EIL101        101&

21、#160;       639        629        1.59%        10203             13   

22、     LIN105        105        14379        14379        0.00%        13640&

23、#160;            14        PR107        107        44303        44303  

24、0;     0.00%        13812             15        PR124        124     &

25、#160;  59030        59030        0.00%        20671             16       &#

26、160;BIER127        127        118822        118282        0.46%        19375    

27、         17        CH130        130        6199        6110       

28、; 1.46%        19453             18        PR136        136        98178

29、60;       96772        1.45%        21578             19        PR144  

30、0;     144        58537        58537        0.00%        30000         

31、;    20        CH150        150        6592        6528        0.98%   

32、;     26188             21        PR152        152        73840     &#

33、160;  73682        0.21%        32750             22        U159       

34、0;159        42080        42080        0.00%        33250             23 &#

35、160;      D198        198        15862        15780        0.52%       

36、0;54922             24        KROB200        200        30300        29437 

37、       2.93%        48750             25        KROA200        200   &

38、#160;    29924        29368        1.89%        50078             26     &#

39、160;  TS225        225        126643        126643        0.00%        67843  &#

40、160;          27        TSP225        225        4018        3916     

41、   2.60%        64625             28        PR226        226       

42、60;80571        80369        0.25%        78234             29        GIL262

43、0;       262        2433        2378        2.31%        90375       &

44、#160;     30        PR264        264        49696        49135        1.14% 

45、;       105140     结点数量-误差统计结果如表2所示。由表 2明确看出，随着顶点数量的增加蚁群算法，二点组合算法的误差将会有小幅度增加。顶点数在1-100范围内，平均误差为千分之一；顶点数在100-200范围内，平均误差为1%，顶点数在200-300范围内，平均误差为1.7%,所以可以得到结论：二点组合算法在平面地图顶点300以下，计算1000次就可以得到较好结果。 图1 结点数量-误差 表2 结点数量-误差      

46、;    按顶点数分段        测试样本数        平均误差             1-100        11       

47、; 0.18%             101-200        16        0.95%             201-300    &

48、#160;   7        1.73%             301-400        2        3.33%       

49、;      400-500        4        2.89%             合计        40     

50、0;  1.19%     2.3 时间复杂度分析 根据表2绘制图2，由此图可以看出，随着地图顶点数的增加，消耗的时间也在增加。图中柱型图为消耗时间，曲线为顶点平方辅助线，由图可知，程序消耗时间随顶点增长速度比顶点平方辅助线增长速度略快一些。说明，单次运行二点组合算法的时间复杂度大于免费论文网。 算法的时间复杂度证明： 根据二点组合算法的描述，可以知道，该算法在计算过程中，实际上就是给定一条随机汉密尔顿环路，不停修改其顶点连接次序，直至满足取任意两点都无法进行新的组合，得到更小解。 分析：(1) N点任取两点，根据排列组合公式，需要N

51、×(N-1)次，所以时间复杂度为； (2) 同地图假设有两条不同“汉密尔顿环路”，以按顶点交换进行相互转化，至多需要调整多少次？即使各个顶点的位置均不同，也仅需要N次。 结合上述分析和实验结果，估算“二点组合算法”的“时间复杂度”略大于。 图2 结点数量-误差 2.4 样本和误差关系 取地图TS255蚁群算法，将1000次计算结果，当作样本绘制图3进行分析。 图3 样本-误差 由图3可以看出，任意种子值得到的误差在0%-13%之间，同时可以看出任意种子值和计算误差无必然联系，也就是说使用二点组合算法进行运算，仅运算一次就求出最优解的可能性不大，运算次数越多，可能获得最优解的概率越大。

52、同时也证明二点组合算法，因对解限制了严格的条件，所以求得解的误差本身就是在一定范围的。 继续以TS255做分析，取各阶段误差在1000次计算中命中次数绘制图4，同时取各阶段误差在10000次计算中命中次数绘制图5，分析两图可以得之，二点组合算法每次运算可能得到的误差分布并不是均匀的，而是呈现出正态分布的趋势，说明随着数据规模的增加，其最优解的求难难度也增大。 图4 样本数量-误差 图5 大样本数量-误差 3 算法性能比较 3.1 与蚁群算法的比较 由于在经典算法中，对中小规模的计算，蚁群算法的精度和效率较高，所以对二点组合算法和蚁群算法进行了误差、时间同机比较。测试结果如表3所示。 蚁群算法中

53、参数：蚂蚁数10，计算代数1000。 经过比较可以看出，二点组合算法的平均误差仅有0.76%，而蚁群算法的平均误差为21.95%，计算速度同比提高8倍。所有地图中二点组合算法的结果都比蚁群算法消耗时间短，精度高。 表3 二点组合算法与蚁群算法          地图名        最优解        二点组合算法   

54、60;    蚁群算法             最小解        误差        耗时        最小解       

55、 误差        耗时             BERLIN52        7542        7542        0.00%

56、0;       3046        8078        7.11%        33156             PR76   

57、;     108159        108159        0.00%        6594        121696        12

58、.52%        60328             RD100        7910        7944        0.43% &#

59、160;      11141        9339        18.07%        97813             EIL101   

60、;     629        639        1.59%        10203        790        25.60%

61、0;       101797             CH130        6110        6199        1.46%  

62、60;     19453        7476        22.36%        153719             CH150    

63、    6528        6592        0.98%        26188        7584        16.18% &#

64、160;      203531             U159        42080        42080        0.00%   

65、     33250        51119        21.48%        227483             D198    

66、60;   15780        15862        0.52%        54922        19539        23.82% &#

67、160;      323766             TS225        126643        126643        0.00%  

68、60;     67843        164338        29.76%        436812             TSP225   

69、60;    3916        4018        2.60%        64625        5584        42.59% 

70、;       450823             平均误差        0.76%                    21.95% 

71、;             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:

72、22676,17:21917,18:21677,19:22399,20:22231) 将这20次的解，全部绘制一张网格，如图6所示，可以发现虽然最优解20次没有计算出来，但是最优解的所有边均在这张网格中免费论文网。 图6网格图 继续对网格分析，发现网格每条边被重新绘制的次数不同，最多被绘制了20次，表示在20次二点组合算法中，每个解均含有该边。可以发现明显的规律，被绘制的次数越多，代表是最优解的概率越大，本例中，被绘制超过17次以上边有65条，全部是最优解,占最优解的65%。详细情况请看表4。 根据图6可以分析出，该例中，仅需要计算20次，就可以将最优解边固定在221条边的范围内，甚至可以直接

73、确定一半的最优解所包含的边。为进一步改进算法奠定了基础。（100个顶点的无向图，总包含边数为4950条，每个解含100条边） 表4 最优解概率          绘制次数        边数        最优解边数        概率   

74、0;         20        34        34        100.00%             19   

75、;     13        13        100.00%             18        10      &

76、#160; 10        100.00%             17        5        5        100.00%

77、0;            16        7        6        85.71%             15&#

78、160;       4        4        100.00%             14        1    &

79、#160;   1        100.00%             13        5        4        

80、80.00%             12        9        7        77.78%           &

81、#160; 11        5        3        60.00%             10        3  

82、0;     2        66.67%             9        4        1       

83、; 25.00%             8        5        1        20.00%             7        4        1        25.00%