沈陽理工大學自動化與電氣工程學院 伊文康 曹 帥

蟻群算法中的主要參數(shù)對任務(wù)分配問題影響的分析

沈陽理工大學自動化與電氣工程學院 伊文康 曹 帥

該文主要針對多機器人的任務(wù)分配問題，對蟻群算法的主要參數(shù)進行介紹和分析。首先對蟻群算法進行介紹，并對蟻群算法中的參數(shù)進行分析和選擇，最后根據(jù)選定的參數(shù)對算法進行仿真驗證。

蟻群算法；數(shù)學模型；任務(wù)分配

螞蟻可以說是人類最常見、數(shù)量最龐大的昆蟲之一，它們常常成群結(jié)隊地出現(xiàn)在人類的日常生活環(huán)境中。這些昆蟲群體生物智能方面的特征，于是引起了一些學者的注意。意大利學者M.Dorigo，V.Maniezzo等人在觀察螞蟻的覓食習性時發(fā)現(xiàn)，螞蟻總能找到巢穴與食物源之間的最短路徑。經(jīng)研究發(fā)現(xiàn)，螞蟻的這種群體協(xié)作功能是通過一種遺留在其來往路徑上的叫做”信息素”的揮發(fā)性化學物質(zhì)來進行通信和協(xié)調(diào)的。通過對螞蟻覓食行為的研究，他們發(fā)現(xiàn)，整個蟻群就是通過這種信息素進行相互協(xié)作，形成正反饋，從而使多個路徑上的螞蟻都逐漸聚集到最短的那條路徑上。

1.蟻群算法原理

根據(jù)前面的螞蟻留下的分泌物，螞蟻會選擇相應(yīng)的路徑[21]。在該路徑上放電的強度越大相應(yīng)的螞蟻選擇這條路徑的概率也就越大。因此，這種集體行為可以理解為一種正反饋現(xiàn)象，即由螞蟻群體構(gòu)成的一種積極的學習信息的反饋現(xiàn)象：后面的螞蟻是否選擇某一條路徑取決于在這條路上走過的螞蟻數(shù)量，數(shù)量越大，后面螞蟻選擇該條路徑的概率越大。螞蟻就是這樣選擇最短路徑的。

蟻群算法通過將螞蟻覓食行為轉(zhuǎn)化為一種優(yōu)化算法再用來求解最優(yōu)解[22]。這樣的方法與一般的編程模式不同，有自己的明顯優(yōu)點，可以在一定程度上減少程序的代碼量，而算法本身通過事先設(shè)定好的規(guī)則迭代尋找問題的最優(yōu)解。代表的含義就是如果算法在最開始尋找到的目標一般情況下都不是最優(yōu)的解決策略，而且也很有可能帶有不正確的決策策略。但通過算法的進行，利用螞蟻覓食過程中釋放的信息素，不斷接近最優(yōu)路徑，即解決問題的最短路徑，這就意味著，隨著程序的不斷執(zhí)行，決策的最優(yōu)路徑與問題的最優(yōu)路徑逐漸接近。這似乎看起來像我們數(shù)學中學的歸納概括方法一個具體應(yīng)用。程序本身在運行的同時也在不斷的進行學習[23]。

通過模仿螞蟻的行為，蟻群算法實現(xiàn)優(yōu)化。但是該算法不同于傳統(tǒng)的編程模型，它的優(yōu)點是明顯的，即為了避免長的編程和規(guī)劃，程序本身是基于一定的規(guī)則來找到隨機運行的最佳解決方案[24]。也就是說，如果在一個計劃中在一開始便找到目標，那么它的路徑幾乎不可能是最優(yōu)的路徑，甚至可能包含無數(shù)的錯誤選擇和非常冗長的過程。然而，可以通過在程序中采用螞蟻搜索食物時的信息素的原則，繼續(xù)修改原來的路線，也就是說，若程序執(zhí)行時間較長，路徑更接近最優(yōu)的路徑。這看起來像是很多的例子總結(jié)而形成的最佳路徑。然而事實上，它是一個自我學習的過程[25]。

2.蟻群算法的參數(shù)分析

2.1 蟻群數(shù)目m

通常情況下人們可能普遍認為蟻群數(shù)目越大相應(yīng)的搜索速度越快，但并非如此。初始螞蟻的數(shù)目m越大，相應(yīng)的蟻群算法在全局的收斂性就會越強，但當螞蟻數(shù)目m達到一定程度后，會發(fā)現(xiàn)之前螞蟻留下的信息素在搜索過程中變化不明顯，會影響接下來螞蟻的判斷會走很多彎路影響蟻群算法的收斂速度，但螞蟻數(shù)目m也不能過小，m過小意味著算法的全局搜索性減弱，收斂速度過快，可能造成蟻群算法穩(wěn)定性降低。所以要根據(jù)實際問題選擇合適的數(shù)目m。

2.2 揮發(fā)系數(shù)ρ

揮發(fā)系數(shù)ρ直接影響蟻群算法的全局搜索能力和收斂速度[31]；各個螞蟻之間的相互影響作用可以用（1-ρ）代表的剩余信息素表示，其值越大信息更新的效率就會受到影響，進而算法的收斂速度相應(yīng)減慢；其值越小搜索的多樣性減少，可能導致陷入局部最優(yōu)值，算法收斂速度過快[32]。

2.3 啟發(fā)因子α

α代表某個螞蟻在某個經(jīng)過的路徑上留下的信息素被重視的程度。其值越大對螞蟻選擇這條路徑的影響就越大，但減少了選擇的多樣性。其值低，容易導致陷入局部最優(yōu)。

2.4 啟發(fā)因子β

啟發(fā)因子β稱為期望啟發(fā)因子，代表螞蟻遺留下來的啟發(fā)信息的重要程度，β越大，螞蟻選擇離它近的城市概率越大就是找到局部最優(yōu)路徑的概率越大，加快了收斂速度，但選擇多樣性減少。

3.蟻群算法的求解步驟

基本蟻群算法主要有以下幾個步驟：

（2）初始化位置：輸入機器人初始位置坐標；

（6）根據(jù)公式計算選擇任務(wù)j的轉(zhuǎn)移概率；

（7）移動機器人到轉(zhuǎn)移概率最大的點，并記錄到禁忌表中；

（8）如果沒有訪問所有城市，跳轉(zhuǎn)到（5），反之，轉(zhuǎn)至（9）；

（9）更新信息素；

（10）判斷是否滿足終止條件，若滿足輸出結(jié)果，否則清空禁忌表并轉(zhuǎn)到（4）。

蟻群算法的流程圖如圖1所示：

圖1

4.基于蟻群算法的Matlab仿真

設(shè)定靜止目標數(shù)量為4個，坐標分別位于（3，4），（9，8），（11，13）和（16，17）?？蓤?zhí)行任務(wù)的AUV數(shù)量為4個，坐標分別位于（1，1），（2，2），（10，10）和（120，12）。螞蟻數(shù)量m=10，啟發(fā)因子α=1，啟發(fā)因子β=5，揮發(fā)系數(shù)ρ=0.6，釋放的信息素的總量Q=100，最大循環(huán)次數(shù)Nc max=200。

設(shè)置參數(shù)完成后，進行Matlab仿真，通過多次仿真，最好仿真結(jié)果如圖2所示：

圖2

仿真的結(jié)果顯示，最好情況下，第一個機器人執(zhí)行第一個和第二個任務(wù)，第二個機器人執(zhí)行第三個任務(wù)，第四個機器人執(zhí)行第四個任務(wù)。但不是每次都能得到最優(yōu)情況，且即使兩次結(jié)果都取到最優(yōu)值時，所經(jīng)過的路程也不同。