基本蟻群算法在解決TSP問題中參數選擇的研究

◆楊昌昊 張 琢

基本蟻群算法在解決TSP問題中參數選擇的研究

◆楊昌昊 張 琢

（東北師范大學信息科學與技術學院 吉林 130117）

蟻群算法是受自然界中真實蟻群覓食行為的啟發而提出的一種優化算法，基本蟻群算法是其中基礎且較為經典的一種算法，而基本蟻群算法中的參數對算法效果有很大的影響。本文以使用基本蟻群算法解決TSP問題為例，在對相關內容進行介紹后，進而對基本蟻群算法的參數選擇進行了實驗及分析，最終給出了基本蟻群算法中各個參數的基本選擇范圍。

蟻群算法；基本蟻群算法；TSP問題

0 引言

啟發式算法(Heuristic algorithm)是一類基于生物學、物理學和人工智能的，具有全局優化性能、魯棒性強、通用性強且適用于并行處理的算法[1]。現階段，啟發式算法以仿生優化算法[2]為主，主要包括模擬退火算法[3]、粒子群算法[4]、遺傳算法[5]、混合蛙跳算法[6]、蟻群算法等。

蟻群算法(Ant colony optimization algorithm)是受自然界中真實蟻群覓食行為的啟發，發現雖然單個螞蟻沒有太多的智力，也無法掌握附近的地理信息，但整個蟻群卻可以找到一條從巢穴到食物源之間的最優路線而提出的一種仿生優化算法[7]。

在蟻群算法的研究中，研究者們常以TSP問題作為該算法的運行實例。TSP (Traveling salesman problem)問題又稱為旅行商問題，是一種比較經典的NP難題，問題描述較簡單，而獲得最優解卻十分困難。求解TSP問題不僅為其他算法提供了使用平臺，而且算法的優劣性能也可通過其求得TSP問題的解集來驗證。TSP問題的經典描述為：已知N個城市及相互間的距離，旅行商從某城市出發遍歷這N個城市后再回到原點，在旅行商每個城市都只訪問一次的前提下確定一條最短路徑[8]。本文也將以TSP問題作為基本蟻群算法中對參數設計方案進行驗證的運行實例。

基本蟻群算法是蟻群算法中最經典且基礎的一種，在使用基本蟻群算法解決TSP問題時，算法中的各個參數對算法的效果有很大影響，在Wei Xianmin所著論文[9]中便提到了蟻群數量、信息素重要程度系數及兩城市間距離重要程度系數三個參數算法效果的影響，并給出了實驗數據。但對于全部參數對算法的影響情況，目前暫未有論文進行實驗論證。

因此，本文將對基本蟻群算法的執行流程、影響算法執行的參數進行介紹，并對相關參數進行一系列實驗與分析，最終得出使用基本蟻群算法解決TSP問題時參數的基本選擇范圍。

1 基本蟻群算法模型介紹

1.1基本蟻群算法簡介

基本蟻群算法通過模擬自然界的螞蟻覓食過程對目標進行搜索，人工螞蟻會根據路徑上的信息素濃度的函數，按概率選擇下一個將要訪問的城市，信息素濃度越高，則該路徑被選擇的概率越大。當人工螞蟻進行完一次循環后，其會在其訪問過的每條邊上都留下相應的信息素。

1.2基本蟻群算法執行流程

（1）初始化

算法開始時，將m只螞蟻隨機的放到n座城市中。將每只螞蟻k的禁忌表tabuk的第一個元素設置為當前它所在的城市，下一步允許選擇的城市表allowedk設為除當前它所在的城市外的所有城市。同時，將各條路徑上的信息素量統一設為一較小的常數。該常數的選擇有很多種方式，本文中選為1/(m*n)。

（2）每只螞蟻獨立的選擇一次周游的路徑

每只螞蟻按照各條路徑上的信息素量、兩城市間的距離及其相關的參數獨立的選擇下一座城市。在時刻t，螞蟻k在城市i上選擇城市j的概率Pijk(t)為：

其中，allowedk表示螞蟻k下一步允許選擇的城市，即在所有城市中減去禁忌表tabuk中的城市，α代表信息素的相對重要程度，β代表兩城市間距離的相對重要程度。

當allowedk變為空時，即完成了一次周游。

（3）每只螞蟻獨立的選擇一次周游的路徑

當全部m只螞蟻都完成一次循環之后，各路徑上的信息素將會根據下式進行更新：

其中，ρ代表信息素的殘留系數。關于Δτijk的計算方法，M.Dorigo給出了三種不同的實現方法，分別對應三種不同的螞蟻系統模型[11]：Ant-cycle模型、Ant-density模型及Ant-quantity模型。它們的計算方法如下：

在Ant-quantity模型中：

在Ant-density模型中：

在Ant-cycle模型中：

上面的三個公式中，Q為一正常數，表示螞蟻循環一周所釋放的信息素總量。Lk表示螞蟻k在本次循環中所經過的路徑的長度。

2 基本蟻群算法中各參數對算法性能影響的研究

在蟻群算法中，算法運行參數的選取對算法性能有著至關重要的影響。對于不同的優化問題，算法的參數選取不同。即使對于同一類型優化問題，由于問題規模不一樣，算法的參數選取也不盡相同[12]。

本文使用TSPLIB提供的att48數據集，針對基本蟻群算法中各個參數的不同取值進行了大量實驗，意圖找出參數選擇的規律。

att48數據集包含美國本土48州州府的地理位置坐標，其最優解為10628。

2.1實驗硬件、軟件環境

實驗使用MacBook Pro (Retina, 13-inch, Early 2013)型計算機，處理器為2.6 GHz Intel Core i5，內存為8 GB 1600 MHz DDR3。操作系統為macOS High Sierra 10.13.2，JDK版本為JDK 1.7.0_80。

2.2蟻群數量對算法性能的影響

蟻群算法是一種并行隨機搜索算法, 它是通過多個候選解組成的群體進化過程來搜索最優解。蟻群數量越大可以提高蟻群算法的全局搜索能力以及算法的穩定性，但螞蟻數目增加到一定程度以后，會使大量的曾被搜索過的解(路徑)上的信息量的變化比較平均，信息正反饋的作用不明顯，搜索的隨機性增強，造成收斂速度變慢。反之，蟻群數量越小，特別是當要處理的問題規模比較大時，會使那些從來沒被搜索到的路徑上信息素量減小到接近0，搜索的隨機性減弱，雖然收斂速度較快，但是會使算法的全局性能降低。

為了研究蟻群數量對算法性能的影響，將算法中其他的參數固定(采用Ant-quantity模型，迭代次數=100次，ρ=0.5，α=1.0，β=10，Q=10)，針對att48數據集，對不同的蟻群數量各進行10次測試，結果如下表1：

表1 蟻群數量對算法性能的影響

根據實驗結果可見，當螞蟻數量小于30時，隨著蟻群數量的不斷增大，100次迭代后得到的平均路徑長度不斷優化，而當螞蟻數量超過30時，螞蟻數量對于結果的影響開始變得不再那么明顯。耗時方面，每增加5個螞蟻，耗時約增加4秒。因而，針對att48數據集，考慮效果與耗時，可將螞蟻數目設為30個，即約0.6倍的城市數目。

2.3算法模型對算法性能的影響

三種算法模型中，關于信息素增量的算法截然不同，因而可能會對算法結果產生較大的影響。

在Ant-quantity模型中，從城市i到城市j的螞蟻在路徑上的信息素增量為一個與路徑無關的常量Q。在Ant-density模型中，從城市i到城市j的螞蟻在路徑上的信息素增量為Q/dij，dij為城市i到城市j的距離，因而信息素增量會隨著城市間距離的不同而變化。在Ant-cycle模型中，從城市i到城市j的螞蟻在路徑上的信息素增量為Q/Lk，由于Lk為第k只螞蟻在該次循環中所走過的路徑的總長度，因此信息素增量與該次循環中所獲得解循環路徑的優劣有關，更新規則會讓短路經較優的解上對應的信息素量逐步增加。

為了研究算法模型對算法性能的影響，將算法中其他的參數固定(蟻群數量=30，迭代次數=100次，ρ=0.5，α=1.0，β=10，Q=10)，針對att48數據集，對不同的算法模型各進行10次測試，結果如下表2：

表2 算法模型對算法性能的影響

根據實驗結果可見，當螞蟻數量小于30時，隨著蟻群數量的不斷增大，100次迭代后得到的平均路徑長度不斷優化，而當螞蟻數量超過30時，螞蟻數量對于結果的影響開始變得不再那么明顯。耗時方面，每增加5個螞蟻，耗時約增加4秒。因而，針對att48數據集，考慮效果與耗時，可將螞蟻數目設為30個，即約0.6倍的城市數目。

2.4信息素殘留系數(ρ)對算法性能的影響

在蟻群算法中，人工螞蟻是具有記憶功能的，隨著時間的推移，以前留下的信息素將逐步消逝。當信息素殘留系數(ρ)過大時，以前被搜索過的解被選擇的可能性過大，會影響到算法的隨機性能和全局搜索能力。反之，當ρ過小時，雖然可以提高算法的隨機性能和全局搜索能力，但又會使算法的收斂速度降低。因此，選擇一個合適的信息素殘留系數是十分必要的。

為了研究信息素殘留系數對算法性能的影響，將算法中其他的參數固定(采用Ant-quantity模型，蟻群數量=30，迭代次數=100次，α=1.0，β=10，Q=10)，針對att48數據集，對不同的信息素殘留系數各進行10次測試，結果如下表3：

表3 ρ對算法性能的影響

根據實驗結果可見，針對att48數據集，信息素殘留系數為0.5時，平均路徑長度最小，而五組不同的ρ值對于耗時幾乎不存在影響。因而，本文認為，信息素殘留系數設為0.5較優，原因在于，每只螞蟻需要忘記過去獲得的一部分經驗，避免螞蟻過早的收斂到一個局部最優解，使得螞蟻可以更好的探索新引入的全局信息。

2.5信息素重要程度系數(α)對算法性能的影響

信息素重要程度系數(α)的大小反映了在蟻群路徑搜索中的隨機性因素作用的強度，其值越大，螞蟻選擇以前走過的路徑的可能性也越大，搜索的隨機性減弱。因而，α值過大會使蟻群的搜索過早陷于局部最優。

為了研究信息素重要程度系數對算法性能的影響，將算法中其他的參數固定(采用Ant-quantity模型，蟻群數量=30，迭代次數=100次，ρ=0.5，β=10，Q=10)，針對att48數據集，對不同的信息素重要程度系數各進行10次測試，結果如下表4：

表4 α對算法性能的影響

根據實驗結果可見，針對att48數據集，信息素重要程度系數為1.0時，平均路徑長度最小，而六組不同的α值對于耗時的影響不大。因而，本文認為，信息素重要程度系數設為1.0左右較優。原因在于，α過小時，而且算法易陷入局部最優解；而α過大時，局部最優路徑上的正反饋作用很強，算法會出現過早收斂，同樣對結果存在負影響。

2.6兩城市間距離重要程度系數(β)對算法性能的影響

兩城市間距離(β)的大小反映了在蟻群路徑搜索中確定性因素作用的強度，其值越大，螞蟻在某個局部點上選擇局部最短路徑的可能性越大，盡管搜索的收斂速度加快，但蟻群在最優路徑的搜索過程中的隨機性減弱，易于陷入局部最優。

為了研究兩城市間距離重要程度系數對算法性能的影響，將算法中其他的參數固定(采用Ant-quantity模型，蟻群數量=30，迭代次數=100次，ρ=0.5，α=1.0，Q=10)，針對att48數據集，對不同的兩城市間距離重要程度系數各進行10次測試，結果如下表5：

表5 β對算法性能的影響

根據實驗結果可見，針對att48數據集，在兩城市間距離重要程度系數小于10時，隨著β值的增長，效果迅速優化；而當β值超過10后，β值對于結果開始呈現負影響。因而，本文認為，兩城市間距離重要程度系數設為10左右較優，既保證了一定的隨機性，又保證了路徑搜索中確定性因素作用的強度。

2.7螞蟻循環一周在經過的路徑上釋放的信息素總量(Q)對算法性能的影響

螞蟻循環一周在經過的路徑上釋放的信息素總量(Q)越大，則在螞蟻所走過的路徑上的信息素的累積加快，因而可以加強蟻群搜索時的正反饋性能，有助于算法的快速收斂。但一般認為，蟻群算法參數中對算法性能起主要作用是α、β及ρ三個參數，而總信息量對算法性能的影響有賴于以上三個參數的配置，對算法性能的影響不大。

為了研究Q值對算法性能的影響，將算法中其他的參數固定(采用Ant-quantity模型，蟻群數量=30，迭代次數=100次，ρ=0.5，α=1.0，β=10)，針對att48數據集，對不同的Q值各進行10次測試，結果如下：

表6 Q對算法性能的影響

根據實驗結果可見，針對att48數據集，Q值在1~20之間時，對結果的影響的影響十分微弱，直到Q值為50時，結果才有較為明顯的劣化。而在耗時方面，Q值幾乎對耗時不存在任何影響。因而在實際使用時，Q值可以在1~20之間靈活的選取。

3 結束語

在基本蟻群算法的實際使用中，參數對算法效果有十分顯著的影響，若選擇不當，則容易暴露出其存在的但搜索時間長、易陷于局部最優解的缺點。本文通過一系列的實驗，研究了在att48數據集下參數的設置對蟻群算法性能的影響。實驗結果表明，基本蟻群算法中參數的最優設置為：蟻群數量約為0.6倍城市數量，信息素重要程度系數(α)約為1.0左右，兩城市間距離重要程度系數(β)約為10左右，信息素殘留系數(ρ)約為0.5左右，螞蟻循環一周在經過的路徑上釋放的信息素總量(Q)可以在1~20之間靈活的選取。算法模型方面，若Ant-cycle模型的效果較其他兩者優勢較大，則應選擇Ant-cycle模型；若效果優勢不大，則可考慮選擇耗時較短的其他兩種模型。

[1]叢明煜，王麗萍.現代啟發式算法理論研究[J].高技術通訊, 2003.

[2]熊偉平，曾碧卿.幾種仿生優化算法的比較研究[J].計算機技術與發展，2010.

[3]馮玉蓉.模擬退火算法的研究及其應用[D].昆明理工大學，2005.

[4]梁軍.粒子群算法在最優化問題中的研究[D].廣西師范大學，2008.

[5]王銀年.遺傳算法的研究與應用[D].江南大學，2009.

[6]鄒采榮，張瀟丹，趙力.混合蛙跳算法綜述[J].信息化研究，2012.

[7]吳慶洪，張穎，馬宗民.蟻群算法綜述[J].微計算機信息， 2011.

[8]吳華鋒，陳信強，毛奇凰等.基于自然選擇策略的蟻群算法求解TSP問題[J].通信學報，2013.

[9]Wei Xianmin. Parameters Analysis for Basic Ant Colony Optimization Algorithm in TSP[J]. International Journal of u-and e-Services, Science and Technology, Vol.7, No.4 (2014).

[10]楊劍峰.蟻群算法及其應用研究[D].浙江大學，2007.

[11]劉乃文，王奎峰.蟻群優化算法及其應用[J].山東師范大學學報(自然科學版)，2006.

[12]劉利強，戴運桃，王麗華.蟻群算法參數優化[J].計算機工程，2008.