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

王啟明，徐向藝，時合生

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

王啟明，徐向藝，時合生

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

最優路線規劃；車輛導航；自適應算法；最優求解

0 引言

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

1 車輛導航路線規劃方法原理

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

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

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

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

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

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

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

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

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

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

2 車輛導航最優路線規劃方法相關理論

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

2.1 搜索車輛導航路線

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

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

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

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

2.2 選取車輛導航最優路線

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

3 實驗仿真結果分析

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

圖1 車輛運行環境模擬

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

圖2 車輛運行速度曲線

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

圖3 傳統算法規劃結果

圖4 改進算法規劃結果

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

圖5 規劃線路協同誤差

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

圖6 線路規劃誤差

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

表1 傳統算法實驗數據表

表2 改進算法實驗數據表

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

4 總結

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

[1] 孫世博,馮勇,鄭劍飛.車輛導航系統最優路線規劃研究[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] 陳立潮.城市交通智能咨詢系統的設計與實現[J].計算機工程.2003,29:32-34.

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

TN393

A

2015.02.10）

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

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

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

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