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

0 引言

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

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

1 粒子群算法的描述

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

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

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

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

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

2.1 粒子編碼

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

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

2.2 適應度函數(shù)

2.2.1 適應度函數(shù)的設計

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

（1）當0

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

（3）當0.75≤n≤1時，嚴重擁堵狀態(tài)。

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

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

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

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

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

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

If（th）

取滿足dp-gbest

Else

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

End

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

3 算法驗證與分析

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

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

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

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

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

最后當在路段中設置嚴重交通擁堵，即0.75≤n≤1時，其路徑規(guī)劃的結果如圖7所示。

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

4 結論

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

參考文獻

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

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

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

[4] 楊易.智能車輛組合定位與路徑導航技術研究[D].長沙：湖南大學，2007.

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

[6] 于海璁，陸鋒.一種基于遺傳算法的多模式多標準路徑規(guī)劃方法[J].測繪學報，2014，43（1）：89-96.

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

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

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

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

編輯：jq