基于改進(jìn)混合遺傳算法的無人車路徑規(guī)劃①

，

(安徽工業(yè)大學(xué)機(jī)械工程學(xué)院，安徽 馬鞍山 243000)

0 引 言

無人車的路徑規(guī)劃技術(shù)是智能導(dǎo)航系統(tǒng)的關(guān)鍵環(huán)節(jié)，實(shí)現(xiàn)無人車路徑規(guī)劃的關(guān)鍵技術(shù)是路徑規(guī)劃算法，它直接決定著搜索結(jié)果的優(yōu)良和搜索時(shí)間的長短，選擇一個(gè)合理的路徑規(guī)劃算法顯得尤其重要。經(jīng)過半個(gè)多世紀(jì)的探索，國內(nèi)外學(xué)者主要從路徑規(guī)劃算法的實(shí)時(shí)性、全局收斂性和運(yùn)算效率這三個(gè)方面進(jìn)行研究改進(jìn)，已經(jīng)實(shí)現(xiàn)了從最初的盲目搜索到智能搜索算法的發(fā)展。用于全局路徑規(guī)劃的算法主要有A*算法[1]、人工勢(shì)場法[2]、人工神經(jīng)網(wǎng)絡(luò)算法[3]、細(xì)菌覓食算法、遺傳算法[4]等，其中A*算法和人工勢(shì)場算法屬于傳統(tǒng)規(guī)劃算法，人工神經(jīng)網(wǎng)絡(luò)算法、細(xì)菌覓食算法、遺傳算法屬于智能路徑規(guī)劃方法。當(dāng)無人車在整潔的工廠、倉庫、街道等環(huán)境中工作時(shí)，空間中障礙物個(gè)數(shù)少且體積大，針對(duì)這種較簡單的靜態(tài)工作環(huán)境，采用自由空間法構(gòu)建環(huán)境模型，根據(jù)自由空間法構(gòu)建的環(huán)境模型特點(diǎn)，提出一種結(jié)合Bellman-Ford算法與精英交叉機(jī)制遺傳算法的混合遺傳算法，用于規(guī)劃較簡單環(huán)境中的無人車全局最短路徑。

1 基于自由空間法構(gòu)建無人車環(huán)境模型

采用矢量對(duì)象描述方式來描述障礙物并進(jìn)行建模，將環(huán)境空間障礙物抽象表示為各種不規(guī)則多邊形，環(huán)境空間W的邊界為200×200，其中初始點(diǎn)S坐標(biāo)為(10,190)，如圖1中圓點(diǎn)所示，目標(biāo)點(diǎn)坐標(biāo)T為(190,10)，如圖1中方塊點(diǎn)所示，基于鏈接圖法[5]使用自由鏈接線將環(huán)境空間劃分成各種凸多邊形，并基于MATLAB軟件通過抽象表達(dá)環(huán)境空間和構(gòu)造空間連通圖兩個(gè)步驟完成無人車的自由空間法建模，環(huán)境模型如圖1所示。

圖1 自由空間法構(gòu)建的環(huán)境模型

2 基于自由空間法的改進(jìn)混合遺傳算法

提出一種融合Bellman-Ford算法與遺傳算法的混合遺傳算法，用于實(shí)現(xiàn)無人車的全局路徑規(guī)劃。這種算法的規(guī)劃思路是：

(1)先用Bellman-Ford算法搜索出連通圖中初始點(diǎn)到目標(biāo)點(diǎn)的最短路徑，獲取粗路徑點(diǎn)；

(2)然后用遺傳算法優(yōu)化每個(gè)粗路徑點(diǎn)，獲得無人車安全行走的最短路徑。

(3)將Bellman-Ford算法與精英交叉機(jī)制遺傳算法相結(jié)合構(gòu)成一種改進(jìn)的混合遺傳算法。

這種改進(jìn)的混合遺傳算法使用固定長度的染色體，極大簡化個(gè)體編碼方法，絕不產(chǎn)生無效初始路徑，且有效提高遺傳算法的收斂速度，能夠避免算法陷入局部最優(yōu)解，將其應(yīng)用于自由空間模型中的無人車路徑規(guī)劃中表現(xiàn)出優(yōu)越的搜索性能。

3 改進(jìn)混合遺傳算法執(zhí)行無人車路徑規(guī)劃的實(shí)現(xiàn)步驟

3.1 Bellman-Ford算法的實(shí)現(xiàn)步驟

由圖1知加權(quán)連通圖中共有頂點(diǎn)38個(gè)，從初始點(diǎn)S到目標(biāo)點(diǎn)T的最短路徑最多有37條邊，用vi表示加權(quán)圖中各個(gè)頂點(diǎn)，邊的權(quán)值為ω(vj,vi)，其中，v1為初始點(diǎn)S，i,j∈[1,38]。Bellman-Ford算法的實(shí)現(xiàn)步驟為：

(1)初始化初始點(diǎn)S與每個(gè)頂點(diǎn)vi的路徑長度dist，令dist0[S]=0,dist0[vi]=。

(2)當(dāng)i=2時(shí)，從k=1到k=37時(shí)分別計(jì)算distk[vi]=min{distk-1[vi],distk-1[vk]+ω(vk,vi)}的結(jié)果，輸出初始點(diǎn)S到頂點(diǎn)vi的最短路徑長度dist37[vi]，并記錄從初始點(diǎn)S行走到的最短路徑上vi的前一個(gè)頂點(diǎn)序號(hào)，將其存儲(chǔ)在集合Path中。

(3)令i=i+1，重復(fù)步驟(2)直至i=38，輸出從初始點(diǎn)S到目標(biāo)點(diǎn)T的最短路徑長度dist37[T]及最短路徑的頂點(diǎn)集合Path。

(4)對(duì)Path采用“倒向追蹤”方法追溯到初始點(diǎn)S，獲得由初始點(diǎn)S到目標(biāo)點(diǎn)T的最短行走路徑節(jié)點(diǎn)。

3.2 精英交叉機(jī)制遺傳算法的實(shí)現(xiàn)步驟

采用Bellman-Ford算法求出的最短路徑不一定是最短無碰路徑，下面基于精英交叉機(jī)制遺傳算法對(duì)每個(gè)粗路徑點(diǎn)進(jìn)行優(yōu)化，搜索出無人車在工作空間中無碰撞行走的最佳路徑，實(shí)現(xiàn)步驟為：

(1)個(gè)體編碼方法及初始群體的確定

采用實(shí)值參數(shù)表達(dá)，用優(yōu)化粗路徑點(diǎn)的n個(gè)比例參數(shù)值來組成一系列初始路徑。

(2)定義目標(biāo)函數(shù)，確定適應(yīng)度函數(shù)

將每條染色體對(duì)應(yīng)路徑的總長度定義為路徑規(guī)劃的目標(biāo)函數(shù)，選取“界限構(gòu)造法”來構(gòu)造適應(yīng)度函數(shù)。

(3)選擇算子

將適應(yīng)度最大的個(gè)體確定精英個(gè)體，采用輪盤賭方法隨機(jī)選擇出100條普通個(gè)體。

(4)隨機(jī)交叉和精英交叉操作

首先，按交叉概率Pc隨機(jī)選取20條普通個(gè)體分為10對(duì)，每對(duì)個(gè)體間隨機(jī)產(chǎn)生一個(gè)交叉位進(jìn)行單點(diǎn)交叉。然后按精英交叉概率Pe隨機(jī)選取20條普通個(gè)體，隨機(jī)設(shè)置每個(gè)個(gè)體的交叉點(diǎn)，以0.5的概率確定前交叉或后交叉，使精英個(gè)體的部分染色體片段復(fù)制到普通個(gè)體上。

(5)變異算子

使用逆轉(zhuǎn)變異方式，按照變異概率Pm隨機(jī)選取一個(gè)個(gè)體并隨機(jī)設(shè)置兩個(gè)逆轉(zhuǎn)變異點(diǎn)，反向排序放置該個(gè)體兩逆轉(zhuǎn)點(diǎn)間的編碼串。然后對(duì)變異個(gè)體進(jìn)行編碼串檢驗(yàn)，若變異個(gè)體與精英個(gè)體完全相同，則隨機(jī)生成一條個(gè)體代替變異個(gè)體。

利用精英交叉機(jī)制遺傳算法優(yōu)化局部最優(yōu)解，通過若干代的迭代進(jìn)化后搜索出環(huán)境模型中的最短路徑，完成改進(jìn)的混合遺傳算法在自由空間模型中路徑規(guī)劃工作。

4 自由空間模型下無人車路徑規(guī)劃的仿真結(jié)果及分析

4.1 基于Bellman-Ford算法求解最短粗路徑

基于已構(gòu)造的自由空間模型，運(yùn)行Bellman-Ford算法，仿真求出無人車在連通圖中的最短路徑行走路線如圖2中黑色虛線所示。

圖2 Bellman-Ford算法求得最短粗路徑

4.2 基于精英交叉機(jī)制遺傳算法優(yōu)化粗路徑

分別運(yùn)用基本遺傳算法、保留精英策略遺傳算法、及精英交叉機(jī)制遺傳算法優(yōu)化Bellman-Ford算法產(chǎn)生粗路徑點(diǎn)，并從最優(yōu)解、收斂速度和算法波動(dòng)性三個(gè)方面進(jìn)行了大量的仿真實(shí)驗(yàn)對(duì)比。

(1)最優(yōu)解比較

如圖3(a)、圖4(a)、圖5(a)中實(shí)線所示分別為基本遺傳算法、保留精英策略遺傳算法、及精英交叉機(jī)制遺傳算法在100次仿真實(shí)驗(yàn)中搜索到的最短路徑。三種遺傳算法搜索的最短路徑都比Bellman-Ford算法求解的路徑更短，驗(yàn)證了提出的改進(jìn)混合遺傳算法在求解自由空間模型中最短路徑問題的可行性。

圖3 基本遺傳算法路徑規(guī)劃仿真結(jié)果

圖4 保留精英策略遺傳算法路徑規(guī)劃仿真結(jié)果

圖5 精英交叉機(jī)制遺傳算法路徑規(guī)劃仿真結(jié)果

(2)收斂速度比較

如圖3(b)、圖4(b)、圖5(b)分別為三種算法在搜索到最優(yōu)解的一次實(shí)驗(yàn)中迭代次數(shù)與最短路徑、平均路徑的收斂曲線圖。分別比較三種算法最短路徑和平均路徑的收斂曲線，如圖6、圖7所示，可知精英交叉機(jī)制遺傳算法產(chǎn)生的平均路徑最小且最快趨于穩(wěn)定，且僅在最短路徑附近的小范圍內(nèi)波動(dòng)。

以上分析證明，運(yùn)行參數(shù)相同時(shí)精英交叉機(jī)制遺傳算法收斂速度最快。

圖6 三種算法的最優(yōu)路徑收斂曲線圖

圖7 三種算法的平均路徑收斂曲線圖

圖8 三種算法在100次仿真實(shí)驗(yàn)中的最優(yōu)解波動(dòng)對(duì)比圖

(3)算法的波動(dòng)性比較

分析三種算法的波動(dòng)性。使用相同的運(yùn)行參數(shù)分別對(duì)三種算法進(jìn)行100次仿真實(shí)驗(yàn)，記錄每一次實(shí)驗(yàn)求出的最優(yōu)解。圖8是三種算法的最優(yōu)解波動(dòng)情況比較圖，100次實(shí)驗(yàn)中精英交叉機(jī)制遺傳算法的最優(yōu)解波動(dòng)范圍最小，說明精英交叉機(jī)制遺傳算法獲得的最優(yōu)解波動(dòng)小，集中性高。

綜上三個(gè)方面的仿真分析，驗(yàn)證了提出的精英交叉機(jī)制遺傳算法在無人車路徑規(guī)劃上的可行性和高效性。

5 結(jié) 論

提出的改進(jìn)混合遺傳算法，將其用于搜索環(huán)境空間中最短路徑，并通過仿真分析驗(yàn)證改進(jìn)算法的高效性。依據(jù)仿真結(jié)果得到如下結(jié)論：

a.采用自由空間法構(gòu)造無人車環(huán)境模型，其顯著優(yōu)點(diǎn)是無人車起始點(diǎn)及目標(biāo)點(diǎn)的位置改變與構(gòu)造的連通圖無關(guān)。

b通過仿真實(shí)驗(yàn)，驗(yàn)證了該融合Bellman-Ford算法和精英交叉機(jī)制遺傳算法的改進(jìn)混合遺傳算法進(jìn)行無人車路徑規(guī)劃的可行性。

c從最優(yōu)解、收斂速度和最優(yōu)解波動(dòng)性三個(gè)方面分析精英交叉機(jī)制遺傳算法、保留精英策略遺傳算法與基本算法的搜索性能，證明精英交叉機(jī)制遺傳算法進(jìn)行無人車路徑規(guī)劃時(shí)搜尋最優(yōu)解的能力更強(qiáng)，收斂速度更快，穩(wěn)定性更高。