基于蟻群算法的路徑規劃改進方法研究

田涌君，張金煒，戎 輝，王文揚，郭 蓬，3，高 嵩，3

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

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

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

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

1 經典蟻群算法

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

1.1 蟻群算法流程圖

圖1為經典蟻群算法流程圖。

1）構造解空間 解空間的構造通過搭建柵格地圖來完成，用白色柵格表示可行駛區域，黑色柵格表示障礙物區域，從中設置出發點和目標點。

2）節點選擇 螞蟻從當前節點選擇下一個節點的方法如公式（1）所示。

圖1 經典蟻群算法流程圖

式中：i——當前節點的周圍8個節點集合；——信息素；——啟發值。

首先計算當前節點j與四周節點i之間的選擇概率，然后利用選擇概率采用輪轉賭法選擇下一節點。公式（2）為的計算方法。

3）信息素更新 在路徑搜索中，螞蟻每過一個節點就會對該節點進行信息素更新。公式（3）為信息素更新公式。

2 基于經典蟻群算法改進

2.1 改進啟發函數

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

式中：g（n）——節點S到可選節點n的代價；h（n）——可選節點n到目標節點S代價。則蟻群算法的啟發函數可改進為公式（5）。

式中：——柵格i與柵格j的距離；——柵格j與目標點E的距離。

2.2 改進狀態選擇策略

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

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

2.3 改進信息素分配規則

經典蟻群算法的信息素分配規則是當所有螞蟻走完路程之后才更新全局信息素，在這種信息素更新機制中，把螞蟻所走過的全部路徑都參與到信息素的更新中，這樣容易降低算法的收斂速度。

改進的信息素分配規則如下。

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

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

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

3 蟻群算法與其他智能算法結合

3.1 融合人工勢場的改進

蟻群算法與人工勢場算法的融合，是全局路徑規劃和局部路徑規劃的有效結合。人工勢場算法，采用引力與斥力的思想，引導無人車向終點運動，利用這種方法構建蟻群算法的啟發信息素，如公式（9）所示。

式中：dij——節點i到節點j的歐氏距離；Lig——采用人工勢場法求到的節點j到目標節點g的距離；Ncmax——最大迭代次數；Nc——當前迭代次數；ξ——啟發信息遞減系數，且ξ＞1。

3.2 融合粒子群算法的改進

融合粒子群的改進，其思想是應用粒子群建模的方法，能夠快速規劃出從出發點到目的點的路徑。這些規劃出來的路徑并不是最優路徑，再結合蟻群算法，在快速搜索出來的路徑上添加信息素，那么就會對螞蟻搜索具有引導作用，將會提高蟻群算法全局搜索效率。

4 總結

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

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

［2］ 孫梅.移動機器人路徑規劃技術綜述［J］.山東工業技術，2016（21）：164.

［3］ 霍鳳財，任偉建，劉東輝.基于改進的人工勢場法的路徑規劃方法研究［J］.自動化技術與應用，2016，35（3）：63-67.

［4］ 陳剛，沈林成. 復雜環境下路徑規劃問題的遺傳路徑規劃方法［J］.機器人，2001，23（1）：40-44.

［5］ 李士勇，陳永強，李研.蟻群算法及應用［M］.哈爾濱：哈爾濱工業大學出版社，2004.

［6］ 史恩秀，陳敏敏，李俊，等.基于蟻群算法的移動機器人全局路徑規劃方法研究 ［J］.農業機械學報，2014，45（6）：53-57.

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