陳 中，陳克偉，張前圖，劉瑤華

(1.鹽城工學(xué)院 電氣工程學(xué)院，江蘇 鹽城 224051;2.陸軍裝甲兵學(xué)院 兵器與控制系, 北京 100072; 3.中國(guó)人民解放軍駐重慶地區(qū)第五軍代室，重慶 404000)

1 引言

在智能車智能移動(dòng)車輛領(lǐng)域，路徑規(guī)劃是智能車完成自主移動(dòng)的首要條件，可以說(shuō)是智能車的關(guān)鍵技術(shù)之一，一直以來(lái)都是國(guó)內(nèi)外學(xué)者的研究重點(diǎn)[1-2]。智能車的路徑規(guī)劃，簡(jiǎn)而言之就是在整個(gè)運(yùn)行環(huán)境內(nèi)，找到一條從起點(diǎn)至終點(diǎn)的無(wú)障礙行駛路徑，并滿足行駛路徑最短、能耗最少、耗時(shí)最短等要求。關(guān)于路徑規(guī)劃方法，從目前國(guó)內(nèi)外已有的文獻(xiàn)來(lái)看，主要包括傳統(tǒng)方法和智能方法2種。傳統(tǒng)方法主要包括人工勢(shì)場(chǎng)法[3-4]、A*算法[5-6]等，智能方法主要是通過(guò)一些智能算法(如蟻群算法[7]、遺傳算法[8]、粒子群算法[9]等)進(jìn)行路徑規(guī)劃。和傳統(tǒng)方法相比，智能算法的總體運(yùn)算速度更快、計(jì)算效果更高，獲得的移動(dòng)路徑更優(yōu)。

雖然上述提到的智能算法在路徑規(guī)劃中有較好的效果，但由于算法本身存在一定的缺陷，這就導(dǎo)致得到的路徑規(guī)劃結(jié)果可能并沒(méi)有達(dá)到最佳狀態(tài)。因此，國(guó)內(nèi)外很多學(xué)者又對(duì)這些智能算法進(jìn)行改進(jìn)設(shè)計(jì)，以此來(lái)進(jìn)一步提升路徑規(guī)劃的能力。如，Zhou等[10]針對(duì)天牛須搜索算法的不足，提出基于改進(jìn)天牛須搜索的智能車路徑規(guī)劃新方法，相比于改進(jìn)前，規(guī)劃得到的移動(dòng)路徑大幅縮短；Paikray等[11]針對(duì)粒子群算法的不足，提出正余弦粒子群算法的多機(jī)器人路徑規(guī)劃方法，實(shí)驗(yàn)結(jié)果表明正余弦粒子群算法在無(wú)碰撞路徑、到達(dá)時(shí)間和能耗上均比粒子群算法更優(yōu)；Guo等[12]針對(duì)地面無(wú)人車輛多目標(biāo)路徑全局規(guī)劃問(wèn)題，提出改進(jìn)粒子群算法對(duì)該問(wèn)題進(jìn)行求解，實(shí)驗(yàn)結(jié)果驗(yàn)證了改進(jìn)的有效性。

果蠅優(yōu)化算法[13](fruit fly optimization algorithm，F(xiàn)OA)也是一種智能優(yōu)化算法，同樣可以應(yīng)用到智能車的路徑規(guī)劃中。但FOA同前文所述的智能算法相似，算法本身存在易陷入局部最優(yōu)[14-15]、后期搜索精度不高[16-17]等問(wèn)題，如果直接將其用于智能車的路徑規(guī)劃中，算法本身存在的缺陷勢(shì)必會(huì)對(duì)路徑規(guī)劃效果造成影響。因此，有必要對(duì)其缺陷進(jìn)行改進(jìn)設(shè)計(jì)，以達(dá)到提升智能車路徑規(guī)劃效果的目的。

本文以FOA為智能車路徑規(guī)劃方法，同時(shí)針對(duì)FOA存在的缺陷，對(duì)其進(jìn)行改進(jìn)，提出增強(qiáng)型果蠅算法(enhanced fruit fly optimization algorithm，EFOA)，以得到提高智能車路徑規(guī)劃效果的目的。3個(gè)典型函數(shù)的測(cè)試結(jié)果和3種不同行駛環(huán)境的智能車路徑規(guī)劃實(shí)例驗(yàn)證了EFOA算法的有效性。

2 智能車路徑規(guī)劃模型

利用智能算法進(jìn)行路徑規(guī)劃主要包括兩部分。首先，是進(jìn)行環(huán)境建模，在幾何法、單元分解法、可視圖法、柵格法等幾種常用的環(huán)境建模方法中，柵格法的操作最為簡(jiǎn)單，更適用于智能車行駛環(huán)境建模；其次，是在環(huán)境模型的基礎(chǔ)上，利用智能算法反復(fù)迭代以找到一條最優(yōu)的移動(dòng)路徑。

圖1 10×10柵格地圖

圖2 8個(gè)移動(dòng)方向示意圖

在完成環(huán)境建模后，就可以利用智能算法進(jìn)行路徑規(guī)劃。而對(duì)于智能算法而言，需要建立一個(gè)目標(biāo)函數(shù)來(lái)評(píng)價(jià)規(guī)劃路徑的好壞。目標(biāo)函數(shù)可以是滿足路徑最短、能耗最少、行駛時(shí)間最短等單個(gè)目標(biāo)，也可以是多個(gè)目標(biāo)的組合。目標(biāo)函數(shù)可以表示為

minf(p),p∈Γ(ps,pt)

(1)

其中，f(p)為與路徑相關(guān)的目標(biāo)函數(shù)；p表示路徑；ps和pt分別表示路徑的起點(diǎn)和終點(diǎn)；Γ(ps,pt)表示從起點(diǎn)ps至終點(diǎn)pt所有可行路徑的集合。在本文的研究中，將路徑最短設(shè)定為目標(biāo)來(lái)進(jìn)行路徑的規(guī)劃。

3 增強(qiáng)型果蠅算法

3.1 果蠅算法

眾所周知，F(xiàn)OA是模仿自然界中果蠅的覓食行為而提出的一種新型仿生優(yōu)化算法，它主要有如下7個(gè)步驟：

1)設(shè)置相關(guān)參數(shù)，主要包括：果蠅種群的規(guī)模M，種群的最大迭代次數(shù)Gmax、種群的初始位置X_axis和Y_axis、果蠅個(gè)體的搜索視覺(jué)長(zhǎng)度L；2)更新果蠅個(gè)體的位置，如式(2)所示。

(2)

3)計(jì)算果蠅個(gè)體與坐標(biāo)原點(diǎn)之間的距離Disti，而后將距離的倒數(shù)值Si作為發(fā)現(xiàn)食物的味道濃度判定值：

(3)

4)計(jì)算果蠅個(gè)體的食物味道濃度Smelli，即將Si代入適應(yīng)度函數(shù)(在智能車的路徑規(guī)劃中，適應(yīng)度函數(shù)可以為路徑最短、能耗最少等，通常以實(shí)際需要進(jìn)行設(shè)定)得到Smelli。

Smelli=function(Si)

(4)

5)對(duì)于當(dāng)次迭代，通過(guò)式(5)對(duì)種群中Smelli值最大的果蠅個(gè)體的位置信息和食物味道濃度信息進(jìn)行保留；

[bestSmell,bestindex]=max(Smelli)

(5)

6)在將當(dāng)次迭代中bestSmell值記錄到數(shù)組Smellbest中的同時(shí)，所有果蠅個(gè)體均移動(dòng)至bestSmell值最大的果蠅個(gè)體處；

(6)

7)繼續(xù)迭代，重復(fù)執(zhí)行上述步驟2)～步驟6)，并判斷當(dāng)次迭代所得bestSmell是否比前一次迭代更優(yōu)，如是，則將其記錄至Smellbest中；反之，則仍將上次迭代所得bestSmell記錄至Smellbest。當(dāng)?shù)螖?shù)達(dá)到Gmax，則停止迭代，輸出最優(yōu)結(jié)果。

3.2 增強(qiáng)型果蠅算法

從上述FOA的基本步驟中可知，當(dāng)算法的步驟5)執(zhí)行完畢后，當(dāng)次迭代中最優(yōu)果蠅個(gè)體位置信息得到了記錄。以此位置為基礎(chǔ)，在步驟6)中，所有的果蠅個(gè)體都會(huì)移動(dòng)到該位置，即果蠅種群從分散的位置完成了聚集，并隨后以這個(gè)聚集的位置為中心，通過(guò)搜索視覺(jué)長(zhǎng)度L向四周進(jìn)行搜索。但是，如果當(dāng)次迭代中搜索到的位置是局部最優(yōu)位置且L設(shè)置得不合理時(shí)，則果蠅種群在該位置聚集后，就極有可能陷入局部最優(yōu)而無(wú)法跳出，不能在更廣闊的空間進(jìn)行搜索，從而降低算法的尋優(yōu)精度。

因此，本文為克服FOA中存在的上述不足，對(duì)果蠅個(gè)體的位置更新方式進(jìn)行改進(jìn)，即在尋找到當(dāng)次迭代中最優(yōu)果蠅個(gè)體所在的位置后，其余果蠅個(gè)體并不是直接聚集到該位置，而是緩慢的向當(dāng)次迭代中最優(yōu)個(gè)體所在的位置靠近，改進(jìn)后的果蠅個(gè)體位置更新方式如式(7)所示。

(7)

其中，c為一個(gè)0～1之間的隨機(jī)數(shù)。式(7)實(shí)現(xiàn)了式(2)和式(6)的部分融合，通過(guò)這一改進(jìn)，果蠅個(gè)體就不再單純的向當(dāng)次迭代中的最優(yōu)位置聚集，而是緩慢的向其靠近。并且，整個(gè)迭代過(guò)程都不再受L設(shè)置是否合理的影響。同時(shí)，由于c為一個(gè)0～1之間的隨機(jī)數(shù)，且每次迭代所得最優(yōu)位置往往都是不同的，這使得果蠅個(gè)體每次移動(dòng)的步長(zhǎng)和方向是不同的，果蠅個(gè)體搜索的隨機(jī)性和廣泛性就得到了保證，從而避免算法陷入局部最優(yōu)后無(wú)法跳出。

3.3 EFOA測(cè)試

為了驗(yàn)證對(duì)FOA改進(jìn)的有效性，本文利用1個(gè)單峰值Sphere函數(shù)、1個(gè)多峰值Griewank函數(shù)和1個(gè)無(wú)限震蕩Scahffer函數(shù)對(duì)FOA和EFOA的性能進(jìn)行對(duì)比分析，上述3個(gè)函數(shù)的表達(dá)式依次如式(8)、式(9)和式(10)所示。其中，3個(gè)函數(shù)的搜索范圍依次為[-100,100]、[-600,600]和[-100,100]；3個(gè)函數(shù)的維數(shù)依次為30、30和2；3個(gè)函數(shù)的理論極值依次為0、0和-1。

(8)

(9)

(10)

在計(jì)算開(kāi)始前，設(shè)置FOA和EFOA的最大迭代次數(shù)Gmax均為2 000，設(shè)置果蠅種群規(guī)模M均為40。依次采用FOA和EFOA對(duì)3個(gè)函數(shù)進(jìn)行20次理論極值的搜索，得到如表1所示的測(cè)試結(jié)果。其中，最優(yōu)值表示20次中搜索到的最優(yōu)結(jié)果；最差值為20次中搜索到的最差結(jié)果；平均值為20次搜索結(jié)果的平均值；標(biāo)準(zhǔn)差為20次搜索結(jié)果的標(biāo)準(zhǔn)差。圖3給出了2種方法得到的3個(gè)函數(shù)的尋優(yōu)迭代曲線(為便于展示，縱坐標(biāo)取以10為底的對(duì)數(shù))。

表1 測(cè)試結(jié)果

從表1可知，對(duì)于3個(gè)不同類型的測(cè)試函數(shù)而言，EFOA得到4個(gè)指標(biāo)均比FOA好，如EFOA求得的Sphere函數(shù)最差值比FOA求得的最優(yōu)值都還高3個(gè)數(shù)量級(jí)；又如EFOA在20次計(jì)算中部分搜索到了Griewank函數(shù)理論極值0，而FOA一次也沒(méi)有；再如EFOA在20次計(jì)算中都搜索到了Scahffer函數(shù)的理論極值-1，而FOA同樣是一次也沒(méi)有。從圖3可知，對(duì)于3個(gè)測(cè)試函數(shù)而言，F(xiàn)OA在搜索前期就陷入了局部最優(yōu)，換言之就是迭代曲線在開(kāi)始稍有下探后就保持不變了，而EFOA在整個(gè)搜索過(guò)程中迭代曲線卻是在不斷的往下探。表1和圖3的結(jié)果表明，無(wú)論是在搜索精度、搜索速度和搜索穩(wěn)定性方面，EFOA均是要強(qiáng)于FOA。

圖3 3個(gè)函數(shù)的迭代曲線

4 路徑規(guī)劃應(yīng)用

本文在MATLAB環(huán)境中分別構(gòu)建簡(jiǎn)易地圖(20×20柵格地圖)和復(fù)雜地圖(40×40柵格地圖)用于分別模擬智能車在簡(jiǎn)易空間和較復(fù)雜空間的路徑規(guī)劃。同時(shí)，本文還采用自主搭建的智能車系統(tǒng)進(jìn)行路徑規(guī)劃實(shí)驗(yàn)驗(yàn)證。為驗(yàn)證EFOA在智能車路徑規(guī)劃中的效果，本文還將EFOA與FOA、文獻(xiàn)[15]中的LFOA方法、文獻(xiàn)[17]中的RCFOA方法進(jìn)行對(duì)比分析。其中，LFOA和RCFOA是2種與本文EFOA不同的改進(jìn)型FOA算法。在利用上述方法進(jìn)行路徑規(guī)劃時(shí)，最大迭代次數(shù)Gmax和果蠅種群規(guī)模M分別設(shè)置為200和30，LFOA和RCFOA方法所需參數(shù)均按照原文獻(xiàn)進(jìn)行設(shè)置。

4.1 20×20柵格地圖

利用EFOA、FOA、LFOA和RCFOA分別在簡(jiǎn)易20×20柵格地圖中進(jìn)行智能車的移動(dòng)路徑規(guī)劃。分別得到如圖4所示的路徑規(guī)劃結(jié)果圖、如圖5所示的搜索過(guò)程迭代曲線、如表2所示的計(jì)算結(jié)果。由圖4、圖5和表2可知，對(duì)于最短路徑而言，EFOA得到了4種方法中最短路徑27.77，比LFOA、RCFOA和FOA得到的路徑分別縮短了2.01%、6.78%和13.14%；對(duì)于達(dá)到最短路徑所需的最佳迭代次數(shù)而言，EFOA所需的次數(shù)和LFOA一樣，均為11次就搜索到了最短路徑，相比于FOA和RCFOA的13次和16次，分別減少了2次和5次，這說(shuō)明EFOA和LFOA可以更快的搜索到最優(yōu)解；對(duì)于運(yùn)行時(shí)間而言，EFOA的耗時(shí)最短，比LFOA、RCFOA和FOA的耗時(shí)同比縮短了19.79%、18.48%和18.60%。需要說(shuō)明的是，雖然EFOA和LFOA搜索到最優(yōu)解所需的迭代次數(shù)相同，但由于LFOA算法在FOA的基礎(chǔ)上增加了種群劃分和Levy飛行步長(zhǎng)的計(jì)算步驟，導(dǎo)致算法的復(fù)雜度有所增加，因此在耗時(shí)上就出現(xiàn)了差異。

圖4 20×20柵格路徑規(guī)劃結(jié)果地圖

圖5 20×20柵格地圖路徑規(guī)劃迭代曲線

表2 20×20柵格地圖各算法計(jì)算結(jié)果

4.2 40×40柵格地圖

利用EFOA、FOA、LFOA和RCFOA分別在復(fù)雜40×40柵格地圖中進(jìn)行智能車的移動(dòng)路徑規(guī)劃。分別得到如圖6所示的路徑規(guī)劃結(jié)果圖、如圖7所示的搜索過(guò)程迭代曲線、如表3所示的計(jì)算結(jié)果。由圖6、圖7和表3可知，對(duì)于最短路徑而言，EFOA得到了4種方法中最短路徑56.86，比LFOA、RCFOA和FOA得到的路徑分別縮短了4.4%、9.18%和10.23%；對(duì)于達(dá)到最短路徑所需的最佳迭代次數(shù)而言，EFOA所需的次數(shù)為17次，比LFOA的16次多了一次，比FOA和RCFOA分別減少了6次和14次；對(duì)于運(yùn)行時(shí)間而言，EFOA是最少的，比其余3種方法中耗時(shí)最短的RCFOA都還節(jié)省了約10 s。需要說(shuō)明的是，雖然LFOA在迭代次數(shù)上比EFOA少1次，但是由于LFOA算法的復(fù)雜度要比EFOA強(qiáng)，因此在時(shí)間消耗上比EFOA要多。上述分析表明，EFOA在處理較為復(fù)雜環(huán)境的路徑規(guī)劃時(shí)，效果同樣明顯。

圖6 40×40柵格路徑規(guī)劃結(jié)果地圖

圖7 40×40柵格地圖路徑規(guī)劃迭代曲線

表3 40×40柵格地圖各算法計(jì)算結(jié)果

4.3 實(shí)驗(yàn)

在利用模擬仿真進(jìn)行智能車移動(dòng)路徑規(guī)劃的基礎(chǔ)上，本文還利用搭建的智能車系統(tǒng)在真實(shí)的環(huán)境中進(jìn)行移動(dòng)路徑的規(guī)劃，如圖8所示。其中，圖8(a)為智能車起點(diǎn)位置示意圖，圖8(b)為智能車運(yùn)行過(guò)程示意圖，圖中的實(shí)驗(yàn)場(chǎng)景為20×20柵格。

圖8 實(shí)驗(yàn)環(huán)境示意圖

EFOA、FOA、LFOA和RCFOA等4種方法得到的計(jì)算結(jié)果如表4所示。從表4中的數(shù)據(jù)可知，EFOA得到的路徑是4種方法中最短的，且耗時(shí)最少。這一結(jié)果表明本文的EFOA方法在智能車路徑規(guī)劃實(shí)際應(yīng)用中可以以更快的速度找到更優(yōu)的移動(dòng)路徑，可有效提高路徑規(guī)劃的效率。

表4 真實(shí)環(huán)境計(jì)算結(jié)果

5 結(jié)論

為有效提升智能車的路徑規(guī)劃效果，提出了EFOA算法并通過(guò)3個(gè)典型測(cè)試函數(shù)驗(yàn)證了方法的有效性。將EFOA用于智能車不同行駛環(huán)境的路徑規(guī)劃中，效果更優(yōu)。