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

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

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

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

結(jié)合神經(jīng)網(wǎng)絡(luò)算法的路徑規(guī)劃方法有很好的適應(yīng)性，因此市場(chǎng)應(yīng)用前景良好[16].所以近年來(lái)與之相關(guān)的問(wèn)題也成為研究人員們的關(guān)注熱點(diǎn)[17-20].例如：為解決網(wǎng)絡(luò)流量時(shí)間序列的預(yù)測(cè)問(wèn)題，文獻(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í)間成本急劇增加這一問(wèn)題.

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

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 問(wèn)題描述

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

對(duì)智能駕駛車(chē)輛的行駛環(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í)：智能駕駛車(chē)輛由一個(gè)特定的地方開(kāi)始沿著行駛區(qū)域的邊界或與邊界緊挨著的障礙的邊界按某一特定方向搜索一周，在此過(guò)程中獲知整個(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)路徑選擇

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

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

(1)

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

定理1等價(jià)代價(jià)的增長(zhǎng)并不隨著網(wǎng)絡(luò)規(guī)模或者路網(wǎng)中節(jié)點(diǎn)數(shù)目固定比例規(guī)律增長(zhǎng)，而是隨著網(wǎng)絡(luò)的變大，結(jié)點(diǎn)的增多，增長(zhǎng)速率越來(lái)越大，即網(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ī)劃路徑長(zhǎng)度和躲避障礙形式路徑長(zhǎng)度值越大，等價(jià)代價(jià)越高.因此有

(2)

(3)

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

定義2根據(jù)路徑規(guī)劃過(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ī)劃路徑長(zhǎng)度越長(zhǎng)，對(duì)應(yīng)躲避障礙行駛代價(jià)路徑越長(zhǎng)，反之，躲避障礙行駛代價(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ì)算的躲避障礙行駛距離長(zhǎng)度都為不小于零的數(shù)，因此，初始節(jié)點(diǎn)與終止節(jié)點(diǎn)坐標(biāo)距離越大，每次計(jì)算的代價(jià)路徑長(zhǎng)度累加值就越大，對(duì)應(yīng)躲避障礙行駛代價(jià)路徑越長(zhǎng)，反之亦成立.

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

1.2.1 粒子群算法

基本的PSO算法原理簡(jiǎn)單，假設(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在算法迭代過(guò)程中，慣性權(quán)重更新設(shè)計(jì)采用閾值非線性遞減策略計(jì)算，設(shè)計(jì)將慣性權(quán)重的調(diào)整與迭代次數(shù)關(guān)聯(lián)，并定義

(10)

式中：ωmax,ωmin表示慣性權(quán)重的最大值和最小值；kT表示迭代閾值;遞減因子λ>0.迭代過(guò)程由于遞減因子引入，ωk隨迭代次數(shù)增加而非線性遞減，有利于避免陷入局部極值.算法開(kāi)始慣性權(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)化問(wèn)題的可行解能夠用每個(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)橹悄荞{駛車(chē)輛目前并不能完全實(shí)現(xiàn)理想的駕駛理念，因此在研究和試應(yīng)用中，都將對(duì)象設(shè)置為中高速車(chē)輛，在保證安全的前提下，實(shí)現(xiàn)其他功能.因此根據(jù)實(shí)際情況，在進(jìn)行智能駕駛車(chē)輛的路徑規(guī)劃設(shè)計(jì)時(shí)，更關(guān)注算法對(duì)于突發(fā)交通狀況的處理速度，聯(lián)系適應(yīng)度函數(shù)參數(shù)的意義，相比而言，行駛距離的代價(jià)權(quán)重要次于當(dāng)前節(jié)點(diǎn)(即智能駕駛車(chē)輛本身)的安全性權(quán)重，其與障礙物之間距離越近越危險(xiǎn)，因此設(shè)置系統(tǒng)隨機(jī)分配它們值，且滿足：α<β.

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

通過(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è)反向過(guò)程，此時(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].本文中為智能駕駛車(chē)輛的路徑規(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)沒(méi)有函數(shù)變換，共有3個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)代表一個(gè)方向的數(shù)據(jù)信息，即Front、Left和Right，用來(lái)描述關(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來(lái)進(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ī)則前件的匹配.通過(guò)與第2層節(jié)點(diǎn)之間的連接，進(jìn)行組合匹配，通過(guò)各輸入模糊值的邏輯運(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)見(jiàn)圖2，這樣的模糊神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)設(shè)計(jì)既能夠保證模糊算法功能的實(shí)現(xiàn)，又具有比傳統(tǒng)的模糊神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)簡(jiǎn)潔的優(yōu)勢(shì)，在實(shí)際路徑規(guī)劃中，尤其在大型復(fù)雜網(wǎng)絡(luò)中，能夠?yàn)檎w規(guī)劃算法提供更好的時(shí)間和效率優(yōu)勢(shì).

1.4 HPFA算法步驟

本文算法的執(zhí)行流程規(guī)劃見(jiàn)圖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ù)，若沒(méi)有，則根據(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ì)和分析中，將求解問(wèn)題的關(guān)鍵操作指定為基本操作，通常把算法執(zhí)行基本操作的次數(shù)定義為算法的時(shí)間復(fù)雜度.算法的空間復(fù)雜度定義為所耗費(fèi)的存儲(chǔ)空間，即關(guān)于問(wè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矩陣來(lái)存儲(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ī)劃最長(zhǎng)路徑和最短路徑之間都有很大差距，這是因?yàn)樵?種算法最開(kāi)始都是未經(jīng)訓(xùn)練和學(xué)習(xí)的結(jié)果，隨著算法的運(yùn)行，3種算法的結(jié)果都趨于最優(yōu)解.FNN算法雖然規(guī)劃的最長(zhǎng)路徑較其他兩種算法差，但從平均規(guī)劃路徑長(zhǎng)度可以看出，其多次訓(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ò)中障礙的比例，并以此來(lái)模擬針對(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ī)劃路徑的最長(zhǎng)路徑都增加很多，尤其是FNN算法，這是由于雖然網(wǎng)絡(luò)大小不變，但是由于臨時(shí)障礙的增加，使得系統(tǒng)需要處理的關(guān)系變多，因此相對(duì)復(fù)雜的系統(tǒng)無(wú)效搜索也就變多，而PSO的簡(jiǎn)單系統(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)出快速增長(zhǎng)的趨勢(shì)；隨著節(jié)點(diǎn)持續(xù)增多，PSO算法因其生物特性優(yōu)勢(shì)，使得其增長(zhǎng)趨勢(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í)間的增長(zhǎng)沒(méi)有PSO算法與FNN算法增長(zhǎng)趨勢(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ì)有所增長(zhǎng)，這是由于新增障礙導(dǎo)致安全柵格變少所致；而相比之下，PSO算法的等價(jià)代價(jià)增長(zhǎng)較為明顯，F(xiàn)NN算法次之，HPFA算法的等價(jià)代價(jià)增長(zhǎng)最為緩慢，這是由于FNN算法的自適應(yīng)性使之表現(xiàn)出較好性能，而本文算法則在此基礎(chǔ)上又兼顧了系統(tǒng)的簡(jiǎn)潔使算法更高效，因此能夠以最小的等價(jià)代價(jià)獲取最優(yōu)路徑.

Apollo是很好的智能駕駛研究案例,其基本的路徑規(guī)則算法為A*算法,因此在算法性能分析中,將HPFA算法與A*的改進(jìn)算法(A* Algorithm Optimization, AAO)，以及智能駕駛車(chē)輛路徑規(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ī)劃路徑在長(zhǎng)度和平滑性方面明顯優(yōu)于其他四種算法，根據(jù)定理2可以判斷出算法在規(guī)劃路徑的長(zhǎng)度方面具有優(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)彎較少的情況下避開(kāi)所有障礙規(guī)劃出了一條長(zhǎng)度較短的路徑，即HPFA算法能夠在等價(jià)代價(jià)較小的條件下，規(guī)劃出一條最優(yōu)路徑.而其他幾種算法也能夠成功規(guī)劃出從起點(diǎn)到終點(diǎn)的路徑，但相對(duì)比而言，轉(zhuǎn)彎數(shù)量和長(zhǎng)度不占優(yōu)勢(shì).

為了更好地說(shuō)明問(wèn)題，不同障礙比例環(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)過(guò)多次仿真實(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)越來(lái)越多的情況下，這種優(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)營(yíng)口道的路徑；其中ACO算法、AAO算法與KSPA算法分別用3個(gè)轉(zhuǎn)彎規(guī)劃出相對(duì)較短路徑，GA算法所規(guī)劃路徑相對(duì)略長(zhǎng)，包含兩個(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)粒子群算法，并通過(guò)該算法對(duì)模糊神經(jīng)網(wǎng)絡(luò)的模糊子集參數(shù)按照定義規(guī)則進(jìn)行訓(xùn)練的方法來(lái)解決這一問(wèn)題.

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

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