陳高遠 宋云雪

(中國民航大學航空工程學院 天津 300300)

0 引 言

針對移動機器人的路徑規(guī)劃問題[1]，人們提出了不同方法，例如人工勢場法[2-3]、Dijkstra算法[4-5]、快速擴展隨機樹算法(RRT)[6]、A*算法[7-8]、粒子群算法(PSO)[9]等。其中遺傳算法(GA)最早是由John Holland基于生物進化原理提出的啟發(fā)式搜索算法[10-11]，隨著深入研究，因其靈活性以及與可擴展性等優(yōu)勢被廣泛應用于路徑規(guī)劃問題。在遺傳迭代過程中由于種群初始規(guī)模過小、選擇和變異的不確定性等原因，會出現過早收斂僅僅得到局部最優(yōu)，為此許多學者對遺傳算法進行了改進。儀孝展[12]將模擬退火算法與遺傳算法相結合，利用模擬退火算法可變的概率選擇新解，并且能在較好的解空間進行搜索的特性，解決遺傳算法迭代到一定次數后進化停滯問題。魏彤等[13]提出了相鄰幀之間關聯(lián)來平穩(wěn)路徑，通過上一幀的路徑信息作為下一幀路徑規(guī)劃的參考，減少上下兩幀的差異，有效地提高了行駛過程中的穩(wěn)定。Xin等[14]提出了基于多域反演的遺傳算法，利用多域反演增加后代數量的策略，并進行第二次適應性評價，以消除不需要的后代保留最有利的個體。這種方法增強搜索的能力和產生優(yōu)秀個體的可能性。Nazarahari等[15]提出了多目標增強的遺傳算法，在連續(xù)環(huán)境中從路徑長度、平滑度和安全性方面尋找最優(yōu)路徑，該算法結合人工勢場法并且對初始變異算子進行改進能夠在連續(xù)的環(huán)境中找到可行的網格路徑。宋宇等[16]將RRT算法與遺傳算法相結合，用RRT算法產生初始路徑，同時增加了插入算子，最后使用遺傳算法來優(yōu)化路徑。Lee等[17]提出一種基于障礙物的搜索方法，來識別出與給定障礙物相鄰的臨界無碰撞點，同時，將遺傳算法與目標點方向因子相結合來獲取有效路徑。

在對遺傳算法的研究和對文獻研究分析的基礎上，考慮到遺傳算法既可以用于單目標簡單路徑規(guī)劃，也可以用于多目標復雜路徑規(guī)劃，并且具有較強的魯棒性和與其他算法結合的可擴展性等優(yōu)點，對遺傳算法進行了改進，提出采用粒子群優(yōu)化算法來重構變異算子，提高算法的速度，確定遺傳算法進化的方向。在遺傳迭代過程中，對適合度函數加入懲罰因子避免過早收斂，如果路徑因與障礙物相交而不可行的，則對其適合度進行懲罰。同時為了解決由于交叉和突變產生大量的不可行路徑，加入修復機制研究不可行路徑，然后對其修復。

1 構型空間

1.1 地圖構建

將地圖定義為大小為n的正方形[0,n-1]2，使用規(guī)則間隔對其進行離散化，得到以下網格：

G={(i,j)|0≤i,j≤n-1}

(1)

地圖中障礙物占有的網格occ∈Rn×n可以如下表示：

在單目標簡單地形中表示為：

(2)

多目標復雜地形中表示為：

(3)

式中：f(xi)表示第i格的復雜度，可以用該位置的高度表示，并且對其進行歸一化操作。

1.2 路徑表示

針對文獻[18]中采用的符號編碼方式，本文采用二進制編碼方式來表示路徑，更方便地進行后續(xù)的交叉、變異等遺傳操作。路徑由n-1個對方向和距離動作描述，如表1所示。每個動作都會告訴機器人從當前單元格朝哪個方向移動，以及沿該方向經過了多少個單元格，該問題可以用2種不同類型的路徑來表示：X單調路徑：每個動作都會使路徑的x坐標正好增加1。Y單調路徑：每個動作都會使路徑的y坐標正好增加1。這種方式能夠在x軸上和y軸上分別執(zhí)行n-1個操作之后到達最后一列或行如圖1所示。

表1 路徑動作編碼

圖1 路徑的二進制表示

可以將路徑存儲為固定長度的二進制數組ε，該數組的長度為：

len(ε)=1+(n-1)×(2+1+log2(n))

(4)

其中二進制數組的第一位ε[0]=0時表示路徑是X單調，ε[0]=1表示路徑是Y單調，2+1+log2(n)代表每行或每列的方向和距離，前兩位表示前進的方向，剩下的二進制位，如果方向為00，則表示將距離表示為有符號的整數，否則將被忽略隨機填充。當X單調并且方向為00時，如果距離為正，路徑向上移動，則沿副對角線右上角移至下一列，否則向下并沿主對角線右下角移動。當Y單調且方向為00時，如果距離為正，路徑向下移動，然后沿副對角線向左下移至下一行，否則向右并沿主對角線右下移動。

2 改進遺傳算法

2.1 初始化

初始化一個具有固定大小為p的路徑個體種群S，其中的P-2個隨機初始化，具體來說，它們的二進制表示形式是隨機生成的，每個位在[0,1]之間進行均勻采樣。最后兩個路徑分別是X單調和Y單調直線路徑,路徑個體種群S可以定義為：

S={l0,l1,…,lp-2,lx,ly}

(5)

式中：li表示隨機生成的二進制路徑；lx是X單調路徑；ly是Y單調路徑。對于多目標復雜地形來說，則需要初始化一個空的帕累托最優(yōu)解集。

2.2 遺傳操作

2.2.1 選擇和交叉

錦標賽選擇法[19]是一個根據適應度對比結果選擇的過程，隨機從種群中選擇個體，這些個體之間相互競爭，適應度值高的個體獲勝并被選擇用于遺傳算法的進一步處理。這種方法的優(yōu)點是時間復雜度為ο(n)，相較于其他選擇策略較低，易于并行實現，且不需要調整適應度參數。交叉的方式選擇多點交叉。

2.2.2 適合度

當路徑長度被最小化時，一個可行的路徑的適合度可以如下表示：

f1(x)=n2-ncell

(6)

式中：ncell是指從開始到結束的過程中穿過的單元格的數量。如果路徑因障礙物相交而不可行的，則對其適合度進行如下懲罰：

(7)

式中：ncoll是道路上與障礙物碰撞的次數。

這種碰撞懲罰允許根據碰撞次數和路徑的長度對不可行的路徑進行“分層”。最后，如果該路徑不可行，因為它超出范圍或未在最終單元格中結束，則該路徑的適用性很低，為:

f1(x)=1

(8)

當復雜情況下來求解路徑，需要再添加一個適應度函數：

(9)

對于不可行的路徑同樣加入懲罰因子：

(10)

2.2.3 粒子群變異算子

粒子優(yōu)化算法的數學描述如下[20]：假設搜索空間的維數為D，粒子數為n，向量Si=(si,1,si,2,…,si,D)表示第i個粒子的位置，pBesti=(pi,1,pi,2,…,pi,D)是當前搜索到的粒子的最佳位置，這個粒子群的最佳位置表示為gBesti=(g1,g2,…,gD)，向量Vi=(vi,1,vi,2,…,vi,D)是第i個粒子的位置變化率，每個粒子都會根據式(12)更新其位置。

vi,d(t+1)=w×vi,d(t)+c1×r1()×

[pi,d(t)-si,d(t)]+c2×

r2()×[gi(t)-si,d(t)]

(11)

(12)

式中：t為進化的代數；c1和c2是加速度系數參數，用來控制粒子做最大的步進；r1()和r2()是隨機函數，其范圍為[0,1]；w是慣性權重。

本文將粒子群方法用于變異算子的改進，首先，將種群劃分為n個大小不同的子種群，迭代了k次之后，則種群可以表示為Pk={xk,1,xk,2,…,xk,n}，根據式(11)和式(12)對變異算子進行了重構，重構粒子群公式來作為變異算子，形式如下：

Δxmax,i(k+1)=Δxmax,i(k)+

c1×r1()×(xmax,i-xk,i)+

c2×r2()×(Xmax,i-xk,i)

(13)

xk+1,i=xk,i+Δxmax,i(k+1)

(14)

按式(15)來求解xmax,i的累計差。

Δxmax,i(k-1)+

(15)

式中：粒子群算法中的si,d由xk,n代替；pi,d由Pk中第i個子種群上的歷史最優(yōu)xmax,i來替換；gi由整個子種群的歷史最優(yōu)Xmax,i來替換；vi,d由Δxmax,i來替換；Δxmax,i是xmax,i的累計差的算術平均值。式(13)用來預測變異的方向和幅度，在突變之前進行預測，可以克服傳統(tǒng)遺傳算法中突變算子的隨機性和盲目性，有效地提高種群中個體對進化環(huán)境的適應性，避免過早收斂。在式(14)中則表示進行變異操作。

2.2.4 修復過程

經過交叉和突變步驟后，會產生大量的不可行路徑。因此，根據圖2描述的修復機制，嘗試將不可行的路徑修復為一條可行的路徑。

圖2 修復機制遺傳算法流程

該過程的詳細描述如下：修復機制研究迭代過程中的所有不可行路徑，并確定其無效的原因。首先，判斷是否是“越界”修復，因為這個過程可能導致“未終止”和“碰撞”問題。然后判斷“未終止”的問題，這個過程可能導致新的碰撞沖突。最后，判斷路徑上的碰撞。不是所有的路徑都能完全修復，不可行的路徑加入懲罰因子被重新注入新的種群中，以保持一個固定的規(guī)模的種群。(1) 越界修復，導致出界的操作分別被X單調路徑和Y單調路徑的一個水平或垂直步驟所替代。(2) 非終止修復，最后一個操作被更改，以便路徑在結束單元格處結束。修復過程分別填充X單調路徑和Y單調路徑的最后一列或最后一行中的剩余單元格，以關閉該路徑。(3) 碰撞修復，從開始的單元格開始，修復過程中嘗試通過更改先前的操作來避免碰撞。然后更改下一個動作，以填充丟失的單元格并與路徑的其余部分重新連接，重建路徑并檢查是否有新的碰撞。(4) 修復過程會在碰撞過程中反復進行，直到所有碰撞都可以避免或無法修復為止。

3 仿真結果

3.1 單目標簡單環(huán)境

為了驗證本文改進方法的可行性和有效性，對該改進遺傳方法進行了仿真實驗，經過50次迭代的路徑效果以及最優(yōu)路徑長度與平均路徑長度隨迭代變化如圖3和圖4所示。

圖3 “20×20”地圖

圖4 路徑長度變化

為了評估改進的遺傳算法性能，將其與傳統(tǒng)遺傳算法、文獻[16]、文獻[17]進行對比。傳統(tǒng)遺傳算法在每一代根據適應度均勻采樣一個新的個體種群, 因此效果不好。本文算法與傳統(tǒng)遺傳算法、文獻[16]初始種群均為100，根據文獻[17]描述選擇初始種群為60,并對它們都進行100次的迭代。如圖5和圖6所示，在這些地圖上，繪制出了本文改進遺傳算法、傳統(tǒng)遺傳算法、文獻[16]、文獻[17]尋找的路徑。

圖5 “窄谷”地圖

圖6 “迷宮”地圖

結果是對100次運行的結果取平均值，并匯總在表2中。

表2 算法在不同地圖的比較

對于“窄谷”和“迷宮”圖，圖7和圖8分別顯示了傳統(tǒng)遺傳算法、文獻[16]算法、文獻[17]和本文算法相對于迭代數的最佳路徑長度的演變。

圖7 “窄谷”地圖路徑長度變化

圖8 “迷宮”地圖路徑長度變化

可以看出，本文改進遺傳算法在尋找可行路徑方面性能更好。在圖7中，它需要大約33代來找到一個可行的路徑，比傳統(tǒng)遺傳算法更快地縮短了路徑的長度，本文算法比傳統(tǒng)遺傳算法大約縮短了7個單元格，比文獻[16]大約縮短了3個單元格，比文獻[17]大約縮短了3個單元格。這在圖8中更加清晰，對于更復雜的“迷宮”地圖，即使經過100次隨機種群初始化，傳統(tǒng)遺傳算法也很難找到一條最優(yōu)可行的路徑。文獻[16]隨著地圖的復雜，因為RRT算法前期搜索路徑，會耗費較長的時間；文獻[17] 結合了目標點方向因子，加快了迭代速度，但因為初始種群規(guī)模過小以及迭代過程中種群多樣性的降低，容易造成早熟收斂；本文算法通過粒子群變異算子以及加入懲罰因子避免了過早收斂，同時修復機制保證了迭代過程中種群多樣性，所以路徑尋優(yōu)方面更具優(yōu)勢。在“迷宮”地圖中，平均而言，改進遺傳算法的可行路徑比傳統(tǒng)算法約短17個單元格，比文獻[16]得到的路徑約短了8個單元格，比文獻[17]約短了4個單元格。

此外,從表2可以看出，改進的遺傳算法的最優(yōu)路徑比例遠高于傳統(tǒng)遺傳算法，并且相對于文獻[16]和文獻[17]在最優(yōu)路徑比例方面也要高，當地形變得復雜時，最優(yōu)路徑的比例越高，效果越好。

3.2 多目標復雜地形

對于矩陣的線性組合，最優(yōu)控制算法只輸出一個最優(yōu)路徑，而復雜地形給出了一組可以選擇的帕累托最優(yōu)路徑。

在尺寸n=51的地圖上測試了復雜地形，如圖9所示。連續(xù)的地圖展示了不同海拔高度的表面，以及不能交叉的山峰和低谷。為了在這個地圖上運行改進的遺傳算法，連續(xù)地圖被預處理成一個2D占用網格，如圖10所示。將山峰和孔洞轉換為固體障礙物，然后將高度歸一化調整為0到1之間。最后計算單元的難度為對應區(qū)域的平均高度。

圖9 連續(xù)3D地圖

圖10 2D占有網格

運行復雜地圖之后，從帕累托最優(yōu)解集中提取了兩個特定路徑，它們分別滿足不同的目標，其中a路徑長度為90，困難度為21.92。b路徑長度為102，困難度為4.78。從圖10可以看出通過改進遺傳算法在多目標復雜環(huán)境下路徑規(guī)劃中可以獲得不同的路徑解。

4 結 語

綜上，本文針對傳統(tǒng)遺傳算法中存在的問題，提出改進的遺傳算法，算法考慮了單目標和多目標路徑規(guī)劃情況，經過仿真實驗，證明了改進后的算法的可行性和有效性，綜合來說本文具有以下特點：(1) 路徑表示采用了二進制編碼的方式，方便了后續(xù)的遺傳操作，便于理解和實施。(2) 用粒子群優(yōu)化算法重構變異算子，加大算法前期搜索有效解的數目，有利于提升遺傳算法效率，避免局部最優(yōu)。(3) 對適用性加入了懲罰因子，對每代個體根據適應度進行懲罰進一步提高全局搜索能力，避免陷入局部最優(yōu)。(4) 加入修復機制，解決由于交叉和突變產生大量的不可行路徑，維持種群的規(guī)模和多樣性。(5) 對單目標和多目標路徑規(guī)劃都進行了描述，提高了算法的可擴展性。