何雅穎，范昕煒

中國(guó)計(jì)量大學(xué) 質(zhì)量與安全工程學(xué)院，杭州310018

機(jī)器人路徑規(guī)劃是指根據(jù)已知障礙環(huán)境，自行規(guī)劃出一條從起始點(diǎn)到達(dá)終止點(diǎn)無(wú)碰撞的最優(yōu)路徑[1]。其中傳統(tǒng)方法包括柵格法、A*算法[2]、人工勢(shì)場(chǎng)算法[3]等。隨著智能群算法的發(fā)展，遺傳算法[4]、粒子群算法[5]、蟻群算法等也開(kāi)始應(yīng)用于路徑規(guī)劃中。

蟻群算法（Ant Colony Optimization，ACO）是由意大利學(xué)者Dorigo等[6]提出的一種仿生螞蟻覓食的智能群算法，具有正反饋、并行性、強(qiáng)魯棒性和較好適應(yīng)性的特點(diǎn)，但同時(shí)也具有易陷入局部最優(yōu)、收斂速度較慢和易陷入死鎖等問(wèn)題。其中信息素對(duì)算法結(jié)果具有重要影響，不少學(xué)者通過(guò)信息素不同的設(shè)置方式來(lái)優(yōu)化算法。文獻(xiàn)[7]提出非均勻信息素分布劃定起點(diǎn)到終點(diǎn)兩個(gè)點(diǎn)為頂點(diǎn)的矩形區(qū)域?yàn)橛欣麉^(qū)域，提高該區(qū)域的初始值。該方法能有效防止螞蟻在初期向目標(biāo)點(diǎn)反方向搜索，但是區(qū)域內(nèi)信息素并沒(méi)有差別，改進(jìn)效果有限。文獻(xiàn)[8]提出雙層蟻群算法，先通過(guò)外層算法求取最優(yōu)解延伸其解空間，后利用內(nèi)層算法進(jìn)行局部尋優(yōu)，如果在此空間內(nèi)找到更優(yōu)路徑則執(zhí)行信息素二次更新。該方法雖然提高了最優(yōu)解的可能性，但是僅限于有限空間探索，算法可能陷入局部最優(yōu)。文獻(xiàn)[9]引入了最優(yōu)解與最差解改進(jìn)信息素更新規(guī)則，增強(qiáng)當(dāng)前最優(yōu)路徑的信息素，減弱最差路徑的信息素。該方法有效加快了收斂速度，但同時(shí)也減少了種群的多樣性，不利于最優(yōu)解的獲取。文獻(xiàn)[10]提出在算法搜索過(guò)程中加入人工勢(shì)場(chǎng)局部搜索尋優(yōu)算法，將人工勢(shì)場(chǎng)中力因素轉(zhuǎn)換為局部擴(kuò)散信息素，算法有效減少了交叉路徑與螞蟻“迷失”數(shù)量，提高了蟻群對(duì)障礙物的預(yù)避障能力，但算法結(jié)構(gòu)設(shè)計(jì)較為復(fù)雜，環(huán)境適應(yīng)能力有待提高。文獻(xiàn)[11]將遺傳算法與蟻群算法相融合，提出利用遺傳算法生成初始路徑，將較優(yōu)路徑作為蟻群算法初始信息素的參考信息，減少初期算法盲目性，后利用蟻群算法對(duì)初始路徑進(jìn)一步優(yōu)化。該改進(jìn)算法能避免局部最優(yōu)，但算法運(yùn)行時(shí)間較長(zhǎng)。

綜上所述，信息素的設(shè)置能有效提高收斂速度，但同時(shí)也有可能降低算法尋優(yōu)能力，不利于獲取最優(yōu)解。為平衡尋求最優(yōu)解與算法收斂速度，提出改進(jìn)的蟻群算法，其中包括：對(duì)初始信息素進(jìn)行非均勻分配，提高收斂速度；提出局部分塊優(yōu)化策略優(yōu)化子區(qū)域路徑提高求解質(zhì)量；利用信息素增強(qiáng)因子保留更優(yōu)解，避免陷入局部最優(yōu)；引入反向?qū)W習(xí)對(duì)信息素進(jìn)行優(yōu)化，改進(jìn)狀態(tài)選擇概率，提高算法全局尋優(yōu)能力。

1 相關(guān)知識(shí)

1.1 蟻群算法

1.1.1轉(zhuǎn)移概率

在t時(shí)刻螞蟻m從節(jié)點(diǎn)i到節(jié)點(diǎn)j由式（1）計(jì)算轉(zhuǎn)移概率并根據(jù)輪盤賭法則對(duì)下一路徑點(diǎn)進(jìn)行選擇。

式中，τij(t)為路徑(i,j)間的信息素含量，α為信息素啟發(fā)因子，ηij(t)為期望啟發(fā)項(xiàng)，通過(guò)式（2）計(jì)算可得；d(i,j)為路徑(i,j)間的歐式距離，β為期望啟發(fā)式因子。α和β分別代表信息素、期望啟發(fā)項(xiàng)的重要程度。allowedm表示螞蟻m所有下一可行節(jié)點(diǎn)集合。

1.1.2信息素更新

每只螞蟻在行走過(guò)程中都會(huì)留下一定量的信息素，隨著迭代次數(shù)的增加，信息素不斷地增加，同時(shí)也在不斷揮發(fā)。所有螞蟻完成一次迭代后，會(huì)對(duì)殘留信息素進(jìn)行更新，根據(jù)式（3）、（4）更新信息素。

式（3）中ρ為揮發(fā)系數(shù)，Δτij為本次迭代中路徑(i,j)的信息素增量，W為螞蟻總數(shù)，為本次迭代中第m只螞蟻在路徑(i,j)留下的信息素。式（4）中值的計(jì)算采用的更新方式為蟻周模型，除此之外還有蟻量模型和蟻密模型。式中Q是一個(gè)常數(shù)，表示信息素強(qiáng)度值，Lm表示第m只螞蟻在本次迭代中所走路徑總長(zhǎng)度。

1.2 反向?qū)W習(xí)

反向?qū)W習(xí)的概念于2005年由Tizhoosh[12]提出，后被成功用于算法的進(jìn)化，解決優(yōu)化問(wèn)題。以下為反向解定義。

定義1假設(shè)x是一維空間的一個(gè)實(shí)數(shù)，x∈[a,b]，因此x反向解為[13]：

定義2假設(shè)P=(x1,x2,…,xD)為D維空間中一點(diǎn)，其中xi∈[ai,bi],?i∈{1,2,…,D},則其反向解為Pˉ=

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

2.1 非均勻初始信息素分布

蟻群算法中，螞蟻主要根據(jù)柵格間信息素的差異尋求最優(yōu)路徑，而在傳統(tǒng)的蟻群算法中，初始信息素采用的是均勻分布，因此每只螞蟻的狀態(tài)轉(zhuǎn)移概率只取決于期望啟發(fā)項(xiàng)，而柵格間期望啟發(fā)項(xiàng)差異較小，因此初期算法由于缺少信息素引導(dǎo)具有盲目性，且搜索速度較慢，最終影響解的質(zhì)量與收斂速度[14]。因此對(duì)初始化信息素進(jìn)行非均勻分布處理，提高柵格間信息素的差異能有效提高搜索效率。為避免改進(jìn)后的初始信息素過(guò)度或者錯(cuò)誤引導(dǎo)后續(xù)螞蟻探索最優(yōu)解，信息素的非均勻分布僅針對(duì)區(qū)域進(jìn)行差異處理而非單個(gè)柵格點(diǎn)，即只提高有利區(qū)域內(nèi)的初始信息素，降低算法陷入局部最優(yōu)的可能。由于最優(yōu)路徑多集中于起點(diǎn)S至目標(biāo)點(diǎn)E的連線附近區(qū)域，其區(qū)域范圍受障礙物影響，以起點(diǎn)S和目標(biāo)點(diǎn)E連線作x軸，以連線中點(diǎn)作為原點(diǎn)建立坐標(biāo)系，以起點(diǎn)至終點(diǎn)距離dSE為長(zhǎng)軸，全局優(yōu)選區(qū)域距離ddiff為短軸建立橢圓，其計(jì)算公式如式（8）。在該橢圓內(nèi)的區(qū)域?yàn)槿謨?yōu)選區(qū)域R，并提高優(yōu)選區(qū)域R內(nèi)的路徑點(diǎn)初始信息素，而不在該范圍內(nèi)的路徑點(diǎn)則保持原初始信息素值τ0。非均勻初始信息素分布規(guī)則如式（7）所示：

式（7）中τ0為信息素初始值，C為全局優(yōu)選區(qū)域信息素增量。式（8）中ddiff與地圖障礙物有關(guān)，ξ為環(huán)境障礙物占比，ξ越高，則ddiff越大，全局優(yōu)選區(qū)域范圍更廣；r和c分別表示矩陣地圖的行數(shù)與列數(shù)。

2.2 改進(jìn)信息素更新規(guī)則

信息素的更新包括對(duì)原有路徑上信息素的揮發(fā)與新增路徑信息素的積累，因此提出局部信息素分塊優(yōu)化策略對(duì)信息素的更新規(guī)則進(jìn)行了改進(jìn)。

在傳統(tǒng)蟻群算法中，所有的螞蟻完成當(dāng)前迭代后將對(duì)螞蟻路徑進(jìn)行更新。路徑的好壞評(píng)價(jià)取決于全局路徑的長(zhǎng)度，而忽略了對(duì)局部區(qū)域路徑的評(píng)價(jià)。圖1中實(shí)線路徑與虛線路徑分別代表歷史最優(yōu)路徑和當(dāng)前迭代最優(yōu)路徑，橫坐標(biāo)x∈[0,5]時(shí)，當(dāng)前迭代最優(yōu)路徑更短；而在x∈[5,20]時(shí)，歷史最優(yōu)路徑更短，因此提出局部信息素分塊優(yōu)化策略。算法初期并不知道路徑將會(huì)經(jīng)過(guò)哪些路徑點(diǎn)，無(wú)法利用具體坐標(biāo)作為分割依據(jù)，因此將矩陣地圖按x坐標(biāo)以一定間隔步長(zhǎng)n縱向切割均勻劃分為多個(gè)區(qū)域，n越小容易造成路徑曲折較多，不利于尋求最佳路徑，n較大則達(dá)不到分塊優(yōu)化的效果。如圖1所示矩陣地圖被以步長(zhǎng)n=5劃為4個(gè)區(qū)域，有多個(gè)點(diǎn)都經(jīng)過(guò)同一切分線時(shí)，以最后經(jīng)過(guò)點(diǎn)作為終止點(diǎn)。隨后引入精英螞蟻[15]的策略，當(dāng)所有螞蟻完成當(dāng)前迭代后，對(duì)各區(qū)域內(nèi)的最優(yōu)局部路徑信息素進(jìn)行更新。全局最優(yōu)路徑本質(zhì)上是由各個(gè)局部最優(yōu)路徑組合而成的，對(duì)局部最優(yōu)路徑信息素的更新旨在引導(dǎo)后續(xù)螞蟻行駛至該區(qū)域內(nèi)的路徑選擇，一旦螞蟻行駛至該區(qū)域最優(yōu)路徑附近則能通過(guò)此策略更大概率選擇最優(yōu)路徑點(diǎn)。但局部區(qū)域路徑優(yōu)劣如果僅從區(qū)域內(nèi)路徑長(zhǎng)度考慮，很容易導(dǎo)致區(qū)域內(nèi)水平方向的路徑被認(rèn)為是最優(yōu)而非更接近終點(diǎn)的路徑，因此路徑長(zhǎng)度考慮其路徑段與起點(diǎn)和終點(diǎn)的總距離，如式（9）所示。同時(shí)由于非均勻初始化信息素的改進(jìn)，對(duì)局部路徑長(zhǎng)度的選擇也更有利。

圖1 信息素分塊優(yōu)化Fig.1 Pheromone block optimization

因?yàn)榫植扛轮皇轻槍?duì)局部區(qū)域，缺乏全局信息素引導(dǎo)，所以對(duì)每個(gè)區(qū)域內(nèi)最優(yōu)路徑更新后，再對(duì)螞蟻的全局信息素進(jìn)行更新。鑒于此前已經(jīng)對(duì)局部最優(yōu)路徑進(jìn)行了更新，為了避免信息素重復(fù)疊加，只對(duì)全局最優(yōu)路徑信息素進(jìn)行更新。局部最優(yōu)路徑更新規(guī)則與全局最優(yōu)路徑更新規(guī)則相同，如式（9）和式（10）所示。

式中，當(dāng)計(jì)算局部最優(yōu)路徑信息素時(shí)，Lbest為各個(gè)區(qū)域內(nèi)最優(yōu)路徑長(zhǎng)度，Ldist為各局部區(qū)域內(nèi)最優(yōu)路徑段長(zhǎng)度，Lds為路徑段第一個(gè)路徑點(diǎn)到起點(diǎn)距離，Lde為路徑段最后一個(gè)路徑點(diǎn)到終點(diǎn)距離。在計(jì)算全局最優(yōu)路徑信息素時(shí)，Lds和Lds都為0，則Lbest為全局最優(yōu)路徑長(zhǎng)度。

如果只對(duì)最優(yōu)路徑進(jìn)行更新，隨著迭代次數(shù)增加，最優(yōu)路徑上的信息素累積越來(lái)越多，高濃度的信息素含量會(huì)導(dǎo)致即使迭代后期出現(xiàn)了比歷史更優(yōu)路徑，這條新路徑上釋放的信息素仍然遠(yuǎn)遠(yuǎn)少于現(xiàn)有最優(yōu)路徑上的信息素，容易陷入局部最優(yōu)且可能在迭代收斂時(shí)丟失該解[16]。針對(duì)該問(wèn)題，在信息素更新規(guī)則中引入信息素增強(qiáng)因子r，當(dāng)出現(xiàn)比歷史更優(yōu)的路徑時(shí)，通過(guò)增強(qiáng)因子提高此路徑上的信息素，如式（11）所示。增強(qiáng)因子r隨著當(dāng)前迭代次數(shù)Nc的改變而發(fā)生改變，初期r值較小，避免信息素過(guò)量疊加防止算法陷入局部最優(yōu)，后期值較大，加快收斂，如式（12）。

式中，Nmax為迭代總數(shù)，Lbest為當(dāng)前局部區(qū)域或全局最優(yōu)路徑，L為歷史最優(yōu)路徑。

2.3 改進(jìn)狀態(tài)轉(zhuǎn)移概率

反向?qū)W習(xí)的主要思想在于對(duì)一個(gè)可行解，同時(shí)評(píng)估其反向解，對(duì)比后選擇較優(yōu)解。蟻群算法的正反饋機(jī)制不適用于完全解[17]，因此反向?qū)W習(xí)更適用于擴(kuò)展蟻群算法解空間而非評(píng)估反向解，通過(guò)反向?qū)W習(xí)增加解空間覆蓋率達(dá)到提高求解質(zhì)量的效果。文獻(xiàn)[12]提出基于反向?qū)W習(xí)的蟻群系統(tǒng)用于解決TSP問(wèn)題，文獻(xiàn)[16]提出反向蟻群優(yōu)化算法解決故障診斷監(jiān)控參數(shù)優(yōu)化問(wèn)題。

參考以上文獻(xiàn)，引入反向信息素改進(jìn)蟻群算法狀態(tài)轉(zhuǎn)移概率，用于路徑規(guī)劃尋求最優(yōu)解。根據(jù)反向?qū)W習(xí)的定義，反向信息素計(jì)算如下式：

此時(shí)的信息素τij為局部和全局更新完畢后的信息素，分布優(yōu)化策略已結(jié)束，因此式（13）中Lgbest為全局最優(yōu)路徑長(zhǎng)度。第一次迭代過(guò)程中不會(huì)產(chǎn)生Lgbest，因此第一次迭代時(shí)的值為初始信息素。其中確定反向信息素的值為初始信息素τij(0)和最優(yōu)路徑長(zhǎng)度Lgbest，因?yàn)樾畔⑺氐姆e累由初始信息素和最優(yōu)路徑長(zhǎng)度共同決定。

當(dāng)螞蟻m在t時(shí)刻進(jìn)行路徑點(diǎn)選擇時(shí)，其轉(zhuǎn)移概率為：

式中，λc為反向概率，λc∈(0,1)，λ為隨機(jī)數(shù)；當(dāng)λ<λc時(shí)，使用反向信息素計(jì)算選擇概率，當(dāng)λ>λc時(shí)，選擇概率為原公式計(jì)算值。d(j,e)為下一節(jié)點(diǎn)j到終點(diǎn)e的歐氏距離。

3 改進(jìn)蟻群算法的應(yīng)用步驟

步驟1建立矩陣柵格地圖，設(shè)置起始位置起點(diǎn)S與目標(biāo)點(diǎn)E；初始化參數(shù)，包括信息素啟發(fā)因子α，期望啟發(fā)式因子β，揮發(fā)系數(shù)ρ，螞蟻總數(shù)W，迭代總數(shù)Nmax，信息素強(qiáng)度值Q，反向概率λc，信息素初始值τ0與初始信息素增量C。

步驟2初始信息素非均勻處理。通過(guò)式（8）確定ddiff，計(jì)算全局優(yōu)選區(qū)域R的范圍，并根據(jù)式（7）對(duì)初始信息素非均勻處理得出τij(0)。

步驟3路徑點(diǎn)選擇。將W只螞蟻放置于起點(diǎn)處，初始化禁忌表、路徑點(diǎn)、路徑長(zhǎng)度，并將起點(diǎn)加入禁忌表中。根據(jù)式（14）和（15）計(jì)算每一只螞蟻下一路徑點(diǎn)選擇概率，通過(guò)輪盤賭選擇下一個(gè)節(jié)點(diǎn)，并將該節(jié)點(diǎn)加入禁忌表中。

步驟4判斷螞蟻是否到達(dá)了終點(diǎn)，如果沒(méi)有，則返回到步驟3直至到達(dá)目標(biāo)點(diǎn)為止。否則執(zhí)行步驟5。

步驟5局部信息素分塊更新。當(dāng)所有螞蟻完成當(dāng)前迭代后，對(duì)所有地圖進(jìn)行分塊處理，并分別計(jì)算每個(gè)區(qū)域的最佳局部路徑，按式（9）、（10）和（11）分別對(duì)每個(gè)區(qū)域進(jìn)行信息素更新，此時(shí)Lbest為每個(gè)區(qū)域最優(yōu)局部解。當(dāng)出現(xiàn)更優(yōu)解時(shí)，按照式（12）計(jì)算增強(qiáng)因子并代入式（11）中進(jìn)行計(jì)算，L為每個(gè)區(qū)域歷史最優(yōu)路徑。

步驟6全局信息素更新。在局部區(qū)域信息素更新完畢后，按式（9）、（10）和（11）對(duì)全局信息素進(jìn)行更新。此時(shí)Lbest為全局最優(yōu)解。當(dāng)出現(xiàn)更優(yōu)解時(shí)，按照式（11）計(jì)算增強(qiáng)因子并代入式（11）中進(jìn)行計(jì)算，L為全局歷史最優(yōu)路徑。

步驟7反向信息素更新。按照式（13）對(duì)反向信息素進(jìn)行更新，式中Lbest為全局最優(yōu)解。

步驟8判斷是否達(dá)到最大迭代數(shù)。如果達(dá)到最大迭代數(shù)則輸出當(dāng)前最優(yōu)全局路徑，如果沒(méi)有，則清空禁忌表，并將迭代次數(shù)加1，重復(fù)步驟3到步驟7，直到達(dá)到最大迭代數(shù)。

4 模擬實(shí)驗(yàn)和分析

為驗(yàn)證改進(jìn)蟻群算法的有效性，在MATLAB 2018b上進(jìn)行仿真實(shí)驗(yàn)，操作系統(tǒng)為Win10（64 bit）操作系統(tǒng)，CoreTMi5-10210U處理器，16 GB運(yùn)行內(nèi)存。仿真實(shí)驗(yàn)采用兩組對(duì)比實(shí)驗(yàn)，分別為20×20、30×30的柵格地圖，并在相同地圖下將本文改進(jìn)蟻群算法與傳統(tǒng)蟻群算法、文獻(xiàn)[8]算法結(jié)果進(jìn)行對(duì)比分析。

4.1 參數(shù)選取

蟻群算法參數(shù)多利用經(jīng)驗(yàn)值取值，并利用多次對(duì)比結(jié)果選取最佳參數(shù)，但算法參數(shù)還涉及局部分塊優(yōu)化的步長(zhǎng)n，因此基于以上參數(shù)，取分割步長(zhǎng)n=1,2,…,c（c為地圖的列數(shù)）在隨機(jī)20×20、30×30地圖上進(jìn)行實(shí)驗(yàn)。其余仿真參數(shù)設(shè)置為：α=1,β=7,ρ=0.2,W=50,Nmax=

從20×20仿真結(jié)果圖2（a）來(lái)看，n∈[4,6]時(shí)，即將地圖分為4~5個(gè)區(qū)域效果較好，當(dāng)n較小時(shí)，迭代次數(shù)比不分塊更高，算法信息素分布分散，難收斂，無(wú)法找到較優(yōu)值，因此路徑長(zhǎng)度也比不分塊更長(zhǎng)。隨著n的增加，雖然迭代收斂次數(shù)有時(shí)能較快收斂，但是算法也容易陷入局部最優(yōu)。從30×30的仿真結(jié)果圖2（b）也可以看出這一點(diǎn)，當(dāng)n∈[4,7]時(shí)，對(duì)應(yīng)將地圖分為4~5效果較好，n過(guò)長(zhǎng)或過(guò)短都將影響收斂與最終結(jié)果，造成收斂速度與局部最優(yōu)解的矛盾?；诖?，對(duì)20×20和30×30都分為4塊，20×20地圖取n=5，30×30地圖取n=6。

圖2 n取值對(duì)結(jié)果的影響Fig.2 Influence of n value on results

4.2 20×20地圖實(shí)驗(yàn)仿真

在20×20柵格地圖下，分別對(duì)傳統(tǒng)蟻群算法、文獻(xiàn)[8]、本文改進(jìn)算法進(jìn)行仿真，路徑仿真分別如圖3和圖4所示。最終實(shí)驗(yàn)數(shù)據(jù)如表1所示：傳統(tǒng)算法路徑規(guī)劃長(zhǎng)度為32.866，文獻(xiàn)[8]規(guī)劃長(zhǎng)度為33.452，本文改進(jìn)算法規(guī)劃長(zhǎng)度為28.038。本文算法較另外兩種算法路徑規(guī)劃長(zhǎng)度更短，拐點(diǎn)更少，對(duì)比傳統(tǒng)算法與文獻(xiàn)[8]算法，路徑長(zhǎng)度分別縮短了14.6%和16.2%，拐點(diǎn)分別減少66.6%和75.0%。傳統(tǒng)蟻群算法收斂次數(shù)為21次，文獻(xiàn)[8]為5次，本文改進(jìn)算法收斂次數(shù)為12次。雖然文獻(xiàn)[8]收斂次數(shù)為5，但是其求解質(zhì)量明顯低于本文改進(jìn)算法，這也說(shuō)明本文在算法收斂速度與求解全局最優(yōu)解上平衡得更好。傳統(tǒng)蟻群算法在迭代后期丟失最優(yōu)解，最后收斂為局部最優(yōu)值，而由于本文引入了增強(qiáng)因子r避免了這一問(wèn)題，保留了最優(yōu)解，避免了陷入局部最優(yōu)。

圖3 20×20環(huán)境下四種算法仿真結(jié)果Fig.3 Simulation results of four algorithms in 20×20 environment

圖4 各算法路徑收斂曲線Fig.4 Convergence curve of each algorithm path

表1 20×20環(huán)境下各個(gè)算法結(jié)果對(duì)比Table 1 Comparison of results of various algorithms in 20×20 environment

為進(jìn)一步驗(yàn)證各個(gè)改進(jìn)環(huán)節(jié)的有效性，分別對(duì)每個(gè)環(huán)節(jié)改進(jìn)和本文整體改進(jìn)在20×20柵格地圖下進(jìn)行獨(dú)立實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如表2所示。初始化與分塊策略這一改進(jìn)環(huán)節(jié)對(duì)比傳統(tǒng)蟻群算法有效減少了迭代次數(shù)，同時(shí)找到了更優(yōu)解。反向?qū)W習(xí)信息素的引入對(duì)比傳統(tǒng)算法也有效提高了算法的全局尋優(yōu)能力，避免陷入了局部最優(yōu)，但也由于缺乏信息素引導(dǎo)，導(dǎo)致迭代次數(shù)較多。而本文的改進(jìn)方法綜合以上步驟，結(jié)合了收斂速度的提升與全局尋優(yōu)能力上的改進(jìn)，能在較少的迭代次數(shù)內(nèi)找到更優(yōu)解，同時(shí)曲線更平滑，路徑拐點(diǎn)數(shù)更少。

表2 20×20環(huán)境下各改進(jìn)環(huán)節(jié)結(jié)果對(duì)比Table 2 Comparison of results of improvement steps in 20×20 environment

4.3 30×30地圖實(shí)驗(yàn)仿真

在30×30復(fù)雜環(huán)境下，實(shí)驗(yàn)仿真結(jié)果如圖5和圖6所示。隨著地圖的復(fù)雜度增加，三種算法收斂迭代次數(shù)都有所增加，傳統(tǒng)蟻群算法收斂曲線波動(dòng)較大，算法穩(wěn)定性較差，且依然陷入了局部最優(yōu)。文獻(xiàn)[8]雖然對(duì)比傳統(tǒng)算法結(jié)果更優(yōu)，但由于該算法僅針對(duì)于最優(yōu)解拓展出來(lái)的小區(qū)域進(jìn)行局部?jī)?yōu)化，缺少全局探索，因此也陷入局部最優(yōu)。最終實(shí)驗(yàn)數(shù)據(jù)如表3所示，綜合指標(biāo)來(lái)看，本文改進(jìn)算法在復(fù)雜環(huán)境下也有不錯(cuò)效果。最優(yōu)路徑長(zhǎng)度上來(lái)看，本文改進(jìn)算法路徑長(zhǎng)度對(duì)比傳統(tǒng)蟻群算法和文獻(xiàn)[8]分別縮短了14.1%和7.9%，拐點(diǎn)個(gè)數(shù)減少63.3%和60.0%，迭代次數(shù)減少23.0%和39.3%。在30×30地圖上也對(duì)各個(gè)步驟的改進(jìn)進(jìn)行了驗(yàn)證，如表4，其結(jié)果與20×20地圖結(jié)果類似，再一次驗(yàn)證了本文算法的有效性與優(yōu)越性。

圖5 30×30環(huán)境下四種算法仿真結(jié)果Fig.5 Simulation results of four algorithms in 30×30 environment

圖6 各算法路徑收斂曲線Fig.6 Convergence curve of each algorithm path

表3 30×30環(huán)境下各個(gè)算法結(jié)果對(duì)比Table 3 Comparison of results of various algorithms in 30×30 environment

表4 30×30環(huán)境下各改進(jìn)環(huán)節(jié)結(jié)果對(duì)比Table 4 Comparison of results of improvement steps in 30×30 environment

5 結(jié)束語(yǔ)

本文針對(duì)傳統(tǒng)蟻群算法存在易陷入局部最優(yōu)、收斂速度慢等不足，提出改進(jìn)蟻群算法。首先根據(jù)地圖的障礙物占比以及矩陣地圖大小構(gòu)建全局優(yōu)選區(qū)域，對(duì)初始信息素進(jìn)行差異化處理，提高區(qū)域內(nèi)信息素初始濃度而非具體柵格點(diǎn)信息素濃度，避免陷入局部最優(yōu)的同時(shí)提高了收斂速度；利用局部信息素分塊優(yōu)化策略對(duì)矩陣地圖進(jìn)行分塊處理，分別對(duì)各個(gè)子區(qū)域進(jìn)行尋優(yōu)并更新最優(yōu)路徑信息素，后對(duì)全局路徑進(jìn)行尋優(yōu)，更新最優(yōu)路徑信息素。為避免只更新最優(yōu)路徑信息素，丟失更優(yōu)解，在信息素更新公式中引入增強(qiáng)因子，保留更優(yōu)解，避免收斂于次優(yōu)解。最后應(yīng)用反向?qū)W習(xí)優(yōu)化信息素，改進(jìn)狀態(tài)選擇概率，拓展了解空間，提高了全局搜索能力。實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的算法明顯提高了收斂速度，尋優(yōu)能力更強(qiáng)。對(duì)初始化非均勻分布的處理、信息素更新規(guī)則的改進(jìn)以及反向?qū)W習(xí)在蟻群路徑規(guī)劃上的應(yīng)用對(duì)比傳統(tǒng)算法均有明顯的改進(jìn)，進(jìn)一步驗(yàn)證了算法的有效性與優(yōu)越性。