基于適應度函數的無人船遺傳算法航徑規劃

劉長吉，黃宴委

(福州大學 電氣工程與自動化學院，福州 350116)

0 引言

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

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

1 貝塞爾曲線改進遺傳算法

本節在遺傳算法的初始種群中利用貝塞爾曲線，對初始種群生成的折線路徑進行平滑優化，在適應度函數中添加曲率判斷，以最小轉彎半徑為約束條件設置曲線曲率，利用適應度函數篩選出符合最小轉彎半徑約束的曲線路徑。改進的遺傳算法路徑規劃流程圖如圖1所示。

圖1 改進遺傳算法路徑規劃流程圖

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

1.1 規劃空間表示

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

圖2 規劃空間示例

1.2 染色體編碼和初始種群

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

圖3 染色體示例

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

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

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

(1)

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

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

(2)

優化后的路徑如圖3實線路徑所示。貝塞爾曲線的導數也是由這些路徑點確定的，貝塞爾曲線的一階導數如下所示：

(3)

貝塞爾曲線的高階導數也可以通過計算得到。例如，貝塞爾曲線的二階導數表示為：

P″(t)=

(4)

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

(5)

圖4 初始路徑示例

1.4 適應度函數曲率優化

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

(6)

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

(7)

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

(8)

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

1.5 選擇算子和交叉算子

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

圖5 交叉過程

1.6 變異算子

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

2 仿真實驗與分析

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

圖6 路徑效果對比

圖7 路徑曲率比較

圖8 適應度函數值比較

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

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

3 結束語

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