淺談關(guān)于PSO算法路徑規(guī)劃的研究

0 引言

路徑規(guī)劃是車載導(dǎo)航系統(tǒng)的基本功能，由于其有較強(qiáng)的應(yīng)用價(jià)值，國(guó)內(nèi)外學(xué)者對(duì)此進(jìn)行了深入的研究[1-3]?，F(xiàn)今較流行的算法有Dijstra算法（簡(jiǎn)稱D算法）和A*算法，但D算法搜索速度較慢，A*算法搜索速度快但成功率不高，且這些算法只能在靜態(tài)地圖上進(jìn)行路徑規(guī)劃，沒有考慮實(shí)時(shí)變化的交通狀況。

近年來，智能算法因其強(qiáng)大的搜索能力而被廣泛應(yīng)用于路徑規(guī)劃中。楊易[4]把遺傳算法與A*算法相結(jié)合，提高路徑規(guī)劃算法的效率；王健[5]把蟻群算法應(yīng)用到導(dǎo)航的路徑規(guī)劃中，但其沒有考慮隨時(shí)間的動(dòng)態(tài)變化因素；于海璁等人[6]提出了一種適用于多模式路徑規(guī)劃的遺傳算法，可用于個(gè)性化的路徑導(dǎo)航。本文將PSO算法應(yīng)用到車載導(dǎo)航的路徑規(guī)劃中，引入變異算子解決PSO算法的局部最優(yōu)問題，不僅擁有較快的收斂速度，還能增強(qiáng)全局搜索能力。

1 粒子群算法的描述

粒子群算法由Eberhart博士和Kennedy博士在1995年提出[7]，它通過粒子間的協(xié)作和信息共享來尋找最優(yōu)解。算法在搜索時(shí)，根據(jù)粒子自身歷史的最佳位置pbest和種群內(nèi)所有粒子歷史的最佳位置gbest的基礎(chǔ)上進(jìn)行位置變化，其速度和位置公式如下：

其中，t表示迭代次數(shù)，r1、r2是（0，1）之間的隨機(jī)數(shù)，c1、c2為學(xué)習(xí)因子，w為慣性權(quán)重，其表達(dá)式為：

其中wmax、wmin為權(quán)重的最大和最小值，tmax為最大迭代次數(shù)。

2 粒子群算法在路徑規(guī)劃中的應(yīng)用

本章節(jié)的主要內(nèi)容是解決粒子的編碼和適應(yīng)度函數(shù)的構(gòu)造，編碼方式涉及粒子位置和速度的更新操作，適應(yīng)度函數(shù)用來評(píng)價(jià)粒子的適應(yīng)值。最后還解決了PSO算法自身陷入局部最優(yōu)的問題。

2.1 粒子編碼

編碼即粒子位置的表達(dá)方式，是設(shè)計(jì)粒子群優(yōu)化和應(yīng)用操作的關(guān)鍵問題，根據(jù)路徑規(guī)劃的實(shí)際情況，本文采用直觀、方便的實(shí)數(shù)編碼[8]。粒子狀態(tài)表達(dá)方式如式（4）所示，編碼方式如式（5）所示。

其中，f（x）表示適應(yīng)值，m表示粒子個(gè)數(shù)。

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

2.2.1 適應(yīng)度函數(shù)的設(shè)計(jì)

將粒子群算法用于路徑規(guī)劃時(shí)，適應(yīng)度函數(shù)的設(shè)計(jì)使得該算法不僅能夠在靜態(tài)網(wǎng)絡(luò)下獲得最優(yōu)路徑，通過增加懲罰項(xiàng)M[9]也能適用于實(shí)時(shí)變化的交通狀況，其適應(yīng)度函數(shù)定義為：

（1）當(dāng)0

（2）當(dāng)0.5≤n<0.75時(shí)，微擁擠狀態(tài)；

（3）當(dāng)0.75≤n≤1時(shí)，嚴(yán)重?fù)矶聽顟B(tài)。

針對(duì)不同的擁堵狀態(tài)采用不同的適應(yīng)度函數(shù)。

適應(yīng)度函數(shù)主要取決于是否有交通擁堵等狀況，車載導(dǎo)航儀[10]將接收到的交通信息轉(zhuǎn)換成路段的相關(guān)特性數(shù)據(jù)，同時(shí)給出交通擁堵系數(shù)n，并根據(jù)n的大小選擇相應(yīng)的適應(yīng)度函數(shù)。采用該適應(yīng)度函數(shù)的優(yōu)點(diǎn)是占用的存儲(chǔ)空間少，并根據(jù)實(shí)時(shí)的交通狀況找出最佳路徑。

2.2.2 適應(yīng)度函數(shù)對(duì)路徑規(guī)劃的影響

如圖1所示，粒子群的起點(diǎn)為S，終點(diǎn)為D。粒子群從S點(diǎn)開始搜索，若不定義適應(yīng)度函數(shù)，則粒子隨機(jī)選擇移動(dòng)方向，而根據(jù)適應(yīng)度函數(shù)（式（6）），大部分粒子選擇更靠近終點(diǎn)的右方，小部分粒子選擇左方，如圖1（a）所示。當(dāng)粒子到達(dá)下一路口時(shí)，重新計(jì)算自身適應(yīng)值，并共享當(dāng)前全局最優(yōu)解，各個(gè)粒子根據(jù)式（1）、（2）更新自身的速度與方向。因此，在單位時(shí)間段內(nèi)，沿著上方行走的粒子數(shù)量高于其他方向的粒子數(shù)，同時(shí)這些粒子記錄自身的局部最優(yōu)解，也能得到全局最優(yōu)解。后續(xù)粒子選擇路徑時(shí)會(huì)受這些最優(yōu)解的影響，沿著粒子較多的方向前進(jìn)，也有小部分粒子會(huì)選擇其他方向來尋求更短的路徑，如圖1（b）所示。當(dāng)某個(gè)粒子到達(dá)終點(diǎn)時(shí)，其他粒子將會(huì)收到該粒子共享的信息，所有粒子將會(huì)朝該方向前進(jìn)，如圖1（c）所示。

2.3 解決陷入“局部最優(yōu)”的問題

為了避免PSO陷入“局部最優(yōu)”，本文在PSO算法中引入變異算子，其思想是：當(dāng)算法達(dá)到特定的迭代次數(shù)h之后，除去之前擁有全局最優(yōu)解的粒子外，計(jì)算其他粒子與當(dāng)前全局最優(yōu)值gbest的距離，若距離小于閾值，則取這些粒子的百分比重新初始化，使這部分粒子重新尋找最優(yōu)值，使種群獲得更高的粒子多樣性，擴(kuò)大搜索范圍，避免粒子群算法陷入局部最優(yōu)，同時(shí)能夠增強(qiáng)全局搜索能力。帶變異算子的粒子群算法如下：

If（th）

取滿足dp-gbest

Else

按式（1）、（2）更新粒子速度和位置；

End

其中，t為當(dāng)前迭代次數(shù)，tmax為最大迭代次數(shù)，h為特定的迭代次數(shù)，dp-gbest表示粒子的當(dāng)前點(diǎn)到全局最優(yōu)解gbest的距離，DistValue為設(shè)定的距離值。

3 算法驗(yàn)證與分析

為了驗(yàn)證上述算法的可行性，本文根據(jù)上海市松江區(qū)部分實(shí)際地圖抽象得到的路網(wǎng)數(shù)據(jù)結(jié)構(gòu)進(jìn)行實(shí)驗(yàn)，如圖2所示。

其中路段數(shù)為134，路口數(shù)為92，粒子數(shù)為95，最大迭代次數(shù)為200，wmax=0.9，wmin=0.4，c1=c2=2。最優(yōu)路徑標(biāo)準(zhǔn)采用最短路徑，PSO算法的路徑規(guī)劃結(jié)果如圖3所示，D算法路徑規(guī)劃的結(jié)果如圖4所示。

由圖3和圖4可知，D算法規(guī)劃出的最優(yōu)路徑與粒子群算法的最優(yōu)路徑是一樣的，但兩個(gè)算法的搜索時(shí)間不同，D算法搜索時(shí)間為46 ms，粒子群算法搜索時(shí)間為55 ms。

上述結(jié)果是在實(shí)際地圖上進(jìn)行的小規(guī)模節(jié)點(diǎn)數(shù)的實(shí)驗(yàn)，圖5和圖6是對(duì)大規(guī)模節(jié)點(diǎn)數(shù)進(jìn)行仿真的結(jié)果比較。

由圖5可知，PSO算法和D算法在節(jié)點(diǎn)數(shù)相當(dāng)?shù)那闆r下，算法求得的路徑長(zhǎng)度是相同或相似的，但由圖6可知，由于D算法與PSO算法的原理和收斂方式不同，在節(jié)點(diǎn)數(shù)目較少時(shí)，PSO算法需要更多的時(shí)間，但是隨著節(jié)點(diǎn)數(shù)目的增加，PSO算法的收斂速度較D算法明顯要快，在大規(guī)模路網(wǎng)中，PSO算法具有較大優(yōu)勢(shì)。

最后當(dāng)在路段中設(shè)置嚴(yán)重交通擁堵，即0.75≤n≤1時(shí)，其路徑規(guī)劃的結(jié)果如圖7所示。

由圖7可知，當(dāng)在道路上設(shè)置擁堵路段時(shí)，算法重新規(guī)劃出了一條避開擁堵路段的最優(yōu)路徑，相比于只能夠運(yùn)用在靜態(tài)路網(wǎng)的D算法，該算法更具有實(shí)際意義。

4 結(jié)論

本文將粒子群算法用于路徑規(guī)劃中，從粒子的編碼規(guī)則到適應(yīng)度函數(shù)的設(shè)計(jì)，再到解決局部最優(yōu)問題等，充分體現(xiàn)了本文的創(chuàng)新性技術(shù)，為路徑規(guī)劃算法提供了新的研究思路。實(shí)驗(yàn)結(jié)果表明，該算法切實(shí)可行，其搜索效率高，時(shí)間開銷隨路網(wǎng)規(guī)模的擴(kuò)大增幅較小，適用于大規(guī)模路網(wǎng)，同時(shí)在實(shí)時(shí)變化的交通路況中更具有實(shí)際意義。

參考文獻(xiàn)

[1] 岳雙.動(dòng)態(tài)路徑規(guī)劃算法在車輛導(dǎo)航領(lǐng)域中的應(yīng)用[J].數(shù)字技術(shù)與應(yīng)用，2012（3）：95-96.

[2] 殷超.基于改進(jìn)Dijkstra算法的最短路徑搜索仿真[J].山東理工大學(xué)學(xué)報(bào)（自然科學(xué)版），2011，24（6）：33-36.

[3] 張仁平，周慶忠，熊偉，等.A*算法改進(jìn)算法及其應(yīng)用[J].計(jì)算機(jī)系統(tǒng)應(yīng)用，2009（9）：98-100，107.

[4] 楊易.智能車輛組合定位與路徑導(dǎo)航技術(shù)研究[D].長(zhǎng)沙：湖南大學(xué)，2007.

[5] 王健.基于蟻群算法的車輛導(dǎo)航自適應(yīng)路徑規(guī)劃算法研究[D].青島：青島科技大學(xué)，2011.

[6] 于海璁，陸鋒.一種基于遺傳算法的多模式多標(biāo)準(zhǔn)路徑規(guī)劃方法[J].測(cè)繪學(xué)報(bào)，2014，43（1）：89-96.

[7] 唐小勇，于飛，潘洪悅.改進(jìn)粒子群算法的潛器導(dǎo)航規(guī)劃[J].智能系統(tǒng)學(xué)報(bào)，2010，5（5）：443-448.

[8] 史輝.車載導(dǎo)航路徑規(guī)劃算法研究[D].鄭州：解放軍信息工程大學(xué)，2010.

[9] 李淑紅，張巧榮.二進(jìn)制粒子群算法在路徑規(guī)劃中的應(yīng)用[J].計(jì)算機(jī)工程與設(shè)計(jì)，2009，30（21）：4953-4955.

[10] 孫海鵬，翟傳潤(rùn)，戰(zhàn)興群，等.基于實(shí)時(shí)交通信息的動(dòng)態(tài)路徑規(guī)劃技術(shù)[J].微計(jì)算機(jī)信息，2007，23（8-3）：177-178.

編輯：jq