初始信息素不均勻分布的蟻群算法

薛永才，古姝祺，張均富*

（1.西華大學(xué)機(jī)械工程學(xué)院,四川 成都 610039；2.成都市自來(lái)水有限責(zé)任公司，四川 成都 610031）

路徑規(guī)劃是移動(dòng)機(jī)器人的一項(xiàng)重要研究?jī)?nèi)容。機(jī)器人路徑規(guī)劃首先利用機(jī)載傳感器獲取機(jī)器人位置及環(huán)境信息，然后由規(guī)劃算法自主規(guī)劃出一條能避開(kāi)障礙物并到達(dá)目標(biāo)位置的可行安全路徑。目前常用的路徑規(guī)劃算法可分為傳統(tǒng)規(guī)劃算法和智能規(guī)劃算法。傳統(tǒng)規(guī)劃算法包括可視圖方法、人工勢(shì)場(chǎng)方法等；智能規(guī)劃算法包括遺傳算法、蟻群算法等[1]。

蟻群算法是模擬自然界螞蟻覓食過(guò)程而提出的仿生智能優(yōu)化算法。算法基本思想是螞蟻在覓食的過(guò)程中分泌信息素用以指導(dǎo)后續(xù)經(jīng)過(guò)該路徑的螞蟻進(jìn)行路徑選擇，路徑越短，螞蟻留下的信息素也越多，螞蟻選擇更短路徑的概率也越大，從而可以讓蟻群找到一條到食物位置的最短路徑[2]。

蟻群算法具有群體智能和正反饋特性，其尋路能力強(qiáng)，但存在收斂性差、易陷入局部最優(yōu)解等缺點(diǎn)。其初始信息素分布直接影響算法的收斂性及收斂速度。針對(duì)該問(wèn)題，學(xué)者們提出了多種改進(jìn)方法。丁建立等[3]提出了一種遺傳算法與蟻群算法相結(jié)合的初始信息素分配策略，采用遺傳算法得到路徑信息，再根據(jù)該信息與原始初始信息疊加作為信息素初值，將其應(yīng)用于旅行商問(wèn)題，得到了較好效果，但未應(yīng)用于存在障礙物的地圖類(lèi)路徑規(guī)劃。楊樂(lè)[4]依據(jù)零點(diǎn)定理提出了一種初始信息素不均衡分配策略，其目的在于增強(qiáng)起始節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)間的所有節(jié)點(diǎn)的初始信息素，這對(duì)起點(diǎn)與終點(diǎn)所在直線上障礙物少的情況有較好提升效果。Verdaguer等[5]提出了采用有界信息素來(lái)解決搜索最優(yōu)解失敗的情況，其提出的蟻群算法提高了搜索效率，但未應(yīng)用于存在障礙物的地圖類(lèi)路徑規(guī)劃。Luo 等[6]結(jié)合當(dāng)前節(jié)點(diǎn)、下一個(gè)節(jié)點(diǎn)以及起點(diǎn)與終點(diǎn)之間的距離等因素計(jì)算得出初始信息素初值，從而得到不均勻的初始信息素，但沒(méi)有考慮到障礙物分布對(duì)搜索的影響。何雅穎[7]提出了一種初始信息素增強(qiáng)方法，其根據(jù)環(huán)境障礙占比的多少而調(diào)整橢圓區(qū)域的大小，并將橢圓形內(nèi)節(jié)點(diǎn)作為初始信息素增強(qiáng)區(qū)域，該方法考慮了障礙物的多少，但未考慮實(shí)際障礙物分布情況對(duì)搜索的影響。

可見(jiàn)，初始信息素的合理分配是提升蟻群算法尋優(yōu)性能的方法之一。為此，本文提出一種基于雙向搜索構(gòu)建初始信息素增強(qiáng)區(qū)域的初始信息素不均勻分配策略，從而改善前期搜索的盲目性，提升蟻群算法前期收斂性。

1 蟻群算法基本原理

1.1 算法基本流程

傳統(tǒng)蟻群算法包括參數(shù)初始化、禁忌表更新及走向確定、信息素更新等核心步驟。

1）參數(shù)初始化。初始化所有節(jié)點(diǎn)信息素T、初始禁忌表，設(shè)置起點(diǎn)終點(diǎn)位置、螞蟻數(shù)量m、迭代次數(shù)L、信息素重要程度 α、啟發(fā)式信息重要程度 β、信息素蒸發(fā)系數(shù) ρ、信息素增強(qiáng)系數(shù)Q[8]。

2）禁忌表更新及走向確定。在算法開(kāi)始時(shí)，將螞蟻放置于起始點(diǎn)，出動(dòng)螞蟻開(kāi)始尋路。螞蟻尋路時(shí)，每只螞蟻在任意時(shí)間t選擇下一移動(dòng)節(jié)點(diǎn)時(shí)均根據(jù)轉(zhuǎn)移概率公式進(jìn)行移動(dòng)，其表達(dá)式為

式中：i表示當(dāng)前所在點(diǎn)；j表示下一個(gè)可移動(dòng)點(diǎn)；Jk(i)表示螞蟻所有的下一個(gè)可移動(dòng)點(diǎn)組成的集合；τij(t)表 示在時(shí)間t時(shí) 刻從節(jié)點(diǎn)i到 節(jié)點(diǎn)j該條路徑上的信息素濃度；ηij(t)表 示在時(shí)間t時(shí)刻時(shí)所在位置j的啟發(fā)式信息，在傳統(tǒng)算法中，啟發(fā)式信息為節(jié)點(diǎn)到下一可行節(jié)點(diǎn)直線距離的倒數(shù)。

3）信息素更新。當(dāng)一次迭代中的所有螞蟻均完成尋路后，各路徑上的信息素按式（2）進(jìn)行更新。

式中，?τij表 示在該次迭代中邊ij上信息素的增量，其表達(dá)式為

其中，?τijk表示第k只螞蟻在本次迭代中留在邊ij上的信息素。如果螞蟻k沒(méi)有經(jīng)過(guò)邊ij，則?τijk的值為0。? τijk有3 種模型，分別為ant-cycle 模型、ant-density 模型、ant-quantity 模型。其中，ant-cycle模型具有更好的性能，因?yàn)閍nt-cycle 模型利用全局信息進(jìn)行信息素的更新，其余2 種采用局部信息進(jìn)行更新，故蟻群算法通常采用ant-cycle 模型。antcycle 模型表達(dá)式為

式（4）重復(fù)迭代，輸出結(jié)果：當(dāng)一次迭代中的所有螞蟻完成尋路后，記錄下該次迭代的最短路徑路線及其長(zhǎng)度。重復(fù)上述步驟，在達(dá)到迭代上限次數(shù)后，最終輸出本次算法迭代出的最優(yōu)路徑路線。

1.2 算法分析

在蟻群算法中，影響螞蟻轉(zhuǎn)移的2 個(gè)關(guān)鍵因素為信息素與啟發(fā)信息。當(dāng)螞蟻有多個(gè)可移動(dòng)點(diǎn)供選擇時(shí)，各點(diǎn)的信息素值與啟發(fā)信息值大小直接影響螞蟻轉(zhuǎn)移時(shí)的移動(dòng)概率，信息素值高、啟發(fā)信息值高的點(diǎn)，螞蟻在概率上會(huì)更傾向于往該點(diǎn)移動(dòng)。

啟發(fā)信息是根據(jù)節(jié)點(diǎn)所在位置決定的，當(dāng)環(huán)境地圖確定后，各節(jié)點(diǎn)的啟發(fā)信息值也相應(yīng)確定且不再變化，故其在傳統(tǒng)算法中，對(duì)螞蟻尋路過(guò)程的影響有限；信息素是根據(jù)初始信息素與后續(xù)更新確定的，同一節(jié)點(diǎn)的信息素會(huì)隨著多輪迭代中螞蟻的移動(dòng)而增加或減少，在同一地圖中，各點(diǎn)的信息素會(huì)不斷地變化，故同一節(jié)點(diǎn)在不同時(shí)刻對(duì)螞蟻的吸引力也可能不同：因此，在傳統(tǒng)算法中，信息素對(duì)螞蟻的影響更大。

蟻群算法中，信息素存在著初始值賦值與后續(xù)更新。初始信息素值會(huì)影響算法的收斂速度與收斂性。傳統(tǒng)蟻群算法中，所有節(jié)點(diǎn)的初始信息素值為同一常數(shù)，不同節(jié)點(diǎn)的信息素在數(shù)值上沒(méi)有差異性，故第一輪的螞蟻尋路中，各個(gè)可轉(zhuǎn)移節(jié)點(diǎn)在信息素上對(duì)螞蟻的影響是相同的，此時(shí)螞蟻依靠節(jié)點(diǎn)啟發(fā)信息值的不同進(jìn)行概率性地移動(dòng)。傳統(tǒng)算法中所有節(jié)點(diǎn)相同初值的信息素分布方式，會(huì)導(dǎo)致蟻群前期搜索盲目、收斂性不強(qiáng)、收斂速度慢等問(wèn)題的出現(xiàn)。

2 初始信息素不均勻分布策略

初始信息素不均勻分布是解決上述問(wèn)題的可行方法。初始信息素不均勻分布的作用在于通過(guò)信息素差值引導(dǎo)蟻群更快地找到最短路徑。其實(shí)現(xiàn)方式是通過(guò)對(duì)地圖進(jìn)行區(qū)域劃分，找出可能存在最優(yōu)路徑的區(qū)域并增強(qiáng)該區(qū)域的初始信息素值，從而使增強(qiáng)區(qū)域與其他普通區(qū)域產(chǎn)生信息素上的數(shù)值差，蟻群在可行節(jié)點(diǎn)間移動(dòng)時(shí)，會(huì)更傾向于向信息素濃度高的區(qū)域移動(dòng)。因此，合理地構(gòu)建初始信息素增強(qiáng)區(qū)域能夠有效地加快算法收斂性能。

對(duì)此，文獻(xiàn)[4]基于零點(diǎn)定理提出了一種初始信息素不均勻分布策略。該算法的核心思想是：在進(jìn)行路徑規(guī)劃時(shí)，當(dāng)起點(diǎn)與終點(diǎn)確定后，若起點(diǎn)與終點(diǎn)連線上不存在障礙物，該連線必定為最短路徑，故基于零點(diǎn)定理，增強(qiáng)起點(diǎn)與終點(diǎn)間所有節(jié)點(diǎn)的信息素值。該算法在起點(diǎn)與終點(diǎn)所在連線上障礙物分布少時(shí)，算法的效果提升較佳，但在障礙物較多時(shí)，效果較差，原因在于該算法沒(méi)有考慮到障礙物分布所產(chǎn)生的影響，導(dǎo)致其對(duì)不同地圖的適應(yīng)性較差。

對(duì)此，本文提出一種基于初始障礙物的初始信息素不均勻分布策略。該策略相較于文獻(xiàn)[4]算法的主要差異在于：該策略考慮了由于障礙物分布不同而導(dǎo)致的可能存在最優(yōu)路徑區(qū)域的變化。該策略會(huì)根據(jù)不同地圖的初始障礙物的不同而劃分出對(duì)應(yīng)的信息素增強(qiáng)區(qū)域，故該種算法對(duì)不同地圖有一定適應(yīng)性，且該策略基于雙向搜索的思想對(duì)起點(diǎn)與終點(diǎn)附近的初始障礙物進(jìn)行了局部路徑尋優(yōu)，進(jìn)一步提高了增強(qiáng)區(qū)域內(nèi)存在最優(yōu)路徑的可能性。

2.1 基本思想

傳統(tǒng)蟻群算法各節(jié)點(diǎn)初始信息素等值，會(huì)導(dǎo)致前期收斂速度慢、搜索盲目。為此，本文結(jié)合雙向搜索策略[9]，提出一種基于初始障礙物初始信息素不均勻分布的策略，以提升算法的收斂速度。

該策略的基本思想如下：首先以節(jié)點(diǎn)A為起始點(diǎn)、B點(diǎn)為目標(biāo)點(diǎn)，沿搜索，遇首個(gè)障礙則開(kāi)展繞障局部路徑搜索，得到最短路徑及其末端節(jié)點(diǎn)C，由節(jié)點(diǎn)C為起點(diǎn)構(gòu)造與AB平 行的直線L1，得到L1與邊界相交的節(jié)點(diǎn)E；然后按照相同原理，以節(jié)點(diǎn)B為起始點(diǎn)、沿搜 索，獲得節(jié)點(diǎn)D和直線L2，以及與邊界相交的節(jié)點(diǎn)F；最后所構(gòu)造出的ACEBDFA的 邊界及其內(nèi)部的封閉區(qū)域即為初始信息素增強(qiáng)區(qū)域，如圖1（a）所示，若2 邊界所在直線L1與L2重合，則表示得到了一條首尾相連的路徑，該路徑所穿越的節(jié)點(diǎn)ACDB所構(gòu)造的區(qū)域即為初始信息素增強(qiáng)區(qū)域，如圖1（b）所示。

圖1 局部尋優(yōu)構(gòu)建信息素增強(qiáng)區(qū)域

2.2 實(shí)現(xiàn)步驟

搜索策略在算法中具體實(shí)現(xiàn)步驟如下。

步驟1，創(chuàng)建記錄表。創(chuàng)建節(jié)點(diǎn)坐標(biāo)記錄表，用以記錄關(guān)鍵節(jié)點(diǎn)位置。

步驟2，探尋首個(gè)障礙物位置。從起始點(diǎn)開(kāi)始，以終點(diǎn)為前進(jìn)方向，找尋第一個(gè)不可行節(jié)點(diǎn)（即碰到第一個(gè)初始障礙物），記錄下遇到障礙物前最后一個(gè)可行節(jié)點(diǎn)位置。

步驟3，對(duì)障礙物進(jìn)行邊界判斷。對(duì)障礙物進(jìn)行邊界搜索，記錄下障礙物邊界節(jié)點(diǎn)。

步驟4，判斷障礙物與起點(diǎn)的相對(duì)位置。進(jìn)行數(shù)值判斷，判斷障礙物是否處于某些特殊位置從而導(dǎo)致特殊情況出現(xiàn)，例如初始障礙物上邊界與地圖上邊界重合，導(dǎo)致螞蟻不能從障礙物上邊界經(jīng)過(guò)，若存在這種特殊情況，則搜索策略跳過(guò)步驟5 進(jìn)入步驟6，否則，進(jìn)入步驟5。

步驟5，判斷局部最優(yōu)路徑方向。進(jìn)行數(shù)值判斷，判斷起點(diǎn)與各障礙物的邊界節(jié)點(diǎn)直線距離大小，距離小的節(jié)點(diǎn)則是繞過(guò)障礙物的最短路徑，記錄下節(jié)點(diǎn)位置。

步驟6，連接局部最優(yōu)路徑。連接節(jié)點(diǎn)表中的關(guān)鍵節(jié)點(diǎn)，得到一條局部最優(yōu)路徑。

步驟7，連接邊界。連接節(jié)點(diǎn)表中的關(guān)鍵節(jié)點(diǎn)，得到一條直線邊界。

步驟8，終點(diǎn)方向與之同理，重復(fù)上述步驟得到另一局部最優(yōu)路徑及邊界。

步驟9，賦值。加強(qiáng)所記錄節(jié)點(diǎn)及2 條邊界內(nèi)所圍成的封閉區(qū)域間的節(jié)點(diǎn)的初始信息素?cái)?shù)值。

步驟10，初始信息素不均勻分布策略結(jié)束，進(jìn)入算法全局路徑尋優(yōu)部分。

步驟11，初始信息素的分布賦值。根據(jù)前述搜索得到的增強(qiáng)區(qū)域按式（5）進(jìn)行不均勻賦值。

式中：T代表信息素；P代表信息素具體的數(shù)值大小。為了體現(xiàn)不同節(jié)點(diǎn)的信息素差異性，增強(qiáng)節(jié)點(diǎn)的信息素值會(huì)大于普通節(jié)點(diǎn)的信息素值。為了避免增強(qiáng)節(jié)點(diǎn)的信息素過(guò)大造成在節(jié)點(diǎn)選擇上陷入局部最優(yōu)情況的出現(xiàn)，同時(shí)為了防止增強(qiáng)信息素過(guò)低導(dǎo)致增強(qiáng)效果不明顯，本文將增強(qiáng)信息素的值限制在普通信息素值的2～5 倍間。

在存在障礙物的地圖中，障礙物的分布決定最優(yōu)路徑的長(zhǎng)度。初始信息素的不均勻分布可以為蟻群提供方向指導(dǎo)，避免盲目性，其實(shí)現(xiàn)原理為增強(qiáng)部分節(jié)點(diǎn)的信息素值，從而在提高蟻群在可行節(jié)點(diǎn)間轉(zhuǎn)移時(shí)增強(qiáng)節(jié)點(diǎn)的被選擇概率。

改進(jìn)的初始信息素更新策略考慮了由初始障礙物分布決定的搜索方向，結(jié)合雙向搜索的思想，對(duì)終點(diǎn)所在方向同樣進(jìn)行預(yù)搜索。該策略根據(jù)地圖中的初始障礙物及終點(diǎn)的初始障礙物進(jìn)行區(qū)域的劃分，故對(duì)障礙物分布情況不同的不同環(huán)境地圖有適應(yīng)性。

2.3 改進(jìn)算法的流程

基于初始信息素不均勻分布策略的改進(jìn)蟻群算法流程圖如圖2 所示。

圖2 改進(jìn)蟻群算法流程圖

步驟1，對(duì)參數(shù)進(jìn)行數(shù)值的初始化。

步驟2，按所述的策略進(jìn)行柵格的初始信息素?cái)?shù)值計(jì)算，并按式（5）計(jì)算得出的數(shù)值對(duì)信息素進(jìn)行對(duì)應(yīng)更新，然后開(kāi)始尋路。

步驟3，尋路時(shí)，m只螞蟻選擇起點(diǎn)作為其初始位置。

步驟4，出動(dòng)第1 只螞蟻，從所給出的起點(diǎn)位置開(kāi)始搜索，根據(jù)當(dāng)前位置及下一步的可選柵格位置按式（1）計(jì)算出每個(gè)可轉(zhuǎn)移柵格的轉(zhuǎn)移概率，再根據(jù)概率選擇柵格進(jìn)行移動(dòng)，直到到達(dá)終點(diǎn)或無(wú)可移動(dòng)?xùn)鸥窨蛇x，第1 只螞蟻尋路結(jié)束。記錄下該只螞蟻的行走路線及其長(zhǎng)度，再出動(dòng)下一只位于起點(diǎn)位置的螞蟻進(jìn)行尋路。該步驟在一輪迭代中共執(zhí)行m次。

步驟5，一輪迭代的尋路結(jié)束后，對(duì)比每只螞蟻的路徑長(zhǎng)度，記錄下當(dāng)次迭代的最優(yōu)路線及其長(zhǎng)度。

步驟6，依據(jù)此路線按式（4）更新信息素。

步驟7，在達(dá)到迭代次數(shù)前，重復(fù)步驟3 至步驟6，直到達(dá)到迭代次數(shù)。

步驟8，達(dá)到迭代次數(shù)后，對(duì)每代的最優(yōu)路徑進(jìn)行長(zhǎng)度對(duì)比，輸出最優(yōu)路徑，算法結(jié)束。

3 仿真及分析

3.1 環(huán)境地圖建模

移動(dòng)機(jī)器人路徑規(guī)劃時(shí)的地圖建模方法有幾何圖法、可視圖法、柵格法等[10]。其中柵格法因其構(gòu)圖方式簡(jiǎn)單，便于更新維護(hù)而廣泛應(yīng)用于路徑規(guī)劃算法中。為此，本文采用柵格法進(jìn)行地圖構(gòu)建。在柵格地圖中，黑色柵格表示不可行柵格，為障礙物，且所在柵格被編入禁忌表；白色柵格為可行柵格，如圖3 所示。

圖3 柵格法建圖

在向下一柵格運(yùn)動(dòng)時(shí)，若周?chē)鷽](méi)有障礙物，共有8 個(gè)運(yùn)動(dòng)方向，每次移動(dòng)1 個(gè)柵格；當(dāng)某個(gè)方向存在障礙物時(shí)，則規(guī)定不能朝著該方向移動(dòng)，如圖4所示。

圖4 柵格法中機(jī)器人的可移動(dòng)方向

3.2 仿真分析

采用MATLAB R2018a 作為仿真環(huán)境，所構(gòu)造的柵格地圖如圖5 所示，設(shè)置起點(diǎn)為節(jié)點(diǎn)A，其坐標(biāo)為（0.5，19.5），終點(diǎn)為節(jié)點(diǎn)B，其坐標(biāo)為（19.5，0.5）。在傳統(tǒng)蟻群算法的基礎(chǔ)上融入初始信息素不均勻分布策略是本文算法。為驗(yàn)證所提出的信息素不均勻分布策略的有效性，這里將文獻(xiàn)[4]所提算法的初始信息素分布策略融入傳統(tǒng)蟻群算法作為文獻(xiàn)[4]算法用于仿真實(shí)驗(yàn)，與傳統(tǒng)蟻群算法一同開(kāi)展對(duì)比研究。表1 為3 種算法的主要參數(shù)設(shè)置。

圖5 仿真柵格地圖環(huán)境

表1 算法的主要參數(shù)設(shè)置

圖6 示出采用本文算法、文獻(xiàn)[4]算法、傳統(tǒng)算法獲得的最優(yōu)路徑。由圖可知，3 種算法均可獲得一條最優(yōu)路徑。

圖6 3 種算法的最優(yōu)路徑

圖7 示出3 種算法的蟻群探尋軌跡。由圖可知，受初始信息素增強(qiáng)的影響，本文算法在探尋時(shí)，蟻群多集中于最優(yōu)路徑附近，沒(méi)有螞蟻進(jìn)入死鎖區(qū)域，僅有少數(shù)螞蟻進(jìn)入了右上的較差區(qū)域。文獻(xiàn)[4]算法及傳統(tǒng)算法均存在螞蟻進(jìn)入死鎖區(qū)域的情況。可見(jiàn)，本文提出的初始信息素不均勻分布策略可以有效避免初期搜索的盲目性。

圖7 3 種算法的蟻群探尋軌跡

在仿真實(shí)驗(yàn)中，筆者對(duì)3 種算法均進(jìn)行了15 次仿真。本文算法收斂成功率為100%，其余2 種算法均存在不收斂及收斂于局部最優(yōu)解的情況，如表2 所示。表2 同時(shí)給出每次仿真算法收斂時(shí)的迭代次數(shù)的平均值。本文算法相較于傳統(tǒng)算法縮短了13.77 次，相較于文獻(xiàn)[4]算法縮短了21.27次。可見(jiàn)，本文算法收斂速度均比其他2 種算法快。在最優(yōu)路徑長(zhǎng)度方面，3 種算法均迭代出了相同長(zhǎng)度的最優(yōu)路徑。在尋優(yōu)時(shí)間上，本文算法相較于文獻(xiàn)[4]算法快了0.059 s，相較于傳統(tǒng)算法快了0.054 s。

表2 算法性能對(duì)比

4 結(jié)論

針對(duì)蟻群算法在機(jī)器人路徑規(guī)劃中存在收斂性差、易陷入局部最優(yōu)等問(wèn)題，本文提出了一種基于初始障礙物的初始信息素不均勻分布策略的蟻群算法。通過(guò)雙向搜索與初始障礙物的分布情況，劃分出特定的信息素增強(qiáng)區(qū)域，實(shí)現(xiàn)初始信息素的不均勻分布，解決蟻群算法前期搜索的盲目性，以此提升蟻群算法的收斂速度。仿真實(shí)驗(yàn)結(jié)果表明，在同一柵格地圖下，本文算法相較于傳統(tǒng)蟻群算法和文獻(xiàn)[4]算法，在收斂成功率、收斂速度方面均明顯提升，并且可有效避免初始搜索的盲目性。