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%