張曉莉，楊亞新，謝永成

西安科技大學 通信與信息工程學院，西安710000

1 引言

蟻群算法[1]（ACO）是一種啟發(fā)式智能群體仿生優(yōu)化算法[2]，該算法是Dorigo等最早提出的一種基于種群的模擬進化算法，其目的就是蟻群在蟻巢和食物源之間尋找一條最短的可行路徑[3]，這與機器人路徑規(guī)劃的目的不謀而合[4]，兩者存在著本質(zhì)上的聯(lián)系。因此，把蟻群算法運用到路徑規(guī)劃問題上具有合理性。此外，移動機器人路徑規(guī)劃也是機器人研究中的重要問題[5]。由于蟻群算法存在的運行時間長，易陷入局部最優(yōu)等問題[6]，限制了它在求解最短路徑問題上的應用。對此，一些學者提出了一些改進算法來緩解上述問題[7]。

文獻[8]對傳統(tǒng)A*算法加以改進，提出正反向搜索交替機制的方法，運行速度和擴展節(jié)點規(guī)模兩個方面的性能有了明顯的改善，搜索效率較高并且具有較好的實時性，但是A*算法難以保證得到的解為最優(yōu)解。文獻[9]提出將單向A*搜索算法應用于蟻群算法啟發(fā)函數(shù)中，并考慮前期螞蟻易陷入局部最優(yōu)問題，引入自適應調(diào)整啟發(fā)函數(shù)來提高解的質(zhì)量，但是單向A*算法存在的搜索效率和穩(wěn)定性低的問題沒有得到很好的解決。文獻[10]對蟻群算法中針對信息素正反饋的原理強化性能較好的解而出現(xiàn)的停滯現(xiàn)象，提出動態(tài)修改增加信息素的方法，采用時變函數(shù)Q(t)來調(diào)整常數(shù)項信息素強度Q，并提出錦標賽競爭法的信息素更新策略，找到最為優(yōu)秀的螞蟻，修改其所走過路徑對應邊的信息素，避免算法陷入局部最優(yōu)且提高算法搜索效率，卻只考慮了每條路徑的重要程度，沒有考慮到路徑上每個路段的權重。文獻[11]提出一種基于自適應調(diào)整信息素的改進蟻群算法，根據(jù)人工螞蟻所獲得解的情況，動態(tài)調(diào)整路徑上的信息素，從而使得算法跳離局部最優(yōu)解，該改進方法雖然在一定程度上提高了解的質(zhì)量，但是改進方法單一并未能考慮較優(yōu)路徑重要路段上的信息素強度，使得算法搜索效率不高。

在對以上改進算法研究分析的基礎上，考慮到蟻群算法具有自組織性、較強的魯棒性、尋優(yōu)能力強且易于和其他算法相結合等優(yōu)點。提出將改進后的雙向A*算法應用于蟻群算法中，在改進雙向搜索方向機制的啟發(fā)函數(shù)中繼續(xù)加入比例系數(shù)引導因子和衡量搜索空間大小的閾值，不僅使算法容易跳出局部最優(yōu)解，而且可以加大螞蟻后期搜索的目的性。并針對算法模型改進引入路段權重因子，找到適合的函數(shù)模型來強化重要路段信息素增量，有效提高搜索速度和解的質(zhì)量。

2 蟻群算法原理

蟻群算法通過信息素引導整個搜索過程[12]，該算法的核心在于模擬自然界螞蟻的覓食行為，即螞蟻從巢穴出發(fā)利用前一批次的螞蟻釋放的信息素選取到達目標點的最優(yōu)路徑[13]。螞蟻在尋找食物的過程中，會在其走過的路線上留下一種被稱為信息素的物質(zhì)，其他螞蟻能夠感知到這種物質(zhì)并以此作為它們的前進方向[14]。

在人工蟻群算法中，設m 為螞蟻總數(shù)，螞蟻從某個節(jié)點轉移到另一個節(jié)點是由路徑上的信息素量決定的，在t 時刻，螞蟻k 從節(jié)點i 轉移到節(jié)點j 的狀態(tài)轉移概率為：

其中，dk={c-tabuk} 為螞蟻k 下一步可選城市集合，tabuk為禁忌表，用來記錄螞蟻走過的節(jié)點；α 表示路徑上信息素對螞蟻選擇的重要程度；β 為期望啟發(fā)因子；τij(t)為節(jié)點i 與節(jié)點j 之間的信息素量；ηij(t)為啟發(fā)函數(shù)，一般取做節(jié)點i 與節(jié)點j 之間歐式距離的倒數(shù)，即：

所有螞蟻都完成一次覓食以后，需要對信息素進行更新。更新公式為：

其中，ρ 為信息素揮發(fā)系數(shù)，表示信息素會隨著時間的推移而慢慢蒸發(fā)，信息素增量Δτij可表示為：

例如式（5）是最常用的蟻周模型：

其中，Q 為常數(shù)，Lk為螞蟻k 在本次循環(huán)中所走過的路徑長度。

移動機器人路徑規(guī)劃是指按照一定的性能指標規(guī)劃出一條從起始位置到目標位置的可通行路徑[16]。將改進后的蟻群算法應用于移動機器人在未知環(huán)境中搜索目標和尋求最短路徑問題上[17]。

3 改進的蟻群算法路徑規(guī)劃方法

3.1 添加雙向搜索方向機制和比例系數(shù)引導因子的啟發(fā)函數(shù)

經(jīng)典蟻群算法中的啟發(fā)函數(shù)是通過相鄰柵格距離構造的，所得的數(shù)值差別很小，而且沒有考慮到從起點到目標點的方向性問題，可能導致在搜索過程中螞蟻會選擇與終點方向相背的區(qū)域行走或者走回路，從而導致算法的搜索效率很低并且尋得的路徑長度增大。針對這個問題，本文提出基于頭尾雙向搜索的A*算法對蟻群算法的啟發(fā)函數(shù)進行改進。

基于頭尾雙向搜索的A*算法是在傳統(tǒng)A*算法的基礎上進行改進的方法。改進后的A*算法中h*(n)將原來的當前節(jié)點到目標點的曼哈頓距離改為當前節(jié)點與另一搜索方向上的當前節(jié)點間的曼哈頓距離，即：

其中，g(n)表示初始節(jié)點s 到可選節(jié)點n 的代價，h*(n)表示當前可選節(jié)點n 與另一搜索方向上的當前節(jié)點d之間的曼哈頓距離。

雙向搜索方向分別存放了從初始節(jié)點出發(fā)和目標節(jié)點出發(fā)的當前節(jié)點信息，將原始算法的兩個隊列擴大為四個隊列，分別為從初始節(jié)點開始搜索的SOPEN、SCLOSED 隊列，從目標節(jié)點開始搜索的EOPEN、ECLOSED 隊列。每個子節(jié)點要從上、下、左、右、左上、左下、右上、右下8個方向上進行遍歷，搜索出有最小f(n)的擴展節(jié)點并放入CLOSED 隊列，直到某個擴展節(jié)點的啟發(fā)函數(shù)h*(n)值為零時，算法結束。

將雙向搜索機制和單向搜索在三種環(huán)境模型下進行仿真，圖1（a）和圖1（b）分別為在環(huán)境模型1下的搜索路徑和擴散節(jié)點區(qū)域；圖2（a）和圖2（b）分別為在環(huán)境模型2下的搜索路徑和擴散節(jié)點區(qū)域；圖3（a）和圖3（b）分別為在環(huán)境模型3下的搜索路徑和擴散節(jié)點區(qū)域。

圖1（a）環(huán)境模型1單向搜索算法

圖1（b）環(huán)境模型1雙向搜索算法

圖2（a）環(huán)境模型2單向搜索算法

圖2（b）環(huán)境模型2雙向搜索算法

圖3（a）環(huán)境模型3單向搜索算法

圖3（b）環(huán)境模型3雙向搜索算法

對三種環(huán)境模型下算法的運行時間和擴展節(jié)點兩項性能指標進行分析，得出表1所示結果。

表1 算法性能對比

由以上分析得出，雙向搜索算法相較于單向搜索運行時間更短，節(jié)點擴散個數(shù)也更少。

將改進后的A*算法估價函數(shù)值用于構造蟻群算法的啟發(fā)函數(shù)。改進后為如下公式：

在添加雙向搜索的啟發(fā)函數(shù)后，不僅考慮了源節(jié)點與目標節(jié)點的方向性問題，而且因為搜索是頭尾雙向并行進行的，相比單向搜索更易找到最優(yōu)解。其運行速度和擴展節(jié)點規(guī)模兩個方面的性能也有了明顯的改善，從而有效提高搜索速率。

但是目標點方向信息對啟發(fā)函數(shù)的影響主要體現(xiàn)在后期螞蟻尋優(yōu)路徑過程中。對于在前期過早引入目標點會導致初始時期搜索空間太小，算法容易陷入局部最優(yōu)的問題，提出了在前期通過設置閾值范圍，不引入目標點對啟發(fā)函數(shù)的影響。用初始階段起始節(jié)點s 和當前節(jié)點i 之間的距離dsi作為衡量搜索空間大小的標準。在后期也即是閾值范圍外，引入雙向搜索目標點，并添加比例系數(shù)引導因子k 。 k 的取值又與當前螞蟻的迭代次數(shù)和螞蟻數(shù)量呈動態(tài)變化，路徑越靠近最優(yōu)解，k 的取值就越大，相應的啟發(fā)函數(shù)值就越大，螞蟻在最優(yōu)路徑上收斂越快，更容易快速找到最優(yōu)解。

將前期和后期蟻群算法存在的問題考慮到其中，公式（8）中的啟發(fā)函數(shù)改進后為：

其中，Dsd為起始節(jié)點s 和從目標點搜索到的當前節(jié)點d 的距離；Dij為當前節(jié)點i 和下一步可選節(jié)點j 的距離。 μ 為極小鄰域值，由Dsd的長度具體決定。k 為比例系數(shù)引導因子，它隨著當前螞蟻數(shù)量mk和迭代次數(shù)Nc的增加而產(chǎn)生動態(tài)變化，k 的函數(shù)設定如下：

其中，m 為螞蟻總量，Ncmax為設定的最大迭代次數(shù)。

3.2 加入信息素權重的算法模型

由于蟻周模型具有更好的全局搜索能力，蟻周模型成為目前使用最多的模型，公式如式（5）所示，某只螞蟻走過的路徑上更新同路徑長度相對應的信息素量，但是由于每條路徑上不同部分的重要程度不同，如圖4 所示，螞蟻k 走過的路徑由5小段1-3-4-5-7組成，其中4段是最優(yōu)路徑的一部分，很顯然，4段比其他幾個路段具有更重要的地位，因此對于路段4的信息素增量需要設置更大一些，而傳統(tǒng)的蟻周模型在每小段路徑上更新的信息素都相等。

圖4 螞蟻k 走過路徑和最優(yōu)路徑

為加快算法的收斂速度，在蟻周模型的基礎上進行改進。根據(jù)一次迭代中螞蟻選擇的次數(shù)來衡量路徑上每一部分的重要程度，進而確定路徑k 上節(jié)點i 與節(jié)點j 之間的重要程度。引入路段權重因子μij，改進后的公式如下：

通過查閱資料發(fā)現(xiàn)神經(jīng)網(wǎng)絡激活函數(shù)Softplus函數(shù)適合這個算法模型路段權重因子μij的改進。Softplus函數(shù)表達式為f(x)=ln(1+ex)，Softplus 函數(shù)是一個單調(diào)遞增的函數(shù)，其函數(shù)圖像如圖5所示。圖5中Relu函數(shù)表達式為y={x,x≥00,x ＜0 。

圖5 Softplus函數(shù)

本文提出的算法模型改進點綜合考慮了每條路徑的長度以及路徑上的每個路段的重要程度，每個路段的重要程度和被選擇的次數(shù)有關，被選擇次數(shù)越多，其重要程度越高，信息素增量就設置越多，這就強化了重要程度高的路徑，因此就加快了算法的收斂速度。

4 算法仿真與分析

為了驗證改進后的蟻群算法的可行性，在MATLAB R2014a 平臺環(huán)境下進行仿真實驗，其中，螞蟻個數(shù)為50，α=1，β=7，信息素蒸發(fā)系數(shù)ρ=0.95，信息素增加強度系數(shù)Q=1，分別在兩種實驗環(huán)境下對文獻[9]蟻群算法路徑規(guī)劃方法和文獻[10]動態(tài)調(diào)節(jié)信息素增量路徑規(guī)劃方法中的改進算法與本文改進后的蟻群算法進行分析對比，得出如圖6～9所示的實驗結果。

圖6 實驗1三種蟻群算法最短路徑長度對比圖

圖7 實驗1三種蟻群算法迭代次數(shù)對比圖

圖8 實驗2三種蟻群算法最短路徑長度對比圖

圖9 實驗2三種蟻群算法迭代次數(shù)對比圖

在實驗環(huán)境1中的仿真對比圖如圖6和圖7所示。

在實驗環(huán)境2中的仿真對比圖如圖8和圖9所示。

同時本文對兩次實驗進行了文獻[9]中蟻群算法路徑規(guī)劃方法與文獻[10]中動態(tài)調(diào)節(jié)信息素增量改進的蟻群算法以及本文提出的改進方法在最優(yōu)路徑長度和迭代次數(shù)兩項指標的對比。如表2 和表3 所示，本文改進算法對比文獻[9]中算法在效率上提升了63.64%，文獻[10]中算法對比文獻[9]搜索效率上最大提升了54.55%。在路徑規(guī)劃結果上，本文改進算法最大減少了32.72%，文獻[10]中算法最大減少了31.39%。

表2 實驗1路徑長度與迭代次數(shù)仿真結果對比情況

表3 實驗2路徑長度與迭代次數(shù)仿真結果對比情況

此外，在第二種實驗下文獻[9]算法在搜索前期陷入了局部最優(yōu)狀態(tài)，導致可行方向背離目標點。雖然最后跳出了局部最優(yōu)解，但是使得算法搜索效率降低。文獻[10]中算法雖然能夠跳出局部最優(yōu)解且算法搜索速度相比文獻[9]中算法有很大的提升，但是對比本文改進算法增加了4.06%的最優(yōu)路徑長度，迭代次數(shù)也增加了14.28%。綜上所述，本文改進算法在前期能夠保證跳出局部最優(yōu)解，且找到最佳路徑的前提下，顯著縮短了算法運行時間，提高算法的搜索效率和解的質(zhì)量。

5 結語

本文選用神經(jīng)網(wǎng)絡激活函數(shù)建立數(shù)學模型來改變重要路段信息素增量并添加雙向搜索方向機制和比例系數(shù)引導因子調(diào)整啟發(fā)函數(shù)，考慮了蟻群算法存在如前期易陷入局部極小值、收斂速度慢的缺點。并在兩種實驗環(huán)境下進行三種算法仿真對比分析，從仿真結果可以看出，本文算法在跳出局部最優(yōu)解以及搜索效率上有所提高。但是，由于改進后的算法采用柵格法環(huán)境建模，所得出的路徑并不一定是最優(yōu)的，所以算法的有效性還有待進一步的改善。