，

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

0 引 言

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

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

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

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

2 基于自由空間法的改進混合遺傳算法

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

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

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

(3)將Bellman-Ford算法與精英交叉機制遺傳算法相結合構成一種改進的混合遺傳算法。

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

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

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

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

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

(2)當i=2時，從k=1到k=37時分別計算distk[vi]=min{distk-1[vi],distk-1[vk]+ω(vk,vi)}的結果，輸出初始點S到頂點vi的最短路徑長度dist37[vi]，并記錄從初始點S行走到的最短路徑上vi的前一個頂點序號，將其存儲在集合Path中。

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

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

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

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

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

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

(2)定義目標函數(shù)，確定適應度函數(shù)

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

(3)選擇算子

將適應度最大的個體確定精英個體，采用輪盤賭方法隨機選擇出100條普通個體。

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

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

(5)變異算子

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

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

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

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

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

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

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

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

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

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

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

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

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

(2)收斂速度比較

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

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

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

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

圖8 三種算法在100次仿真實驗中的最優(yōu)解波動對比圖

(3)算法的波動性比較

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

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

5 結 論

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

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

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

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