改進(jìn)蟻群算法在移動機(jī)器人路徑規(guī)劃上的應(yīng)用

陳 志，韓興國

(桂林航天工業(yè)學(xué)院 機(jī)械工程學(xué)院，廣西 桂林 541000)

0 引 言

傳統(tǒng)的移動機(jī)器人路徑規(guī)劃算法主要包括人工勢場法、網(wǎng)格法等[1,2]，但傳統(tǒng)路徑規(guī)劃算法目標(biāo)不可達(dá)性和局部最小點(diǎn)的問題容易導(dǎo)致路徑規(guī)劃的失敗，且隨著路徑環(huán)境復(fù)雜性的增加，存在數(shù)據(jù)存儲空間大、計(jì)算速度慢、實(shí)時決策差等缺陷[3,4]。

蟻群算法是由M.Dorigo等學(xué)者提出的分布式智能仿生算法[5]。該算法模擬了螞蟻合作覓食行為的性質(zhì)。它具有正反饋、高穩(wěn)健性和并行性的優(yōu)點(diǎn)，但是該算法存在搜索空間大、局部最優(yōu)、搜索效率低、計(jì)算量大等問題[6,7]。張?jiān)嚨萚8]提出一種改進(jìn)的多步長蟻群算法。將蟻群每次迭代產(chǎn)生的最優(yōu)路徑作為引導(dǎo)徑，利用路徑引導(dǎo)搜索策略確定多步長的移動路徑，提高搜索范圍的多樣性，該算法有效提高了算法跳出局部最優(yōu)的能力，但改進(jìn)算法在算法的收斂速度方面還有待改善。張強(qiáng)等[9]針對傳統(tǒng)人工勢場算法存在死鎖及局部路徑欠優(yōu)等問題，對其進(jìn)行改進(jìn)。利用障礙物檢測算法識別出有效障礙物和有效路徑中間點(diǎn)，通過引力場和邊界條件規(guī)劃出起點(diǎn)到中間點(diǎn)的局部路徑，將中間點(diǎn)置為新的起點(diǎn)進(jìn)行反復(fù)迭代，直至起點(diǎn)與目標(biāo)點(diǎn)重合則規(guī)劃完成，解的質(zhì)量明顯提高，但仍存在尋優(yōu)過程中搜索時間較長的問題。王慧等[10]利用粒子群算法個體加權(quán)平均值并加入慣性權(quán)重提出了一種改進(jìn)粒子群路徑優(yōu)化算法，但該算法搜索到最優(yōu)解時迭代次數(shù)較多，搜索時間較長。

鑒于此，提出了一種改進(jìn)的蟻群算法。該算法根據(jù)中間節(jié)點(diǎn)與起始終端線之間的距離關(guān)系設(shè)置不均勻分布的初始信息素，減少了初始階段的盲目性問題；將衰減因子引入啟發(fā)函數(shù)，隨著迭代次數(shù)的增加，啟發(fā)式信息在路徑選擇中的作用逐漸減弱，從而加快了收斂速度；使用偽隨機(jī)狀態(tài)轉(zhuǎn)移概率規(guī)則，并根據(jù)迭代次數(shù)和該迭代的最優(yōu)解計(jì)算狀態(tài)轉(zhuǎn)移概率值，以自適應(yīng)地調(diào)整確定選擇和隨機(jī)選擇的比例。對于死鎖問題，根據(jù)路徑上丟失的螞蟻數(shù)量，對不完整路徑的最后兩步進(jìn)行處罰，以減少丟失螞蟻的數(shù)量，確保算法的多樣性。仿真實(shí)驗(yàn)在不同的移動環(huán)境中進(jìn)行，實(shí)驗(yàn)結(jié)果表明，改進(jìn)的蟻群算法在性能指標(biāo)上有顯著提高。

1 基本蟻群算法

蟻群算法模擬了螞蟻“探索”的行為特征，即螞蟻將使用前螞蟻在覓食過程中留下的信息素，根據(jù)一定的概率選擇路徑或探索新的路徑并同時分泌信息素。路徑上的信息素會積累、揮發(fā)和擴(kuò)散，并影響下面的螞蟻。螞蟻傾向于選擇具有高信息素濃度的路徑并最終尋找最佳路徑[11]，蟻群算法的兩個最重要的步驟就是路徑選擇和信息素更新。

假設(shè)螞蟻k在t時刻位于節(jié)點(diǎn)i，則路徑轉(zhuǎn)換的概率可由式(1)表示，然后利用輪盤賭模型選擇下一個節(jié)點(diǎn)

(1)

式中：C為螞蟻允許在下一步選擇的節(jié)點(diǎn)集；τij為路徑(i，j)的信息素值；α為信息素激勵因子，它反映了信息素濃度對路徑選擇的重要性，α越大則信息素對于路徑選擇越重要，螞蟻將更傾向于選擇大多數(shù)螞蟻采取的路徑；β是預(yù)期的啟發(fā)因子，它反映了啟發(fā)式信息在路徑上的重要性。β越大則螞蟻越傾向于選擇最短路徑；ηij(t)為啟發(fā)式值，表示螞蟻從節(jié)點(diǎn)j轉(zhuǎn)移到目標(biāo)節(jié)點(diǎn)g的期望程度，如式(2)所示

(2)

式中：djg是節(jié)點(diǎn)j和目標(biāo)節(jié)點(diǎn)g之間的歐幾里德距離。每個螞蟻在使用路徑上的信息素的同時也會不斷分泌信息素，因此路徑上的信息素將不斷積累。為了防止過多的信息素導(dǎo)致啟發(fā)信息泛濫，在每個螞蟻采取一步或完成一個周期之后更新路徑上的信息素，并且從t+1時刻獲得路徑上的信息素，如式(3)所示

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

(3)

式中：ρ為信息素?fù)]發(fā)系數(shù)，主要模擬螞蟻信息素隨時間的自然揮發(fā)；1-ρ為信息素殘留因子；Δτij(t)為循環(huán)路徑(i，j)上信息素的增量。當(dāng)信息素更新策略時，有不同的計(jì)算方法。如式(4)所示為螞蟻循環(huán)模型計(jì)算方式

(4)

式中：Q為信息素的強(qiáng)度；Lk為螞蟻在此循環(huán)中所采用路徑的總長度。

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

2.1 改善初始信息素

基本蟻群算法的信息素值在算法的初始階段是固定的，螞蟻在初始路徑搜索中有一些盲目性，因此算法的搜索時間將會增加。鑒于此本文提出了一種改進(jìn)的信息素方法，該方法根據(jù)當(dāng)前節(jié)點(diǎn)、下一節(jié)點(diǎn)和起始點(diǎn)連接之間的相對距離計(jì)算初始信息素，如式(5)所示

(5)

其中，dSE為從起點(diǎn)到終點(diǎn)的歐幾里德距離；dSi為從起點(diǎn)到當(dāng)前節(jié)點(diǎn)的歐幾里德距離；dij為當(dāng)前節(jié)點(diǎn)和下一個節(jié)點(diǎn)之間的歐幾里德距離；djE為從下一個節(jié)點(diǎn)到終點(diǎn)的歐幾里德距離；C為下一個節(jié)點(diǎn)的集合；a0為常數(shù)。從式(5)中可以看出，當(dāng)dSi+dij+djE越小，路徑上的初始信息素越大。針對這一現(xiàn)象，根據(jù)位置關(guān)系設(shè)置了不均勻分布的初始信息素，避免了算法初始搜索的盲目性，進(jìn)一步提高了搜索速度。

2.2 改進(jìn)啟發(fā)式信息功能

基本蟻群算法的啟發(fā)式信息值與從下一個節(jié)點(diǎn)到目標(biāo)點(diǎn)的距離成反比，從而驅(qū)動螞蟻選擇短距離路徑。然而在不考慮當(dāng)前節(jié)點(diǎn)和下一節(jié)點(diǎn)的位置的情況下，所選路徑不一定是最短路徑，并且在后期搜索階段，為了加快收斂速度，啟發(fā)式信息對路徑選擇的影響將會削弱。因此本文提出了一種通過引入阻尼系數(shù)來改進(jìn)啟發(fā)式信息函數(shù)的方法，如式(6)所示

(6)

其中

(7)

式中：NCmax為最大迭代次數(shù)；NC為當(dāng)前的迭代次數(shù)。

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

信息素更新主要用于模擬天然螞蟻信息素隨時間的積累和自然揮發(fā)。目前對于信息素的更新主要有本地更新和全局更新兩種方式，本文結(jié)合最大-最小蟻群系統(tǒng)(MMAS)[12]的基本模型和精英蟻群算法，對信息素更新規(guī)則進(jìn)行了改進(jìn)。

在一個螞蟻完成循環(huán)后，可根據(jù)式(3)、式(4)實(shí)現(xiàn)本地更新路徑。在所有螞蟻完成迭代后，所有路徑上的信息素都會更新，且所有完整路徑都可以找到最佳解決方案和最差解決方案如式(8)所示，通過該式可有效增強(qiáng)當(dāng)前最優(yōu)解對后續(xù)迭代的指導(dǎo)作用。另外，對最差解決方案的懲罰可用于減少最差路徑對后續(xù)迭代的誤導(dǎo)效應(yīng)，從而該算法將收斂速度加速到全局最優(yōu)解

(8)

式中：Lbest是當(dāng)前最佳路徑的長度；Lworst是當(dāng)前完整路徑中最差路徑的長度。為了避免算法停滯，將信息素的范圍設(shè)置為[τmin，τmax]，如式(9)所示

(9)

2.4 改進(jìn)狀態(tài)轉(zhuǎn)換規(guī)則

為了提高搜索效率和算法質(zhì)量，使用偽隨機(jī)狀態(tài)轉(zhuǎn)換規(guī)則。設(shè)螞蟻k在t時刻位于節(jié)點(diǎn)i，則在t+1時刻螞蟻k的位置為

(10)

其中，q0為轉(zhuǎn)換率，范圍為(0,1)，q為隨機(jī)數(shù)，當(dāng)q≤q0時，下一個節(jié)點(diǎn)直接由信息素濃度最大值和啟發(fā)式信息來確定。

q0的值決定了確定性選擇和隨機(jī)選擇模式的比率。如果q0值很大，則路徑移位更可能是確定性模式，從而加速了收斂速度，但這種情況下會降低全局搜索能力。相反，如果q0的值較小，則路徑移位更傾向于輪盤賭模式，這增加了路徑選擇的隨機(jī)性并進(jìn)一步增加了全局搜索能力。因此，q0值的設(shè)置對收斂速度和全局搜索能力有重要影響。本文提出了一種新的自適應(yīng)計(jì)算q0的方法，通過迭代次數(shù)NC和當(dāng)前最佳路徑長度Lbest來確定q0值，如式(11)所示，其中b為(0,1)之間的常數(shù)。

(11)

為了進(jìn)一步防止過早收斂到局部最優(yōu)解并停滯，建立迭代次數(shù)閾值N0。當(dāng)?shù)螖?shù)NC小于N0時，q0值為b；否則自適應(yīng)地計(jì)算q0的值。

2.5 解決死鎖問題

當(dāng)環(huán)境更加復(fù)雜時，螞蟻可能會陷入無路的狀態(tài)，即死鎖。如圖1所示，環(huán)境中的P1位置是一個“陷阱”，當(dāng)螞蟻?zhàn)哌M(jìn)那里時，它無法移動到另一個位置。雖然在P2位置沒有明顯的陷阱，但如果螞蟻按圖片路徑行走最終也會出現(xiàn)死鎖。

圖1 死鎖狀態(tài)

針對僵局問題，在圖1中P1位置需要后退兩步才能擺脫它，計(jì)算復(fù)雜性將成倍增加。在本文中，使用了一種折衷方法，它可以殺死處于死鎖狀態(tài)的螞蟻，并計(jì)算進(jìn)入同一死鎖點(diǎn)的螞蟻數(shù)量nLost(i，j)，不完整路徑的最后兩步將由式(12)懲罰

(12)

式中：λ為懲罰因子，其值為(0,1)之間的常數(shù)。很容易看出，同一條路徑中的螞蟻越多，對路徑的懲罰就越大，后續(xù)螞蟻通過這條路徑的概率就越小，從而大大減少了失去的螞蟻數(shù)量。

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

將改進(jìn)的蟻群算法應(yīng)用于路徑規(guī)劃。具體步驟如下：

步驟1 初始化參數(shù)。其中包括起始位置S，目標(biāo)位置G，螞蟻數(shù)m，最大迭代次數(shù)NCmax，迭代次數(shù)NC，信息素強(qiáng)度Q，信息素啟發(fā)式因子α，期望啟發(fā)式因子β，死鎖懲罰因子λ。其中，初始化目標(biāo)位置S、目標(biāo)位置G由實(shí)驗(yàn)網(wǎng)格環(huán)境決定，螞蟻數(shù)m=50，最大迭代次數(shù)NCmax=100，信息素強(qiáng)度Q=100，α、β、λ作為變量根據(jù)實(shí)驗(yàn)對象分別進(jìn)行設(shè)置。

步驟2 計(jì)算初始信息素。其中常數(shù)a0=0.5，將起點(diǎn)到當(dāng)前節(jié)點(diǎn)的歐幾里德距離dSi、當(dāng)前節(jié)點(diǎn)和下一個節(jié)點(diǎn)之間的歐幾里德距離dij、下一個節(jié)點(diǎn)到終點(diǎn)的歐幾里德距離djE分別代入式(5)中計(jì)算初始信息素。

步驟3 路徑選擇。假設(shè)螞蟻k在t時刻位于節(jié)點(diǎn)i處，則利用式(1)由路徑(i，j)的信息素值τij、信息素激勵因子α計(jì)算出螞蟻選擇下一節(jié)點(diǎn)的概率，然后利用式(10)計(jì)算螞蟻在t+1時刻的路徑選擇。

步驟4 更新信息素和啟發(fā)式信息。當(dāng)螞蟻建立完整路徑時，對信息素和啟發(fā)式信息進(jìn)行更新，其中信息素可將信息揮發(fā)系數(shù)ρ、信息素殘留因子1-ρ、信息素的增量Δτij(t)代入式(3)中進(jìn)行更新，其中信息素的增量Δτij(t)由式(4)計(jì)算得到，啟發(fā)式信息可由式(6)更新。

步驟5 死鎖解決方案。當(dāng)螞蟻創(chuàng)建一條不完整的路徑時，此時需要對所創(chuàng)建的死鎖路徑上的信息素利用懲罰因子λ進(jìn)行懲罰，根據(jù)死鎖發(fā)生的具體路徑位置利用式(12)進(jìn)行懲罰，當(dāng)死鎖被懲罰后轉(zhuǎn)到步驟3并繼續(xù)循環(huán)執(zhí)行直到完成搜索。

步驟6 信息素的全局更新。在所有螞蟻完成搜索之后，需要找到該迭代中所有完整路徑的最佳路徑和最差路徑，并根據(jù)式(3)和式(8)增強(qiáng)最佳路徑上的信息素，削弱最差路徑上的信息素。

步驟7 自適應(yīng)調(diào)整q0。當(dāng)?shù)螖?shù)Nc大于迭代閾值N0時，可由當(dāng)前最佳路徑長度Lbest、最大迭代次數(shù)NCmax、從起點(diǎn)到終點(diǎn)的歐幾里德距離dSE通過式(11)計(jì)算新的狀態(tài)轉(zhuǎn)移率q0以更新狀態(tài)轉(zhuǎn)移規(guī)則。

步驟8 搜索結(jié)束。確定是否滿足結(jié)束條件，如果滿足，則輸出最佳路徑長度，否則清除禁忌清單，讓NC=NC+1，然后轉(zhuǎn)到步驟3并繼續(xù)循環(huán)執(zhí)行，直到滿足結(jié)束條件或達(dá)到最大迭代次數(shù)。如圖2所示為基于改進(jìn)蟻群算法的路徑規(guī)劃的具體過程。

圖2 改進(jìn)蟻群算法的路徑規(guī)劃的具體過程

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

為驗(yàn)證所述改進(jìn)勢場蟻群算法的有效性，在Matlab R2010a中進(jìn)行仿真實(shí)驗(yàn)，計(jì)算機(jī)操作系統(tǒng)為Windows 7，CPU為core i5-650，內(nèi)存為8 GB，仿真環(huán)境分別為10×10、20×20、30×30的平面柵格環(huán)境。同時，為了驗(yàn)證本文算法的優(yōu)越性，在相同環(huán)境中將本文算法所得結(jié)果分別與文獻(xiàn)[13]和文獻(xiàn)[14]中改進(jìn)蟻群算法的結(jié)果進(jìn)行比較。

4.1 模擬環(huán)境的建立

為了便于蟻群算法搜索最優(yōu)路徑，本文采用網(wǎng)格法建立二維移動環(huán)境空間，網(wǎng)格按從上到下，從左到右的順序編號。其中障礙網(wǎng)格稱為不可行網(wǎng)格，無障礙網(wǎng)格稱為可行網(wǎng)格。為了便于算法的實(shí)現(xiàn)，螞蟻在行進(jìn)過程中當(dāng)遇到障礙網(wǎng)格時，算法默認(rèn)將其標(biāo)注為“1”，無障礙網(wǎng)格標(biāo)注為“0”，從而將網(wǎng)格圖轉(zhuǎn)換為0和1分布的二維電子地圖，如圖3所示。

圖3 網(wǎng)格圖和相應(yīng)的電子地圖

通過式(13)確定網(wǎng)格編號與坐標(biāo)之間的數(shù)學(xué)對應(yīng)關(guān)系

(13)

其中，r為網(wǎng)格的比例，由機(jī)器人的幾何尺寸決定；n為網(wǎng)格號；R為網(wǎng)格的行數(shù)；mod函數(shù)為余數(shù)函數(shù)；ceil函數(shù)是向右舍入函數(shù)。

4.2 參數(shù)優(yōu)化選擇

蟻群算法的參數(shù)選擇直接決定了算法的性能，常用的方法有遺傳算法，粒子群算法(PSO)，三步法，經(jīng)驗(yàn)和實(shí)驗(yàn)方法等。但到目前為止，還沒有完美的方法直接確定參數(shù)的最優(yōu)組合。為了降低算法的復(fù)雜度，本文采用經(jīng)驗(yàn)和實(shí)驗(yàn)方法，通過設(shè)置不同的參數(shù)進(jìn)行仿真實(shí)驗(yàn)，分析實(shí)驗(yàn)結(jié)果的優(yōu)缺點(diǎn)，選擇最優(yōu)參數(shù)組合。

測試方法為每個參數(shù)設(shè)置一組值，在每個實(shí)驗(yàn)中，只有一個參數(shù)被更改，其它參數(shù)為常量。分別測試迭代次數(shù)，最佳路徑長度和丟失的螞蟻數(shù)量。本文僅介紹啟發(fā)式因子α，期望啟發(fā)式因子β，揮發(fā)系數(shù)ρ和死鎖懲罰因子λ的最優(yōu)組合。其它參數(shù)可以以相同的方式執(zhí)行。

使用環(huán)境1(如圖3(a))作為組合實(shí)驗(yàn)的測試環(huán)境，參數(shù)設(shè)置如下：

m=50，NCmax=100，Q=100，β=6，ρ=0.2，λ=0.2，N0=5，q0=0.3。當(dāng)α=0.8，α=0.9，…，α=2.0時，分別測試算法的迭代次數(shù)，最佳路徑長度和丟失的螞蟻數(shù)量，實(shí)驗(yàn)結(jié)果如圖4所示。實(shí)驗(yàn)結(jié)果表明，當(dāng)α很小時，改進(jìn)的蟻群算法無法搜索全局最優(yōu)解；當(dāng)α∈[1,1.2]時，它具有更好的收斂速度和搜索全局最優(yōu)解的能力。隨著α的進(jìn)一步增加，算法的收斂速度逐漸增大，但全局搜索能力逐漸減弱，更容易陷入局部最優(yōu)解。總體而言，與基本蟻群算法相比，本文改進(jìn)的蟻群算法大大提高了收斂速度、全局最優(yōu)解搜索能力和丟失螞蟻數(shù)的性能指標(biāo)。

圖4 啟發(fā)式因子與迭代次數(shù)、最佳路徑長度、丟失螞蟻數(shù)的關(guān)系

在同一環(huán)境中，設(shè)置如下參數(shù)：m=50，NCmax=100，Q=100，α=1.1，ρ=0.2，λ=0.2，N0=5，q0=0.3。當(dāng)β=1，β=2，…，β=9時進(jìn)行一系列實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果如圖5所示。實(shí)驗(yàn)結(jié)果表明，無論β如何變化，它都具有更快的收斂速度和更少的螞蟻損失，并且當(dāng)β∈[4,7]時，有最佳的性能指標(biāo)。最小迭代次數(shù)為8.7次，最佳路徑長度為13.898，丟失的螞蟻數(shù)為28.2。

當(dāng)ρ=0.1，ρ=0.2，…，ρ=0.9時，分別測試算法的迭代次數(shù)，最佳路徑長度和丟失的螞蟻數(shù)。實(shí)驗(yàn)結(jié)果如圖6所示。當(dāng)ρ增加時，收斂速度更快，失去的螞蟻更少，但路徑更長。當(dāng)ρ在[0.1,0.2]之間時，算法具有最佳性能指標(biāo)。全局最優(yōu)路徑長度為13.898，迭代次數(shù)為9.6，丟失螞蟻數(shù)為58.4。

當(dāng)λ=0.1，λ=0.2，λ=0.3……，λ=0.9時，進(jìn)行相同的實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果如圖7所示。結(jié)果表明當(dāng)λ∈[0.2，0.5]時，具有最佳性能指標(biāo)，最小迭代次數(shù)為7.9，最佳路徑長度為13.898，丟失螞蟻數(shù)為39.3。總之，改進(jìn)的蟻群算法大大提高了基本蟻群算法的性能指標(biāo)。當(dāng)α∈[1,1.2]，β∈[4,7]，ρ∈[0.1,0.2]，λ∈[0.2，0.5]時，有更好的綜合性能指標(biāo)。

圖5 預(yù)期啟發(fā)式因子與迭代次數(shù)、最佳路徑長度、丟失螞蟻數(shù)的關(guān)系

圖6 信息素?fù)]發(fā)系數(shù)與迭代次數(shù)、最佳路徑長度、丟失螞蟻數(shù)的關(guān)系

圖7 懲罰因子與迭代次數(shù)、最佳路徑長度、丟失螞蟻數(shù)的關(guān)系

4.3 與其它算法進(jìn)行比較

4.3.1 20×20情況(環(huán)境2)

為了驗(yàn)證所提出的算法的有效性與優(yōu)越性，將其與文獻(xiàn)[13]的算法在環(huán)境2(如圖8(a))情況下進(jìn)行對比實(shí)驗(yàn)，實(shí)驗(yàn)參數(shù)設(shè)置為：m=50，NCmax=100，Q=100，α=1.1，ρ=0.2，β=7，λ=0.2，N0=5，q0=0.3。如圖8所示為對比實(shí)驗(yàn)仿真結(jié)果，圖8(a)中的實(shí)線是本文算法的規(guī)劃路徑，虛線是參考文獻(xiàn)[13]中的算法路徑。為避免偶然情況，重復(fù)了10次實(shí)驗(yàn)，表1為平均結(jié)果。從圖8和表1可以看出，文獻(xiàn)[13]中的算法比本文算法具有更快的收斂速度和更少的運(yùn)行時間，但本文算法在最優(yōu)路徑搜索的性能指標(biāo)上具有更大的優(yōu)勢，且丟失的螞蟻數(shù)量更少。本文算法的最優(yōu)路徑長度收斂到30.968，而文獻(xiàn)[13]中算法的平均路徑長度為35.6573，這進(jìn)一步說明了本文的算法更穩(wěn)定。

4.3.2 30×30情況(環(huán)境3)

為了驗(yàn)證復(fù)雜環(huán)境的有效性和優(yōu)越性，將其與文獻(xiàn)[14]的算法在環(huán)境3(如圖9(a))情況下進(jìn)行對比實(shí)驗(yàn)，仿真結(jié)果如圖9所示。圖9(a)中的實(shí)線是本文算法的規(guī)劃路徑，虛線是文獻(xiàn)[14]中算法的規(guī)劃路徑，表2給出了在相同參數(shù)下重復(fù)10次實(shí)驗(yàn)的平均值。

圖8 兩種算法在路徑規(guī)劃中的比較結(jié)果

表1 兩種算法在路徑規(guī)劃中的比較結(jié)果

從實(shí)驗(yàn)結(jié)果上來看，在復(fù)雜的環(huán)境中本文算法仍然可以快速搜索最優(yōu)路徑。文獻(xiàn)[14]中算法的最佳路徑長度為48.425，而本文的最佳路徑長度為44.522，路徑長度縮短3.903；文獻(xiàn)[14]中的平均迭代次數(shù)為59次，本文算法的平均迭代次數(shù)為22.1次，收斂速度提高了近3倍且丟失的螞蟻數(shù)量僅占文獻(xiàn)[14]中算法的三分之一。在運(yùn)行時間上，本文算法較文獻(xiàn)[14]中的算法更長，但考慮到算法的性能指標(biāo)，本文算法可以在運(yùn)行時間上做出一點(diǎn)犧牲，從而獲得更好的路徑長度和更快的收斂速度。

圖9 兩種算法在路徑規(guī)劃中的比較結(jié)果

表2 兩種算法在路徑規(guī)劃中的比較結(jié)果

綜上所述，本文將改進(jìn)的蟻群算法與文獻(xiàn)[13]、文獻(xiàn)[14]的算法進(jìn)行了比較。本文提出的改進(jìn)算法能夠自適應(yīng)地調(diào)整了偽隨機(jī)狀態(tài)轉(zhuǎn)移比例基數(shù)，以改進(jìn)路徑選擇規(guī)則，啟發(fā)式信息函數(shù)和信息素更新規(guī)則，進(jìn)一步提高了收斂速度和全局搜索能力，大大減少了螞蟻丟失的數(shù)量，具有很大的優(yōu)越性和實(shí)用性。

5 結(jié)束語

路徑規(guī)劃是當(dāng)前機(jī)器人在復(fù)雜環(huán)境下行進(jìn)的關(guān)鍵技術(shù)，蟻群算法作為一種仿生算法能夠有效實(shí)現(xiàn)機(jī)器人的路徑規(guī)劃。針對基本蟻群算法在路徑規(guī)劃中存在的收斂速度慢、搜索效率低的問題提出了一種改進(jìn)的蟻群算法。實(shí)驗(yàn)中將改進(jìn)的蟻群算法應(yīng)用于機(jī)器人路徑規(guī)劃，并通過實(shí)驗(yàn)和經(jīng)驗(yàn)方法確定算法參數(shù)的最優(yōu)組合。通過模擬多個移動環(huán)境，并與其它算法進(jìn)行比較，實(shí)驗(yàn)結(jié)果表明改進(jìn)的蟻群算法有效解決了算法初期盲目搜索的問題，提高了收斂速度，驗(yàn)證了該算法的有效性和優(yōu)越性。