基于自適應算法的車輛導航路線規(guī)劃研究

王啟明，徐向藝，時合生

基于自適應算法的車輛導航路線規(guī)劃研究

王啟明，徐向藝，時合生

最優(yōu)路線規(guī)劃應用到車輛導航系統(tǒng)中時，會導致建模較慢、規(guī)劃耗時。為了線規(guī)劃。將自適應遺傳算法與貪婪算法相結合，獲取最合理的導航優(yōu)路線規(guī)劃，能夠縮短定位時間，較好的滿足了車輛導航系統(tǒng)實時性和實用性的要求。

最優(yōu)路線規(guī)劃；車輛導航；自適應算法；最優(yōu)求解

0 引言

車輛導航系統(tǒng)綜合應用了車輛自動定位技術、地理信息系統(tǒng)技術、計算機技術、多媒體技術和現(xiàn)代通信技術等高新技術，它能為車輛駕駛員提供自動車輛定位、路線規(guī)劃、路線引導、綜合信息服務、無線通信等重要功能[1]。最優(yōu)路線規(guī)劃是車輛定位導航系統(tǒng)的一個基本應用，要求能夠按照電子地圖的拓撲信息，幫助車輛駕駛人員或調度人員在車輛出發(fā)地和目的地確定的情況下，按照某種策略，如時間最少或路線最短等，實時準確地選定一條最優(yōu)的行車路線，并顯示在計算機屏幕的電子地圖上[2]。由于道路環(huán)境具有一定的復雜性、多變性，導致傳統(tǒng)的車輛導航規(guī)劃模型具有一定的局限性，降低工作效率。本文提出基于自適應算法的車輛導航路線規(guī)劃，并對傳統(tǒng)算法做了比較深入的探討，在此基礎上構造了新的車輛導航路線規(guī)劃模型[3-5]。

1 車輛導航路線規(guī)劃方法原理

車輛導航路線規(guī)劃過程中，可以將所有的線路作為蜜源構成初始集合，在該集合中，所有的元素都能代表導航線路規(guī)劃過程中的解，所有的解構成的集合是Yj(1,2,...,n)，采用蜜蜂式搜索方式在類似區(qū)域內搜索具有相同屬性個體，重復執(zhí)行搜索模式，以獲取最優(yōu)解[6][7]。

根據(jù)公式(1)對所有的導航線路進行實時跟蹤監(jiān)測，并對蜜源更新定位。設置l與k表示隨機選取的下標，且具有一定的關聯(lián)性，當監(jiān)測系統(tǒng)搜索到車輛導航路線適應性越強，yjk的取值范圍越小如公式（1）、（2）：

在車輛導航路線最優(yōu)解的選取中，利用公式（2）計算具有較強適應性的車輛導航路線占總導航路線的概率。其中，用fitj表示第j個解的適應度值。

為了車輛導航路線的多樣性，利用公式（3）對控制端中具有高強度適應性的車輛導航路線進行變異處理，以便搜索出具有更強適應性的車輛導航路線[8]。具體操作方法如下所述：

（1）采用迭代方法，按照一定規(guī)律對舊值變量進行不斷遞推，進而獲取新值。設置蜜源的初始迭代次數(shù)用H表示，且H=0，最大迭代次數(shù)用Hmax表示，最大限制次數(shù)為Limit值。

（2）在蜜源中隨機選取n個車輛導航路線，并利用公式（1）計算每個車輛導航路線的適應值，根據(jù)每條導航線路的適應性能夠判斷該解的優(yōu)越性。

（3）利用公式（2）計算具有較強適應性的車輛導航路線占總逃生路線的概率Qi，根據(jù)概率Qi選擇最優(yōu)蜜源，并記錄較優(yōu)蜜源位置，對數(shù)據(jù)L位置進行實時更新。

（4）在仿真模型中，假如L(j)的值大于最大限制次數(shù)Limit的值，在解空間內進一步進行搜索，并記錄最優(yōu)解的位置，保存到監(jiān)測系統(tǒng)中。

（5）H+1表示在H的基礎上進行了一次迭代算法更新，當H大于Hmax值時，記錄最優(yōu)蜜源代表車輛導航路線的最優(yōu)值。進行第（6）步操作。反之，當H小于Hmax值時，跳轉到步驟（3），繼續(xù)重復操作關于概率Qi的計算。

（6）根據(jù)當前車輛導航最優(yōu)路線規(guī)劃窗口中的全部導航路線點，在有效的時間內選取越過道路障礙物的最短車輛導航路線，獲取車輛導航路線規(guī)劃。

2 車輛導航最優(yōu)路線規(guī)劃方法相關理論

利用傳統(tǒng)算法進行車輛導航最優(yōu)路線規(guī)劃,建立的規(guī)劃模型需要滿足的約束條件較多，建模耗時較長,降低了規(guī)劃效率。為此，提出基于自適應算法的車輛導航最優(yōu)路線規(guī)劃方法[9][10]。

2.1 搜索車輛導航路線

根據(jù)遺傳算法對水車輛導航路線進行求解。遺傳算法中交叉率QD和變異率QN對車輛導航路線最優(yōu)解的選取有著決定性的作用，表達式如公式（4）、（5）：

在上述公式中，gmax表示車輛導航路線最大適應度，gavg表示車輛導航路線平均適應度，g'表示參與交叉運算的兩個車輛導航路線中較大的適應度，g表示經過變異處理后車輛導航路線的適應度。設置[0,1]，分別表示交叉概率和變異概率的調整參數(shù)。在進行交叉運算后保留適應性最強的車輛導航路線最優(yōu)解。

為了簡化運算，提高計算效率，對交叉概率QD和變異概率QN進行優(yōu)化處理[0,1]，所得公式（6），（7）：

利用上述公式，隨機選取兩條不同車輛導航路線作為交叉或變異元素，在進行交叉和變異計算時，當兩條車輛導航路線中最大的適應度值小于當前導航線路的平均適應度值時，關于導航線路交叉或變異概率的選取，應在最大和最小適應度范圍之間進行最優(yōu)求解，以達到求解標準。

2.2 選取車輛導航最優(yōu)路線

由于車輛所在的公路環(huán)境具有一定的復雜性，導致傳統(tǒng)的遺傳算法所建立的模擬模型，具有一定的局限性。利用自適應算法優(yōu)化初始車輛導航路線，可以提高挖掘能力，加快計算的收斂速度。假設有n個有效車輛導航線路規(guī)劃，利用自適應算法優(yōu)化初始車輛導航路線的基本思路為：結合車輛所處位置和周圍環(huán)境以及車流量的大小和方向，隨機選取一條最有效的導航路線，設置為1，然后從余下（n-1）條導航線路中尋找最有效的導航路線進行對比。綜合各個影響因素，如果第（n-1）條車輛導航路線的適應強度高于第n條車輛導航路線，則用第（n-1）條替代第n條車輛導航路線。將已經作比較的導航線路排除，依次進行對比選擇，生成新的個體。

3 實驗仿真結果分析

為了驗證本文提出的自適應算法的有效性,需要進行一次實驗。在實驗的過程中，車輛行走的道路和障礙分布情況描述如圖1所示：

圖1 車輛運行環(huán)境模擬

在車輛導航路線規(guī)劃過程中，車輛的運行速度能夠用下圖2所示：

圖2 車輛運行速度曲線

分別利用傳統(tǒng)算法和改進算法進行車輛導航路線規(guī)劃，獲取的規(guī)劃線路用下述兩幅圖3圖4所示：

圖3 傳統(tǒng)算法規(guī)劃結果

圖4 改進算法規(guī)劃結果

根據(jù)圖3和圖4的對比結果可以得知，傳統(tǒng)算法已經陷入到局部最優(yōu)解，得到的車輛導航線路優(yōu)越性較差，線路較長，而且沒有合理避開障礙。改進算法避免了上述傳統(tǒng)算法的缺陷，得到了全局最優(yōu)解，獲取了更加合理的導航線路。在車輛導航路線規(guī)劃過程中，分別利用傳統(tǒng)算法和本文算法進行水下機器人線路規(guī)劃時，規(guī)劃線路的協(xié)同誤差能夠用圖5所示：

圖5 規(guī)劃線路協(xié)同誤差

在上述實驗過程中，線路規(guī)劃過程中的誤差能夠用下圖進行描述圖圖6所示：

圖6 線路規(guī)劃誤差

對上述實驗過程中的相關數(shù)據(jù)進行整理分析，能夠得到表1和表2所示：

表1 傳統(tǒng)算法實驗數(shù)據(jù)表

表2 改進算法實驗數(shù)據(jù)表

根據(jù)上述實驗可以得知，利用本文算法進行車輛導航最優(yōu)路線規(guī)劃，能夠避免傳統(tǒng)算法在線路規(guī)劃方面的缺陷，提高路線選取的合理性，取得了令人滿意的結果。

4 總結

本文首先對車輛導航系統(tǒng)進行了研究，針對傳統(tǒng)算法無法避免由于建立的規(guī)劃模型需要滿足的約束條件較多造成建模耗時較長的缺陷，提出基于自適應算法的車輛導航最優(yōu)路線規(guī)劃方法，并對傳統(tǒng)算法和改進算法做了比較深入的探討，在此基礎上構造了新車輛模型。經過分析，采用自適應遺傳算法進行車輛導航最優(yōu)路線規(guī)劃，選擇的導航路線更具有智能性和協(xié)調性，解決路線規(guī)劃這類問題是有實際意義的，它可以較好地滿足車輛導航系統(tǒng)實時性的要求。

[1] 孫世博,馮勇,鄭劍飛.車輛導航系統(tǒng)最優(yōu)路線規(guī)劃研究[J].計算機應用.2006,(09):44-46.

[2] KATRASNIK J,PERNUS F,LIKAR B.A survey of mobile robots for distribution power line inspection[J].IEEE Transactions on Power Delivery,2010,(01):485-493.

[3] WANG Jidai,SUN Aiqin,ZHENG Candong. Research on a new crawler type inspection robot for power transmission lines[C].Piscataway,NJ,USA:IEEE,2010.1-5.

[4] Zhou X F,Guan Y S,Cai C W. Modeling and planning for stable walking of a novel 6-DOF biped robot[C].Piscataway,NJ,USA:IEEE,2010.7-12.

[5] Duan X G,Huang Q,Rahman N. Kinematic modeling of a small mobile robot with multi-locomotion modes[C].Piscataway,NJ,USA:IEEE,2006.5582-5587.

[6] Kanehiro F,Hirukawa H,Kaneko K. Locomotion planning of humanoid robots to pass through narrow spaces[C].Piscataway,NJ,USA:IEEE,2004.604-609.

[7] Chandra Mohan B, Baskaran R. Ant Colony Optimization based recent research and implementation on several engineering domain [J]. Expert Systems with Applications, 2012, 39(4): 4618-4627.

[8] Yeoreum Y,Danielar A. A robot that climbs 3D trusses[J]. Shady3D:IEEE,2007.(03)4071-4076.

[9] 陳立潮.城市交通智能咨詢系統(tǒng)的設計與實現(xiàn)[J].計算機工程.2003,29:32-34.

[10] 王凌.智能優(yōu)化算法及其應用[M].北京:清華大學出版社,2003.

TN393

A

2015.02.10）

1007-757X(2015)07-0041-03

王啟明（1980-），男，魯山人，平頂山學院，計算機科學與技術學院，講師，碩士，研究方向：軟件工程算法和物聯(lián)網，平頂山，467002

徐向藝（1979-），女，平頂山人，平頂山學院，軟件學院，講師，碩士，研究方向：智能算法、網絡安全，平頂山，467002

時合生（1977-），男，郾城縣人，平頂山學院，計算機科學與技術學院，講師，碩士，研究方向：計算機軟件與理論，平頂山，467002