陳繼清，莫榮現(xiàn)，譚成志，劉 旭，王志奎

（1.廣西大學 機械工程學院，廣西 南寧 530004；2.廣西制造系統(tǒng)與先進制造技術重點實驗室，廣西 南寧 530004）

0 引言

移動機器人是集監(jiān)測傳感、動態(tài)決策、路徑規(guī)劃、行為控制和執(zhí)行為一體的復雜智能控制系統(tǒng)。它的“智能”主要體現(xiàn)在機器人在運動過程中是否具有良好的環(huán)境交互能力，這一能力主要指路徑規(guī)劃能力。對路徑規(guī)劃的研究可以追溯到20 世紀60年代，經(jīng)過幾十年的研究和發(fā)展，大量優(yōu)良的算法被提出，如A?star 算法、人工勢場法、模糊控制算法等傳統(tǒng)算法和蟻群算法、魚群算法等仿生智能算法。其中，蟻群算法因為魯棒性強、易與其他算法結(jié)合、能并行運算等優(yōu)點被廣泛用于解決移動機器人的路徑規(guī)劃問題。從20 世紀90年代提出至今，無數(shù)專家和學者對其進行改進，使蟻群算法成功應用在不同的行業(yè)。如文獻[8]利用蟻群算法來優(yōu)化生產(chǎn)車間的運輸效率，有效地節(jié)約能源和降低生產(chǎn)成本；文獻[9]提出一種作業(yè)路徑生成算法和蟻群算法相結(jié)合的改進蟻群算法，并應用在無人機植保方面，有效縮短了無人機的搜索路徑等。

然而，蟻群算法也有易受參數(shù)影響、收斂速度慢、易陷入局部最優(yōu)解和前期路徑有效性差等缺點。根據(jù)文獻[10?11]和蟻群算法程序可知，蟻群算法在找到可行路徑前，每個柵格的信息素濃度都相等，蟻群算法根據(jù)轉(zhuǎn)移概率公式隨機地選擇可行柵格，這可能會出現(xiàn)蟻群算法搜尋遠離目標點的方向，從而增加搜索時間和加大陷入局部最優(yōu)解的概率。此外，文獻[10]提出的蟻群算法前期的路徑有效性差；文獻[12?13]提及的蟻群算法的收斂速度慢和搜索時間長。為了解決這些問題，本文提出一種改進的蟻群算法。

1 改進蟻群算法描述

蟻群算法的改進包括兩個部分：第一個部分是提出一種方向性信息素，該信息素與目標點方向的夾角有關，越靠近目標點方向信息素濃度越大，反之則越小。引入方向性信息素可以減少蟻群算法前期的盲目搜索，縮短搜索時間、減少轉(zhuǎn)折點數(shù)量和蟻群算法陷入局部最優(yōu)解的概率。第二個部分是提出一種針對方向性信息素的蒸發(fā)函數(shù)，該蒸發(fā)函數(shù)能減少前期方向性信息素濃度的蒸發(fā)，使蟻群算法更快速地搜索到可行路徑，進而縮短搜索時間，減少迭代次數(shù)；而后期能加快方向性信息素濃度的蒸發(fā)，減少方向性信息素濃度對原有信息素濃度的影響。

1.1 方向性信息素

根據(jù)蟻群轉(zhuǎn)移概率公式（1）可知，蟻群算法在沒有信息素殘留的初期，每個方向的概率是一樣的，因而每只螞蟻會隨機選擇搜索方向，這可能導致螞蟻選擇與目標點方向相反的路徑進行搜索，增加了前期的搜索時間，可能使搜尋的路徑長度陷入局部最優(yōu)解。為了解決這個問題，本文提出一種方向性信息素。方向性信息素與偏離目標點方向的夾角有關，當偏離目標點方向的夾角在0°～180°時，夾角越小，方向性信息素的數(shù)值越大；當偏離目標點方向的夾角在180°～360°時，夾角越大，方向性信息素的數(shù)值越大。

本文將方向性信息素和蟻群算法原有的轉(zhuǎn)移概率公式結(jié)合起來，通過方向性信息素濃度限制蟻群算法前期對偏離目標點方向的搜索，從而避免蟻群算法陷入局部最優(yōu)解和減少搜索時間。帶有方向性信息素的轉(zhuǎn)移概率公式前期大概率會選擇靠近目標點方向的路徑，減少前期盲目搜索的時間。

為了設計出滿足要求的方向性信息素函數(shù)，本文分兩步：第一步是確定選取基本函數(shù)種類和確定遞增遞減關系，得出函數(shù)的大概輪廓；第二步是利用實驗的方法將函數(shù)中特殊位置的坐標求出，然后利用插值的方法求出最終函數(shù)。

首先確定選取基本函數(shù)種類和遞增、遞減關系。方向性信息素函數(shù)與偏離目標點方向的夾角有關，因此選取三角函數(shù)cos和sin作為基本函數(shù)。其次，偏離目標點方向的夾角為0°～360°，且當偏離目標點方向的夾角在0°～180°時，夾角越小，方向性信息素的數(shù)值越大；當偏離目標點方向的夾角在180°～360°時，夾角越大，方向性信息素的數(shù)值越大。為了方便函數(shù)擬合，本文規(guī)定當偏離目標點方向的夾角為180°時，方向性信息素大小為0。由此可知，方向性信息素函數(shù)在0°～180°遞減，在180°～360°遞增，在夾角為180°時方向性信息素大小為0。第二步，做如下實驗：分別在偏離目標點方向夾角為0°，45°和90°時加入等梯度的方向性信息素，求出0°，45°和90°的最優(yōu)路徑長度對應的方向性信息素；然后，利用函數(shù)擬合的方法求出方向性信息素的函數(shù)表達式。方向性信息素的取值范圍為[0，1.6]，步長為0.1。蟻群算法的基本參數(shù)為：=1；=8；=1；=0.6；=200；=50。

方向性信息素的大小和算法最優(yōu)路徑的關系如圖1 所示。

圖1 三種夾角的方向性信息素與最優(yōu)路徑的關系

從圖1 可以看出：偏離目標點方向夾角為0，加入方向性信息素的值為1.4 時，算法路徑最短；同理，夾角為45°和90°，加入方向性信息素分別是1.2 和0.7 時，路徑最短。

0°，45°和90°與360°，325°和270°是對稱的，且當夾角為180°時的方向性信息素濃度為0。因此，可以通過上述求出的7 個點擬合出方向性信息素的函數(shù)。擬合結(jié)果如下：

式中為偏離目標點方向的夾角。擬合的函數(shù)圖像如圖2 所示。從圖2 可以看出，方向性信息素函數(shù)是連續(xù)的，蟻群算法的搜索方向越靠近目標點方向，方向性信息素的數(shù)值越大。而由蟻群轉(zhuǎn)移概率公式可知，蟻群算法在初期階段向每個方向搜索的概率是一樣的，如果加上方向性信息素，那么靠近目標點方向搜索的概率會變大，避免了前期蟻群算法其他非必要方向的搜索，可大大縮短搜索的時間；同時還可以避免路徑長度陷入局部最優(yōu)解，因為方向性信息素的限制使蟻群算法朝著目標點方向搜索的概率增大，而朝著目標點方向搜索的路徑長度最優(yōu)。最后，增加方向性信息素的蟻群算法還可以增加前期路徑的有效性，因為前期蟻群算法是沒有目標點方向的盲目搜索，所以搜索的方向是隨機的，只有小部分路徑能“幸運”地到達目標點，且路徑長度不是最優(yōu)。而增加方向性概率的蟻群算法開始就有目標點方向的指引，能到達目標點的概率增大且路徑長度比蟻群算法要短，因而前期的路徑有效性增加。

圖2 方向性信息素函數(shù)圖像

方向性信息素在前期可以減少蟻群算法的搜索時間，提高算法的效率。但方向性信息素不會隨著迭代次數(shù)改變，而殘留的信息素不斷蒸發(fā)，導致殘留信息素濃度比方向性信息素濃度小，最后使蟻群算法尋路失敗或陷入局部最優(yōu)解。為此，需要引入一種適合的蒸發(fā)函數(shù)。該蒸發(fā)函數(shù)前期需要減少方向性信息素的蒸發(fā)，使改進的蟻群算法能快速找到可行路徑，避免局部最優(yōu)解和縮短時間；而后期則加快方向性信息素的蒸發(fā)，避免方向性信息素的濃度影響新增的信息素濃度，從而影響蟻群算法最優(yōu)路徑的搜索。

1.2 針對方向性信息素的蒸發(fā)函數(shù)

為了發(fā)揮方向性信息素前期的作用，避免后期方向性信息素對新增信息素的影響，需要合適的蒸發(fā)函數(shù)來調(diào)節(jié)每次迭代后的方向性信息素濃度。本文列出蟻群算法的蒸發(fā)函數(shù)，通過分析該蒸發(fā)函數(shù)來確定方向性信息素的蒸發(fā)函數(shù)。蟻群算法的蒸發(fā)函數(shù)如下：

式中：是蒸發(fā)系數(shù)；是迭代次數(shù)；τ(0) 表示信息素的初始濃度，一般為8。

原始的蒸發(fā)函數(shù)不能滿足方向性信息素前期減少蒸發(fā)而后期加快蒸發(fā)的要求，因此本文對原有的蒸發(fā)函數(shù)進行改進，假設方向性信息素蒸發(fā)函數(shù)的表達式如下：

式中：τ(0) 是方向性信息素的初始濃度；是待確定的系數(shù)。因為方向性信息素要在前期路徑的選擇中占主導作用，所以方向性信息素的初始濃度要比信息素的初始濃度高。其次，為了加快后期方向性信息素的蒸發(fā)，方向性信息素的蒸發(fā)函數(shù)要比蟻群蒸發(fā)函數(shù)更快遞減。根據(jù)上述兩個條件不難得出，τ( 0 )>τ( 0 )=8 且>1。

為了求出系數(shù)和方向性信息素的初始濃度τ( 0 )，本文設計如下實驗：設置等梯度實驗求出改進蟻群算法路徑長度和迭代次數(shù)最優(yōu)時的初始方向性信息素濃度τ( 0 )和系數(shù)。初始方向性信息素濃度τ( 0 )的取值范圍為[8，10]，梯度步長為1；系數(shù)的取值范圍為[1，2.5]，梯度步長為0.1。初始方向性信息素濃度為8，9，10 時，系數(shù)與路徑長度、迭代次數(shù)的關系如圖3圖5 所示。

圖3 初始濃度為8 時a 與路徑長度和迭代次數(shù)的關系

由圖3 可知，當初始濃度為8、系數(shù)為1.8 時，算法路徑長度最短，為42.183 8，迭代次數(shù)為76 次；由圖4 可知，初始濃度為9、系數(shù)為1.9 時，算法路徑長度最短且迭代次數(shù)最優(yōu)，分別為42.183 8 和51；由圖5 可知，初始濃度為10、系數(shù)為1.2 時，算法路徑長度最短且迭代次數(shù)最優(yōu)，分別為42.183 8 和49。通過上述實驗可知，當初始濃度取10，系數(shù)取1.2 時改進蟻群算法路徑長度和迭代次數(shù)最優(yōu)，所以方向性信息素的蒸發(fā)函數(shù)表達式如下：

圖4 初始濃度為9 時a 與路徑長度和迭代次數(shù)的關系

圖5 初始濃度為10 時a 與路徑長度和迭代次數(shù)的關系

式中，方向性信息素的初始濃度τ( 0 )為10，系數(shù)為1.2。

引入方向性信息素蒸發(fā)函數(shù)可以減少算法初期方向性信息素濃度的蒸發(fā)，使蟻群算法大概率向目標點方向搜索，減少非必要方向的搜索，從而減少搜索時間；而后期則加快方向性信息素濃度的蒸發(fā)，減少對殘留信息素濃度的影響。

1.3 改進的蟻群算法轉(zhuǎn)移概率公式

式中，為當前節(jié)點前進方向與目標節(jié)點的夾角。

由公式（6）可以看出，改進蟻群算法的轉(zhuǎn)移概率公式由兩部分組成，前面的部分是原有的轉(zhuǎn)移概率公式，后面的部分是方向性信息素和對應的蒸發(fā)函數(shù)。原有的轉(zhuǎn)移概率公式在開始階段由于沒有殘留信息素，所以向每個方向搜索的概率相同，而方向性信息素越靠近目標點方向數(shù)值越大，所以前期蟻群算法的搜索方向由方向性信息素決定，且大概率向目標點方向搜索。而后期方向性信息素比殘留信息素蒸發(fā)快，所以后期方向性信息素對蟻群算法搜索方向的影響變小，防止蟻群算法受方向性信息素的影響而無法收斂或陷入局部最優(yōu)解。

圖6 是改進蟻群算法的程序流程。首先初始化所有參數(shù)；然后開始循環(huán)迭代次數(shù)和螞蟻個數(shù)，根據(jù)轉(zhuǎn)移概率選擇搜索節(jié)點并修改禁忌表；所有螞蟻搜索完成便更新原始信息素和方向性信息素，再開始下一次迭代，直到迭代次數(shù)完成；最后輸出最優(yōu)解并結(jié)束程序。

圖6 改進蟻群算法的程序流程

2 仿真分析與對比

為了驗證改進蟻群算法的性能，將改進蟻群算法、原始蟻群算法和文獻[10]算法進行仿真分析，仿真地圖采用30×30 的隨機柵格地圖，障礙比為0.2，機器人的起點坐標為（0.5，29.5），終點坐標為（29.5，0.5）。三種蟻群算法的隨機地圖對比結(jié)果如圖7 所示。

圖7 30×30 障礙比為0.2 的隨機地圖對比

為了對比改進算法和原始算法、文獻[10]算法的性能，本文列出路徑長度、搜索時間、迭代次數(shù)的對比，如表1 所示。

表1 三種蟻群算法對比

從表1 可知，相比原始蟻群算法，改進算法所需的迭代次數(shù)更少，路徑長度也更短。迭代次數(shù)變少是因為方向性信息素可以減少前期的盲目搜索，使蟻群算法能更快速地搜索到可行路徑；路徑長度變短是因為方向性信息素可以避免蟻群算法陷入局部最優(yōu)解。文獻[10]的算法在路徑長度、搜索時間優(yōu)于原始蟻群算法，但路徑長度和搜索時間都比本文算法更長，因為該算法只規(guī)定了核心區(qū)域的信息素減少蒸發(fā)，蟻群算法會大概率在核心區(qū)域搜索，但沒有指向目標點方向的信息素，無法保證蟻群算法以最短的路徑向目標點方向搜索，所以路徑長度更長、搜索時間也更久。

此外，圖7b）中改進算法的收斂曲線比原始蟻群算法更快速地達到平滑，震蕩幅度更小。由表1 可知，改進的蟻群算法性能要比原始的蟻群算法更好，路徑長度縮短了3.15%，迭代次數(shù)減少了50.74%，搜索時間縮短了14.19%；相比文獻[10]的算法，本文算法在路徑長度上縮短了1.87%，在搜索時間上減少了6.79%，在迭代數(shù)上減少了45%，本文算法在搜索時間和路徑長度上優(yōu)于文獻[10]的算法。

3 實驗分析

本文用TurtleBot2 機器人來驗證改進蟻群算法的性能。TurtleBot2 是一種開放式的機器人平臺，最大的移動速度為0.7 m/s，最大的轉(zhuǎn)向速度為180（°）/s。為了提高測試的精度，設定TurtleBot2 的線速度為0.2 m/s，角速度為30（°）/s。構(gòu)建環(huán)境地圖的傳感器是RPLIDAR A1 激光雷達。實驗場地選在實驗樓樓梯口處，場地尺寸為6 m×5.5 m，用Rplidar A1 構(gòu)建樓道2D 地圖。改進的蟻群算法尋路結(jié)果和原始的蟻群算法尋路結(jié)果如圖8 和圖9 所示，選用的柵格尺寸為0.3 m×0.3 m。圖8 中的黑色區(qū)域表示障礙物區(qū)域，粉紫色為可行區(qū)域，青藍色為膨脹區(qū)域。機器人的起點和終點都相同，從圖8 和圖9 中可以看出，改進的蟻群算法路徑更平滑，距離障礙物邊界更遠，減少發(fā)生碰撞的風險。為了更方便地比較改進蟻群算法的性能，本文將兩種算法的尋路時間和路徑長度進行對比，對比結(jié)果如表2 所示。

表2 兩種算法尋路時間和路徑長度的對比

從圖8和圖9可以看出，改進的蟻群算法可以用于機器人的路徑規(guī)劃，且相比傳統(tǒng)的蟻群算法，改進的蟻群算法搜尋的路徑更平滑，距離障礙物邊界更遠。從表2 可以看出，改進的蟻群算法在運行時間和路徑長度上都優(yōu)于原始的蟻群算法，在路徑長度上縮短了4.27%，在運行時間上減少了4.53%。因此，本文認為改進的蟻群算法能用于機器人的路徑規(guī)劃，且比原始的蟻群算法更優(yōu)。

圖8 改進的蟻群算法尋路結(jié)果圖

圖9 原始的蟻群算法尋路結(jié)果圖

4 結(jié)語

針對蟻群算法中存在搜索時間長、收斂速度慢和容易陷入局部最優(yōu)解等問題，本文提出一種改進的蟻群算法。第一個改進的部分是引入方向性信息素，該信息素可以減少蟻群算法前期的盲目搜索，降低蟻群算法的搜索時間，避免蟻群算法陷入局部最優(yōu)解。第二個部分是提出針對方向性信息素的蒸發(fā)函數(shù)，使改進的蟻群算法減少前期方向性信息素的蒸發(fā)，加快可行路徑的搜索；而后期能加快方向性信息素的蒸發(fā)，使改進的蟻群算法更快收斂，避免方向性信息素對新增信息素的影響。仿真結(jié)果和機器人實驗結(jié)果表明，改進的蟻群算法在路徑長度、迭代次數(shù)和搜索時間上相比蟻群算法和文獻[10]的算法有明顯的提升。后續(xù)工作是將改進的蟻群算法和局部規(guī)劃算法結(jié)合起來，使機器人能適應動態(tài)的實驗環(huán)境。