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

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

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

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

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

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

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

1.1 蟻群算法流程圖

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

1）構(gòu)造解空間 解空間的構(gòu)造通過搭建柵格地圖來完成，用白色柵格表示可行駛區(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）信息素更新 在路徑搜索中，螞蟻每過一個(gè)節(jié)點(diǎn)就會對該節(jié)點(diǎn)進(jìn)行信息素更新。公式（3）為信息素更新公式。

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

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

經(jīng)典蟻群算法中的啟發(fā)函數(shù)是通過相鄰柵格距離構(gòu)造的，所得的數(shù)值差別很小，算法的搜索效率很低。針對這個(gè)問題，仿照A*算法的估價(jià)函數(shù)對蟻群算法的啟發(fā)函數(shù)進(jìn)行改進(jìn)，增加目標(biāo)點(diǎn)對啟發(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í)，由于螞蟻會在走過的路徑上留下信息素，這樣就造成路徑積累信息素過多，從而使得螞蟻很大概率選擇信息素多的路徑，因此蟻群算法在初始階段就失去了選擇路徑的多樣性，陷入局部最優(yōu)解。針對此問題，對狀態(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ī)制中，把螞蟻所走過的全部路徑都參與到信息素的更新中，這樣容易降低算法的收斂速度。

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

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

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

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

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

3.1 融合人工勢場的改進(jìn)

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

式中：dij——節(jié)點(diǎn)i到節(jié)點(diǎn)j的歐氏距離；Lig——采用人工勢場法求到的節(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ī)劃出來的路徑并不是最優(yōu)路徑，再結(jié)合蟻群算法，在快速搜索出來的路徑上添加信息素，那么就會對螞蟻搜索具有引導(dǎo)作用，將會提高蟻群算法全局搜索效率。

4 總結(jié)

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

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

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

［3］ 霍鳳財(cái)，任偉建，劉東輝.基于改進(jìn)的人工勢場法的路徑規(guī)劃方法研究［J］.自動化技術(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］ 史恩秀，陳敏敏，李俊，等.基于蟻群算法的移動機(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.