基于PSO算法路徑規(guī)劃的研究

禹素萍，郁曉慧，許武軍，范　紅

基于PSO算法路徑規(guī)劃的研究

禹素萍1，2，郁曉慧1，2，許武軍1，2，范紅1，2

（1.東華大學信息科學與技術學院，上海201620；2.東華大學數字化紡織服裝技術教育部工程研究中心，上海201620）

在實時的交通路況中，路徑規(guī)劃的核心問題是快速而有效地找到從起點到達終點的最優(yōu)路線。將PSO算法應用到的路徑規(guī)劃中來，針對實時變化的交通路況，在適應度函數中引入懲罰項來實現(xiàn)靜態(tài)和動態(tài)下的路徑規(guī)劃，并通過引入變異算子的操作來避免該算法陷入局部最優(yōu)。實驗表明，改進后的PSO算法搜索效率高，時間開銷隨路網規(guī)模的擴大增幅較小，適用于大規(guī)模路網和動態(tài)路徑規(guī)劃。

車載導航；路徑規(guī)劃；變異算子；局部最優(yōu)

0　引言

路徑規(guī)劃是車載導航系統(tǒng)的基本功能，由于其有較強的應用價值，國內外學者對此進行了深入的研究［1-3］。現(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)解。算法在搜索時，根據粒子自身歷史的最佳位置pbest和種群內所有粒子歷史的最佳位置gbest的基礎上進行位置變化，其速度和位置公式如下：

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

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

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

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

2.1粒子編碼

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

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

2.2適應度函數

2.2.1適應度函數的設計

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

其中，（xp，yp）為當前點粒子的坐標，（xs，ys）為起點坐標，（xd，yd）為終點坐標，為某粒子當前點到終點的估計代價表示從起點到當前點的距離之和，。M為懲罰項，取較大的數。n為交通擁堵系數，定義如下：

（1）當0＜n＜0.5時，暢通；

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

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

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

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

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

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

圖1　適應度函數對路徑規(guī)劃的影響

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

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

If（t＜tmax&&＞h）

取滿足dp-gbest＜DistValue粒子中的百分比，并根據式（1）、（2）對其速度與位置進行重新初始化；

Else

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

End

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

3　算法驗證與分析

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

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

圖2　根據實際地圖抽象得到的路網數據結構

圖3　基于粒子群算法的路徑規(guī)劃結果

圖4　Dijkstra算法路徑規(guī)劃的結果

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

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

圖5　PSO算法與D算法路徑長度的比較

圖6　PSO算法與D算法時間開銷的比較

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

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

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

圖7　設置交通擁堵時路徑規(guī)劃的結果

4　結論

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

［1］岳雙.動態(tài)路徑規(guī)劃算法在車輛導航領域中的應用［J］.數字技術與應用，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.

Research o f path p lanning based on PSO algorithm

Yu Suping1，2，Yu Xiaohui1，2，Xu Wujun1，2，F(xiàn)an Hong1，2
（1.College of Information Sciences and Technology，Donghua University，Shanghai 201620，China；2.Engineering Research Center of Digitized Textile&Fashion Technology，Ministry of Education，Donghua University，Shanghai 201620，China）

In real-time traffic conditions，the key problem of path planning is finding the optimal path accurately and quickly. This article uses PSO algorithm in the path planning，for the real-time changes in traffic conditions，penalty term is introduced into the fitness function to achieve the path planning in both static and dynamic conditions，and in order to effectively prevent defects of local optimum，mutation operator is introduced into the algorithm.Experimental results show that the algorithm has the better searching efficiency，and the spending time has a little increase with the expansion of road network.The last but not the least，the algorithm is suitable for large-scale road network and dynamical route planning.

vehicle navigation；path planning；mutation operator；local optimum

TP391.9

A

1674-7720（2015）04-0017-03

（2014-10-20）

禹素萍（1977-），女，碩士生導師，主要研究方向：機器視覺與圖像處理，模式識別。

郁曉慧（1989-），女，碩士研究生，主要研究方向：機器視覺與圖像處理，導航與定位技術。

許武軍（1972-），男，碩士生導師，主要研究方向：嵌入式計算與系統(tǒng)，導航與定位技術。