陳文卓，劉 萍，姜 豐，曹春雨

(華北科技學院,北京 東燕郊 065201)

0 引言

隨著5G、人工智能算法、無線傳感網(wǎng)絡的發(fā)展，機器人的應用場景更加多樣化，例如自然災害、防爆排爆、醫(yī)療健康、公共服務等。其中在高危環(huán)境下救援機器人存活能力、運動能力、通訊能力和作業(yè)能力等指標成為衡量這一領(lǐng)域性能的關(guān)鍵，尤其是如何在最短時間內(nèi)確定運動路徑以提高工作效率。蟻群算法具有分布式計算、魯棒性強、強大的全局搜索能力以及易于與其它方法相結(jié)合等優(yōu)點，可廣泛應用于組合優(yōu)化、網(wǎng)絡優(yōu)化、路徑規(guī)劃、機器學習等領(lǐng)域。作為一種啟發(fā)式的算法，蟻群算法中啟發(fā)因子等參數(shù)極大地影響著算法性能，同時參數(shù)初始值的設置對收斂速度至關(guān)重要。因此，參數(shù)優(yōu)化問題成為近年來研究蟻群算法方向的熱點。

目前，學者對蟻群算法參數(shù)優(yōu)化進行了多方面、多領(lǐng)域的研究，文獻[1]提出一種新的信息素更新規(guī)則，再對信息殘留因子進行實驗，找到重要參數(shù)在該信息素更新規(guī)則下的最佳合理值；文獻[2]在基本蟻群算法的基礎上對其路徑選擇策略、啟發(fā)函數(shù)和信息素更新策略進行改進，為地鐵疏散人群求解最優(yōu)疏散路徑。文獻[3]采用一種依據(jù)方向指導信息來優(yōu)化初始信息素的分布，通過優(yōu)化信息素的揮發(fā)和更新規(guī)則來改善算法性能的改進蟻群算法，對機器人在復雜環(huán)境下的路徑規(guī)劃具有時效性和適應性；文獻[4]運用多目標分配的精英蟻群算法對配送路徑進行優(yōu)化，信息素的規(guī)則中參數(shù)進行改進，算法在配送路徑規(guī)劃中表現(xiàn)出極高的正確性和可行性；文獻[5]中針對中央空調(diào)冷凍水系統(tǒng)存在的的問題，提出遺傳蟻群算法綜合優(yōu)化控制策略，利用遺傳算法對參數(shù)進行優(yōu)化，使冷凍水系統(tǒng)更節(jié)能、更穩(wěn)定。

以上研究均采用改進算法結(jié)構(gòu)的方法優(yōu)化參數(shù)進而提高算法性能，使用時需要廣泛搜集各種環(huán)境、任務等信息以確定算法中使用的各個參數(shù)值，計算復雜度高，不具有高效性和廣泛適用性。

因此本文利用單因素法從基本蟻群算法入手，僅針對螞蟻數(shù)目m、救援點數(shù)n，信息素揮發(fā)因子ρ、信息素啟發(fā)式因子α、距離啟發(fā)式因子β、信息素強度Q這些參數(shù)分別進行定性數(shù)據(jù)對比，通過實驗仿真驗證，最終確定出簡單易設的最優(yōu)參數(shù)組合。

1 蟻群算法數(shù)學模型

蟻群算法是基于生物的人工智能算法[6]，不需要復雜的數(shù)學模型就可以完成隨機搜索，因此容易實現(xiàn)。其算法原理是：起初人工螞蟻進行單獨搜索，并分泌信息素在群體間進行信息交流。人工螞蟻留在路徑上的信息素越多，路徑被選的概率越大。人工螞蟻信息傳遞的行為實際體現(xiàn)了信息的正反饋[7]，每次遍歷完，信息素都會進行全局更新，從而保證隨機搜索特征。經(jīng)過多次迭代，最終找到遍歷所有點的最短距離的路徑，從而提高搜救效率。

本文以m只螞蟻求解遍歷n個救援點最短路徑的TSP問題的基礎，蟻群算法模型主要包括兩部分：螞蟻在救援點間轉(zhuǎn)移規(guī)則和信息素更新規(guī)則。在蟻群系統(tǒng)中轉(zhuǎn)移規(guī)則如下:

(1)

α為信息素啟發(fā)因子，表示信息素在螞蟻選擇中的重要程度；τij為邊(i,j)上的信息素濃度。β為距離啟發(fā)因子；ηij為視距函數(shù)，表示由救援點i轉(zhuǎn)移到救援點j的可見度，通常η表示救援點i到救援點j的歐式距離dij倒數(shù)，即：

(2)

在此基礎上設置禁忌列表，用以記錄螞蟻k走過的救援點，避免螞蟻走回頭路，在遍歷完所有救援點一周之前不會被清零。此外，為了使螞蟻的隨機搜索能力能夠逐步優(yōu)化改進，每只人工螞蟻遍歷所有救援點一次后進行全局信息素更新，更新公式如下：

τij(t+1)=(1-ρ)τij+Δτij

(3)

式中，Δτij根據(jù)蟻周模型表示為：

(4)

式中，Lk表示螞蟻K在這次遍歷中所走過的路徑長度，Q為常數(shù)，表示信息素強度。

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

由文獻[8]可知，螞蟻的數(shù)量的增多能夠降低蟻群算法搜索的盲目性。在蟻群算法中，螞蟻數(shù)目m與救援點數(shù)目n的比例關(guān)系的取值，影響算法的全局搜索能力和收斂速度。當m與n的比值過大時,每條路徑上的信息素濃度差距很微弱，螞蟻對于信息素的預判困難從而導致蟻群收斂速度降低；當m與n的比值過小時，不僅導致螞蟻探索其他路徑的能力降低，而且因為各條路上來往的螞蟻數(shù)少，使得各條路上的信息素的差距降低，進而影響蟻群的收斂速度。

信息素啟發(fā)因子α反映了螞蟻在運動過程中所積累的信息素的量在指導蟻群搜索中的相對重要程度；由文獻[9]可知，α的取值過大導致螞蟻在選擇下一個救援點時，會將該條路上的信息素濃度作為首要考慮因素，蟻群將失去路徑探索能力從而陷入局部最優(yōu)。α的取值過小會導致螞蟻在選擇路徑時，信息素濃度的作用降低，雖然加了螞蟻探索新路徑的能力，但是降低了蟻群的收斂速度。

啟發(fā)函數(shù)因子β反映了距離啟發(fā)信息對于算法搜索的重要程度；β的取值大小影響螞蟻在選擇時對于路徑長度的重視程度，從而影響算法的收斂速度。

通過觀察自然界的螞蟻所遺留的信息素可知，信息素濃度會隨著時間的推移逐漸揮發(fā)，因此在算法中添加了信息素揮發(fā)系數(shù)ρ來對信息素揮發(fā)的程度定性分析。當ρ設置過大時，算法中的信息素揮發(fā)較快，導致各條路上的信息素濃度的差距降低，從而降低算法的收斂速度；當ρ設置較小時，信息素的揮發(fā)較慢，各條路上的信息素堆積，導致信息素對于路徑選擇的正反饋性能減弱。

信息素強度Q是螞蟻在完成一次遍歷的過程中遺留的信息素的總量。Q是正反饋機制的重要指標，Q越大，正反饋機制在螞蟻路徑選擇中的主導作用越能凸顯。

3 最優(yōu)參數(shù)組合的確定

當災害發(fā)生后，根據(jù)災害現(xiàn)場的情況確定出救援機器人執(zhí)行搜救巡檢任務的區(qū)域范圍，同時結(jié)合地理環(huán)境信息構(gòu)建二維平面的運動地圖模型。設定救援機器人從救援區(qū)域的任意一點作為起始點，利用蟻群算法遍歷所有救援點完成執(zhí)行任務之后返回起點，力圖在最短時間內(nèi)高效完成任務，獲得最優(yōu)的可行路線。

為得到每個參數(shù)的最優(yōu)取值，并對其在救援機器人實行路徑規(guī)劃的精確性進行檢驗，在此以實際的礦井二維救援點平面圖圖1為例，利用單因素法進行救援機器人基本蟻群算法的路徑規(guī)劃。

圖1 救援點地圖二維模型

在進行路徑模擬前，根據(jù)公式(1)～(4)所示數(shù)學模型，并結(jié)合上述因素限制，在考慮蟻群算法自身特點的情況下,算法參數(shù)范圍分別選取為α∈(0,5]，β∈(0,5]，ρ∈(0,0.99]，Q∈[10,1000]，m=(1～5)n。在此范圍內(nèi)以單因素法, 分別對數(shù)學模型中提及的蟻群算法參數(shù)α、β、ρ和Q以及建立蟻群算法規(guī)模的m和n進行多次仿真實驗，確定蟻群算法的最優(yōu)參數(shù)組合范圍。

每次實驗在利用蟻群算法進行路徑模擬規(guī)劃的初始時刻，如圖2所示，首先設置初始參數(shù)(6個參數(shù)中，每次模擬只改變其中一個參數(shù)的值)。然后將每個被訪問過的救援任務點加入禁忌列表，因此此時螞蟻將根據(jù)當下時刻救援任務地圖各救援點信息素濃度選擇應該前往的下一個救援點，直到禁忌列表被填滿。然后，更新規(guī)劃路徑上的信息素，輸出該參數(shù)在單因素法中迭代路徑長度的最優(yōu)解，之后清空禁忌列表，作為一次迭代結(jié)束。為保證算法的全局規(guī)劃能力，每次實驗進行2000次的迭代。從而獲得該參數(shù)在此救援地圖中的最優(yōu)取值，重復上述步驟，最終獲得所有參數(shù)的組合最優(yōu)解。

圖2 單因素蟻群算法流程圖

4 實驗仿真

根據(jù)之前分析，首先設置ρ=0.5，Q=200，m=50，n=50為初始固定參數(shù)，控制變量α在0～5范圍內(nèi)以0.25為間距進行變化，每個α的取值都對應β∈[0，0.25，0.5， ... 4.75,5]進行實驗仿真，結(jié)果如圖3所示。

圖3 α、β對路徑規(guī)劃算法的影響圖

由圖3可以看出，當α和β在1～2區(qū)間時，在此區(qū)域內(nèi)迭代距離下沉明顯且集中，這表明蟻參數(shù)取在該范圍內(nèi)，算法能快速迭代出最短距離，算法性能最佳。

蟻群算法中螞蟻數(shù)目m與救援點數(shù)目n的比例關(guān)系的取值，影響算法的全局搜索能力和收斂速度。當m與n的比值過大時,螞蟻對于信息素的預判困難從而導致蟻群收斂速度降低；當m與n的比值過小時，使得各條路上的信息素的差距降低，進而影響蟻群的收斂速度。以α=1，β=2，ρ=0.5，Q=200為初始值，該實驗分別設置n=50和n=20，結(jié)果如圖4、圖5所示。

圖4 n=50時m對路徑規(guī)劃算法的影響曲線

圖5 n=20時m對路徑規(guī)劃算法的影響曲線

將圖4和圖5進行對比可知，螞蟻數(shù)對蟻群算法的搜索性能的影響并不是單一的比較螞蟻的個數(shù)。當螞蟻數(shù)未超過救援點數(shù)時，也就是m小于n，即m/n<1時，實驗迭代次數(shù)多，算法性能相對較差，難以迭代出最短距離；在當螞蟻數(shù)大于或等于救援點數(shù)時，即m/n∈[1,3]時，迭代次數(shù)最少且實驗結(jié)果相對穩(wěn)定，算法性能較好算法均能迭代出最短路徑。因此可得出螞蟻數(shù)對算法性能的影響與救援點數(shù)n有比例關(guān)系，由圖5看出，m/n>3時，迭代次數(shù)上下波動，算法性能不穩(wěn)定，而在螞蟻數(shù)時救援點數(shù)的一倍到三倍之間迭代次數(shù)相對最少，所以推知m與n存在最優(yōu)比例為m/n∈[1,3]。

同時利用信息素濃度中的信息素揮發(fā)系數(shù)ρ可以對信息素揮發(fā)的程度定性分析。在α=1，β=2，Q=200，m=50,n=50為初始值的條件下，對ρ進行實驗仿真，結(jié)果如圖6所示：

圖6 ρ對路徑規(guī)劃算法的影響曲線

由圖6可知，隨著ρ的不斷增大，變化算法迭代次數(shù)呈現(xiàn)先降低后增加的趨勢，總體來看，算法迭代性能較好的取值集中在0.2～0.7區(qū)間內(nèi)，其中ρ取0.5時迭代次數(shù)最少，算法性能最佳，能體現(xiàn)出螞蟻的全局搜索和快速收斂的能力。

信息素強度Q是螞蟻在完成一次遍歷的過程中遺留的信息素的總量。Q是正反饋機制的重要指標，Q越大，正反饋機制在螞蟻路徑選擇中的主導作用越能凸顯。在α=1，β=2，ρ=0.5，m=50，n=50為初始值條件下，對Q進行仿真分析。

圖7 Q對路徑規(guī)劃算法的影響曲線

由圖7可知，Q的取值隨著迭代次數(shù)的增加而改變，時大時小，但是從整體發(fā)展趨勢中可以發(fā)現(xiàn)，當Q取200時，迭代次數(shù)是Q取值范圍內(nèi)的最小值，此時獲得最佳性能。

綜上，對基于同一環(huán)境信息進行路徑規(guī)劃的以上參數(shù)，在每條影響曲線圖中找到路徑最短或迭代次數(shù)最少時對應的范圍，得到基本蟻群算法參數(shù)組合選取范圍為α∈[1,2]、β∈[1,2]、ρ∈[0.4,0.6]、Q∈[150,250]且m=(1～3)n。

為驗證這一組合范圍的性能，選取參數(shù)全部優(yōu)化的組合與未優(yōu)化做對比，觀察其路徑長度和迭代次數(shù)。如表1所示，在針對采用優(yōu)化組合參數(shù)使得救援機器人進行規(guī)劃路徑時僅需要迭代次數(shù)89次，遠遠少于僅優(yōu)化螞蟻數(shù)目m和救援點數(shù)n的參數(shù)組合，且規(guī)劃距離長度僅取3687M更少，且走過的路徑長度更短。因此對于參數(shù)組合優(yōu)化的更為合理，實用性更高。

表1 優(yōu)化參數(shù)組合與部分參數(shù)優(yōu)化組合的路徑規(guī)劃結(jié)果對比

5 結(jié)論

(1) 針對蟻群算法參數(shù)對算法性能的影響問題，基于研究旅行商問題的全局路徑規(guī)劃算法，運用單因素法對蟻群算法參數(shù)進行實驗對比，分析了各參數(shù)對于算法路徑尋優(yōu)效率的影響，并得出在此類問題上各個參數(shù)的取值范圍。

(2) 通過仿真結(jié)果證明了使用優(yōu)化參數(shù)組合后，能夠大幅度的提高救援機器人的路徑搜索和自主運動能力，節(jié)約任務執(zhí)行時間，提高了救援機器人參與實際作業(yè)的效率。同時為機器人優(yōu)化路徑規(guī)劃提供了有力的理論依據(jù)和數(shù)據(jù)支持。