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

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

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

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

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

蟻群算法；數學模型；任務分配

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

1.蟻群算法原理

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

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

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

2.蟻群算法的參數分析

2.1 蟻群數目m

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

2.2 揮發系數ρ

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

2.3 啟發因子α

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

2.4 啟發因子β

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

3.蟻群算法的求解步驟

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

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

（6）根據公式計算選擇任務j的轉移概率；

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

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

（9）更新信息素；

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

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

圖1

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

設定靜止目標數量為4個，坐標分別位于（3，4），（9，8），（11，13）和（16，17）。可執行任務的AUV數量為4個，坐標分別位于（1，1），（2，2），（10，10）和（120，12）。螞蟻數量m=10，啟發因子α=1，啟發因子β=5，揮發系數ρ=0.6，釋放的信息素的總量Q=100，最大循環次數Nc max=200。

設置參數完成后，進行Matlab仿真，通過多次仿真，最好仿真結果如圖2所示：

圖2

仿真的結果顯示，最好情況下，第一個機器人執行第一個和第二個任務，第二個機器人執行第三個任務，第四個機器人執行第四個任務。但不是每次都能得到最優情況，且即使兩次結果都取到最優值時，所經過的路程也不同。