基于TSP的蟻群算法參數選擇問題分析

丁上凌++李斌

摘要：根據目前針對社會性動物群體活動的實驗調查，發現其自組織行為廣泛存在，例如群體活動較為頻繁的螞蟻，在群體覓食過程中能夠找到蟻穴到食物的最短路徑，即蟻群算法。文章圍繞蟻群算法在TSP中的應用，就算法的參數選擇進行了深入的研究。最后通過對全文的研究工作進行了總結，并展望了其應用價值及后期還需繼續研究的問題。

關鍵詞：蟻群算法 TSP 最短路徑 參數選擇

中圖分類號：TP183 文獻標識碼：A 文章編號：1007-9416（2016）12-0131-02

蟻群算法是一種用來在圖中尋找優化路徑的機率型算法。它由Marco Dorigo提出，它主要的依據就是螞蟻在覓食過程中能夠找到蟻穴到食物的最短路徑。螞蟻的視覺系統非常薄弱，幾乎可以說是瞎子，但是它們卻能發現食物與蟻穴之間最短的距離。生態學家的研究表明，螞蟻是借助信息素來實現這一點的。蟻群算法也越來越多被應用到實際的問題中，并且取得了較好的效果，例如調度問題、著色問題、求解旅行商問題（TSP），并在大規模集成電路設計，通信路由控制等諸多領域表現出較好的性能。本文在介紹蟻群算法的基本原理的基礎上，主要分析了蟻群算法參數的選擇策略問題。

1 蟻群算法的基本原理

1.1 蟻群算法的原理

蟻群算法是從自然界啟發中得到的一種新型的模擬進化算法，應用該算法求解TSP問題取得了較好的結果?？茖W家發現雖然單個螞蟻無法掌握附近的地理信息，但整個蟻群卻可以找到一條從巢穴到食物源之間的最優路線。經過大量研究發現：螞蟻在運動過程中，能夠留下一種稱之為信息素的物質，而且螞蟻在運動過程中能夠感知這種物質，并以此指導自己的運動方向，因此，由大量螞蟻組成的蟻群的集體行為便表現出一種信息正反饋現象：某一路徑上單位時間走過的螞蟻越多，表明該路線的可用性越好，則后來者選擇該路徑的概率就越大。蟻群算法具有實現簡單、正反饋、分布式的優點。

人工蟻群和自然界蟻群的相似之處在于，兩者優先選擇的都是含“信息素”濃度較大的路徑。這在兩種情況下，較短的路徑上都能聚集比較多的信息素，受到上述情況的啟發，科研人員在此基礎上提出了蟻群算法，它不僅具有蟻群覓食行為中的信息傳遞功能，還具有自然界蟻群所沒有的記憶能力，即能夠保存已經去過的地方和已經走過的路徑，從而能夠更加智能的選擇下一地點和路徑，并且按照一定的規律總結出特有的算法進行最短路徑的選擇。

1.2 基于TSP問題的蟻群算法數學模型

TSP問題又稱為旅行商問題，是數學領域中著名問題之一。假設有一個旅行商人要拜訪M個城市，他必須選擇所要走的路徑，路徑的限制是每個城市只能拜訪一次，而且最終要回到原來出發的城市。路徑的選擇目標是要求旅行商人怎樣才能得到最短的路徑，取得最佳的利益。

根據信息素更新的策略不同，Dorigo M曾給出了不同的蟻群算法模型，分別稱為ant-cycle模型，ant-quantity模型和ant-density模型。它們的差別在于循環中路徑的信息素的增量的求法不同。

在ant-quantity模型中：

其中，是信息素強度，它影響算法的收斂速度是指兩座城市之間的歐氏距離，是指第只螞蟻所走的路徑長度。ant-quantity和ant-density是利用局部信息完成求解運算，ant-cycle是利用整體信息完成求解運算。通過實驗得到ant-cycle的模型比其他兩種模型效果好。

2 參數優化策略

通過對蟻群算法基本原理及其數學模型的學習理解，可以使用MATLAB進行蟻群算法求解TSP最短路徑問題的仿真試驗工作，其主要任務是：根據城市的坐標，使用蟻群算法求解TSP最優化問題，并繪制最佳結果的路徑圖，生成平均距離和最短距離統計圖。

算法中的主要參數有：城市的個數，城市的坐標（城市個數*2的矩陣），最大循環次數（即迭代的次數），螞蟻個數，表征信息素重要程度的參數，表征啟發因子（期望）重要程度的參數，信息素揮發系數，信息素強度的系數（一般是一個常量），最佳路線的長度。

實現步驟為：第一步：變量初始化；第二步：循環開始，判斷變量是否達到最大迭代次數，如果沒有達到，繼續下一步運行，否則，循環結束；第三步：將所有螞蟻隨機放到所有城市上；第四步：所有螞蟻按概率函數選擇下一座城市，完成各自的周游；第五步：記錄本次迭代最佳路線；第六步：更新信息素；禁忌表清零，回到第二步，達到停止條件時跳到第七步；第七步：輸出結果。

仿真中采用最短路徑作為參考項，進行多目標測試得出結果，并由結果分析出蟻群算法中的參數如何選擇優化。

2.1 缺省值的選擇

在實驗過程中，本文在進行參數選擇時，取城市個數為20，迭代次數為100，螞蟻個數為15，信息素重要程度為1，啟發因子重要程度為1，信息素揮發系數為0.15，信息素強度的系數為100，并設定20個城市坐標為（602，972）（989，483）（54，550）（95，868）（529，430）（982，351）（654，23）（738，372）（539，594）（560，850）（229，806）（411，710）（83，706）（937，801）（12，994）（694，809）（795，759）（339，148）（956，644）（346，726）。

多次運行程序后，求得最佳路線的長度的最優解為4148.6，使用其作為缺省值，以此在下面進行參數關系選擇時作為對比參考值。

2.2 迭代次數的選擇

由于蟻群算法中迭代的重要性，所以選取合適的迭代次數可以在較少耗費系統資源的同時得到較優的解。經過試驗可以得出在迭代次數太少時，求出的解與最優解相差很大，這是由于迭代次數太少時，解還未收斂造成的。當迭代次數太多時，其耗費了大量系統資源，但是求出的解已基本不再變化，甚至有時出現抖動，求出不優解。所以合適選取迭代次數的值非常重要，在其他參數采用缺省值的情況下，可以通過實驗得出選取110次左右的迭代次數較好。

2.3 信息素重要程度與啟發因子重要程度參數的關系選擇

從上述分析過程來看，我們所取的參數只是針對某一方面，參數較為單一，沒有考慮不同參數值的組合所能呈現的不同效果，所以，接下來，本文就這一問題的缺陷性，對信息素重要程度與啟發因子重要程度參數的關系選擇進行了重新組合，在試驗過程中，取不同組合的信息素重要程度α與啟發因子重要程度β參數組合，求最短路徑長度的最優解，其中，α在1到3之間取值，β在3到5之間取值，進行排列組合取值，特別地，α和β同時取1作為缺省值，即總共有10種情況。經過多次試驗得出：α和β的值為（1，1）、（1，4）、（1，5）時均能取得較好的解。

2.4 螞蟻個數與城市個數的關系選擇

經過實際應用可以知道，螞蟻的個數與城市個數影響著TSP的求解，當少數螞蟻在較大的城市中運動，它們所能得到的信息是有限的，這時算法不穩定，容易出現早停滯現象。相反，當大量的螞蟻在較小的城市運動，它們雖然能夠搜索的較為全面的信息，但是浪費了資源，收斂速度慢。本文選取螞蟻個數/城市個數為0.5、1.5、2.5進行比較，經多次實驗可以得出在城市數較少的系統中，螞蟻數的變化對其影響較小，而在城市數較多的系統中時，螞蟻數/城市數為1.5時可以取得較好的解，如表1所示。

在通信系統中，路由是關鍵的組件之一，它涉及到建立和使用路由表來指導數據通信量在網絡范圍內的分配活動。普通路由問題可以理解為是要建立一個路由表使得網絡性能的一些量度最大化，是基于TSP的蟻群算法的重要應用。

3 結論和展望

蟻群算法易于與其他算法融合，在實際應用中參數對最優路徑的選擇有較大的影響，本文針對蟻群的參數選擇問題進行分析，經過試驗得到了一些參數的最佳取值范圍。在以后的研究中可以將其應用于路由選擇協議中，并考慮更多的網絡實際情況，加入流量控制、網絡擁塞等將其應用于實際之中，以取得更為準確的測試結果。

參考文獻

[1]高博，盧輝斌.改進型粒子蟻群算法的應用研究[J].計算機安全，2010（11）：11-13.

[2]王戈，徐俊剛.基于路徑選擇的自適應蟻群算法研究[J].電子技術，2010，37（1）：14-16.

[3]葉菁.基于免疫-蟻群算法的TSP問題研究.[J].計算機工程，2010，36（24）：156-157+160.