改進(jìn)蟻群算法在AGV路徑規(guī)劃中的應(yīng)用

胡春陽，姜 平，周根榮

南通大學(xué) 電氣工程學(xué)院，江蘇 南通226019

1 引言

路徑規(guī)劃是指在有障礙物的環(huán)境中，尋找一條從起點到終點的無碰撞最優(yōu)路徑[1]。傳統(tǒng)的路徑規(guī)劃算法包括人工勢場法[2]、啟發(fā)式搜索法[3]、滾動窗口法[4]等。如今，隨著智能算法的不斷發(fā)展，越來越多的學(xué)者將遺傳算法[5]、粒子群算法[6]、蟻群算法[7]等智能算法應(yīng)用到路徑規(guī)劃上。

蟻群算法是Dorigo M 受螞蟻覓食啟發(fā)，于1996 年提出的一種仿生算法[8]。隨著國內(nèi)外學(xué)者大量研究，現(xiàn)已被廣泛應(yīng)用于解決旅行商問題[9]、車輛調(diào)度問題[10]、機(jī)器人路徑規(guī)劃問題[11]等。根據(jù)自然界中螞蟻覓食時會在走過的路徑上留下可被任意螞蟻感知的信息素，單個螞蟻覓食時便會選擇信息素濃度較大的路徑。隨著蟻群不斷搜索到食物并將其搬回至蟻穴，路徑上的信息素濃度便越來越高，下一代螞蟻便會通過此路徑找到食物。由此可見，蟻群算法是一種正反饋算法，隨著螞蟻迭代次數(shù)的不斷增多來逼近最優(yōu)解。但這也使蟻群算法易陷入局部最優(yōu)，且前期搜索目標(biāo)盲目性較大，導(dǎo)致收斂速度慢[12]。為此，許多學(xué)者對蟻群算法進(jìn)行改進(jìn)。文獻(xiàn)[13]對信息素進(jìn)行優(yōu)化，設(shè)定信息素最大最小閾值避免陷入局部最優(yōu)，雖然有用但效果并不明顯。由于蟻群算法參數(shù)對結(jié)果的影響明顯，可傳統(tǒng)算法卻采用經(jīng)驗法設(shè)定參數(shù)，浪費大量時間[14]。因此，文獻(xiàn)[15]中提出通過粒子群算法對傳統(tǒng)蟻群算法進(jìn)行參數(shù)優(yōu)化，雖然效果明顯，但執(zhí)行時間過長。上述文獻(xiàn)僅僅針對傳統(tǒng)蟻群算法進(jìn)行改進(jìn)，主要解決旅行商問題。而對AGV 路徑規(guī)劃問題來說，大多研究采用柵格地圖建立工作環(huán)境，并根據(jù)易陷入U 型陷阱的特點對傳統(tǒng)蟻群算法改進(jìn)[16]。文獻(xiàn)[17]采用一種自適應(yīng)參數(shù)的改進(jìn)蟻群算法，使得算法在前期收斂速度較快，在后期局部搜索能力變強(qiáng)。但仍未解決算法易陷入局部最優(yōu)的問題。文獻(xiàn)[18]提出了一種基于頭尾雙向搜索的A*啟發(fā)函數(shù)算法來改進(jìn)傳統(tǒng)蟻群算法，很大程度上提高了算法運(yùn)行速度和全局搜索能力。但是，由于采用了頭尾相遇即停止策略，對局部搜索能力提高不足。文獻(xiàn)[19]對移動機(jī)器人的路徑規(guī)劃中采用多指標(biāo)條件，根據(jù)AGV小車路徑彎折度、運(yùn)行到位時間、能耗問題等進(jìn)行多方面限制選擇最優(yōu)路徑，雖然未對傳統(tǒng)蟻群算法進(jìn)行改進(jìn)，卻引入多指標(biāo)的思維，對解決實際系統(tǒng)運(yùn)行時產(chǎn)生的問題有很大幫助。

在對上述文獻(xiàn)研究分析的基礎(chǔ)上，考慮到蟻群算法具有速度快、精度高、尋優(yōu)能力強(qiáng)且易與其他算法相結(jié)合等優(yōu)點。采用頭尾雙向搜索策略提高全局搜索能力，加快算法前期搜索效率，提高算法前期有效解。增強(qiáng)尋找全局最優(yōu)解能力；參考遺傳算法中變異思想，引進(jìn)變異因子，增加算法局部搜索空間；參考狼群算法中“按勞分配”原則對傳統(tǒng)蟻群算法信息素改進(jìn)，引入獎懲因子，通過對最優(yōu)解的信息素進(jìn)行獎勵，對最差解的信息素進(jìn)行懲罰，并設(shè)立最大最小閾值，使算法跳出局部最優(yōu)解的能力得到加強(qiáng)；對傳統(tǒng)遺傳算法引入模擬退火思想，對改進(jìn)的蟻群算法參數(shù)進(jìn)行優(yōu)化找到對于本地圖模型來說，運(yùn)行時間最短、路徑最少的參數(shù)；最后對規(guī)劃出的路徑進(jìn)行多指標(biāo)處理，減少路徑彎折次數(shù)所帶來的不必要能耗和時間。

2 環(huán)境建模

對AGV小車進(jìn)行路徑優(yōu)化時需要根據(jù)其所處工作環(huán)境進(jìn)行二維空間建模，建模方法通常包括自由空間法、拓?fù)浞?、柵格法等[20]。因為柵格地圖具有簡單有效、易于實現(xiàn)等特點，故而采用柵格法進(jìn)行建模。將AGV小車的工作環(huán)境分為20×20的柵格，并將障礙物進(jìn)行膨化處理，設(shè)AGV 小車為質(zhì)點。確保小車不會在障礙物邊界觸碰到障礙物。并根據(jù)公式（1）建立柵格地圖。若柵格上有障礙物則此柵格為黑色，否則為白色，代表可以通過。如圖1所示。在實驗平臺上設(shè)定起始位置（0，0）和

圖1 AGV小車路徑規(guī)劃地圖模型

終止位置（19，19）。小車共有8個運(yùn)動方向：北；東北；東；東南；南；西南；西；西北。AGV小車每步可移動步長為1或 2 ，如圖2所示。

圖2 AGV小車運(yùn)行方向

3 傳統(tǒng)蟻群算法

傳統(tǒng)蟻群算法在AGV小車路徑規(guī)劃的應(yīng)用主要分為覓食規(guī)則、信息素規(guī)則和移動規(guī)則[21]。覓食規(guī)則要求設(shè)立禁忌表，規(guī)定螞蟻不可行走位置。為避免螞蟻原地打轉(zhuǎn)，螞蟻移動后應(yīng)在禁忌表內(nèi)加入當(dāng)前所在位置。

移動規(guī)則要求，螞蟻k 由當(dāng)前節(jié)點i 轉(zhuǎn)移到下一節(jié)點j 時的轉(zhuǎn)移概率根據(jù)信息素濃度與啟發(fā)式函數(shù)確定，一旦下一步?jīng)]有可以移動的節(jié)點便退出本次查找。為保證路徑多樣性，假設(shè)每只螞蟻都有犯錯的可能，采用輪盤賭法保證小概率節(jié)點仍具有被選擇的可能，以此加大算法搜索能力。轉(zhuǎn)移概率由式（2）～（4）確定：

信息素規(guī)則要求，在螞蟻運(yùn)動釋放信息素的同時，路徑上已存在的信息素按一定比例揮發(fā)。蟻群循環(huán)一次后，各路徑上的信息素按式（5）更新：

式中，ρ 為信息素?fù)]發(fā)因子，值為0到1，m 為蟻群數(shù)量，為第k 只螞蟻在當(dāng)前迭代過程中留下的信息素，如式（6）：

式中Q 為常量，為螞蟻信息素強(qiáng)度，Lk為螞蟻k 在本次循環(huán)中所走過的路徑總長度。

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

4.1 雙向搜索機(jī)制

傳統(tǒng)蟻群算法將螞蟻全部放置起始點，所有螞蟻由起始點開始向終止點搜索路徑，起始路徑大致相同，這樣便導(dǎo)致全局搜索能力不足[22]。為此采用將蟻群螞蟻分為奇偶兩組，奇數(shù)螞蟻放置起始點，由起始點向終止點搜索，模擬自然界蟻群尋找食物。偶數(shù)螞蟻放置終止點，由終止點向起始點搜索。模擬自然界蟻群找到食物并運(yùn)回蟻穴的過程。因此，啟發(fā)函數(shù)應(yīng)按式（7）（8）改進(jìn)：

di表示螞蟻當(dāng)前位置距離目標(biāo)點（起始點、終止點）的幾何距離。 Ix表示螞蟻當(dāng)前位置的橫坐標(biāo)，Iy表示螞蟻當(dāng)前螞蟻位置的縱坐標(biāo)。Ex表示終止點的橫坐標(biāo)，Ey表示終止點的縱坐標(biāo)。Sx表示起始點的橫坐標(biāo)，Sy表示起始點的縱坐標(biāo)。

當(dāng)兩只螞蟻相遇后便會生成一條新的路徑，之后兩只螞蟻繼續(xù)向各自的目標(biāo)點移動。兩只螞蟻相遇條件為兩者當(dāng)前坐標(biāo)的幾何距離小于。公式如下：

dkl表示起始點出發(fā)的螞蟻與終止點出發(fā)的螞蟻之間距離，ISx代表起始點出發(fā)螞蟻當(dāng)前橫坐標(biāo)，ISy代表起始點出發(fā)螞蟻當(dāng)前縱坐標(biāo)，IEx代表終止點出發(fā)螞蟻當(dāng)前橫坐標(biāo)，IEy代表終止點出發(fā)螞蟻當(dāng)前縱坐標(biāo)。

對螞蟻轉(zhuǎn)移概率引入變異因子，對轉(zhuǎn)移概率函數(shù)進(jìn)行改進(jìn)，改進(jìn)公式如式（10）所示，當(dāng)隨機(jī)轉(zhuǎn)移概率大于變異率時，不再選擇概率最大的下一節(jié)點而是根據(jù)當(dāng)前節(jié)點的位置進(jìn)行隨機(jī)選擇。增大算法的全局搜索能力和跳出局部最優(yōu)能力。

式中，Pk代表從螞蟻k 從當(dāng)前節(jié)點i 到下一節(jié)點j 的概率代表無變異時的轉(zhuǎn)移概率由式（2）得來。rand代表變異概率，每次轉(zhuǎn)移都會隨機(jī)生成一個0 到1 范圍內(nèi)的數(shù)。 pvar代表變異因子，如果rand 小于變異因子則表明發(fā)生變異，當(dāng)前螞蟻按改進(jìn)后的轉(zhuǎn)移概率進(jìn)行轉(zhuǎn)移。

4.2 引入獎懲因子

傳統(tǒng)蟻群算法根據(jù)每代最優(yōu)路徑按式（5）進(jìn)行信息素的更新。因為揮發(fā)因子的存在，隨著迭代次數(shù)的增多，會造成選擇區(qū)域信息素堆積，未選擇區(qū)域信息素經(jīng)過多次迭代其值接近為0，造成信息擁結(jié)。不利于全局搜索。因此參考文獻(xiàn)[23]中狼群算法，引進(jìn)獎懲因子，不只對最優(yōu)路徑進(jìn)行信息素更新，而是采用“論功行賞”策略。對效果最好的路徑大幅獎勵，對每代最優(yōu)卻非全局最優(yōu)部分獎勵，對最差路徑進(jìn)行懲罰。如式（11）～（14）：

式（11）在式（5）的基礎(chǔ)上引入了Δ*τij和Δ**τij兩個參數(shù)。其中，Δ*τij代表每次迭代最優(yōu)路徑經(jīng)過節(jié)點i、j的信息素大小，由式（13）決定。式中L*表示本代中最優(yōu)路徑長度。Q 為增強(qiáng)因子設(shè)為1。并且根據(jù)式（12）判斷當(dāng)前最優(yōu)路徑與目前最優(yōu)路徑是否一致，對最優(yōu)路徑進(jìn)行獎勵，Re 代表獎勵因子其值在1到2；Δ**τij代表每次迭代最差路徑經(jīng)過節(jié)點i、j 的信息素大小，由式（14）決定，式（14）中L**表示本次迭代中最差路徑長度。R為減弱因子其值設(shè)為0 到1，表示對本次最差路徑進(jìn)行懲罰的系數(shù)。

引入最大最小信息素閾值如式（15），避免某路徑經(jīng)過多次迭代后，其上信息素濃度遠(yuǎn)高于其他路徑而導(dǎo)致的搜索停滯，出現(xiàn)早熟收斂。信息素的閾值范圍被限定在了τmin到τmax。

4.3 多指標(biāo)路徑規(guī)劃

對于AGV 小車的路徑規(guī)劃來說，不僅僅需要考慮到路徑最短的情況，還要考慮小車運(yùn)行時間、能耗情況等。小車每次經(jīng)過拐點都會造成一定的能耗，且對機(jī)械磨損也有很大的影響，為此采用多指標(biāo)方法對適應(yīng)度函數(shù)進(jìn)行改進(jìn)。

設(shè)小車處于直線狀態(tài)運(yùn)行時，忽略加減速時間，假設(shè)系統(tǒng)均勻行駛，速度為1 m/s，由于小車每次轉(zhuǎn)彎要根據(jù)轉(zhuǎn)彎的角度對行駛方向進(jìn)行調(diào)整，雖然不會停止但仍會對速度有所損耗。為計算方便，現(xiàn)假設(shè)每次經(jīng)過拐點，小車都要停止對行駛方向進(jìn)行調(diào)整。由此可得運(yùn)行時間表達(dá)式如式（16）：

式中，i、j 代表路徑Mt中的相連節(jié)點，Vt為AGV小車的正常行駛速度。L 為i 節(jié)點和j 節(jié)點之間幾何距離，tw為小車在節(jié)點i、j 拐點處轉(zhuǎn)彎所耗費的時間。計算方法如式（17）：

由于AGV 系統(tǒng)移動方向左右角度一致，都為0°、45°、90°和135°四個角度。因此，為簡化計算才用四段分段函數(shù)表示算法經(jīng)過拐點所用的時間。式中tω代表每次轉(zhuǎn)彎所耗費的時間，tc代表45°內(nèi)轉(zhuǎn)彎所耗費的時間，設(shè)為常值。w 為轉(zhuǎn)彎角度。對于能耗問題為方便計算定義能耗與時間成正比，綜合指標(biāo)為二者相加。因此運(yùn)行時間與能耗問題皆可歸結(jié)為拐點問題。在相同路徑下，拐點越多耗時越長、能耗越大。

4.4 遺傳算法優(yōu)化參數(shù)

對于傳統(tǒng)蟻群算法來說，信息啟發(fā)式因子、期望啟發(fā)式因子和揮發(fā)函數(shù)因子的作用至關(guān)重要。信息啟發(fā)式因子α 的大小反映了信息素因素作用的強(qiáng)度。過大導(dǎo)致全局搜索能力減弱，易陷入局部最優(yōu)；過小導(dǎo)致算法搜索的隨機(jī)性增強(qiáng)，收斂速度變慢，難以找到最優(yōu)路徑。期望啟發(fā)式因子β 反映了先驗性、確定性因素作用的強(qiáng)度。過大則導(dǎo)致算法隨機(jī)性減弱，易陷入局部最優(yōu)；過小將導(dǎo)致螞蟻陷入隨機(jī)搜索，難以找到最優(yōu)解。揮發(fā)函數(shù)因子ρ 關(guān)系到蟻群算法的全局搜索能力及其收斂速度。過大導(dǎo)致路徑殘留信息素過少易導(dǎo)致收斂變慢；過小導(dǎo)致信息素過多，全局搜索能力下降導(dǎo)致易陷入局部最優(yōu)。為此提出利用遺傳算法快速、隨機(jī)的全局搜索能力，對改進(jìn)的蟻群算法中的重要參數(shù)進(jìn)行優(yōu)化，通過較優(yōu)種群的尋找完成蟻群算法參數(shù)的優(yōu)化，優(yōu)化過程中遺傳算法將重復(fù)調(diào)用蟻群算法，并根據(jù)式（18）作為參數(shù)優(yōu)劣的標(biāo)準(zhǔn)：

式中，Mval表示適應(yīng)度函數(shù)值；f( )Mt由式（16）計算得來；iterate 代表算法出現(xiàn)最優(yōu)解的最少迭代次數(shù)；weightm和weighti代表適應(yīng)度函數(shù)和最少迭代數(shù)的權(quán)重，其值范圍0到1。

首先對遺傳算法參數(shù)進(jìn)行設(shè)定，設(shè)定交叉概率、變異概率、種群大小和編碼長度。對改進(jìn)的蟻群算法參數(shù)進(jìn)行二進(jìn)制處理，設(shè)定信息函數(shù)因子α 其值范圍為0到10；期望函數(shù)因子β 其值范圍為0 到10；揮發(fā)函數(shù)因子ρ 其值范圍0到1；將它們隨機(jī)生成一個三維二進(jìn)制的數(shù)組，按式（19）進(jìn)行十進(jìn)制處理，帶入改進(jìn)后的蟻群算法中。

按式（18）選擇適應(yīng)度函數(shù)最高的種群。之后對種群進(jìn)行交叉操作和變異操作，生成新種群，以此提高系統(tǒng)的全局搜索能力。之后根據(jù)新種群進(jìn)行選擇，最后選擇最優(yōu)的參數(shù)，作為本地圖模型的參數(shù)進(jìn)行蟻群算法。

由于傳統(tǒng)遺傳算法易陷入局部最優(yōu)問題，常常對傳統(tǒng)遺傳算法引入模擬退火思想[24]。將變異后新種群的最高適應(yīng)度函數(shù)值與交叉變異前的舊種群的最高適應(yīng)度函數(shù)值對比，決定是否生成新種群[25]如式（20）：

式中，f( m )為種群中交叉變異前的適應(yīng)度，f( n )為交叉變異后的適應(yīng)度，T 為當(dāng)前溫度，隨著進(jìn)化的進(jìn)行T按降溫速率衰減。計算公式為式（21）：

式中，T0代表退火算法初始溫度，q 代表降溫速率，t代表進(jìn)化次數(shù)。

4.5 改進(jìn)蟻群算法流程圖

改進(jìn)的蟻群算法流程圖如圖3所示。

首先進(jìn)行環(huán)境建模并對蟻群算法參數(shù)初始化，將隨機(jī)生成的參數(shù)帶入改進(jìn)后的蟻群算法，判斷是否找到目標(biāo)或?qū)⒛繕?biāo)送回。如若找到則根據(jù)路徑優(yōu)劣對信息素進(jìn)行更新，否則螞蟻按概率移動到下一節(jié)點，繼續(xù)尋找目標(biāo)直到?jīng)]有下一節(jié)點可移動。循環(huán)迭代直到尋找到最優(yōu)路徑，記錄當(dāng)前最少迭代次數(shù)并按式（18）對適應(yīng)度進(jìn)行計算。之后進(jìn)行選擇變異操作，引進(jìn)模擬退火算法，加強(qiáng)傳統(tǒng)遺傳算法全局搜索能力。生成新種群。不斷循環(huán)往復(fù)，直至循環(huán)結(jié)束。

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

5 結(jié)果與分析

為驗證改進(jìn)蟻群算法的有效性，采用VS2017 軟件和MATLAB 進(jìn)行仿真實驗，按照公式（1）構(gòu)建地圖模型。為方便計算，仿真所取相關(guān)參數(shù)如下，遺傳算法交叉概率為0.5；變異概率為0.1；種群規(guī)模為25；初始溫度T0為3 000 ℃；終止溫度為0.000 5 ℃；降溫速率q 為0.9；蟻群算法螞蟻數(shù)目為50；迭代次數(shù)為50；單元格距離為1 m；最小轉(zhuǎn)彎耗時tc=1 s；AGV 小車正常行駛速度Vt=1 m/s；為增加對比性，分析本文算法有效性，分別做了以下幾組的對比實驗。首先是傳統(tǒng)蟻群算法如圖4 所示，其次是文獻(xiàn)[17]對傳統(tǒng)蟻群算法加入自適應(yīng)參數(shù)改進(jìn)如圖5所示。之后是文獻(xiàn)[18]采用雙向搜索機(jī)制對傳統(tǒng)蟻群算法改進(jìn)如圖6 所示。最后是本文算法對最短路徑進(jìn)行優(yōu)化如圖7 所示。根據(jù)運(yùn)行時間和能耗情況對系統(tǒng)進(jìn)行多指標(biāo)規(guī)劃如圖8 所示。各算法每代最優(yōu)路徑情況如圖9 所示。并將四種算法的各類指標(biāo)列入表1中，進(jìn)行對比。結(jié)果表明本文算法與其他算法相比全局搜索能力有所改進(jìn)，但收斂速度有待提高。

圖4 傳統(tǒng)蟻群算法路徑

圖5 文獻(xiàn)[17]算法路徑

圖6 文獻(xiàn)[18]算法路徑

圖7 本文算法路徑

由于本地圖特性，若直接采用多指標(biāo)算法難以體現(xiàn)本文算法優(yōu)越性。因此，首先根據(jù)規(guī)劃路徑的長度作為適應(yīng)度函數(shù)指標(biāo)進(jìn)行路徑規(guī)劃。驗證本文算法搜索全局能力和跳出局部最優(yōu)的能力是否有所提高。由圖4～7可知，各類算法經(jīng)過一定次數(shù)的迭代皆可以找到一條起點到終點的路徑。由傳統(tǒng)蟻群算法圖4可知，路徑陷入了局部最優(yōu)，尋找到的路徑長度為36.970 6 m，明顯有更優(yōu)路徑。根據(jù)文獻(xiàn)[17]對傳統(tǒng)蟻群算法進(jìn)行改進(jìn)參數(shù)優(yōu)化選擇最優(yōu)的參數(shù)進(jìn)行，如圖5 所示，路徑長度為34.970 6 m，跳出局部最優(yōu)能力加強(qiáng)，但全局搜索能力不足。對文獻(xiàn)[18]進(jìn)行改進(jìn)的蟻群算法，采用雙向搜索機(jī)制進(jìn)行路徑優(yōu)化，如圖6 所示，路徑長度為35.556 3 m，與傳統(tǒng)蟻群算法相比跳出局部最優(yōu)，全局搜索能力皆有所加強(qiáng)，但由于采用相遇即停止策略，使算法加快收斂的同時，對全局搜索能力進(jìn)行減弱。最后采用本文算法進(jìn)行路徑規(guī)劃，如圖7所示，在評價路徑距離時，本文算法效果最好，路徑最短為34.384 8 m。證明本文算法在提高全局搜索能力和跳出局部最優(yōu)解的能力更強(qiáng)。

圖8 多指標(biāo)優(yōu)化路徑

圖9 算法比較

除了全局搜索能力外，算法的收斂時間也是評價算法優(yōu)劣的指標(biāo)之一。傳統(tǒng)蟻群算法、文獻(xiàn)[17]改進(jìn)算法、文獻(xiàn)[18]改進(jìn)算法和本文算法每次迭代的最優(yōu)路徑，如圖9所示。

由圖9可知，對比傳統(tǒng)蟻群算法本文算法在收斂速度方面仍有所提升，但對比文獻(xiàn)[17]和文獻(xiàn)[18]來說本文算法在加快算法收斂的方面仍有所不足。然而，對于提高算法全局收斂能力跳出局部最優(yōu)的方面來說，本文算法相較傳統(tǒng)蟻群算法、文獻(xiàn)[17]和文獻(xiàn)[18]具有明顯提升。綜合對比四種算法指標(biāo)如最小路徑長度、運(yùn)行時間、拐點數(shù)目、能源損耗和最佳迭代次數(shù)記入表1。綜合對比驗證本文算法優(yōu)越性。

由表1可知，在綜合各類指標(biāo)后本文算法與其他文獻(xiàn)算法的對比，易知本文算法在提高全局搜索能力跳出局部最優(yōu)方面有很大改進(jìn)。引入多指標(biāo)進(jìn)行路徑規(guī)劃時，由于地圖特性原因，四種算法在路徑優(yōu)化路線大致相同且迭代次數(shù)與圖9變化不大，因此不再贅述，僅列出本文算法在多指標(biāo)條件下對本地圖環(huán)境的路徑規(guī)劃，如圖8所示。路徑規(guī)劃距離為35.799 m，但拐點數(shù)僅為7個，運(yùn)行時間為37.499 s，能源損耗為42.799 W。驗證本文算法在兼顧系統(tǒng)運(yùn)行時間的同時大大減少了能源損耗。

為驗證本文算法在復(fù)雜環(huán)境下的通用性，另外選擇兩組復(fù)雜地圖進(jìn)行實驗，一組地圖為30×30 復(fù)雜情況，根據(jù)地圖建立模型，由于地圖規(guī)模擴(kuò)大，為保證算法可靠性，對螞蟻數(shù)目進(jìn)行修改，將數(shù)目增加至100個，保證算法可以找到路徑。傳統(tǒng)蟻群算法路徑如圖10 所示。文獻(xiàn)[17]算法路徑如圖11 所示。文獻(xiàn)[18]算法路徑如圖12所示。由圖可知上述算法在復(fù)雜地圖中都陷入了局部最優(yōu)。本文算法路徑效果圖如圖13所示。將四種算法在地圖二中的各類指標(biāo)記入表2，驗證本文算法的有效性。

圖10 地圖二傳統(tǒng)蟻群算法路徑

圖11 地圖二文獻(xiàn)[17]算法路徑

圖12 地圖二文獻(xiàn)[18]算法路徑

表1 算法指標(biāo)比較

圖13 地圖二本文算法路徑

由上述可知，傳統(tǒng)蟻群算法路徑長度為43.941 1 m，文獻(xiàn)[17]算法路徑長度為42.769 6 m，文獻(xiàn)[18]算法路徑長度為42.769 6 m，本文算法路徑長度為42.183 8 m。

由圖14 可知在此復(fù)雜地圖中，傳統(tǒng)蟻群算法最少迭代次數(shù)在10 次，收斂速度過慢且陷入局部最優(yōu)后跳出能力較弱。文獻(xiàn)[17]算法最少收斂次數(shù)在6 次，可知文獻(xiàn)[17]算法在加快收斂速度方面有很大改善，但是對于跳出局部最優(yōu)情況有待提高。文獻(xiàn)[18]最少迭代次數(shù)在11次，可知文獻(xiàn)[18]算法在提高全局搜索能力有很大提高，但是收斂速度和跳出局部最優(yōu)能力未有改進(jìn)。本文算法最少收斂次數(shù)在10 次，跟上述算法相比雖然路徑最短，跳出局部最優(yōu)能力有很大改進(jìn)，但對于加快收斂速度提升不大，有待進(jìn)一步加強(qiáng)。

圖14 地圖二算法比較

由表2 可知本文算法相比較其他算法具有全局搜索能力強(qiáng)和跳出局部最優(yōu)能力好的優(yōu)點。

另一組地圖為50×50 復(fù)雜地圖，根據(jù)地圖建立模型，并將螞蟻數(shù)目增加至150 個，保證算法可以找到路徑。傳統(tǒng)蟻群算法路徑如圖15 所示。文獻(xiàn)[17]算法路徑如圖16所示。文獻(xiàn)[18]算法路徑如圖17所示。由圖可知上述算法在此地圖中同樣陷入了局部最優(yōu)。本文算法路徑效果圖如圖18所示。將四種算法在地圖三中的各類指標(biāo)記入表3。通過對比表明在此復(fù)雜地圖本文算法仍具有良好的全局搜索能力。

圖15 地圖三傳統(tǒng)蟻群算法路徑

圖16 地圖三文獻(xiàn)[17]算法路徑

圖17 地圖三文獻(xiàn)[18]算法路徑

圖18 地圖三本文算法路徑

表2 地圖二各算法指標(biāo)比較

表3 地圖三各算法指標(biāo)比較

由上述可知，傳統(tǒng)蟻群算法路徑長度為75.982 8 m，文獻(xiàn)[17]算法路徑長度為74.568 5 m，文獻(xiàn)[18]算法路徑長度為75.154 3 m，本文算法路徑長度為73.982 8 m。驗證了本文算法具有良好的全局搜索能力。

由圖19 可知在此復(fù)雜地圖中，傳統(tǒng)蟻群算法最少迭代次數(shù)在23 次，收斂速度過慢且陷入局部最優(yōu)后跳出能力較弱。文獻(xiàn)[17]算法最少收斂次數(shù)在17次，可知文獻(xiàn)[17]算法在加快收斂速度方面有很大改善，但是跳出局部最優(yōu)能力有待改善。文獻(xiàn)[18]最少迭代次數(shù)在21次，可知文獻(xiàn)[18]算法在提高全局搜索能力有很大提高，但是收斂速度和跳出局部最優(yōu)能力仍有不足。本文算法最少收斂次數(shù)在23 次，跟上述算法相比雖然路徑最短，跳出局部最優(yōu)能力有很大改進(jìn)，但對于加快收斂速度提升不大，有待進(jìn)一步加強(qiáng)。與之前兩種地圖仿真結(jié)論相同，驗證本文算法在各類地圖中皆具有良好的全局搜索能力。

圖19 地圖三算法比較

由表3可知，在復(fù)雜地圖下本文算法相比較其他算法仍具有良好的全局搜索能力和跳出局部最優(yōu)的能力，驗證本文算法的優(yōu)越性。

6 結(jié)語

針對AGV 小車的路徑規(guī)劃問題，提出了一種改進(jìn)的蟻群算法，經(jīng)仿真驗證，改進(jìn)后的算法在路徑規(guī)劃方面是可行的、有效的。本文算法具體有以下特點：

（1）引入雙向搜索策略和變異因子，提高蟻群全局搜索能力，加大算法前期搜索有效解的數(shù)目，提高算法前期收斂能力，避免算法陷入局部最優(yōu)解。

（2）引入狼群算法中獎懲因子，對每代蟻群最優(yōu)個體進(jìn)行獎勵，最差個體進(jìn)行懲罰，以收斂速度為代價，進(jìn)一步提高全局搜索能力，避免陷入局部最優(yōu)。同時設(shè)定信息素最大最小閾值，確保不會出現(xiàn)路徑信息素接近于0而導(dǎo)致算法陷入停滯。

（3）引入多指標(biāo)適應(yīng)度函數(shù)，通過對AGV系統(tǒng)的運(yùn)行時間、能耗情況和拐點數(shù)目等評價指標(biāo)，使規(guī)劃出的路徑更加安全可靠。

（4）采用遺傳算法對改進(jìn)的蟻群算法進(jìn)行參數(shù)優(yōu)化，為避免遺傳算法局部最優(yōu)問題，引入模擬退火算法加強(qiáng)遺傳算法全局搜索能力，保證選擇最優(yōu)參數(shù)對算法進(jìn)行運(yùn)算，提高算法收斂時間，減少最少迭代次數(shù)。