帶個體差異的蟻群算法的應用

摘要：基本蟻群算法在大規模優化問題的處理上，算法的執行效率很低。為此改進的算法引入了螞蟻個體差異，并將不同螞蟻選路策略混合應用，使改進后的蟻群算法在加快收斂速度和提高解的質量的同時，避免了過早停滯現象。實驗表明，該算法在性能上遠優于基本蟻群算法。

關鍵詞：蟻群算法； 旅行商問題； 個體差異

中圖分類號：TP301．6文獻標志碼：A

文章編號：1001－3695(2008)04－1036－03

蟻群算法（ACO）是受自然界中螞蟻搜索食物行為啟發而提出的一種智能優化算法。正反饋機制和通信機制是蟻群算法的重要基礎。正反饋作用能加快算法的搜索，也會導致算法出現停滯現象，而通信機制能使個體相互協作，有利于算法搜索到更優解。目前，該算法在組合優化領域得到應用，并且得到了較好的結果[1~7]。仿照自然界種群中個體的多樣性，本文對基本蟻群算法改進，引入了HSIV算法。首先，通過螞蟻的不同選路策略，使ACO算法的全局搜索能力和收斂速度得到了增強，可提高解的質量。其次，將不同行為策略的螞蟻混合協同工作，避免了解的過早收斂。模擬實驗表明，HSIV算法對于多個實例進行模擬計算的結果均優于或等于TSPLIB給出的現有最佳運行結果。其中：st70實例實驗得到的最短路徑為677．109 6，提供的最佳路徑運算結果為678.59 (但TSPLIB提供的最短路徑值為675)，這一結論與文獻[6]相一致；berlin52實例得到的最短路徑與TSPLIB提供的最佳路徑運算結果相同。

1基本蟻群算法

為更清楚地理解蟻群算法的基本原理，一般多借助經典的對稱TSP來進行說明。TSP的目標函數是TSP的目的，是從有向圖G中尋找出長度最短的Hamilton圈。

2改進HSIV算法的原理、模型及實現

2．1個體差異策略

在基本蟻群算法的幾種模式中，都是采用固定的信息量增減比例策略進行選路操作。若在整個算法運行期間都采用固定的選路策略，不但不能使蟻群存儲在信息素中關于較好路徑的信息得到充分利用，突出蟻群算法的正反饋特征，而且仍然解決不了算法搜索時間過長的問題。改進的個體差異策略的基本思想是動態地、根據當前狀況自適應地進行信息量更新，調整不同路徑上的信息量分布，在加速收斂速度的同時避免過早陷入局部最優解。

筆者在算法中引入了種群中的個體差異性，每個螞蟻選路的概率函數ρ中的參數α和β值并非完全相同，而且還將在算法每輪循環執行后不斷變化。在這種算法中，螞蟻的行為策略是多樣性的。HSIV算法模擬了自然界中種群同類中的個體差異，不同選路策略的螞蟻間相互作用，可得到比單一策略蟻群更好的解。

在HSIV算法的每輪循環中，修改得到最優解的螞蟻的α和β參數，漸進加重信息素在選路的概率函數ρ中的作用，相應減小距離在選路的概率函數ρ中的作用，稱這種方法為獎勵機制，同時修改得到的最差解。這種機制可以在蟻群中實現不同選路策略的螞蟻協同工作。模擬實驗表明，此算法在許多情況下可以提高收斂速度以及解的質量。在st70的實驗中，僅在第22輪便得到了最優解，而且得到的解為677．109 6，優于TSPLIB給出的解678．59。

在HSIV算法中，螞蟻選路的概率函數ρ中的參數α和β分別初始化為1和5。在這種機制下，選路初始時距離的因子將起到主要作用。在每輪循環結束后應用獎勵機制，調整選路最好的螞蟻參數α和β值，提高信息素對ρ的影響。為說明兩個參數對解的影響，筆者特作以下證明：在式(1)中，用ρ(α)表示螞蟻k在兩城市之間(i， j)上信息素的參數為α時的概率函數值;用ρ(α+1)表示螞蟻k在兩城市之間(i， j)上信息素的參數為α+1時的概率函數值。

由上式可以推出：隨著信息素濃度的增加，相應增加信息素參數α的值，則該路徑被選中的概率就越大。同理可證減小距離參數β的值也可使該路徑被選中的概率增大。通過本文的實驗也證明了上述推導。所以本文將程序中每次選路后得到最短路徑的螞蟻的概率ρ中的α值增大，即增加概率中信息素的作用；相應地減小β值，即減小概率中距離因子的作用。在模擬實驗中發現：a)在對選路最好的螞蟻參數進行調整時，改變策略后被選中的螞蟻在信息素更新時濃度增大，此時增大參數α的值，同時降低了距離因子在選路中的作用將使好的解被再次選中的幾率加大。b)有一些螞蟻可能不只在一輪中得到最優解，這樣筆者在獎勵機制中設定加倍獎勵機制，對已經改變策略的螞蟻在再次得到最優解時，增加信息素在概率中的作用。模擬實驗表明這種機制下得到的解更優。

從一系列模擬實驗結果中發現，改進的蟻群算法雖然有較強的發現較好解的能力，但隨TSP城市規模的擴大和城市數量的增加，問題求解更為復雜，最終找到的可能只是可行的較好解。所以在算法中加入了局部優化算法2－opt[3]對所求的解作進一步優化，模擬實驗表明這種改進加快了收斂速度。

2．2改進的HSIV算法的模型及實現

在算法中以文獻[8]提出的算法HBACA模型為基礎，并定義了四種行為模式：

a)使式（1）中的參數α為0，即所有螞蟻按信息素的強度進行選路。

b)使式（1）中的參數β為0，即所有螞蟻按貪婪方式（按距離）進行選路。

c)按式（1）進行選路。

d)按個體差異策略進行選路，提高α的值，增大信息素在選路中的作用；同時降低β的值，減小距離因子在選路中的作用。

將四種策略按0．5:0．1:0．4:0．45的比例來設置蟻群的行為策略，算法的性能最好[8]。

HSIV算法描述如下：

3實驗結果和分析

筆者進行了一系列模擬實驗，比較了ACO與HSIV的性能、收斂速度和求解能力。實驗的硬件平臺是賽揚2．0 GHz的PC機，內存為256 MB，操作系統為Windows 2000 Server，開發工具為VC++ 6．0。程序中使用實例均選自通用TSPLIB（ftp://ftp.iwr.uni－heidelberg.de/iwr/comopt/soft/TSPLIB95/TSPLIB.html）。

在表1中分別列出了ACO和HSIV在求解相同TSP時的解路徑長度。其中：TSPLIB最優解為TSPLIB提供的最佳路徑的運算結果，括號內的值是TSPLIB庫中給出的已知城市的最優解值；NC為最大循環次數，最短解路徑為基本蟻群算法和帶個體差異的蟻群算法在10次測試中采用不同參數組合求得解中的最短路徑長度；平均解路徑結果是取10次模擬實驗中的平均值。標準偏差為所求最短路徑與TSPLIB提供的最佳路徑運算結果之差再除以TSPLIB提供的最佳路徑運算結果的百分比。表中“—”表示無偏差。

由表1可以看出，HSIV算法在收斂速度和最佳解路徑的結果兩方面都要優于基本蟻群算法。在實驗中對于不同問題設定的m和ρ的值都不相同。通過實驗發現這些參數的調整對解路徑的值有很大影響，而這些值的設定又有一定的隨機性。模擬實驗結果表明：通常在程序中螞蟻數量m的值取為

城市規模，ρ取值0．5~0．99，在此設定下解值較好[4]。

在表2中列出了ACO和HSIV在不同限定條件下求解相同TSP時得到的解路徑長度。其中：NC為算法中最大循環次數；解路徑長度是ACO和HSIV算法所求得的最短路徑的長度。

由表2可以看出，HSIV算法在循環次數較小的情況下就能很快得到最優解，獲取最優解的能力和速度都遠遠超過基本蟻群算法。

4結束語

本文對基本蟻群算法提出了改進，在通過增加螞蟻選路策略多樣性提高蟻群收斂速度以及優化蟻群算法實現效率等方面，得到了一些有意義的結果。但在參數選擇時有一定偶然性，缺乏理論指導。有關混合算法和參數自適應選擇的研究，將有望進一步提高基本蟻群算法的運行效率。

參考文獻：

[1]DORIGO M， MANIEZZO V， COLORNI A. The ant system: optimization by a colony of cooperating agents[J]. IEEE Trans on Systems， Man， and Cybernetics: Part B， 1996，26(1):1－13.

[2]COLORNI A， DORIGO M， MANIEZZO V. Distributed optimization by ant colonies[C]//VARELA F， BOURGINE P. Proc of ECAL’91 European Conf of Artificial Life.Paris:Elsevier， 1991:134－144.

[3]DORIGO M， GAMBARDELLA L M. Ant colony system: a cooperative learning approach to the traveling salesman problem[J]. IEEE Trans on Evolutionary Computation， 1997，1(1):53－66.

[4]MERKLE D， MDIDDENDORF M， SCHMECK H. Ant colony optimization for resource－constrained project scheduling[J]. IEEE Trans on Evolutionary Computation， 2002，6(4):333－339.

[5]TALBI E G， ROUX O， FONLUPT C， et al. Parallel ant colonies for the quadratic assignment problem[J]. Future Generation Compu－ter Systems， 2001，17(4):441－449.

[6]吳斌，史忠植.一種基于蟻群算法的TSP問題分段求解算法[J].計算機學報，2001，24(12):1328－1333.

[7]吳慶洪，張紀會，徐心和.具有變異特征的蟻群算法[J].計算機研究與發展，1999，36(10):1240－1245.

[8]胡小兵，黃席樾.基于混合行為蟻群算法的研究[J].控制與決策，2004，20(1):69－72.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”