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

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

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

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

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

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

0　引言

路徑規(guī)劃是車載導(dǎo)航系統(tǒng)的基本功能，由于其有較強(qiáng)的應(yīng)用價(jià)值，國內(nèi)外學(xué)者對(duì)此進(jìn)行了深入的研究［1-3］。現(xiàn)今較流行的算法有Dijstra算法（簡稱D算法）和A*算法，但D算法搜索速度較慢，A*算法搜索速度快但成功率不高，且這些算法只能在靜態(tài)地圖上進(jìn)行路徑規(guī)劃，沒有考慮實(shí)時(shí)變化的交通狀況。近年來，智能算法因其強(qiáng)大的搜索能力而被廣泛應(yīng)用于路徑規(guī)劃中。楊易［4］把遺傳算法與A*算法相結(jié)合，提高路徑規(guī)劃算法的效率；王?。?］把蟻群算法應(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ù)定義為：

其中，（xp，yp）為當(dāng)前點(diǎn)粒子的坐標(biāo)，（xs，ys）為起點(diǎn)坐標(biāo)，（xd，yd）為終點(diǎn)坐標(biāo)，為某粒子當(dāng)前點(diǎn)到終點(diǎn)的估計(jì)代價(jià)表示從起點(diǎn)到當(dāng)前點(diǎn)的距離之和，。M為懲罰項(xiàng)，取較大的數(shù)。n為交通擁堵系數(shù)，定義如下：

（1）當(dāng)0＜n＜0.5時(shí)，暢通；

（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）所示。

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

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（t＜tmax&&＞h）

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

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所示。

圖2　根據(jù)實(shí)際地圖抽象得到的路網(wǎng)數(shù)據(jù)結(jié)構(gòu)

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

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

由圖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算法路徑長度的比較

圖6　PSO算法與D算法時(shí)間開銷的比較

由圖5可知，PSO算法和D算法在節(jié)點(diǎn)數(shù)相當(dāng)?shù)那闆r下，算法求得的路徑長度是相同或相似的，但由圖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í)際意義。

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

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í)際意義。

［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］.長沙：湖南大學(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］孫海鵬，翟傳潤，戰(zhàn)興群，等.基于實(shí)時(shí)交通信息的動(dòng)態(tài)路徑規(guī)劃技術(shù)［J］.微計(jì)算機(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-），女，碩士生導(dǎo)師，主要研究方向：機(jī)器視覺與圖像處理，模式識(shí)別。

郁曉慧（1989-），女，碩士研究生，主要研究方向：機(jī)器視覺與圖像處理，導(dǎo)航與定位技術(shù)。

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