陳高遠(yuǎn) 宋云雪

(中國(guó)民航大學(xué)航空工程學(xué)院 天津 300300)

0 引 言

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

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

1 構(gòu)型空間

1.1 地圖構(gòu)建

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

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

(1)

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

在單目標(biāo)簡(jiǎn)單地形中表示為：

(2)

多目標(biāo)復(fù)雜地形中表示為：

(3)

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

1.2 路徑表示

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

表1 路徑動(dòng)作編碼

圖1 路徑的二進(jìn)制表示

可以將路徑存儲(chǔ)為固定長(zhǎng)度的二進(jìn)制數(shù)組ε，該數(shù)組的長(zhǎng)度為：

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

(4)

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

2 改進(jìn)遺傳算法

2.1 初始化

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

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

(5)

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

2.2 遺傳操作

2.2.1 選擇和交叉

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

2.2.2 適合度

當(dāng)路徑長(zhǎng)度被最小化時(shí)，一個(gè)可行的路徑的適合度可以如下表示：

f1(x)=n2-ncell

(6)

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

(7)

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

這種碰撞懲罰允許根據(jù)碰撞次數(shù)和路徑的長(zhǎng)度對(duì)不可行的路徑進(jìn)行“分層”。最后，如果該路徑不可行，因?yàn)樗龇秶蛭丛谧罱K單元格中結(jié)束，則該路徑的適用性很低，為:

f1(x)=1

(8)

當(dāng)復(fù)雜情況下來求解路徑，需要再添加一個(gè)適應(yīng)度函數(shù)：

(9)

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

(10)

2.2.3 粒子群變異算子

粒子優(yōu)化算法的數(shù)學(xué)描述如下[20]：假設(shè)搜索空間的維數(shù)為D，粒子數(shù)為n，向量Si=(si,1,si,2,…,si,D)表示第i個(gè)粒子的位置，pBesti=(pi,1,pi,2,…,pi,D)是當(dāng)前搜索到的粒子的最佳位置，這個(gè)粒子群的最佳位置表示為gBesti=(g1,g2,…,gD)，向量Vi=(vi,1,vi,2,…,vi,D)是第i個(gè)粒子的位置變化率，每個(gè)粒子都會(huì)根據(jù)式(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為進(jìn)化的代數(shù)；c1和c2是加速度系數(shù)參數(shù)，用來控制粒子做最大的步進(jìn)；r1()和r2()是隨機(jī)函數(shù)，其范圍為[0,1]；w是慣性權(quán)重。

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

Δ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的累計(jì)差。

Δxmax,i(k-1)+

(15)

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

2.2.4 修復(fù)過程

經(jīng)過交叉和突變步驟后，會(huì)產(chǎn)生大量的不可行路徑。因此，根據(jù)圖2描述的修復(fù)機(jī)制，嘗試將不可行的路徑修復(fù)為一條可行的路徑。

圖2 修復(fù)機(jī)制遺傳算法流程

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

3 仿真結(jié)果

3.1 單目標(biāo)簡(jiǎn)單環(huán)境

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

圖3 “20×20”地圖

圖4 路徑長(zhǎng)度變化

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

圖5 “窄谷”地圖

圖6 “迷宮”地圖

結(jié)果是對(duì)100次運(yùn)行的結(jié)果取平均值，并匯總在表2中。

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

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

圖7 “窄谷”地圖路徑長(zhǎng)度變化

圖8 “迷宮”地圖路徑長(zhǎng)度變化

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

此外,從表2可以看出，改進(jìn)的遺傳算法的最優(yōu)路徑比例遠(yuǎn)高于傳統(tǒng)遺傳算法，并且相對(duì)于文獻(xiàn)[16]和文獻(xiàn)[17]在最優(yōu)路徑比例方面也要高，當(dāng)?shù)匦巫兊脧?fù)雜時(shí)，最優(yōu)路徑的比例越高，效果越好。

3.2 多目標(biāo)復(fù)雜地形

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

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

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

圖10 2D占有網(wǎng)格

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

4 結(jié) 語

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