基于增強型果蠅算法的智能車移動路徑規(guī)劃

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

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

1 引言

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

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

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

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

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

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

圖1 10×10柵格地圖

圖2 8個移動方向示意圖

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

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

(1)

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

3 增強型果蠅算法

3.1 果蠅算法

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

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

(2)

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

(3)

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

Smelli=function(Si)

(4)

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

[bestSmell,bestindex]=max(Smelli)

(5)

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

(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 增強型果蠅算法

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

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

(7)

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

3.3 EFOA測試

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

(8)

(9)

(10)

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

表1 測試結(jié)果

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

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

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

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

4.1 20×20柵格地圖

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

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

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

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

4.2 40×40柵格地圖

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

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

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

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

4.3 實驗

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

圖8 實驗環(huán)境示意圖

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

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

5 結(jié)論

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