薛 婷，貝紹軼，李 波

(江蘇理工學(xué)院機(jī)械工程學(xué)院，江蘇 常州 213001)

1 引言

近幾年來(lái)，國(guó)內(nèi)外針對(duì)蟻群算法提出了大量的改進(jìn)算法，大致可以分為以下兩類：第一種，對(duì)算法中的信息素啟發(fā)因子、期望啟發(fā)式因子、信息素濃度等參數(shù)進(jìn)行改進(jìn)，在對(duì)這些參數(shù)進(jìn)行改進(jìn)的研究中Dorigo等人改變了信息素的更新方式，提出了Ant-Q System 蟻群算法[1-3]；第二種，將傳統(tǒng)蟻群算法與其它智能算法相結(jié)合，黃辰等人明確提出一種基于A*蟻群算法的動(dòng)態(tài)路徑規(guī)劃方法[4-6]。目前國(guó)內(nèi)外的研究熱點(diǎn)就是以上兩種方法相結(jié)合。

傳統(tǒng)蟻群算法在運(yùn)算時(shí)會(huì)出現(xiàn)螞蟻陷入局部最優(yōu)點(diǎn)、運(yùn)行時(shí)間長(zhǎng)、迭代次數(shù)多等問(wèn)題。本文結(jié)合了上述兩種改進(jìn)算法的方式對(duì)傳統(tǒng)算法進(jìn)行了改進(jìn)。首先，對(duì)傳統(tǒng)算法中的參數(shù)設(shè)置進(jìn)行了改進(jìn)：令出發(fā)點(diǎn)和目標(biāo)點(diǎn)之間的信息素略大于其它信息素濃度；全局信息素更新取決于最優(yōu)螞蟻，并通過(guò)自適應(yīng)來(lái)控制信息素?fù)]發(fā)因子。其次，在啟發(fā)信息中的距離計(jì)算中結(jié)合勢(shì)場(chǎng)法，避免螞蟻陷入局部最優(yōu)。

2 蟻群算法

2.1 基本原理

螞蟻在一邊尋找食物時(shí)一邊釋放一種揮發(fā)性分泌物pheromone來(lái)吸引其它的螞蟻。然而有些螞蟻可能會(huì)另辟蹊徑，如果另開(kāi)辟的道路較之前螞蟻探索的路徑更短，那么這一條最短的路徑將會(huì)被大多數(shù)螞蟻重復(fù)著[7-9]。

2.2 狀態(tài)轉(zhuǎn)移概率

螞蟻下一步的路徑取決于信息素的濃度，在第t次迭代中，螞蟻k由節(jié)點(diǎn)i選擇下一節(jié)點(diǎn)j的轉(zhuǎn)移概率表示為

(1)

(2)

式中：α為信息素啟發(fā)因子；β為期望啟發(fā)式因子；τij為路徑(i，j)的信息素濃度；allowk表示路徑搜索所有下一可達(dá)節(jié)點(diǎn)的集合；ηij為啟發(fā)信息；dij為當(dāng)前節(jié)點(diǎn)i和待選節(jié)點(diǎn)j的歐氏距離。

2.3 信息素?fù)]發(fā)與更新

i節(jié)點(diǎn)中的信息素會(huì)隨著螞蟻從節(jié)點(diǎn)i向節(jié)點(diǎn)j移動(dòng)的過(guò)程中逐漸揮發(fā)，同時(shí)j節(jié)點(diǎn)的信息素會(huì)越來(lái)越強(qiáng)烈，則t+1時(shí)刻的信息素濃度為

τij(t+1)=(1-ρ)τij(t)+Δτij(t，t+1)

(3)

(4)

式中：ρ為信息素?fù)]發(fā)系數(shù)，ρ∈(0，1)；Δτij(i，j)表示從節(jié)點(diǎn)i向節(jié)點(diǎn)j上的信息素增量；Q為信息素強(qiáng)度；Lk表示第k只螞蟻在本次迭代所走路徑的總長(zhǎng)度。

3 改進(jìn)蟻群算法

3.1 初始信息素不均衡分配

傳統(tǒng)蟻群算法中的所有初始信息素都是均勻分布的，因此螞蟻開(kāi)始搜索路徑時(shí)會(huì)出現(xiàn)無(wú)目的性[10-11]。本文為了解決此問(wèn)題，提出了令初始信息素不均勻分配的原則，即在有效范圍內(nèi)增加信息素的初始值，如下所示

(5)

其中：τx為信息素矩陣中的信息素；τ0為未被處理過(guò)的初始信息素；C為常數(shù)(大于τ0)；x為地圖柵格序號(hào)；R為全局路徑規(guī)劃的有效范圍。

3.2 啟發(fā)信息的改進(jìn)

在傳統(tǒng)蟻群算法中初始信息素均相同，故路徑的選擇取決于啟發(fā)信息，但螞蟻會(huì)在選擇第一個(gè)節(jié)點(diǎn)時(shí)選擇偏向終點(diǎn)的方向，但若選擇的第一個(gè)節(jié)點(diǎn)附近有干擾物時(shí)，則說(shuō)明初始節(jié)點(diǎn)選擇不當(dāng)，那么該路徑也就不是最優(yōu)路徑[12]。本文通過(guò)勢(shì)場(chǎng)法算出節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)之間的距離來(lái)調(diào)整啟發(fā)函數(shù)，調(diào)整后的啟發(fā)函數(shù)如下

(6)

其中：dij為節(jié)點(diǎn)i到節(jié)點(diǎn)j之間的歐氏距離；Ljg為根據(jù)勢(shì)場(chǎng)算法得出節(jié)點(diǎn)j到節(jié)點(diǎn)g之間的距離；Ncmax為迭代的最大次數(shù)；Nc為當(dāng)前的迭代次數(shù)；ξ為啟發(fā)信息遞減函數(shù)(ξ>1)。在該式中，啟發(fā)函數(shù)會(huì)隨著迭代次數(shù)的增加而減少，改進(jìn)的啟發(fā)信息函數(shù)可以有效地避免出現(xiàn)局部最優(yōu)的問(wèn)題，提高搜索效率[13-15]。

3.3 信息素更新改進(jìn)

當(dāng)螞蟻經(jīng)過(guò)i節(jié)點(diǎn)后，i節(jié)點(diǎn)處的局部信息素會(huì)發(fā)生變化，變化規(guī)則如下

τij(t)=(1-λ)τij(t)+λτ0

(7)

其中：λ為局部信息素?fù)]發(fā)系數(shù)(λ∈(0，1))；τ0為一個(gè)很小的正常量；當(dāng)τij(t)超過(guò)上限或小于下限值時(shí)，就令τij(t)的大小等于上限或下限值，防止算法陷入停滯狀態(tài)。

當(dāng)一次迭代完成之后，會(huì)出現(xiàn)有的螞蟻?zhàn)哌^(guò)的路徑接近于最優(yōu)路徑，這類螞蟻稱為最優(yōu)螞蟻；反之，也有螞蟻?zhàn)哌^(guò)的路徑耗時(shí)長(zhǎng)、路徑繁瑣，這類螞蟻稱為最差螞蟻[13]。本文根據(jù)優(yōu)質(zhì)螞蟻規(guī)則來(lái)更新全局信息素，更新規(guī)則如下所示

(8)

其中：ε為該算法引入的一個(gè)參數(shù)(ε∈(0，1))；Lworst為最差螞蟻?zhàn)哌^(guò)的路徑長(zhǎng)度；Lbest最優(yōu)螞蟻?zhàn)哌^(guò)的路徑長(zhǎng)度。

信息素?fù)]發(fā)因子ρ通過(guò)自適應(yīng)控制來(lái)提高全局性，在該算法中，若連續(xù)迭代T次，所得的最優(yōu)結(jié)果都一樣，那么該算法便陷入了局部最優(yōu)解中，此時(shí)信息素?fù)]發(fā)因子ρ通過(guò)下是做自動(dòng)調(diào)整

(9)

其中：ρmin為信息素?fù)]發(fā)因子的最小值；γ為全局信息素的遞減因數(shù)(γ∈(0，1))。

3.4 二次路徑規(guī)劃

螞蟻在第一次路徑規(guī)劃中很難規(guī)劃出最優(yōu)路徑，因此本文提出二次路徑規(guī)劃，二次路徑規(guī)劃是在第一次規(guī)劃的路徑基礎(chǔ)上進(jìn)行改善。

令第一次規(guī)劃的路徑上的所有拐彎點(diǎn)為節(jié)點(diǎn)，并按順序命名為節(jié)點(diǎn)1、節(jié)點(diǎn)2、節(jié)點(diǎn)3等。依次將節(jié)點(diǎn)1與節(jié)點(diǎn)3連接起來(lái)，若所連路徑安全且無(wú)碰撞，則可以省略中間節(jié)點(diǎn)2，然后節(jié)點(diǎn)1依次與節(jié)點(diǎn)4進(jìn)行比較，直至出現(xiàn)碰撞為止，此時(shí)令開(kāi)始出現(xiàn)碰撞的這個(gè)節(jié)點(diǎn)為初始點(diǎn)，然后依次與下面的節(jié)點(diǎn)進(jìn)行連接比較，依次反復(fù)，直到終點(diǎn)位置，此時(shí)所得路徑即為二次規(guī)劃所得路徑。二次路徑規(guī)劃可以減少轉(zhuǎn)彎次數(shù)，并減少時(shí)間，對(duì)一次規(guī)劃路徑進(jìn)行了優(yōu)化。

4 仿真結(jié)果與分析

本文為驗(yàn)證改進(jìn)后算法的優(yōu)越性，進(jìn)行了大量仿真，算法仿真環(huán)境為：Windows10 64bit；Matlab R2016b；處理器Intel(R) i5。仿真搭建地圖模型為10*10，20*20和30*30，在該環(huán)境下，傳統(tǒng)蟻群算法與改進(jìn)蟻群算法路徑規(guī)劃的參數(shù)如表1所示，經(jīng)仿真的到傳統(tǒng)算法與改進(jìn)算法路徑規(guī)劃圖和收斂圖如圖1所示。

表1 仿真參數(shù)設(shè)置

1)10*10路徑規(guī)劃和收斂對(duì)比圖如下圖所示。

圖1 10*10傳統(tǒng)路徑規(guī)劃圖

圖2 10*10改進(jìn)路徑規(guī)劃圖

圖3 10*10傳統(tǒng)收斂圖

圖4 10*10改進(jìn)收斂圖

由傳統(tǒng)算法和改進(jìn)后算法的對(duì)比圖可知，當(dāng)環(huán)境模型較小時(shí)，改進(jìn)后算法有一定優(yōu)越性，迭代次數(shù)從20次減少為8次，迭代次數(shù)減少60%，并且路線更加平滑，但最小路徑長(zhǎng)度幾乎不變。

2)20*20路徑規(guī)劃和收斂對(duì)比圖如下圖所示。

圖5 20*20傳統(tǒng)路徑規(guī)劃圖

圖6 20*20改進(jìn)路徑規(guī)劃圖

圖7 20*20傳統(tǒng)收斂圖

圖8 20*20改進(jìn)收斂圖

當(dāng)環(huán)境模型變?yōu)?0*20時(shí)，改進(jìn)后算法的路徑規(guī)劃圖更加平滑，不必要的拐彎點(diǎn)明顯減少，并且迭代次數(shù)從50降為15，迭代次數(shù)減少70%，規(guī)劃的路徑也更為平滑，最小路徑長(zhǎng)度也幾乎不變，大大縮短了運(yùn)行時(shí)間，在該環(huán)境模型下可以明顯體現(xiàn)出改進(jìn)后算法的優(yōu)越性。

3)30*30路徑規(guī)劃和收斂對(duì)比圖如下圖所示。

圖9 30*30傳統(tǒng)路徑規(guī)劃圖

圖10 30*30改進(jìn)路徑規(guī)劃圖

圖11 30*30傳統(tǒng)收斂圖

圖12 30*30改進(jìn)收斂圖

當(dāng)環(huán)境模型為30*30時(shí)，傳統(tǒng)算法路徑圖有很多不合理的拐彎點(diǎn)，并且當(dāng)?shù)螖?shù)達(dá)到最大值100時(shí)，依舊不能達(dá)到收斂狀態(tài)，而改進(jìn)后算法只需迭代60次就可以達(dá)到最小路徑，迭代次數(shù)至少減少50%，并且路線更為平滑。由此可見(jiàn)，環(huán)境模型為30*30的狀態(tài)下，傳統(tǒng)算法已不能得到最優(yōu)路徑，反之改進(jìn)后的算法大大縮短了迭代次數(shù)和時(shí)間，減少了運(yùn)行時(shí)間。

由3組不同模型的路徑規(guī)劃和收斂對(duì)比圖可知，改進(jìn)后的路徑更加平滑趨于直線，減少了拐彎的次數(shù)，路線更加合理，故在迭代過(guò)程中螞蟻陷入局部最優(yōu)解的次數(shù)大幅度減少；觀察算法收斂圖可得，傳統(tǒng)算法與改進(jìn)算法最后得到的最優(yōu)路徑長(zhǎng)度都是差不多的，但是改進(jìn)后算法的迭代次數(shù)明顯小于傳統(tǒng)算法的迭代次數(shù)，體現(xiàn)了改進(jìn)后算法的優(yōu)越性，有效地提高了智能小車的效率。由模型的復(fù)雜程度的遞進(jìn)關(guān)系可知，當(dāng)模型越復(fù)雜，改進(jìn)后算法的優(yōu)越性就越明顯。

5 結(jié)論

本文針對(duì)傳統(tǒng)蟻群算法的不足，提出了一種改進(jìn)蟻群算法。

1)初始信息不均勻分配使螞蟻在初期探索路徑時(shí)目的更明確，使產(chǎn)生的優(yōu)質(zhì)螞蟻更多，而劣質(zhì)螞蟻更少，可以有效防止螞蟻陷入局部最優(yōu)點(diǎn)，提高了螞蟻搜索路徑的效率。

2)結(jié)合勢(shì)場(chǎng)法調(diào)節(jié)啟發(fā)信息，通過(guò)勢(shì)場(chǎng)法計(jì)算當(dāng)前節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)之間的距離可減少算法迭代次數(shù)，在不同的環(huán)境模型下迭代次數(shù)都可以減少60%-70%，減少了運(yùn)行時(shí)間。

3)根據(jù)最優(yōu)螞蟻原則調(diào)節(jié)全局信息素更新，使得環(huán)境模型中的信息素更優(yōu)質(zhì)的更新，信息素的有效性提高；通過(guò)自適應(yīng)控制信息素?fù)]發(fā)因子，及時(shí)調(diào)整揮發(fā)參數(shù)，提高了信息素的時(shí)效性，提高了算法的全局搜索能力。

通過(guò)結(jié)合不同仿真環(huán)境模型對(duì)改進(jìn)后算法的實(shí)用性和有效性分析表明，改進(jìn)后規(guī)劃的路線更加平滑，無(wú)效拐彎點(diǎn)次數(shù)減少，迭代次數(shù)也明顯減少。本文的環(huán)境模量全是已知的，并且障礙物都是靜態(tài)的，后續(xù)將結(jié)合未知環(huán)境中的動(dòng)態(tài)障礙物來(lái)深入研究，進(jìn)一步提高該算法的有效性和實(shí)用性。