王啟明，徐向藝，時(shí)合生

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

王啟明，徐向藝，時(shí)合生

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

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1 搜索車輛導(dǎo)航路線

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

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

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

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

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

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

3 實(shí)驗(yàn)仿真結(jié)果分析

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

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

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

圖2 車輛運(yùn)行速度曲線

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

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

圖4 改進(jìn)算法規(guī)劃結(jié)果

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

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

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

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

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

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

表2 改進(jìn)算法實(shí)驗(yàn)數(shù)據(jù)表

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

4 總結(jié)

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

[1] 孫世博,馮勇,鄭劍飛.車輛導(dǎo)航系統(tǒng)最優(yōu)路線規(guī)劃研究[J].計(jì)算機(jī)應(yīng)用.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)的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)工程.2003,29:32-34.

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

TN393

A

2015.02.10）

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

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

徐向藝（1979-），女，平頂山人，平頂山學(xué)院，軟件學(xué)院，講師，碩士，研究方向：智能算法、網(wǎng)絡(luò)安全，平頂山，467002

時(shí)合生（1977-），男，郾城縣人，平頂山學(xué)院，計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，講師，碩士，研究方向：計(jì)算機(jī)軟件與理論，平頂山，467002