王 豐,于 浩

(華北理工大學(xué)機(jī)械工程學(xué)院,唐山 063210)

0 引言

路徑規(guī)劃[1]是輔助移動(dòng)機(jī)器人從起點(diǎn)尋找到達(dá)終點(diǎn)最優(yōu)路徑的機(jī)器人核心技術(shù)。優(yōu)秀的路徑規(guī)劃算法是衡量機(jī)器人先進(jìn)性的重要標(biāo)準(zhǔn)。隨著機(jī)器人技術(shù)的不斷進(jìn)步,移動(dòng)機(jī)器人的應(yīng)用逐漸走向家庭化和社會(huì)化。如家用清潔機(jī)器人可以24 h周期性的進(jìn)行清掃任務(wù);酒店中的自動(dòng)送餐機(jī)器人可以自主進(jìn)行配送任務(wù);應(yīng)用于醫(yī)院場(chǎng)景的醫(yī)用配送機(jī)器人,在醫(yī)院中代替醫(yī)護(hù)人員進(jìn)行配送任務(wù),減少了醫(yī)患之間的接觸幾率,在新冠疫情中發(fā)揮了重要作用。因此,國內(nèi)外的研究者對(duì)路徑規(guī)劃技術(shù)進(jìn)行了大量的研究,相繼出現(xiàn)了基于圖優(yōu)化的Dijsktra、A*、D*、Theta*的路徑算法;基于采樣規(guī)劃的PRM、RRT的路徑規(guī)劃算法[2];模仿自然界和生物的遺傳算法[3]、蟻群算法、粒子群算法[4]、神經(jīng)網(wǎng)絡(luò)算法[5]等智能仿生算法。蟻群算法[6]由于在路徑規(guī)劃中具有高的穩(wěn)定性、與其他算法兼容互補(bǔ)性強(qiáng)的特點(diǎn),得到了大量研究者的關(guān)注和改進(jìn)。

目前,蟻群算法的改進(jìn)方式主要包括對(duì)狀態(tài)轉(zhuǎn)移方程改進(jìn)[7]、與其它算法相結(jié)合[8]、改進(jìn)環(huán)境地圖3種方法[9]。馬世軒等[7]對(duì)傳統(tǒng)蟻群算法的信息素更新方式進(jìn)行動(dòng)態(tài)更新,解決了蟻群算法存在的局部最優(yōu)解以及收斂速度的問題。張?zhí)烊鸬萚10]通過將蟻群算法與遺傳算法相結(jié)合,增強(qiáng)了路徑的搜索指向能力,提高了算法的收斂速度。陳青楨等[11]為了解決傳統(tǒng)蟻群算法中因死鎖影響優(yōu)化能力的問題,通過定義柵格地圖中的U型障礙物,提升了蟻群算法的尋優(yōu)能力。蟻群算法的改進(jìn)內(nèi)容包括收斂速度、局部最優(yōu)解、算法優(yōu)化能力、種群多樣性與收斂速度相互矛盾4種問題。現(xiàn)階段對(duì)蟻群算法在路徑規(guī)劃應(yīng)用的研究中,沒有算法能夠同時(shí)兼顧4種問題。針對(duì)這一點(diǎn),本文提出了基于動(dòng)態(tài)更新狀態(tài)轉(zhuǎn)移規(guī)則的蟻群算法(dynamic state transfer ant colony algorithm,DSTACA)進(jìn)行改進(jìn)。

為了解決傳統(tǒng)蟻群算法的4種優(yōu)化問題,本文提出的DSTACA分別對(duì)4類問題提出了解決方法。通過引入改進(jìn)的勢(shì)場(chǎng)啟發(fā)函數(shù),提升了算法的優(yōu)化能力;通過采用偽隨機(jī)狀態(tài)轉(zhuǎn)移規(guī)則,提升了算法的收斂速度;通過設(shè)置獎(jiǎng)懲機(jī)制改進(jìn)局部信息素更新方式,解決了局部最優(yōu)解問題;提出了動(dòng)態(tài)更新信息素?fù)]發(fā)系數(shù),改善了收斂速度與種群多樣性的矛盾,最后,利用剪枝法對(duì)改進(jìn)算法進(jìn)行優(yōu)化,提升路徑的平滑性。

1 相關(guān)算法描述

1.1 蟻群算法描述

機(jī)器人路徑規(guī)劃時(shí),假設(shè)起點(diǎn)的螞蟻種群數(shù)量m,當(dāng)前節(jié)點(diǎn)i,下一步選擇節(jié)點(diǎn)j。螞蟻根據(jù)可選節(jié)點(diǎn)的信息素濃度以及距離啟發(fā)信息來判斷下一節(jié)點(diǎn)j。傳統(tǒng)蟻群算法的狀態(tài)轉(zhuǎn)移為:

(1)

式中:α表示信息素啟發(fā)因子,反映信息素的重要程度;β表示期望啟發(fā)因子,反映啟發(fā)函數(shù)的重要程度;allowedk表示螞蟻下一步可選節(jié)點(diǎn)j的集合,τij為路徑i-j上信息素濃度,ηij表示路徑i-j的啟發(fā)信息。啟發(fā)函數(shù)為:

(2)

當(dāng)螞蟻完成第t代路徑搜索時(shí),會(huì)在走過的路徑上留下信息,增加螞蟻在第t+1代重新選擇該條路徑的概率。隨著迭代過程的進(jìn)行,如果非最優(yōu)路徑上的信息素濃度不斷累積,將導(dǎo)致算法所選路徑非最優(yōu)解,使算法陷入局部最優(yōu)解。信息素濃度更新方式如下所示:

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

(3)

式中:Δτij(t+1)屬于局部信息素更新方式,表示當(dāng)前迭代過程中路徑i-j上的信息素增量:

(4)

式中:Q表示初始信息素強(qiáng)度,Lk表示螞蟻k在此次迭代過程中走過的路徑長度的和。

1.2 人工勢(shì)場(chǎng)法描述

人工勢(shì)場(chǎng)法在地圖區(qū)域內(nèi)模擬勢(shì)力場(chǎng),使機(jī)器人在障礙物的斥力以及目標(biāo)點(diǎn)的引力共同作用下,幫助機(jī)器人避開障礙物到達(dá)目標(biāo)點(diǎn)。如圖1所示,終點(diǎn)對(duì)機(jī)器人產(chǎn)生引力,圖中黑色障礙物對(duì)機(jī)器人產(chǎn)生斥力,在斥力作用下機(jī)器人避開了障礙物,并在引力的引導(dǎo)下到達(dá)終點(diǎn)。

圖1 人工勢(shì)場(chǎng)原理圖

機(jī)器人在地圖中的當(dāng)前位置坐標(biāo)X=(x,y),目標(biāo)點(diǎn)坐標(biāo)Xe=(xe,ye),引力勢(shì)場(chǎng):

(5)

式中:kp表示引力場(chǎng)增益系數(shù),引力勢(shì)場(chǎng)對(duì)機(jī)器人產(chǎn)生的引力方向?yàn)橐?shì)能的負(fù)梯度方向。引力為:

(6)

隨著機(jī)器人靠近目標(biāo)點(diǎn),引力在不斷的減少。斥力場(chǎng)為:

(7)

式中:λ1表示斥力場(chǎng)增益系數(shù),P0表示障礙物對(duì)機(jī)器人的影響范圍,ρ(X,X0)表示機(jī)器人與障礙物之間的歐式距離。當(dāng)機(jī)器人與障礙物之間的距離小于P0時(shí),障礙物對(duì)機(jī)器人產(chǎn)生斥力,否則斥力為0。斥力勢(shì)場(chǎng)與機(jī)器人排斥力關(guān)系為:

(8)

轉(zhuǎn)換后機(jī)器人與障礙物之間的距離關(guān)系為:

(9)

通過式(8),可以看出機(jī)器人距離障礙物越近,產(chǎn)生的排斥力則越大。合力Ft為:

Ft=Fa+Fr

(10)

機(jī)器人在合力的作用下最終到達(dá)Xe。

2 動(dòng)態(tài)更新狀態(tài)轉(zhuǎn)移概率

2.1 人工勢(shì)場(chǎng)法改進(jìn)啟發(fā)函數(shù)

DSTACA利用文獻(xiàn)[12]中人工勢(shì)場(chǎng)法對(duì)啟發(fā)函數(shù)改進(jìn)啟發(fā)函數(shù)的思路,對(duì)傳統(tǒng)蟻群算法中的啟發(fā)函數(shù)進(jìn)行改進(jìn)。改進(jìn)過程為:

(11)

ω=ln(|X-Xe|+1)

(12)

式(11)表示改進(jìn)后的斥力場(chǎng)函數(shù)。其中,ω代表距離影響因子,它與當(dāng)前位置與目標(biāo)點(diǎn)的距離有關(guān)。在式(12)的作用下,斥力會(huì)隨著機(jī)器人當(dāng)前位置與目標(biāo)點(diǎn)之間距離的減少而減少。改善了機(jī)器人在目標(biāo)點(diǎn)附近出現(xiàn)的受力問題。改進(jìn)后的斥力函數(shù)為:

(13)

式中:Fr1表示由障礙物指向機(jī)器人的分力,Fr2表示由機(jī)器人指向目標(biāo)點(diǎn)的分力。其表達(dá)式為:

(14)

(15)

利用改進(jìn)后的人工勢(shì)場(chǎng)對(duì)勢(shì)場(chǎng)啟發(fā)函數(shù)改進(jìn)。過程為:

(16)

(17)

式中:Xs表示起點(diǎn)坐標(biāo)。為了減少算法受勢(shì)場(chǎng)啟發(fā)函數(shù)的影響,陷入局部最優(yōu)解。式(16)引入δ作為衰減系數(shù),減輕勢(shì)場(chǎng)啟發(fā)函數(shù)對(duì)算法種群多樣性的影響。式(16)中ηd表示距離啟發(fā)函數(shù)。為了保證所選的節(jié)點(diǎn)距離目標(biāo)點(diǎn)最近,從而找到最優(yōu)路徑。DSTACA改進(jìn)原有的距離啟發(fā)函數(shù)dij,用所選下一節(jié)點(diǎn)j到目標(biāo)點(diǎn)e的歐式dje代替dij。改進(jìn)后的距離啟發(fā)函數(shù)為:

(18)

利用改進(jìn)后的人工勢(shì)場(chǎng)中Ft在下一節(jié)點(diǎn)j運(yùn)動(dòng)方向V上的分力,來更新勢(shì)場(chǎng)啟發(fā)函數(shù)ηF:

(19)

式中:dij表示當(dāng)前節(jié)點(diǎn)到下一節(jié)點(diǎn)的歐式距離。改進(jìn)后的勢(shì)場(chǎng)啟發(fā)函數(shù)作用原理如圖2所示。

圖2 勢(shì)場(chǎng)啟發(fā)函數(shù)作用原理圖

假設(shè)機(jī)器人接下來可以選擇的目標(biāo)點(diǎn)有1、2,2點(diǎn)的勢(shì)場(chǎng)啟發(fā)函數(shù)大于1點(diǎn),在勢(shì)場(chǎng)啟發(fā)函數(shù)的介入下,選擇2節(jié)點(diǎn)作為下一移動(dòng)點(diǎn)。圖中淺灰色點(diǎn)表示機(jī)器人,深灰色點(diǎn)表示目標(biāo)點(diǎn)。Fa表示目標(biāo)點(diǎn)對(duì)機(jī)器人的引力。Fra與Frb分別表示障礙物a、b對(duì)機(jī)器人的斥力。由于障礙物c與機(jī)器人之間的距離ρ(X,X0)大于P0,因此不產(chǎn)生斥力。Ft表示機(jī)器人所受到的合力,θ表示合力與運(yùn)動(dòng)方向的夾角,Fv表示Ft在運(yùn)動(dòng)方向V上的分力。

2.2 改進(jìn)狀態(tài)轉(zhuǎn)移方程

為了提高算法的搜索效率,保證算法能快速收斂。DSTACA針對(duì)傳統(tǒng)算法前期節(jié)點(diǎn)j選擇過于隨機(jī)的問題進(jìn)行改進(jìn)。基于偽隨機(jī)狀態(tài)轉(zhuǎn)移策略,對(duì)狀態(tài)轉(zhuǎn)移方程進(jìn)行改進(jìn)。改進(jìn)后的狀態(tài)轉(zhuǎn)移方程為:

(20)

(21)

(22)

2.3 動(dòng)態(tài)更新信息素濃度

在傳統(tǒng)的蟻群算法中揮發(fā)系數(shù)ρ是固定不變的,這將對(duì)算法的種群多樣性以及收斂速度產(chǎn)生限制。DSTACA提出了動(dòng)態(tài)信息素濃度更新策略。能夠在解決局部最優(yōu)解的同時(shí),調(diào)節(jié)種群多樣性與收斂速度之間的矛盾。在局部信息素更新策略中,DSTACA提出最優(yōu)—最差信息素更新策略進(jìn)行優(yōu)化對(duì)蟻群設(shè)立獎(jiǎng)懲機(jī)制,將路徑分為最優(yōu)路徑Lbest、最差路徑Lworst、平均路徑Laverage。根據(jù)螞蟻k走過的路徑長度將局部信息素更新分為4個(gè)階段,如式(23)所示。

(23)

設(shè)立獎(jiǎng)懲機(jī)制可以幫助算法排除較差路徑,通過迭代最終找到最優(yōu)解,并克服局部最優(yōu)解。

DSTACA根據(jù)迭代次數(shù),對(duì)全局信息素濃度進(jìn)行動(dòng)態(tài)更新,如式(24)所示。

(24)

式中:Nmax表示最大迭代次數(shù),N為當(dāng)前迭代次數(shù)。為避免因揮發(fā)系數(shù)的變化影響路徑尋優(yōu)能力,限制信息素?fù)]發(fā)系數(shù)ρ的取值范圍[ρmin,ρmax]。初始時(shí)刻ρ0取值為ρmin,提升了算法前期的尋優(yōu)能力。信息素?fù)]發(fā)系數(shù)動(dòng)態(tài)變大,可以提高算法的全局搜索能力,豐富種群多樣性。最后揮發(fā)系數(shù)在逐漸遞減,再次提高算法的收斂速度。算法將全局信息素濃度τij限制在[τmin,τmax],避免算法過早收斂或者停止運(yùn)算。信息素濃度如式(25)所示。

(25)

2.4 剪枝法路徑優(yōu)化

為了進(jìn)一步優(yōu)化DSTACA的路徑,提出了“剪枝”法對(duì)路徑規(guī)劃中多余拐點(diǎn)進(jìn)行切除。剪枝法原理如圖3所示。原始路徑為Begin-a-b-c-d-e-f-End,每次只移動(dòng)一個(gè)步長u。當(dāng)路徑Begin-b之間沒有障礙物時(shí),則使用Begin-b代替Begin-a-b(圖3a灰色實(shí)線所示)。路徑Begin-e(圖3a灰色虛線所示)之間存在障礙物,則無法代替Begin-a-b-c-d-e,優(yōu)化后的路徑為Begin-d-e-f-End(圖3b所示)。

(a) 剪枝算法優(yōu)化過程 (b) 剪枝算法優(yōu)化效果

3 DSTACA算法實(shí)現(xiàn)流程

步驟1:初始化DSTACA算法相關(guān)參數(shù),建立二維靜態(tài)柵格地圖,設(shè)置機(jī)器人的起始點(diǎn)s、終點(diǎn)e;

步驟2:m只螞蟻按照式(22)選擇下一節(jié)點(diǎn)j;

步驟3:對(duì)移動(dòng)到的節(jié)點(diǎn)j按照式(23)進(jìn)行局部信息素濃度更新,更新禁忌表,記錄螞蟻的路徑;

步驟4:判斷螞蟻是否到達(dá)目標(biāo)點(diǎn),若未到達(dá)進(jìn)行步驟2,若到達(dá)執(zhí)步驟5;

步驟5:記錄本次迭代最優(yōu)路徑,按照式(24)進(jìn)行全局信息素濃度更新;

步驟6:判斷是否完成所有迭代,如果未完成所有迭代則執(zhí)行步驟2,否則執(zhí)行步驟7,并存儲(chǔ)本次運(yùn)算產(chǎn)生的最優(yōu)路徑;

步驟7:對(duì)步驟6生成的最優(yōu)路徑利用剪枝法進(jìn)行優(yōu)化,輸出優(yōu)化后的路徑。

DSTACA流程圖如圖4所示。

圖4 DSTACA算法流程圖

4 DSTACA仿真分析對(duì)比

4.1 DSTACA改進(jìn)過程有效性分析

為了驗(yàn)證DSTACA算法改進(jìn)過程的有效性,本文將算法的改進(jìn)分為3部分:改進(jìn)勢(shì)場(chǎng)啟發(fā)函數(shù)(DSTACA-1);基于DSTACA-1改進(jìn)狀態(tài)轉(zhuǎn)移規(guī)則(DSTACA-2);基于DSTACA-2引入動(dòng)態(tài)信息素更新策略(DSTACA)。在MATLAB R2018b中搭建二維柵格地圖進(jìn)行仿真測(cè)試。為了增加地圖復(fù)雜程度,在柵格地圖中設(shè)置U型陷阱,并提高障礙物的離散程度。為了避免偶然性,每組仿真進(jìn)行20次測(cè)試。對(duì)每組實(shí)驗(yàn)的最優(yōu)路徑、平均路徑、最差路徑、平均運(yùn)算時(shí)間、方差進(jìn)行記錄。采用式(26)對(duì)比測(cè)試結(jié)果的性能:

(26)

式中:xt和x0分別為測(cè)試算法和對(duì)比算法的比較項(xiàng)目。

4.1.1 仿真試驗(yàn)1有效性分析

在30×30柵格地圖中,對(duì)DSTACA-1與傳統(tǒng)蟻群算法進(jìn)行對(duì)比,試驗(yàn)1參數(shù)選擇如表1所示,仿真結(jié)果如圖5所示。

表1 試驗(yàn)1參數(shù)選擇

(a) 試驗(yàn)1路徑規(guī)劃圖(b) 試驗(yàn)1收斂曲線

根據(jù)圖5a所示,改進(jìn)后的算法相比較于傳統(tǒng)算法路徑更加平滑,并克服了U型陷阱帶來的影響(圖中灰色標(biāo)記所示)。通過圖5b得到DSTACA-1相比較于傳統(tǒng)蟻群算法,能夠更快的收斂,并且路徑長度大大縮短。表2結(jié)果為試驗(yàn)1多次測(cè)試后的數(shù)據(jù)。通過多次測(cè)試,驗(yàn)證了改進(jìn)后的算法在尋優(yōu)能力、穩(wěn)定性、收斂速度等方面的提升。特別是對(duì)路徑的優(yōu)化能力有著很好的效果。但DSTACA-1的路線還存在局部最優(yōu)(圖中灰色標(biāo)記所示)的問題,并且最終迭代次數(shù)在45次之后才趨于穩(wěn)定。

表2 傳統(tǒng)蟻群算法與DSTACA-1性能對(duì)比

4.1.2 仿真試驗(yàn)2有效性分析

在與試驗(yàn)1相同的參數(shù)下,將DSTACA-1與DSTACA-2進(jìn)行對(duì)比。仿真結(jié)果如圖6所示,性能數(shù)據(jù)如表3所示。

表3 DSTACA-1與DSTACA-2性能對(duì)比

(a) 試驗(yàn)2路徑規(guī)劃圖(b) 試驗(yàn)2收斂曲線

根據(jù)圖6b所示,DSTACA-2能夠在第4代快速收斂,在第6代后趨于穩(wěn)定。相比DSTACA-1收斂速度得到提升,在路徑長度方面,DSTACA-2相比較于DSTACA-1進(jìn)一步縮短。在保持了勢(shì)場(chǎng)蟻群算法的優(yōu)化能力的同時(shí)進(jìn)一步提升了收斂速度。

通過仿真試驗(yàn)2結(jié)果可以直觀的看出,DSTACA-2算法具有更好的穩(wěn)定性,更快的收斂速度,且在路徑尋優(yōu)能力上也略有提升,但是局部最優(yōu)解的問題仍未改善。

4.1.3 仿真試驗(yàn)3有效性分析

將動(dòng)態(tài)信息素更新策略引入DSTACA-2中,最終得到DSTACA。將DSTACA與DSTACA-2進(jìn)行對(duì)比,相同參數(shù)不變,新增參數(shù)數(shù)據(jù)如表4所示。仿真結(jié)果如圖7所示,性能數(shù)據(jù)如表5所示。

表4 試驗(yàn)3參數(shù)選擇

表5 DSTACA-2與DSTACA性能對(duì)比

(a) 試驗(yàn)3路徑規(guī)劃圖 (b) 試驗(yàn)3收斂曲線

由圖7a中灰色標(biāo)記可以得到,DSTACA能夠解決局部最優(yōu)問題,且路徑結(jié)果更加平滑,具有很強(qiáng)的尋優(yōu)能力。通過圖7b所示,DSTACA在收斂速度方面有了很大的提升,并且在算法的中后期可以繼續(xù)找到最優(yōu)路徑,證明了算法的全局探索能力,解決了收斂速度與種群多樣性的矛盾。

表5數(shù)據(jù)證明了改進(jìn)后的算法在運(yùn)算時(shí)間、穩(wěn)定性方面均有提升。通過分析仿真試驗(yàn)3可以得到,DSTACA能夠調(diào)節(jié)收斂速度與種群多樣性的矛盾,且能夠解決局部最優(yōu)解問題。

通過有效性試驗(yàn)證明了改進(jìn)過程的合理性。并且仿真結(jié)果顯示,DSTACA相比較于傳統(tǒng)蟻群算法在收斂速度、優(yōu)化能力方面都得到了提升,并且能夠解決局部最優(yōu)解,調(diào)節(jié)收斂速度以及種群多樣性的矛盾。證明改進(jìn)達(dá)到了預(yù)期的試驗(yàn)?zāi)康摹?/p>

4.1.4 剪枝算法優(yōu)化試驗(yàn)分析

利用剪枝優(yōu)化算法對(duì)DSTACA算法進(jìn)行優(yōu)化,試驗(yàn)結(jié)果如圖8所示。

圖8 剪枝算法優(yōu)化結(jié)果

優(yōu)化算法只在DSTACA路徑結(jié)果上進(jìn)行優(yōu)化,因此對(duì)收斂結(jié)果并無影響。引入拐點(diǎn)數(shù)量體現(xiàn)優(yōu)化后算法的平滑度。經(jīng)過20次試驗(yàn)后,結(jié)果如表6所示。

表6 DSTACA與剪枝法優(yōu)化性能對(duì)比

根據(jù)對(duì)比結(jié)果能夠看出優(yōu)化后的算法路徑更加平滑,路徑長度方面也進(jìn)一步縮短,并且穩(wěn)定性也得到提高。

4.2 DSTACA優(yōu)化能力驗(yàn)證

4.2.1 與傳統(tǒng)蟻群算法對(duì)比試驗(yàn)

通過有效性試驗(yàn),驗(yàn)證了DSTACA算法相比較于傳統(tǒng)蟻群算法,在30×30地圖中結(jié)果的性能提升。為了更好的證明DSTACA的優(yōu)化能力,將DSTACA與其它算法在不同尺寸的柵格地圖中進(jìn)行對(duì)比。在體現(xiàn)DSTACA算法有效性的同時(shí),驗(yàn)證其優(yōu)化能力。

由圖9所示,DSTACA相比較于傳統(tǒng)蟻群算法在路徑長度、收斂速度、尋優(yōu)能力等方面都得到了顯著提升,規(guī)劃出的路徑合理沒有多余拐點(diǎn),能夠?qū)崿F(xiàn)全局路徑的搜索。同樣對(duì)3組地圖進(jìn)行20次試驗(yàn),并將改進(jìn)后的算法與傳統(tǒng)蟻群算法進(jìn)行對(duì)比,通過性能的提升來證明DSTACA的優(yōu)化能力。

(a) 20×20路徑規(guī)劃圖 (b) 30×30路徑規(guī)劃圖

(c) 50×50路徑規(guī)劃圖 (d) 20×20收斂曲線

(e) 30×30收斂曲線 (f) 50×50收斂曲線

在50×50柵格地圖20次試驗(yàn)中,蟻群算法成功規(guī)劃出路徑的次數(shù)為9次,成功率為45%,DSTACA成功率為100%,以傳統(tǒng)蟻群算法9次數(shù)值平均值197作為路徑平均值,對(duì)平均路徑性能進(jìn)行估計(jì)。其余地圖均成功規(guī)劃出路徑,性能提升如表7所示。通過多次試驗(yàn),結(jié)果證明了DSTACA相對(duì)于傳統(tǒng)蟻群算法的優(yōu)化能力。

表7 DSTACA及剪枝法優(yōu)化性能對(duì)比 (%)

4.2.2 DSTACA算法分析

文獻(xiàn)[12]融合人工勢(shì)場(chǎng)法改進(jìn)的蟻群算法,相比較于傳統(tǒng)蟻群算法,文獻(xiàn)[12]算法在收斂速度、路徑長度等方面均有很大提升。因此為了進(jìn)一步驗(yàn)證DSTACA算法的優(yōu)化能力,研究將DSTACA算法與文獻(xiàn)[12]算法進(jìn)行對(duì)比,以此證明DSTACA算法的優(yōu)化能力。具體方法是:采用文獻(xiàn)[12]中20×20、30×30柵格地圖,在相同參數(shù)下,對(duì)比路徑長度、迭代次數(shù)、拐點(diǎn)數(shù)量之間的差異。試驗(yàn)結(jié)果如圖10所示。

(a) 20×20DSTACA路徑規(guī)劃圖 (b) 20×20文獻(xiàn)[12]路徑規(guī)劃圖

(c) 20×20DSTACA收斂曲線 (d) 20×20文獻(xiàn)[12]收斂曲線

(e) 30×30DSTACA路徑規(guī)劃圖 (f) 30×30文獻(xiàn)[12]路徑規(guī)劃圖

(g) 30×30DSTACA收斂曲線 (h) 30×30文獻(xiàn)[12]收斂曲線

由表8可以得到在30×30及20×20地圖中,DSTACA由于柵格地圖本身的限制,最優(yōu)路徑長度與文獻(xiàn)[12]相同,但在拐點(diǎn)數(shù)量和迭代次數(shù)相比較于文獻(xiàn)[12]都有了提升,證明了DSTACA的優(yōu)化能力。經(jīng)過剪枝算法優(yōu)化后的DSTACA路徑突破了柵格地圖的限制,最優(yōu)路徑進(jìn)一步縮短,拐點(diǎn)數(shù)量及迭代次數(shù)也進(jìn)一步得到提升,證明了優(yōu)化后DSTACA算法的優(yōu)化能力。

表8 DSTACA及剪枝法優(yōu)化與文獻(xiàn)[12]算法性能對(duì)比

5 結(jié)論

本文對(duì)傳統(tǒng)蟻群算法在路徑規(guī)劃中存在的4種問題提出改進(jìn)方案。將改進(jìn)過程分為3部分,通過分步驗(yàn)證的方式,證明了改進(jìn)過程的合理性。改進(jìn)后的算法相比傳統(tǒng)算法在路徑長度、運(yùn)算時(shí)間、收斂次數(shù)、拐點(diǎn)數(shù)量上分別提升了62.32%、51.84%、60%、77.2%,能夠高效率、高質(zhì)量的規(guī)劃出全局路徑,證明了DSTACA算法在全局路徑規(guī)劃中的應(yīng)用價(jià)值。