陳 志，韓興國(guó)

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

0 引 言

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

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

鑒于此，提出了一種改進(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ī)選擇的比例。對(duì)于死鎖問題，根據(jù)路徑上丟失的螞蟻數(shù)量，對(duì)不完整路徑的最后兩步進(jìn)行處罰，以減少丟失螞蟻的數(shù)量，確保算法的多樣性。仿真實(shí)驗(yàn)在不同的移動(dòng)環(huán)境中進(jìn)行，實(shí)驗(yàn)結(jié)果表明，改進(jìn)的蟻群算法在性能指標(biāo)上有顯著提高。

1 基本蟻群算法

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

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

(1)

式中：C為螞蟻允許在下一步選擇的節(jié)點(diǎn)集；τij為路徑(i，j)的信息素值；α為信息素激勵(lì)因子，它反映了信息素濃度對(duì)路徑選擇的重要性，α越大則信息素對(duì)于路徑選擇越重要，螞蟻將更傾向于選擇大多數(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之間的歐幾里德距離。每個(gè)螞蟻在使用路徑上的信息素的同時(shí)也會(huì)不斷分泌信息素，因此路徑上的信息素將不斷積累。為了防止過多的信息素導(dǎo)致啟發(fā)信息泛濫，在每個(gè)螞蟻采取一步或完成一個(gè)周期之后更新路徑上的信息素，并且從t+1時(shí)刻獲得路徑上的信息素，如式(3)所示

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

(3)

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

(4)

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

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

2.1 改善初始信息素

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

(5)

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

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

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

(6)

其中

(7)

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

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

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

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

(8)

式中：Lbest是當(dāng)前最佳路徑的長(zhǎng)度；Lworst是當(dāng)前完整路徑中最差路徑的長(zhǎ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時(shí)刻位于節(jié)點(diǎn)i，則在t+1時(shí)刻螞蟻k的位置為

(10)

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

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

(11)

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

2.5 解決死鎖問題

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

圖1 死鎖狀態(tài)

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

(12)

式中：λ為懲罰因子，其值為(0,1)之間的常數(shù)。很容易看出，同一條路徑中的螞蟻越多，對(duì)路徑的懲罰就越大，后續(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)對(duì)象分別進(jìn)行設(shè)置。

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

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

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

步驟5 死鎖解決方案。當(dāng)螞蟻創(chuàng)建一條不完整的路徑時(shí)，此時(shí)需要對(duì)所創(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時(shí)，可由當(dāng)前最佳路徑長(zhǎng)度Lbest、最大迭代次數(shù)NCmax、從起點(diǎn)到終點(diǎn)的歐幾里德距離dSE通過式(11)計(jì)算新的狀態(tài)轉(zhuǎn)移率q0以更新狀態(tài)轉(zhuǎn)移規(guī)則。

步驟8 搜索結(jié)束。確定是否滿足結(jié)束條件，如果滿足，則輸出最佳路徑長(zhǎng)度，否則清除禁忌清單，讓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)勢(shì)場(chǎng)蟻群算法的有效性，在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)境。同時(shí)，為了驗(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)格法建立二維移動(dòng)環(huán)境空間，網(wǎng)格按從上到下，從左到右的順序編號(hào)。其中障礙網(wǎng)格稱為不可行網(wǎng)格，無障礙網(wǎng)格稱為可行網(wǎng)格。為了便于算法的實(shí)現(xiàn)，螞蟻在行進(jìn)過程中當(dāng)遇到障礙網(wǎng)格時(shí)，算法默認(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)格編號(hào)與坐標(biāo)之間的數(shù)學(xué)對(duì)應(yīng)關(guān)系

(13)

其中，r為網(wǎng)格的比例，由機(jī)器人的幾何尺寸決定；n為網(wǎng)格號(hào)；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ù)組合。

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

使用環(huán)境1(如圖3(a))作為組合實(shí)驗(yàn)的測(cè)試環(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í)，分別測(cè)試算法的迭代次數(shù)，最佳路徑長(zhǎng)度和丟失的螞蟻數(shù)量，實(shí)驗(yàn)結(jié)果如圖4所示。實(shí)驗(yàn)結(jié)果表明，當(dāng)α很小時(shí)，改進(jìn)的蟻群算法無法搜索全局最優(yōu)解；當(dāng)α∈[1,1.2]時(shí)，它具有更好的收斂速度和搜索全局最優(yōu)解的能力。隨著α的進(jìn)一步增加，算法的收斂速度逐漸增大，但全局搜索能力逐漸減弱，更容易陷入局部最優(yōu)解。總體而言，與基本蟻群算法相比，本文改進(jìn)的蟻群算法大大提高了收斂速度、全局最優(yōu)解搜索能力和丟失螞蟻數(shù)的性能指標(biāo)。

圖4 啟發(fā)式因子與迭代次數(shù)、最佳路徑長(zhǎng)度、丟失螞蟻數(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時(shí)進(jìn)行一系列實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果如圖5所示。實(shí)驗(yàn)結(jié)果表明，無論β如何變化，它都具有更快的收斂速度和更少的螞蟻損失，并且當(dāng)β∈[4,7]時(shí)，有最佳的性能指標(biāo)。最小迭代次數(shù)為8.7次，最佳路徑長(zhǎng)度為13.898，丟失的螞蟻數(shù)為28.2。

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

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

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

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

圖7 懲罰因子與迭代次數(shù)、最佳路徑長(zhǎng)度、丟失螞蟻數(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)行對(duì)比實(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所示為對(duì)比實(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)行時(shí)間，但本文算法在最優(yōu)路徑搜索的性能指標(biāo)上具有更大的優(yōu)勢(shì)，且丟失的螞蟻數(shù)量更少。本文算法的最優(yōu)路徑長(zhǎng)度收斂到30.968，而文獻(xiàn)[13]中算法的平均路徑長(zhǎng)度為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)行對(duì)比實(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]中算法的最佳路徑長(zhǎng)度為48.425，而本文的最佳路徑長(zhǎng)度為44.522，路徑長(zhǎng)度縮短3.903；文獻(xiàn)[14]中的平均迭代次數(shù)為59次，本文算法的平均迭代次數(shù)為22.1次，收斂速度提高了近3倍且丟失的螞蟻數(shù)量?jī)H占文獻(xiàn)[14]中算法的三分之一。在運(yùn)行時(shí)間上，本文算法較文獻(xiàn)[14]中的算法更長(zhǎng)，但考慮到算法的性能指標(biāo)，本文算法可以在運(yùn)行時(shí)間上做出一點(diǎn)犧牲，從而獲得更好的路徑長(zhǎng)度和更快的收斂速度。

圖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ī)劃。針對(duì)基本蟻群算法在路徑規(guī)劃中存在的收斂速度慢、搜索效率低的問題提出了一種改進(jìn)的蟻群算法。實(shí)驗(yàn)中將改進(jìn)的蟻群算法應(yīng)用于機(jī)器人路徑規(guī)劃，并通過實(shí)驗(yàn)和經(jīng)驗(yàn)方法確定算法參數(shù)的最優(yōu)組合。通過模擬多個(gè)移動(dòng)環(huán)境，并與其它算法進(jìn)行比較，實(shí)驗(yàn)結(jié)果表明改進(jìn)的蟻群算法有效解決了算法初期盲目搜索的問題，提高了收斂速度，驗(yàn)證了該算法的有效性和優(yōu)越性。