一種基于粒子群優(yōu)化改進(jìn)策略的智能駕駛車輛路徑規(guī)劃方法

劉曉歡，張德干，張 捷，張 婷，朱浩麗

(1.天津理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，天津 300384;2.北京交通大學(xué) 電子信息工程學(xué)院，北京 100044)

自1959年Dantzig等提出車輛路徑規(guī)劃的問題[1]，隨著研究人員們的深入探索，這一難題得到不同程度的解決[2]，包括遺傳算法，蟻群算法，粒子群優(yōu)化等[3].在設(shè)計(jì)智能駕駛車輛路徑規(guī)劃算法時(shí)，人們將研究重點(diǎn)放在復(fù)雜環(huán)境和多移動(dòng)目標(biāo)的系統(tǒng)上[4-5]，包括模糊控制，強(qiáng)化學(xué)習(xí)，智能決策等[6].

粒子群算法[6-7]通過鳥群搜尋食物源和相互傳遞各自的信息使整個(gè)鳥群都能聚集在食物源周圍[8].該算法在路徑規(guī)劃中的應(yīng)用受到很多研究人員的青睞[9].其結(jié)構(gòu)簡單、需要調(diào)節(jié)的參數(shù)少而被普遍應(yīng)用[10-11].但由于其在搜索后期，粒子群種群的多樣性下降容易導(dǎo)致粒子陷入局部極值最優(yōu)解[12-13].針對(duì)這一問題，文獻(xiàn)[14]提出一種變異操作方法，增加種群多樣性，通過路徑點(diǎn)冗余篩選算法使所規(guī)劃路徑更平滑更短.文獻(xiàn)[15]提出了將細(xì)菌覓食算法引入到粒子群搜索過程的具有全局搜索能力和快速收斂的混合算法.

結(jié)合神經(jīng)網(wǎng)絡(luò)算法的路徑規(guī)劃方法有很好的適應(yīng)性，因此市場(chǎng)應(yīng)用前景良好[16].所以近年來與之相關(guān)的問題也成為研究人員們的關(guān)注熱點(diǎn)[17-20].例如：為解決網(wǎng)絡(luò)流量時(shí)間序列的預(yù)測(cè)問題，文獻(xiàn)[21]提出了量子遺傳算法與模糊神經(jīng)網(wǎng)絡(luò)相結(jié)合的網(wǎng)絡(luò)流量時(shí)間序列預(yù)測(cè)模型.量子遺傳算法具有運(yùn)算效率高、全局尋優(yōu)能力強(qiáng)、穩(wěn)定性好等優(yōu)點(diǎn)[22].因此利用量子遺傳算法優(yōu)化模糊神經(jīng)網(wǎng)絡(luò)的權(quán)值可以獲得較好的預(yù)測(cè)精度和效果[23].文獻(xiàn)[24]提出采用小波網(wǎng)絡(luò)和前向神經(jīng)網(wǎng)絡(luò)相結(jié)合的四層神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu).文獻(xiàn)[25]將神經(jīng)網(wǎng)絡(luò)算法與Dijkstra算法結(jié)合，解決神經(jīng)網(wǎng)絡(luò)的神經(jīng)元活動(dòng)值計(jì)算成本和時(shí)間成本急劇增加這一問題.

本文作者設(shè)計(jì)利用新的權(quán)重和學(xué)習(xí)因子更新方式的粒子群優(yōu)化算法對(duì)模糊神經(jīng)網(wǎng)絡(luò)進(jìn)行優(yōu)化，克服局部極值問題，并將之應(yīng)用于智能駕駛車輛的路徑規(guī)劃中，求解最優(yōu)路徑問題.

1 HPFA算法

本文設(shè)計(jì)利用粒子群優(yōu)化算法對(duì)模糊神經(jīng)網(wǎng)絡(luò)權(quán)值參數(shù)進(jìn)行訓(xùn)練，提出一種基于粒子群優(yōu)化策略與模糊神經(jīng)網(wǎng)絡(luò)算法的混合算法(Hybrid PSO and FNN Algorithm, HPFA).

1.1 問題描述

1.1.1 移動(dòng)環(huán)境建模

對(duì)智能駕駛車輛的行駛環(huán)境進(jìn)行移動(dòng)環(huán)境映射，在進(jìn)行環(huán)境地圖建立模型時(shí)，對(duì)于同一個(gè)工作環(huán)境，劃分的網(wǎng)格數(shù)量愈高，網(wǎng)格就會(huì)愈小，地圖的精度就會(huì)愈高[26].為了更形象的模擬，采用柵格方式進(jìn)行環(huán)境映射，設(shè)計(jì)如下步驟：

1)邊界學(xué)習(xí)：智能駕駛車輛由一個(gè)特定的地方開始沿著行駛區(qū)域的邊界或與邊界緊挨著的障礙的邊界按某一特定方向搜索一周，在此過程中獲知整個(gè)行駛環(huán)境的輪廓及障礙物的分布情況，并對(duì)數(shù)據(jù)進(jìn)行記錄.

2)生成映射環(huán)境：在Matlab中將記錄的數(shù)據(jù)進(jìn)行重現(xiàn)，標(biāo)記所有障礙的形狀，大小，位置等參數(shù).

1.1.2 最優(yōu)路徑選擇

在智能駕駛車輛的移動(dòng)過程中，會(huì)自動(dòng)根據(jù)優(yōu)化指標(biāo)來選擇最優(yōu)的路徑[27].HPFA算法依據(jù)綜合代價(jià)參數(shù)確定最優(yōu)路徑，參數(shù)定義如下：

定義1將智能駕駛車輛在行駛中的路徑成本與躲避障礙物路徑成本進(jìn)行等價(jià)換算，并將結(jié)果定義為等價(jià)代價(jià).其計(jì)算方式為

(1)

式中：C為等價(jià)代價(jià)；N為映射環(huán)境中最大維度的邊界值；n為步長；α、β∈[0,1]，表示加權(quán)系數(shù)；L代表規(guī)劃路徑長度；l表示躲避障礙的代價(jià)路徑長度.

定理1等價(jià)代價(jià)的增長并不隨著網(wǎng)絡(luò)規(guī)模或者路網(wǎng)中節(jié)點(diǎn)數(shù)目固定比例規(guī)律增長，而是隨著網(wǎng)絡(luò)的變大，結(jié)點(diǎn)的增多，增長速率越來越大，即網(wǎng)絡(luò)中后期參與計(jì)算節(jié)點(diǎn)的等價(jià)代價(jià)更大.

證明：根據(jù)式(1)的實(shí)際意義，C的增加和網(wǎng)絡(luò)的大小有關(guān).即網(wǎng)絡(luò)規(guī)模越大，節(jié)點(diǎn)越多，關(guān)聯(lián)邊越多，規(guī)劃路徑長度和躲避障礙形式路徑長度值越大，等價(jià)代價(jià)越高.因此有

(2)

(3)

隨著路網(wǎng)中節(jié)點(diǎn)數(shù)目的增多，L和l可以看作是兩個(gè)與指數(shù)增長趨勢(shì)相同的變量，因此C的增長速率也越來越快，但不是固定的比例規(guī)律.

定義2根據(jù)路徑規(guī)劃過程中的位置坐標(biāo)得出

(4)

(5)

式中：(xg,yg)代表目標(biāo)節(jié)點(diǎn)坐標(biāo)；(xs,ys)代表起始節(jié)點(diǎn)坐標(biāo)；(xn,yn)代表當(dāng)前節(jié)點(diǎn)坐標(biāo)；M代表目標(biāo)節(jié)點(diǎn)最大維度坐標(biāo)值；m表示當(dāng)前節(jié)點(diǎn)坐標(biāo)中的最大維度坐標(biāo)值.

定理2規(guī)劃路徑長度越長，對(duì)應(yīng)躲避障礙行駛代價(jià)路徑越長，反之，躲避障礙行駛代價(jià)路徑越短，所規(guī)劃路徑也越短.

證明：規(guī)劃路徑是指從起始節(jié)點(diǎn)到終止節(jié)點(diǎn)之間的歐氏距離，到達(dá)終點(diǎn)時(shí)的最后一個(gè)節(jié)點(diǎn)計(jì)算中，當(dāng)前節(jié)點(diǎn)坐標(biāo)到達(dá)終止節(jié)點(diǎn)坐標(biāo)，則

xn=xg,yn=yg

(6)

即

(7)

此時(shí)l最小，即最后一次計(jì)算的躲避障礙行駛距離最小.而中間每次計(jì)算的躲避障礙行駛距離長度都為不小于零的數(shù)，因此，初始節(jié)點(diǎn)與終止節(jié)點(diǎn)坐標(biāo)距離越大，每次計(jì)算的代價(jià)路徑長度累加值就越大，對(duì)應(yīng)躲避障礙行駛代價(jià)路徑越長，反之亦成立.

1.2 粒子群算法優(yōu)化策略

1.2.1 粒子群算法

基本的PSO算法原理簡單，假設(shè)存在一個(gè)能夠搜索的n維空間，種群由m個(gè)單獨(dú)粒子組成，并記為X=[x1,x2,…，xm]T，其中，第i個(gè)個(gè)體粒子的位置信息為xi=[xi1,xi2,…，xin]T；速度信息為vi=[vi1,vi2,…，vin]T；每個(gè)粒子的個(gè)體極值表示為Pi=[pi1,pi2,…，pin]T；而用pg=[pg1,pg2,…，pgn]T代表整個(gè)種群的全局極值[28].粒子的位置與速度以迭代方式進(jìn)行更新，其更新方式如下

(8)

(9)

式中：k表示迭代次數(shù)；d代表粒子維度；p表示最優(yōu)解；i和g分別代表粒子個(gè)體和粒子群；ω代表慣性權(quán)重；c1和c2為學(xué)習(xí)因子；r1,r2為均勻分布的隨機(jī)數(shù)，且r1,r2∈U[0,1].

1.2.2 慣性權(quán)重更新

在粒子群算法優(yōu)化中，首先對(duì)慣性權(quán)重的更新進(jìn)行優(yōu)化，方便在優(yōu)化算法的訓(xùn)練中使用.慣性權(quán)重是平衡全局和局部搜索能力的關(guān)鍵，較大的ω值可以保證較強(qiáng)的全局搜索能力，同時(shí)局部搜索能力就會(huì)減弱，反之亦然，因此合理的設(shè)置ω值可以提高算法整體性能以減少迭代次數(shù)，提高搜索效率[29].

定義3在算法迭代過程中，慣性權(quán)重更新設(shè)計(jì)采用閾值非線性遞減策略計(jì)算，設(shè)計(jì)將慣性權(quán)重的調(diào)整與迭代次數(shù)關(guān)聯(lián)，并定義

(10)

式中：ωmax,ωmin表示慣性權(quán)重的最大值和最小值；kT表示迭代閾值;遞減因子λ>0.迭代過程由于遞減因子引入，ωk隨迭代次數(shù)增加而非線性遞減，有利于避免陷入局部極值.算法開始慣性權(quán)重值較大，有利于粒子以較大的速度遍布整個(gè)搜索空間從而確定最優(yōu)解的范圍，然后其值逐漸減小以集中尋找最優(yōu)解[30].

1.2.3 學(xué)習(xí)因子更新

設(shè)計(jì)了新的學(xué)習(xí)因子更新方式，c1保持較大值有助于粒子大范圍地搜索，但是收斂速度相對(duì)較慢.c2保持較大的值，有助于粒子學(xué)習(xí)群體的社會(huì)經(jīng)驗(yàn)從而快速收斂，但是搜索規(guī)劃空間的能力相對(duì)較弱[31].

定義4為增強(qiáng)粒子在算法初期的搜索能力和后期的收斂能力，在算法前期保持較大的c1值和較小的c2值，在算法后期保持較小c1值和較大c2值，定義學(xué)習(xí)因子的更新公式為

(11)

1.2.4 適應(yīng)度函數(shù)

關(guān)于適應(yīng)度函數(shù)的確定，優(yōu)化問題的可行解能夠用每個(gè)個(gè)體粒子的位置信息表示，而適應(yīng)度函數(shù)的取值很大程度上影響解的最優(yōu)與否[32].即適應(yīng)度函數(shù)是對(duì)每個(gè)粒子中包含的網(wǎng)絡(luò)參數(shù)好壞的評(píng)價(jià)，因?yàn)檫m應(yīng)度函數(shù)選擇決定了整個(gè)系統(tǒng)的性能.

定義5在粒子群訓(xùn)練中，通常認(rèn)為適應(yīng)度值越低的個(gè)體性能越好，因此基于代價(jià)函數(shù)設(shè)計(jì)如下適應(yīng)度函數(shù)

(12)

ci=αli+βld

(13)

(14)

(15)

式中：ld表示當(dāng)前節(jié)點(diǎn)與障礙物之間的距離;ci表示當(dāng)前節(jié)點(diǎn)的等價(jià)代價(jià).因?yàn)橹悄荞{駛車輛目前并不能完全實(shí)現(xiàn)理想的駕駛理念，因此在研究和試應(yīng)用中，都將對(duì)象設(shè)置為中高速車輛，在保證安全的前提下，實(shí)現(xiàn)其他功能.因此根據(jù)實(shí)際情況，在進(jìn)行智能駕駛車輛的路徑規(guī)劃設(shè)計(jì)時(shí)，更關(guān)注算法對(duì)于突發(fā)交通狀況的處理速度，聯(lián)系適應(yīng)度函數(shù)參數(shù)的意義，相比而言，行駛距離的代價(jià)權(quán)重要次于當(dāng)前節(jié)點(diǎn)(即智能駕駛車輛本身)的安全性權(quán)重，其與障礙物之間距離越近越危險(xiǎn)，因此設(shè)置系統(tǒng)隨機(jī)分配它們值，且滿足：α<β.

1.2.5 訓(xùn)練規(guī)則

通過訓(xùn)練關(guān)系，確定粒子群優(yōu)化算法對(duì)模糊神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)參數(shù)的訓(xùn)練規(guī)則.

定義6在迭代次數(shù)滿足k

(16)

(17)

迭代次數(shù)到達(dá)閾值后，即ωk=ωmax，是一個(gè)反向過程，此時(shí)在程序中設(shè)置不再更新cij、σij以減少冗余計(jì)算.由于這兩個(gè)參數(shù)用于確定模糊神經(jīng)網(wǎng)絡(luò)隸屬函數(shù)的位置和形狀，需要不斷調(diào)整以獲得更精確的結(jié)果，因此設(shè)計(jì)這樣的訓(xùn)練規(guī)則，促使模糊神經(jīng)網(wǎng)絡(luò)逐漸逼近并確定最優(yōu)解的最小范圍及最優(yōu)解.

1.3 模糊神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)設(shè)計(jì)

神經(jīng)網(wǎng)絡(luò)與模糊系統(tǒng)相結(jié)合得到的模糊神經(jīng)網(wǎng)絡(luò)融合了二者的優(yōu)勢(shì)[33].本文中為智能駕駛車輛的路徑規(guī)劃設(shè)計(jì)使用模糊神經(jīng)網(wǎng)絡(luò)算法實(shí)現(xiàn)，而在模糊規(guī)則定義中，使用粒子群優(yōu)化算法對(duì)神經(jīng)網(wǎng)絡(luò)的輸出進(jìn)行訓(xùn)練，以得到更精確的最優(yōu)路徑解.路徑規(guī)劃的控制模型設(shè)計(jì)如圖1所示.

模糊神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)設(shè)計(jì)使用五層結(jié)構(gòu)的模塊化網(wǎng)絡(luò)，其中：

1)輸入層：用于將系統(tǒng)的輸入層傳輸至下一層，節(jié)點(diǎn)沒有函數(shù)變換，共有3個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)代表一個(gè)方向的數(shù)據(jù)信息，即Front、Left和Right，用來描述關(guān)于障礙的數(shù)據(jù)信息，該層將輸入直接傳遞到下一層，其作用是模糊界面，此時(shí)輸入與輸出相等.

2)模糊化層：將輸入進(jìn)行模糊化，節(jié)點(diǎn)函數(shù)為模糊系統(tǒng)中的隸屬函數(shù)，即為隸屬函數(shù)的生成層.該層每個(gè)節(jié)點(diǎn)計(jì)算一個(gè)隸屬度函數(shù).將輸入的3個(gè)模糊量分別分為3種程度的代價(jià)，分別為較小代價(jià)S、中等代價(jià)M和高昂代價(jià)B來進(jìn)行模糊化.因此本層共有9個(gè)節(jié)點(diǎn)，對(duì)第i個(gè)輸入分量的第j個(gè)隸屬函數(shù)節(jié)點(diǎn)有

(18)

(19)

3)規(guī)則層：即規(guī)則前件匹配層.其功能在于實(shí)現(xiàn)規(guī)則前件的匹配.通過與第2層節(jié)點(diǎn)之間的連接，進(jìn)行組合匹配，通過各輸入模糊值的邏輯運(yùn)算，實(shí)現(xiàn)規(guī)則的前件，并在層內(nèi)完成歸一化耦合.節(jié)點(diǎn)數(shù)目為27個(gè)，該層輸入是隸屬度，輸出為每條規(guī)則的歸一化適用度，即為每條規(guī)則的權(quán)重ωk.

(20)

(21)

4)結(jié)論層：該層節(jié)點(diǎn)計(jì)算規(guī)則后件，并與輸入的規(guī)則歸一化使用度加權(quán)求和.節(jié)點(diǎn)數(shù)與第3層相同，本文中的輸出表示總規(guī)劃路徑成本.

(22)

5)反模糊化層：即模糊判決層，也是輸出層.所有第四層的規(guī)則節(jié)點(diǎn)都與該層輸出節(jié)點(diǎn)連接，完成清晰輸出模糊變量的實(shí)現(xiàn).

具體結(jié)構(gòu)見圖2，這樣的模糊神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)設(shè)計(jì)既能夠保證模糊算法功能的實(shí)現(xiàn)，又具有比傳統(tǒng)的模糊神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)簡潔的優(yōu)勢(shì)，在實(shí)際路徑規(guī)劃中，尤其在大型復(fù)雜網(wǎng)絡(luò)中，能夠?yàn)檎w規(guī)劃算法提供更好的時(shí)間和效率優(yōu)勢(shì).

1.4 HPFA算法步驟

本文算法的執(zhí)行流程規(guī)劃見圖3，具體步驟設(shè)計(jì)如下：

1)初始化路網(wǎng)環(huán)境，完成柵格映射，并獲取起始點(diǎn)和終點(diǎn)位置坐標(biāo).

2)初始化粒子群算法，設(shè)置種群規(guī)模，學(xué)習(xí)因子，障礙權(quán)重，當(dāng)前迭代次數(shù)設(shè)置為1，設(shè)置粒子初始位置和速度，規(guī)定個(gè)體繼承屬性，設(shè)置原始最優(yōu)位置為初始位置.

3)計(jì)算適應(yīng)度函數(shù)，利用初始粒子群算法參數(shù)調(diào)整模糊神經(jīng)網(wǎng)絡(luò)參數(shù)，計(jì)算下一時(shí)刻網(wǎng)絡(luò)輸出.

根據(jù)式(4)和式(12)計(jì)算適應(yīng)度函數(shù)的偽代碼如下

function F=fit(i)

f=0;

for i =1:N

f=fi+(αli+βLd);

%α，β are random?data in[0,1],α<β

% euclidean

dli=sqrt((xi-xs)*(xi-xs)′)+sqrt((xg-xi)*(xg-xi)′)

-sqrt((xg-xs)*(xg-xs)′)

dld=sqrt((xd-xi)*(xd-xi)′)

F=1/f;

end

4)確定當(dāng)前代的個(gè)體最優(yōu)位置和種群最優(yōu)粒子位置.

5)更新粒子群位置和速度，重復(fù)步驟2)～4).

更新位置，速度的偽代碼如下：

for t =1:M

for i=1:N

% update location&speed

v(i,:)=?w*v(i,:)+c1*r1*(p(i,:)-x(i,:))

+c2*r2*(pg-x(i,:));

x(i,:)=?x(i,:)+v(i,:);

if fitness(x(i,:))

y(i)=fitness(x(i,:));

p(i,:)=x(i,:);

end

if y(i)

pg=p(i,:);

end

end

% output best solution

Pbest(t)=fitness(pg);

end

6)判斷是否到達(dá)最大進(jìn)化代數(shù)，若沒有，則根據(jù)式(10)更新權(quán)重參數(shù)，依據(jù)式(11)更新學(xué)習(xí)因子；若達(dá)到最大進(jìn)化代數(shù)，則確定算法結(jié)束條件.

7)根據(jù)式(16)、式(17)的規(guī)則，利用權(quán)重參數(shù)ω和迭代參數(shù)k對(duì)模糊網(wǎng)絡(luò)的模糊子集參數(shù)cij和σij進(jìn)行調(diào)整，并利用最優(yōu)粒子提供的網(wǎng)絡(luò)參數(shù)計(jì)算模糊神經(jīng)網(wǎng)絡(luò)輸出.

function Train

if k

% update c&sigma

ck=ck*(xi-xs)/(xg-xi)*wk;

sigmak=(1-1/k)sigmak;

% update?w&c1,c2

wk=wmax-(wmax-wmin)*((k-1)/(kt-1))∧λ

% λ=2

c1k=c1s-(c1s-c1f)*k/m

c2k=c2s-(c2s-c2f)*k/m

% c1s>c1f,c2s

end

else

% stop update

ck=ck;

sigmak=sigmak;

end

end

8)采用濾波法進(jìn)行平滑處理，對(duì)模糊神經(jīng)網(wǎng)絡(luò)算出的路徑進(jìn)行處理，顯示計(jì)算結(jié)果與最優(yōu)路徑.

1.5 算法復(fù)雜度分析

在算法的設(shè)計(jì)和分析中，將求解問題的關(guān)鍵操作指定為基本操作，通常把算法執(zhí)行基本操作的次數(shù)定義為算法的時(shí)間復(fù)雜度.算法的空間復(fù)雜度定義為所耗費(fèi)的存儲(chǔ)空間，即關(guān)于問題規(guī)模的函數(shù)[34].

定理3HPFA算法的時(shí)間復(fù)雜度為O(n2).

證明 本文所設(shè)計(jì)的算法的時(shí)間復(fù)雜度由網(wǎng)絡(luò)中所有節(jié)點(diǎn)的基本運(yùn)算和粒子群優(yōu)化算法對(duì)模糊神經(jīng)網(wǎng)絡(luò)參數(shù)的訓(xùn)練兩方面決定.對(duì)節(jié)點(diǎn)的基本操作可以認(rèn)為是掃描時(shí)對(duì)所有節(jié)點(diǎn)進(jìn)行搜索，由于在實(shí)際交通網(wǎng)絡(luò)中一個(gè)節(jié)點(diǎn)的相關(guān)聯(lián)節(jié)點(diǎn)數(shù)一般不會(huì)達(dá)到n-1，即不能達(dá)到所有節(jié)點(diǎn)均兩兩相連.因此，復(fù)雜度中的關(guān)聯(lián)點(diǎn)數(shù)可視為一個(gè)常量，則在某些情況下算法的時(shí)間復(fù)雜度為O(n2).而粒子群算法對(duì)神經(jīng)網(wǎng)絡(luò)參數(shù)的訓(xùn)練根據(jù)訓(xùn)練關(guān)系，可以理解為每次操作均為基本運(yùn)算，即時(shí)間復(fù)雜度也為O(n2).因此HPFA算法的整體時(shí)間復(fù)雜度為O(n2).

定理4HPFA算法的空間復(fù)雜度為Ω(n2).

證明 由于路網(wǎng)結(jié)構(gòu)以鄰接矩陣的形式映射及存儲(chǔ)在程序中，所采用的n×n矩陣來存儲(chǔ)節(jié)點(diǎn)和邊等數(shù)據(jù)的關(guān)系.因此HPFA算法的空間復(fù)雜度應(yīng)為Ω(n2).

2 實(shí)驗(yàn)結(jié)果與分析

2.1 參數(shù)設(shè)置

針對(duì)模糊神經(jīng)網(wǎng)絡(luò)算法以及粒子群算法與本文所設(shè)計(jì)HPFA算法在算法功能和性能兩個(gè)方面進(jìn)行仿真對(duì)比，基本參數(shù)設(shè)置如下：

環(huán)境設(shè)置大小為30×30,障礙比例為15%.PSO算法參數(shù)中,粒子群規(guī)模為50.學(xué)習(xí)因子c1為1.5,學(xué)習(xí)因子c2為1.5,最大慣性權(quán)重wmax為0.9,最小慣性權(quán)重wmin為0.3,允許最大迭代次數(shù)m為300.FNN算法中,輸入分量i為3,輸入分量j為3,初始μij為1.5,初始σij為1.HPFA算法中,迭代閾值KT為20,遞減指數(shù)λ為2.

在Matlab平臺(tái)進(jìn)行仿真實(shí)驗(yàn)，首先對(duì)本文算法在路徑規(guī)劃功能方面的效果進(jìn)行仿真；然后對(duì)影響算法的參數(shù)進(jìn)行調(diào)整，在不同環(huán)境下測(cè)試算法的性能.仿真測(cè)試主要分析參數(shù)包括：1)算法收斂速度；2)等價(jià)代價(jià)；3)求得最優(yōu)解概率P；4)算法運(yùn)行時(shí)間.

2.2 仿真實(shí)驗(yàn)分析

圖4為環(huán)境模型和初始環(huán)境設(shè)置，其中橫縱坐標(biāo)表示方向，設(shè)置的起始點(diǎn)和終止點(diǎn)坐標(biāo)分別為(1.5, 0.5)和(29.5, 27.5)，黑色標(biāo)記柵格為障礙，其他為安全柵格，可作為路徑規(guī)劃的下一備選節(jié)點(diǎn).

圖5為初始參數(shù)設(shè)置下的路徑規(guī)劃對(duì)比.由圖5可以看出，3種算法都可以成功規(guī)劃出從起始點(diǎn)到終止點(diǎn)的路徑，但相對(duì)而言本文算法所規(guī)劃路徑較其他兩種方法更平滑一些，路徑較短.

根據(jù)實(shí)驗(yàn)結(jié)果，3種算法在多次實(shí)驗(yàn)中規(guī)劃路徑與求得最優(yōu)解概率如表1所示.

表1 基本參數(shù)實(shí)驗(yàn)結(jié)果

從表1可以看出，3種算法所規(guī)劃最長路徑和最短路徑之間都有很大差距，這是因?yàn)樵?種算法最開始都是未經(jīng)訓(xùn)練和學(xué)習(xí)的結(jié)果，隨著算法的運(yùn)行，3種算法的結(jié)果都趨于最優(yōu)解.FNN算法雖然規(guī)劃的最長路徑較其他兩種算法差，但從平均規(guī)劃路徑長度可以看出，其多次訓(xùn)練之后的結(jié)果仍然較PSO算法更靠近最優(yōu)解，這也是由于兩種算法本身性質(zhì)導(dǎo)致的：FNN算法系統(tǒng)較為復(fù)雜，初始運(yùn)行時(shí)其計(jì)算結(jié)果范圍大，但不能更好的向最優(yōu)解逼近；而PSO算法在后期由于粒子多樣性下降導(dǎo)致運(yùn)行結(jié)果質(zhì)量變差.本文算法在二者基礎(chǔ)上進(jìn)行的改進(jìn)使得其在該實(shí)驗(yàn)中表現(xiàn)出了很好的優(yōu)勢(shì)，既能快速逼近最優(yōu)解，又能保證很好的求解成功概率.

各算法收斂情況仿真結(jié)果分別如圖6所示，可以看出，PSO算法在初始時(shí)收斂較快，之后略有減慢，在約100次迭代時(shí)達(dá)到收斂效果，此時(shí)適應(yīng)度函數(shù)收斂在一個(gè)相對(duì)較高的值上；FNN算法則不然，其收斂速度由慢加快，在約120次左右迭代后實(shí)現(xiàn)收斂，但是適應(yīng)度函數(shù)收斂在一個(gè)較PSO算法略優(yōu)的值上；而本文算法HPFA則以較快速收斂性能，在80次左右迭代后達(dá)到收斂在三者中最低適應(yīng)度函數(shù)的效果，且收斂曲線相對(duì)平滑，而PSO算法與FNN算法的收斂曲線在到達(dá)收斂值之前，均有不同程度抖動(dòng)，這可能是由于粒子可選性與模糊神經(jīng)網(wǎng)絡(luò)的模糊子集參數(shù)變化導(dǎo)致的.

更改網(wǎng)絡(luò)中障礙的比例，并以此來模擬針對(duì)突發(fā)交通狀況所造成的路徑規(guī)劃障礙對(duì)路徑規(guī)劃算法的影響，當(dāng)環(huán)境參數(shù)中障礙比例變?yōu)?0%時(shí)，仿真實(shí)驗(yàn)結(jié)果分別如圖7和表2所示，其中，路徑規(guī)劃仿真結(jié)果可以看出，隨著障礙的增加，為了躲避突然發(fā)障礙，3種算法規(guī)劃路徑都稍有變化，平滑性受到了影響，但由于仿真環(huán)境限制，這種效果并不明顯.

表2中的數(shù)據(jù)也表明，在網(wǎng)絡(luò)規(guī)模不變時(shí)增加障礙后，3種算法所規(guī)劃路徑的最長路徑都增加很多，尤其是FNN算法，這是由于雖然網(wǎng)絡(luò)大小不變，但是由于臨時(shí)障礙的增加，使得系統(tǒng)需要處理的關(guān)系變多，因此相對(duì)復(fù)雜的系統(tǒng)無效搜索也就變多，而PSO的簡單系統(tǒng)則表現(xiàn)出較好的優(yōu)勢(shì)，因此采用PSO算法對(duì)模糊網(wǎng)絡(luò)的模糊子集進(jìn)行訓(xùn)練所得到的算法更能適應(yīng)突然增加的交通障礙和更加復(fù)雜的網(wǎng)絡(luò)，這也從另一個(gè)方面證明了設(shè)計(jì)本算法的意義.

圖8為3種算法的運(yùn)行時(shí)間仿真結(jié)果記錄.可以看出，3種算法運(yùn)行時(shí)間隨網(wǎng)絡(luò)規(guī)格增大的趨勢(shì)大概一致，這是因?yàn)樵诰W(wǎng)絡(luò)較小時(shí)，因?yàn)楣?jié)點(diǎn)數(shù)量較少，運(yùn)算量小，而隨著網(wǎng)絡(luò)增大，可供路徑選擇的節(jié)點(diǎn)數(shù)變多，且需要處理的邊和節(jié)點(diǎn)權(quán)值以及關(guān)系變得復(fù)雜，所以算法運(yùn)行時(shí)間都呈現(xiàn)出快速增長的趨勢(shì)；隨著節(jié)點(diǎn)持續(xù)增多，PSO算法因其生物特性優(yōu)勢(shì)，使得其增長趨勢(shì)相對(duì)變緩，而FNN算法則因?yàn)榻Y(jié)構(gòu)復(fù)雜導(dǎo)致其運(yùn)行時(shí)間明顯大于其他兩種算法.本文算法HPFA則由于采用了PSO算法對(duì)FNN中模糊子集參數(shù)的調(diào)整，使得其在網(wǎng)絡(luò)中節(jié)點(diǎn)少時(shí)運(yùn)行時(shí)間最少，而隨著網(wǎng)絡(luò)節(jié)點(diǎn)增多，其表現(xiàn)出了較好的適應(yīng)性，算法運(yùn)行時(shí)間的增長沒有PSO算法與FNN算法增長趨勢(shì)明顯，本算法在實(shí)際應(yīng)用中對(duì)緩存和系統(tǒng)硬件的要求,證明在同樣網(wǎng)絡(luò)計(jì)算容量的需求下低于其他兩種算法.

記錄網(wǎng)絡(luò)規(guī)格為30×30時(shí)不同障礙比例下的等價(jià)代價(jià)，對(duì)比如圖9所示.由圖9所示結(jié)果可以看出，隨著網(wǎng)絡(luò)中障礙比例由15%分別增加到20%和25%后，3種算法的等價(jià)代價(jià)都會(huì)有所增長，這是由于新增障礙導(dǎo)致安全柵格變少所致；而相比之下，PSO算法的等價(jià)代價(jià)增長較為明顯，F(xiàn)NN算法次之，HPFA算法的等價(jià)代價(jià)增長最為緩慢，這是由于FNN算法的自適應(yīng)性使之表現(xiàn)出較好性能，而本文算法則在此基礎(chǔ)上又兼顧了系統(tǒng)的簡潔使算法更高效，因此能夠以最小的等價(jià)代價(jià)獲取最優(yōu)路徑.

Apollo是很好的智能駕駛研究案例,其基本的路徑規(guī)則算法為A*算法,因此在算法性能分析中,將HPFA算法與A*的改進(jìn)算法(A* Algorithm Optimization, AAO)，以及智能駕駛車輛路徑規(guī)劃中比較常用的其他算法進(jìn)行對(duì)比，其中包括：蟻群算法(Ant Colony Optimization, ACO)，遺傳算法(Genetic Algorithm, GA)，K則最短路徑算法(Kth Shortest Path Algorithm, KSPA)[35].在30×30柵格網(wǎng)絡(luò)環(huán)境，障礙比例為15%時(shí)，幾種算法規(guī)劃路徑結(jié)果對(duì)比如圖10所示.

由圖10所示仿真實(shí)驗(yàn)結(jié)果可以看出，在整體規(guī)劃路徑方面，HPFA算法所規(guī)劃路徑在長度和平滑性方面明顯優(yōu)于其他四種算法，根據(jù)定理2可以判斷出算法在規(guī)劃路徑的長度方面具有優(yōu)勢(shì)，其躲避障礙行駛距離的等價(jià)代價(jià)也最小.

當(dāng)障礙比例增加至20%以模仿交通網(wǎng)絡(luò)中的突發(fā)事故等臨時(shí)因素導(dǎo)致的障礙時(shí)，幾種算法所規(guī)劃路徑如圖11所示.從圖11所示的仿真實(shí)驗(yàn)結(jié)果中可以看出,當(dāng)障礙增加時(shí)，HPFA算法所規(guī)劃路徑在相對(duì)平滑，轉(zhuǎn)彎較少的情況下避開所有障礙規(guī)劃出了一條長度較短的路徑，即HPFA算法能夠在等價(jià)代價(jià)較小的條件下，規(guī)劃出一條最優(yōu)路徑.而其他幾種算法也能夠成功規(guī)劃出從起點(diǎn)到終點(diǎn)的路徑，但相對(duì)比而言，轉(zhuǎn)彎數(shù)量和長度不占優(yōu)勢(shì).

為了更好地說明問題，不同障礙比例環(huán)境下幾種算法規(guī)劃路徑中的等價(jià)代價(jià)統(tǒng)計(jì)如圖12所示.可以看出，HPFA算法在等價(jià)代價(jià)方面都表現(xiàn)出了比較好的優(yōu)勢(shì)，而隨著障礙比例的增加，HPFA算法的等價(jià)代價(jià)增加也是最少的，這也為本算法在實(shí)際應(yīng)用中的可行性提供了保證.

圖13為經(jīng)過多次仿真實(shí)驗(yàn)的幾種算法的運(yùn)行時(shí)間對(duì)比結(jié)果.從圖中所示結(jié)果可以看出,HPFA算法在多次仿真實(shí)驗(yàn)中運(yùn)行時(shí)間方面顯示出明顯優(yōu)勢(shì)，尤其是在網(wǎng)絡(luò)節(jié)點(diǎn)越來越多的情況下，這種優(yōu)勢(shì)體現(xiàn)得更加明顯，這也為本文算法在實(shí)際應(yīng)用中的可行性提供了保證.

2.3 實(shí)驗(yàn)測(cè)試分析

隨機(jī)截取的在3000 m×3000 m的天津市實(shí)際地圖上進(jìn)行了ACO算法、GA算法、AAO算法、KSPA算法與HPFA算法的規(guī)劃路徑測(cè)試對(duì)比，其詳情如圖14～圖16所示.

由圖16所示結(jié)果可以看出，幾種算法都能成功規(guī)劃出由起始點(diǎn)人民醫(yī)院至終點(diǎn)營口道的路徑；其中ACO算法、AAO算法與KSPA算法分別用3個(gè)轉(zhuǎn)彎規(guī)劃出相對(duì)較短路徑，GA算法所規(guī)劃路徑相對(duì)略長，包含兩個(gè)轉(zhuǎn)彎，而本文HPFA算法所規(guī)劃路徑則規(guī)劃出了一條含有一個(gè)轉(zhuǎn)彎的最優(yōu)路徑實(shí)現(xiàn)路徑規(guī)劃.

圖17和圖18為該實(shí)驗(yàn)中5種算法的等價(jià)代價(jià)和平均運(yùn)行時(shí)間對(duì)比結(jié)果.從圖17和圖18所示結(jié)果可以看出，不論是在路徑規(guī)劃中的等價(jià)代價(jià)，還是算法平均運(yùn)行時(shí)間方面，HPFA算法都比幾種常用的路徑規(guī)劃算法優(yōu)秀，該實(shí)驗(yàn)也在一定程度上為本文算法的實(shí)際應(yīng)用提供了證明.

3 結(jié)論

1)針對(duì)粒子群算法在路徑規(guī)劃應(yīng)用中容易陷入局部極值的缺點(diǎn)，設(shè)計(jì)了優(yōu)化慣性權(quán)重和學(xué)習(xí)因子更新方式的改進(jìn)粒子群算法，并通過該算法對(duì)模糊神經(jīng)網(wǎng)絡(luò)的模糊子集參數(shù)按照定義規(guī)則進(jìn)行訓(xùn)練的方法來解決這一問題.

2)設(shè)計(jì)了合理的適應(yīng)度函數(shù)來證明該算法的收斂速度更快，通過仿真分析和實(shí)驗(yàn)測(cè)試證明了本算法在規(guī)劃路徑長度和算法本身效率方面的優(yōu)勢(shì).

3)由于本文算法注重算法效率和收斂狀況，即尋找最優(yōu)解的效率，其算法復(fù)雜度相比而言不占優(yōu)勢(shì)，尋找一種能夠克服算法復(fù)雜度的影響，又能快速響應(yīng)的結(jié)構(gòu)和算法完成智能駕駛車輛的路徑規(guī)劃，是我們下一步的研究方向.