張曉莉，楊亞新，謝永成

西安科技大學(xué) 通信與信息工程學(xué)院，西安710000

1 引言

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

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

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

2 蟻群算法原理

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

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

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

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

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

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

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

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

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

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

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

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

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

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

將雙向搜索機(jī)制和單向搜索在三種環(huán)境模型下進(jìn)行仿真，圖1（a）和圖1（b）分別為在環(huán)境模型1下的搜索路徑和擴(kuò)散節(jié)點(diǎn)區(qū)域；圖2（a）和圖2（b）分別為在環(huán)境模型2下的搜索路徑和擴(kuò)散節(jié)點(diǎn)區(qū)域；圖3（a）和圖3（b）分別為在環(huán)境模型3下的搜索路徑和擴(kuò)散節(jié)點(diǎn)區(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雙向搜索算法

對(duì)三種環(huán)境模型下算法的運(yùn)行時(shí)間和擴(kuò)展節(jié)點(diǎn)兩項(xiàng)性能指標(biāo)進(jìn)行分析，得出表1所示結(jié)果。

表1 算法性能對(duì)比

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

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

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

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

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

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

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

3.2 加入信息素權(quán)重的算法模型

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

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

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

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

圖5 Softplus函數(shù)

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

4 算法仿真與分析

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

圖6 實(shí)驗(yàn)1三種蟻群算法最短路徑長度對(duì)比圖

圖7 實(shí)驗(yàn)1三種蟻群算法迭代次數(shù)對(duì)比圖

圖8 實(shí)驗(yàn)2三種蟻群算法最短路徑長度對(duì)比圖

圖9 實(shí)驗(yàn)2三種蟻群算法迭代次數(shù)對(duì)比圖

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

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

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

表2 實(shí)驗(yàn)1路徑長度與迭代次數(shù)仿真結(jié)果對(duì)比情況

表3 實(shí)驗(yàn)2路徑長度與迭代次數(shù)仿真結(jié)果對(duì)比情況

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

5 結(jié)語

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