基于參數(shù)組合優(yōu)化的救援機(jī)器人蟻群算法研究

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

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

0 引言

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

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

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

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

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

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

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

(1)

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

(2)

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

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

(3)

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

(4)

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

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

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

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

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

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

信息素強(qiáng)度Q是螞蟻在完成一次遍歷的過(guò)程中遺留的信息素的總量。Q是正反饋機(jī)制的重要指標(biāo)，Q越大，正反饋機(jī)制在螞蟻路徑選擇中的主導(dǎo)作用越能凸顯。

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

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

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

圖1 救援點(diǎn)地圖二維模型

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

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

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

4 實(shí)驗(yàn)仿真

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)論

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

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