基于適應(yīng)度函數(shù)的無人船遺傳算法航徑規(guī)劃

劉長(zhǎng)吉，黃宴委

(福州大學(xué) 電氣工程與自動(dòng)化學(xué)院，福州 350116)

0 引言

近年來，無人船得到越來越多的關(guān)注，其中路徑規(guī)劃是無人船研究領(lǐng)域的關(guān)鍵問題之一。路徑規(guī)劃旨在從障礙物環(huán)境中，找到一條從起始位置到目標(biāo)位置的無碰撞可行路徑。關(guān)于路徑規(guī)劃的研究有很多，使用了各種方法。每種方法在不同的環(huán)境中，都有其優(yōu)缺點(diǎn)。遺傳算法最初是由Holland提出的[1]，被認(rèn)為是一種啟發(fā)式的，魯棒性強(qiáng)的優(yōu)化技術(shù)，在大多數(shù)優(yōu)化問題中都能取得較好的效果[2]。Yao Z等人將遺傳算法應(yīng)用于靜態(tài)環(huán)境下移動(dòng)機(jī)器人的路徑規(guī)劃問題中[3]，提出一個(gè)算術(shù)適應(yīng)度函數(shù)和兩個(gè)自定義遺傳算子，結(jié)果表明該方法在簡(jiǎn)單的環(huán)境中能夠較快獲得最優(yōu)解，但在復(fù)雜的環(huán)境中難以獲得最優(yōu)解。Zhang X等人提出一種改進(jìn)的遺傳算法[4]，該方法利用可見空間的概念獲取初始種群，并提出兩種新的變異方法保證算法收斂到全局最優(yōu)解，雖然該方法在復(fù)雜環(huán)境下能獲得最優(yōu)解，但是計(jì)算過于復(fù)雜。Tuncer等人提出一種新的變異算子[5]，該方法從離突變節(jié)點(diǎn)較近的所有自由節(jié)點(diǎn)集合中隨機(jī)選取一個(gè)節(jié)點(diǎn)，然后根據(jù)適應(yīng)度函數(shù)值選取突變節(jié)點(diǎn)，與其他方法相比，該方法的收斂速度較快效果較好。然而上述路徑規(guī)劃方法所生成的路徑都是由線段組成的，并不是光滑的路徑，這將迫使無人船在轉(zhuǎn)折角處停止，轉(zhuǎn)彎，重新啟動(dòng)才能沿著規(guī)劃好的路徑航行[6]。因此必須使路徑變得光滑。近十年來，貝塞爾曲線在光滑路徑規(guī)劃問題中得到越來越多的應(yīng)用[7-9]。Baoye等人提出一種新的移動(dòng)機(jī)器人平滑路徑規(guī)劃遺傳算法[9]，該方法用于尋找最優(yōu)控制點(diǎn)，確定基于貝塞爾曲線的光滑路徑。值得注意的是，這些方法著重于對(duì)遺傳算子的改進(jìn)和路徑光滑程度處理，而未考慮到實(shí)際機(jī)器人的機(jī)動(dòng)性能。由于無人船是一個(gè)高度欠驅(qū)動(dòng)的系統(tǒng)[10]，因此在無人船航徑規(guī)劃中必須考慮無人船的機(jī)動(dòng)性能。

本文提出一種基于適應(yīng)度函數(shù)的無人船遺傳算法航徑規(guī)劃方法。在初始種群中，以染色體的路徑點(diǎn)作為貝塞爾曲線的控制點(diǎn)，利用貝塞爾曲線優(yōu)化方法，將初始的折線路徑變成光滑的曲線路徑；在路徑選擇中，以無人船最小轉(zhuǎn)彎半徑為約束條件，設(shè)置路徑的最大曲率，在適應(yīng)度函數(shù)中添加曲率判斷，利用適應(yīng)度函數(shù)選擇出符合約束條件的曲線路徑。在仿真實(shí)驗(yàn)中，采用基于網(wǎng)格圖的方法構(gòu)建規(guī)劃環(huán)境，驗(yàn)證所提出方法的有效性。

1 貝塞爾曲線改進(jìn)遺傳算法

本節(jié)在遺傳算法的初始種群中利用貝塞爾曲線，對(duì)初始種群生成的折線路徑進(jìn)行平滑優(yōu)化，在適應(yīng)度函數(shù)中添加曲率判斷，以最小轉(zhuǎn)彎半徑為約束條件設(shè)置曲線曲率，利用適應(yīng)度函數(shù)篩選出符合最小轉(zhuǎn)彎半徑約束的曲線路徑。改進(jìn)的遺傳算法路徑規(guī)劃流程圖如圖1所示。

圖1 改進(jìn)遺傳算法路徑規(guī)劃流程圖

將改進(jìn)遺傳算法應(yīng)用在路徑規(guī)劃問題中，主要分為以下幾個(gè)步驟：首先，先構(gòu)建路徑規(guī)劃所需要的規(guī)劃空間；然后根據(jù)染色體的編碼方式生成初始種群；緊接著將生成的初始種群中的染色體經(jīng)過貝塞爾曲線優(yōu)化；然后根據(jù)適應(yīng)度函數(shù)計(jì)算初始種群中染色體的適應(yīng)度值，并根據(jù)染色體適應(yīng)度值的大小對(duì)染色體進(jìn)行選擇；將選擇出的染色體經(jīng)過交叉和變異操作，以產(chǎn)生出適應(yīng)度值更佳的染色體，最后經(jīng)過不斷迭代，當(dāng)?shù)螖?shù)到達(dá)預(yù)期的次數(shù)時(shí)，則停止迭代根據(jù)適應(yīng)度函數(shù)值篩選出最終的最優(yōu)路徑。

1.1 規(guī)劃空間表示

規(guī)劃空間指的是無人船路徑規(guī)劃所需要的環(huán)境區(qū)域，包含障礙物區(qū)域和無障礙物區(qū)域?，F(xiàn)有的路徑規(guī)劃方法大都使用網(wǎng)格圖的方法來表示規(guī)劃空間[4-5,11-12]。如圖2所示，白色網(wǎng)格表示自由區(qū)域，灰色網(wǎng)格表示障礙物區(qū)域。本文采用矩陣編碼的方法來表示網(wǎng)格位置[4]，網(wǎng)格的位置由行索引和列索引決定。例如，b1,3表示第一行第三列的網(wǎng)格位置。

圖2 規(guī)劃空間示例

1.2 染色體編碼和初始種群

染色體表示在路徑規(guī)劃問題中生成的候選路徑。染色體是由起始節(jié)點(diǎn)，目標(biāo)節(jié)點(diǎn)和無人船航行過程中所經(jīng)過的節(jié)點(diǎn)組成。這些節(jié)點(diǎn)通常被稱為染色體的基因。常用的染色體編碼方法主要有二進(jìn)制編碼，浮點(diǎn)數(shù)編碼，十進(jìn)制編碼和字符編碼。本文使用文獻(xiàn)[4]中的編碼方法來表示染色體，該方法對(duì)字符編碼進(jìn)行了一些改進(jìn)，使其不需要解碼，并且能更直觀的表示各個(gè)節(jié)點(diǎn)的位置信息，如圖3所示。

圖3 染色體示例

傳統(tǒng)遺傳算法中初始種群的生成方式一般采用隨機(jī)生成的方法，即隨機(jī)生成一系列染色體。但在路徑規(guī)劃中，這些隨機(jī)生成的染色體可能包含一些不可行的路徑，導(dǎo)致這些路徑與障礙物相交。雖然通過遺傳算子不斷迭代的過程最終也能找到最優(yōu)解或接近最優(yōu)解。但這一迭代過程降低了算法的搜索速度，并增加了算法的計(jì)算時(shí)間。為了解決這個(gè)問題，將從自由區(qū)域中隨機(jī)選擇染色體的節(jié)點(diǎn)。首先在染色體生成之前先獲取障礙物區(qū)域，由于規(guī)劃空間采用矩陣編碼的方法表示，可以快速獲取障礙物的形狀和位置。然后從障礙物區(qū)域以外的自由區(qū)域中隨機(jī)選擇節(jié)點(diǎn)生成初始路徑。如圖3表示初始種群中的一條染色體，其中b1,1表示起始位置，b6,6表示目標(biāo)位置，b4,1，b4,4和b6,4表示所經(jīng)過的路徑點(diǎn)。

1.3 基于貝塞爾曲線的初始種群生成方法

由于遺傳算法生成的路徑是折線路徑，并不是光滑的曲線路徑，如圖4所示。如果無人船沿著規(guī)劃好的折線路徑航行時(shí)，必須在每個(gè)轉(zhuǎn)彎點(diǎn)停下來調(diào)整航向角再重新加速航行，這一過程既占用時(shí)間又損耗機(jī)器性能。因此，必須把折線路徑變成光滑的曲線路徑，使無人船無需停止調(diào)整航向角就能夠沿著規(guī)劃好的路徑航行。本文采用貝塞爾曲線來改進(jìn)初始種群平滑優(yōu)化，貝塞爾曲線是通過線性插值的方法來實(shí)現(xiàn)的，它能簡(jiǎn)潔完美的表達(dá)自由曲線和曲面，在計(jì)算機(jī)圖形學(xué)中得到了廣泛的應(yīng)用。因此，貝塞爾曲線是一種很好的曲線擬合工具。下面將介紹貝塞爾曲線實(shí)現(xiàn)的主要方法，首先將初始種群中染色體的n個(gè)路徑點(diǎn)當(dāng)做貝塞爾曲線的控制點(diǎn)p(j)，j=0,1,2,…,n。如p(j)=(b1,1,b4,1,b4,4,b6,4,b6,6)是初始種群中的一條染色體，p(0)表示染色體中的第一個(gè)路徑點(diǎn)b1,1。貝塞爾曲線由這些路徑點(diǎn)定義如下：

(1)

其中:t是歸一化時(shí)間變量，p(j)=(xj,yj)T表示染色體中第j個(gè)路徑點(diǎn)的坐標(biāo)向量，xj和yj分別對(duì)應(yīng)x坐標(biāo)和y坐標(biāo)的分量，Bj,n(t)是伯恩斯坦基多項(xiàng)式表示貝塞爾曲線中的基函數(shù)，定義如下：

j=0,1,2,...,n

(2)

優(yōu)化后的路徑如圖3實(shí)線路徑所示。貝塞爾曲線的導(dǎo)數(shù)也是由這些路徑點(diǎn)確定的，貝塞爾曲線的一階導(dǎo)數(shù)如下所示：

(3)

貝塞爾曲線的高階導(dǎo)數(shù)也可以通過計(jì)算得到。例如，貝塞爾曲線的二階導(dǎo)數(shù)表示為：

P″(t)=

(4)

在二維空間中，貝塞爾曲線關(guān)于t的曲率表示為：

(5)

圖4 初始路徑示例

1.4 適應(yīng)度函數(shù)曲率優(yōu)化

無人船路徑規(guī)劃問題的目的是從起始位置到目標(biāo)位置之間找到一條最優(yōu)的無碰撞路徑。遺傳算法是通過適應(yīng)度函數(shù)來選擇路徑的，所以在適應(yīng)度函數(shù)中必須考慮路徑的平滑性和可行性。因此適應(yīng)度函數(shù)的選取至關(guān)重要，本文的一個(gè)關(guān)鍵概念是在適應(yīng)度函數(shù)中考慮無人船的機(jī)動(dòng)能力。由于無人船的轉(zhuǎn)彎半徑是有限的，為了保證路徑可行，只需對(duì)路徑的曲率進(jìn)行約束[13]，無人船可行駛路徑的最大曲率可以表示為：

(6)

其中:Rmin是無人船的最小轉(zhuǎn)彎半徑。以此為約束條件，從優(yōu)化后的貝塞爾曲線路徑中篩選出符合最大曲率約束的路徑。遺傳算法是通過適應(yīng)度函數(shù)來選擇路徑的。因此，必須在適應(yīng)度函數(shù)中添加曲率判斷，定義如下：

(7)

d[p(j),p(j+1)]=

(8)

其中:f是適應(yīng)度函數(shù)，p(j)是染色體上的第j個(gè)路徑點(diǎn)，d是兩個(gè)節(jié)點(diǎn)之間的距離，xj和yj表示無人船當(dāng)前的水平和垂直位置，x( j+1)和y( j+1)表示無人船下一個(gè)路徑點(diǎn)的水平和垂直位置，k(t)是貝塞爾曲線的曲率計(jì)算公式，penalty是懲罰值。適應(yīng)度函數(shù)定義為路徑中每個(gè)路徑點(diǎn)之間的距離和路徑的曲率之和。如果路徑與障礙物相交，則在適應(yīng)度函數(shù)中加上一個(gè)懲罰值；如果路徑的曲率k(t)大于最大曲率kmax，則在適應(yīng)度函數(shù)上加上一個(gè)懲罰值，懲罰值必須大于工作環(huán)境中的最大路徑長(zhǎng)度。最后通過適應(yīng)度值的選取來篩選出符合曲率約束的路徑，適應(yīng)度值越小越好。

1.5 選擇算子和交叉算子

選擇算子的主要目的是通過適應(yīng)度函數(shù)值將初始種群中適應(yīng)度值較好的染色體保存下來，并移交給下一代。染色體的選擇過程主要分為三個(gè)步驟：第一步通過適應(yīng)度函數(shù)計(jì)算所有染色體的適應(yīng)度函數(shù)值；第二步將計(jì)算出的適應(yīng)度函數(shù)值按從小到大的順序進(jìn)行排序，并與各自對(duì)應(yīng)的染色體進(jìn)行配對(duì)；第三步是根據(jù)適應(yīng)度函數(shù)值選擇適應(yīng)度值較小的染色體放入交配池中以產(chǎn)生新的染色體。交配池中包含兩個(gè)算子，一個(gè)是交叉算子，一個(gè)是變異算子。下面先介紹交叉算子，交叉算子的目的是交換染色體間的基因以產(chǎn)生新的染色體，避免陷入局部最優(yōu)解。本文采用單點(diǎn)交叉算子，從交配池中隨機(jī)選擇兩個(gè)染色體當(dāng)父代染色體，在父代中隨機(jī)選擇一個(gè)節(jié)點(diǎn)作為交叉點(diǎn)，將交叉點(diǎn)后的兩個(gè)父代染色體的基因相互交換。換句話說就是，第一個(gè)子代染色體是由第一個(gè)父代交叉點(diǎn)前的基因和第二個(gè)父代交叉點(diǎn)后的基因構(gòu)成的。第二個(gè)子代染色體是由第二個(gè)父代交叉點(diǎn)前的基因和第一個(gè)父代交叉點(diǎn)后的基因構(gòu)成的。交叉過程如圖5所示。

圖5 交叉過程

1.6 變異算子

變異算子的目的是增加種群的多樣性，避免過早收斂的現(xiàn)象。本文的變異算子是基于文獻(xiàn)[5]中提出的。在現(xiàn)有的文獻(xiàn)研究中[3,11-12,14]，該算子具有較好的效果。該方法首先從突變的染色體中隨機(jī)選擇一個(gè)不是起始或目標(biāo)節(jié)點(diǎn)的節(jié)點(diǎn)作為突變節(jié)點(diǎn)。然后，定義一個(gè)集合，該集合由突變節(jié)點(diǎn)的所有可行鄰居點(diǎn)組成，由于采用矩陣編碼，可以很快獲得突變節(jié)點(diǎn)的鄰居集合。再依次從鄰居集合中選取一個(gè)節(jié)點(diǎn)代替突變節(jié)點(diǎn)，并計(jì)算所有路徑的適應(yīng)度值。最后，選擇適應(yīng)度值最小的路徑節(jié)點(diǎn)替換原始突變節(jié)點(diǎn)。

2 仿真實(shí)驗(yàn)與分析

本實(shí)驗(yàn)使用Python編程實(shí)現(xiàn)，并運(yùn)行在一臺(tái)Intel Core i7處理器和8 GB內(nèi)存的計(jì)算機(jī)上。為了驗(yàn)證該方法的有效性，將其應(yīng)用于16×16的網(wǎng)格圖中，并與文獻(xiàn)[9]的方法進(jìn)行比較，其中包含12個(gè)障礙物區(qū)域，起始點(diǎn)位置為(1,1)，目標(biāo)點(diǎn)位置為(15,15)。主要參數(shù)如下：無人船最小轉(zhuǎn)彎半徑Rmin=0.2 m，則最大曲率kmax=5 m-1，在[0,1]區(qū)間構(gòu)造具有80個(gè)樣本數(shù)的等差數(shù)列作為伯恩斯坦基多項(xiàng)式t的值，種群大小取80，最大迭代次數(shù)取100，交叉概率為1，變異概率為0.3，對(duì)于每個(gè)不可行路徑的罰值取100。如圖6為遺傳算法、平滑算法和本文方法在相同環(huán)境下形成的路徑比較。從圖中可以看出遺傳算法生成的路徑是折線路徑，并不適合無人船航行。平滑算法只對(duì)路徑進(jìn)行平滑優(yōu)化，并未添加曲率約束。使用本文方法生成的路徑更為平滑，曲率更小。圖7為平滑算法和本文方法生成路徑的曲率比較，從圖中可以看出平滑算法生成的路徑曲率過大，并不能滿足無人船最大曲率約束的曲線曲率，而本文算法生成路徑的曲率明顯小于最大曲率約束，因此可以得出本文方法生成的曲線路徑是符合無人船最小轉(zhuǎn)彎半徑約束的。圖8給出了平滑算法和本文方法每代最優(yōu)染色體的適應(yīng)度函數(shù)值，可以看出本文方法的收斂性更快。表1為平滑算法和本文方法的性能指標(biāo)對(duì)比，性能指標(biāo)有3個(gè)：(1)最大曲率，用來評(píng)估路徑是否符合無人船最小轉(zhuǎn)彎半徑約束，該值小于5表示路徑符合無人船最小轉(zhuǎn)彎半徑約束；(2)平均適應(yīng)度函數(shù)值，該值是路徑長(zhǎng)度和曲率之和，該值越小表示路徑越短。(3)平均搜索時(shí)間，用來評(píng)估算法的時(shí)間性能，該值越小表示算法搜索時(shí)間越快。從表中看出本文方法生成的路徑符合無人船最小轉(zhuǎn)彎半徑約束，平均適應(yīng)度值和平均搜索時(shí)間均優(yōu)于平滑算法，說明本文方法性能更好。

圖6 路徑效果對(duì)比

圖7 路徑曲率比較

圖8 適應(yīng)度函數(shù)值比較

表1 平滑算法與本文算法的性能比較

最大曲率(1/m)平均適應(yīng)度值平均搜索時(shí)間/s平滑算法16.6360.710.76本文方法0.3052.350.59

3 結(jié)束語(yǔ)

本文提出一種基于適應(yīng)度函數(shù)的無人船遺傳算法航徑規(guī)劃方法，為了使遺傳算法生成的折線路徑變成曲線路徑，在遺傳算法初始種群中結(jié)合貝塞爾曲線優(yōu)化方法。在算法中考慮無人船機(jī)動(dòng)性能對(duì)航跡的約束，以最小轉(zhuǎn)彎半徑為約束條件設(shè)置最大曲率，利用適應(yīng)度函數(shù)篩選出符合無人船最小轉(zhuǎn)彎半徑約束的曲線路徑。通過仿真實(shí)驗(yàn)結(jié)果驗(yàn)證了該方法生成的路徑能滿足無人船最小轉(zhuǎn)彎半徑的約束，更有利于無人船跟蹤航行。