基于蟻群算法的路徑規(guī)劃改進(jìn)方法研究

田涌君，張金煒，戎 輝，王文揚(yáng)，郭 蓬，3，高 嵩，3

（1.中國(guó)汽車技術(shù)研究中心有限公司，天津 300300；2.河北工業(yè)大學(xué)，天津 300222；3.天津大學(xué)，天津 300072）

進(jìn)入21世紀(jì)以來(lái)，眾多技術(shù)迅速發(fā)展，無(wú)人駕駛技術(shù)也是其中之一。路徑規(guī)劃作為無(wú)人駕駛的重要組成部分，研究人員對(duì)路徑規(guī)劃提出了很多算法，如傳統(tǒng)算法（模擬退火法、人工勢(shì)場(chǎng)法、模糊邏輯法），智能仿生算法（蟻群算法、粒子群算法、遺傳算法），啟發(fā)式搜索算法（A*算法、D*算法）等算法。

本文主要介紹蟻群算法及其改進(jìn)方法。蟻群算法是一種經(jīng)典的智能仿生算法又稱螞蟻算法，是一種在圖中搜索最優(yōu)或者次優(yōu)路線的智能算法。在1992年，Marcc Dorigo博士提出了蟻群算法，它的主要思想是螞蟻在搜索食物過(guò)程中會(huì)形成一定的規(guī)則，在這種規(guī)則下每只螞蟻都能沿著相同路徑找到食物。

蟻群算法也存在著缺陷，最主要的、關(guān)鍵性的缺點(diǎn)就是搜索時(shí)間長(zhǎng)、較容易陷入局部最優(yōu)解。有關(guān)蟻群算法的改進(jìn)，提出了很多解決方法，大致可以分為兩大類，一類是基于經(jīng)典蟻群算法的改進(jìn)，一類與其它智能算法融合的改進(jìn)。

1 經(jīng)典蟻群算法

螞蟻通過(guò)群體性的方式尋找路徑，它們會(huì)在所走過(guò)的路上留下信息素，此信息素就是螞蟻之間溝通的媒介，當(dāng)下一只螞蟻路過(guò)該路徑時(shí)就會(huì)利用信息素做出下一步的判斷，并且會(huì)釋放出自己的信息素，這樣就形成了信息素的積累，使得后續(xù)螞蟻可以選擇信息素強(qiáng)的路徑，隨著大量螞蟻在信息素的作用下不斷搜索路徑，最終會(huì)得到一條最優(yōu)或者次優(yōu)路徑。

1.1 蟻群算法流程圖

圖1為經(jīng)典蟻群算法流程圖。

1）構(gòu)造解空間 解空間的構(gòu)造通過(guò)搭建柵格地圖來(lái)完成，用白色柵格表示可行駛區(qū)域，黑色柵格表示障礙物區(qū)域，從中設(shè)置出發(fā)點(diǎn)和目標(biāo)點(diǎn)。

2）節(jié)點(diǎn)選擇 螞蟻從當(dāng)前節(jié)點(diǎn)選擇下一個(gè)節(jié)點(diǎn)的方法如公式（1）所示。

圖1 經(jīng)典蟻群算法流程圖

式中：i——當(dāng)前節(jié)點(diǎn)的周圍8個(gè)節(jié)點(diǎn)集合；——信息素；——啟發(fā)值。

首先計(jì)算當(dāng)前節(jié)點(diǎn)j與四周節(jié)點(diǎn)i之間的選擇概率，然后利用選擇概率采用輪轉(zhuǎn)賭法選擇下一節(jié)點(diǎn)。公式（2）為的計(jì)算方法。

3）信息素更新 在路徑搜索中，螞蟻每過(guò)一個(gè)節(jié)點(diǎn)就會(huì)對(duì)該節(jié)點(diǎn)進(jìn)行信息素更新。公式（3）為信息素更新公式。

2 基于經(jīng)典蟻群算法改進(jìn)

2.1 改進(jìn)啟發(fā)函數(shù)

經(jīng)典蟻群算法中的啟發(fā)函數(shù)是通過(guò)相鄰柵格距離構(gòu)造的，所得的數(shù)值差別很小，算法的搜索效率很低。針對(duì)這個(gè)問題，仿照A*算法的估價(jià)函數(shù)對(duì)蟻群算法的啟發(fā)函數(shù)進(jìn)行改進(jìn)，增加目標(biāo)點(diǎn)對(duì)啟發(fā)函數(shù)的影響，加快算法的收斂速度。A*算法是一種有序的啟發(fā)式搜索算法，其基本原理是利用當(dāng)前節(jié)點(diǎn)、可選節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)的位置關(guān)系構(gòu)造估價(jià)函數(shù)，估價(jià)函數(shù)值最小的路徑即為下一步選擇的路徑。估價(jià)函數(shù)為當(dāng)前節(jié)點(diǎn)S到可選節(jié)點(diǎn)n的代價(jià)與從可選節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)E代價(jià)之和。表示為公式（4）。

式中：g（n）——節(jié)點(diǎn)S到可選節(jié)點(diǎn)n的代價(jià)；h（n）——可選節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)S代價(jià)。則蟻群算法的啟發(fā)函數(shù)可改進(jìn)為公式（5）。

式中：——柵格i與柵格j的距離；——柵格j與目標(biāo)點(diǎn)E的距離。

2.2 改進(jìn)狀態(tài)選擇策略

經(jīng)典蟻群算法在初始階段搜索路徑時(shí)，由于螞蟻會(huì)在走過(guò)的路徑上留下信息素，這樣就造成路徑積累信息素過(guò)多，從而使得螞蟻很大概率選擇信息素多的路徑，因此蟻群算法在初始階段就失去了選擇路徑的多樣性，陷入局部最優(yōu)解。針對(duì)此問題，對(duì)狀態(tài)選擇策略做了如公式（6）的改進(jìn)。）

式中：；q0——（0，1）的常量；q——（0，1）的取值符合均勻分布的隨機(jī)數(shù)。當(dāng)時(shí)，按的最大值確定性搜索，否則，依據(jù)按輪盤賭法選擇法隨機(jī)性搜索。兩種選擇策略混合使用，增加解的多樣性。

2.3 改進(jìn)信息素分配規(guī)則

經(jīng)典蟻群算法的信息素分配規(guī)則是當(dāng)所有螞蟻?zhàn)咄曷烦讨蟛鸥氯中畔⑺?，在這種信息素更新機(jī)制中，把螞蟻所走過(guò)的全部路徑都參與到信息素的更新中，這樣容易降低算法的收斂速度。

改進(jìn)的信息素分配規(guī)則如下。

1）在全部螞蟻搜索完路徑之后，把螞蟻搜索的路徑長(zhǎng)度按照從小到大的順序進(jìn)行排序，保留前1/w的螞蟻路徑，并將其信息素更新如公式（7）所示。

2）每次迭代的最優(yōu)解和記錄下來(lái)的全局最優(yōu)解路徑上的信息素進(jìn)行更新可以使算法的收斂速度加快。信息素增量如公式（8）所示。

式中：——記錄下來(lái)的全局最優(yōu)解；——本次迭代最優(yōu)解。

3 蟻群算法與其他智能算法結(jié)合

3.1 融合人工勢(shì)場(chǎng)的改進(jìn)

蟻群算法與人工勢(shì)場(chǎng)算法的融合，是全局路徑規(guī)劃和局部路徑規(guī)劃的有效結(jié)合。人工勢(shì)場(chǎng)算法，采用引力與斥力的思想，引導(dǎo)無(wú)人車向終點(diǎn)運(yùn)動(dòng)，利用這種方法構(gòu)建蟻群算法的啟發(fā)信息素，如公式（9）所示。

式中：dij——節(jié)點(diǎn)i到節(jié)點(diǎn)j的歐氏距離；Lig——采用人工勢(shì)場(chǎng)法求到的節(jié)點(diǎn)j到目標(biāo)節(jié)點(diǎn)g的距離；Ncmax——最大迭代次數(shù)；Nc——當(dāng)前迭代次數(shù)；ξ——啟發(fā)信息遞減系數(shù)，且ξ＞1。

3.2 融合粒子群算法的改進(jìn)

融合粒子群的改進(jìn)，其思想是應(yīng)用粒子群建模的方法，能夠快速規(guī)劃出從出發(fā)點(diǎn)到目的點(diǎn)的路徑。這些規(guī)劃出來(lái)的路徑并不是最優(yōu)路徑，再結(jié)合蟻群算法，在快速搜索出來(lái)的路徑上添加信息素，那么就會(huì)對(duì)螞蟻搜索具有引導(dǎo)作用，將會(huì)提高蟻群算法全局搜索效率。

4 總結(jié)

蟻群算法在1992年被提出來(lái)之后，國(guó)內(nèi)外的眾多學(xué)者對(duì)其做了大量的研究和改進(jìn)，總的來(lái)說(shuō)改進(jìn)方法分為兩大類：一是基于經(jīng)典蟻群算法的改進(jìn)，二是與其它智能算法融合的改進(jìn)。

［1］ 楊帆.無(wú)人駕駛汽車的發(fā)展現(xiàn)狀和展望［J］.上海汽車，2014（3）：35-40.

［2］ 孫梅.移動(dòng)機(jī)器人路徑規(guī)劃技術(shù)綜述［J］.山東工業(yè)技術(shù)，2016（21）：164.

［3］ 霍鳳財(cái)，任偉建，劉東輝.基于改進(jìn)的人工勢(shì)場(chǎng)法的路徑規(guī)劃方法研究［J］.自動(dòng)化技術(shù)與應(yīng)用，2016，35（3）：63-67.

［4］ 陳剛，沈林成. 復(fù)雜環(huán)境下路徑規(guī)劃問題的遺傳路徑規(guī)劃方法［J］.機(jī)器人，2001，23（1）：40-44.

［5］ 李士勇，陳永強(qiáng)，李研.蟻群算法及應(yīng)用［M］.哈爾濱：哈爾濱工業(yè)大學(xué)出版社，2004.

［6］ 史恩秀，陳敏敏，李俊，等.基于蟻群算法的移動(dòng)機(jī)器人全局路徑規(guī)劃方法研究 ［J］.農(nóng)業(yè)機(jī)械學(xué)報(bào)，2014，45（6）：53-57.

［7］ 王憲，王偉，宋書林，等.基于蟻群粒子群融合的機(jī)器人路徑規(guī)劃算法 ［J］.計(jì)算機(jī)系統(tǒng)應(yīng)用，2011，20（9）：98-102.