基于彈性網格的改進遺傳算法在無人艇路徑規劃中的研究

余文曌， 佘航宇， 歐陽子路

(1. 武漢理工大學 a. 交通學院; b. 物流工程學院，武漢 430063; 2. 上海交通大學 a. 海洋工程國家重點實驗室； b. 海洋智能裝備與系統教育部重點實驗室， 上海 200240)

隨著時代發展，無人艇技術已得到深入發展。無人艇不僅可用于民用領域，比如海上搜救、垃圾清理和環境監測等方面，還可用于軍事上的海上巡邏、偵查、監視和掃雷等方面，具有十分廣泛的應用領域。[1]同時，無人艇路徑規劃對于艦船實現自動化航行和航線優化具有重要意義，要求在復雜的海洋環境中，根據已知的地理信息數據，尋找出一條從起點到終點的最安全且航程最短的航線。[2]目前已有多種算法被應用于路徑規劃，例如粒子群算法[3]、神經網絡算法[4]和人工勢場法。[5]其中遺傳算法較為靈活，使用相對廣泛，已被應用于眾多無人設備的路徑規劃。

遺傳算法現已在路徑規劃方面得到一定的運行效果。但是標準遺傳算法搜索空間一般較大，存在過多多余搜索、導致收斂速度慢和運行時間長等缺陷。例如，文獻[6]和文獻[7]所提的基于柵格地圖的改進遺傳算法中，當柵格密度較大時，搜索空間達數百數千柵格，有較多冗余搜索，影響算法搜索收斂速度。本文在原有遺傳算法的基礎上加入彈性網格概念，采用簡單獨立坐標編碼，通過動態變換地圖網格密度，減小算法搜索空間；同時，加入自適應變異算子，以加速收斂速度。

1 環境模型的建立

在路徑規劃中，需先對環境信息進行描述。由于復雜的海面環境導致算法不能直接被利用，采用坐標法建立海平面二維模型，并將復雜的海面地理信息進行簡化，把障礙物適當擴大安全距離，轉化成簡單的封閉幾何圖形(見圖1)。圖1a)地圖位于印度尼西亞附近海域，由部分島礁組成中心經度為123°38′，緯度為01°57′；圖1b)地圖在坐標平面內以黑色部分表示障礙物，(0，0)為起始點，(40，40)為目標點。

2 遺傳算法的改進及實現方法

2.1 路徑編碼

對于個體路徑采用十進制橫、縱坐標簡單獨立編碼，其具體結構為

Xi(xi1→xi2→…→xik→…→xij)

Yi(yi1→yi2→…→yik→…→yij)

(1)

式(1)中：Xi為第i條路徑全部橫坐標編碼；Yi為該路徑全部縱坐標編碼。示例路徑見圖2，可表示為

X1(0,6,10,12,19,21,25,27,29,35,40)

Y1(0,7,11,14,21,22,23,23,25,33,40)

(2)

式(2)中：B為路徑轉向點。

2.2 適應度函數

在全局路徑規劃過程中需選取合適的適應度函數，即將目標函數作為評價群體中路徑優劣的標準和依據。[6]適應度函數的建立應綜合考慮安全性與經濟性，需滿足以下條件：與障礙物無干涉、路徑長度盡可能短和各轉向角要盡可能小。這里綜合考慮3個條件作為適應度函數的評價標準。

2.2.1路徑長度

(3)

式(3)中：len為個體路徑總長度；m為權重因子，用以調整路徑長度評價在總體適應度評價中的權重大小；L為起始點到目標點直線近似距離。

2.2.2路徑轉角

(4)

式(4)中：n為權重因子用以調整路徑轉角評價在總體適應度評價中的權重大小；aveangle為路徑平均轉角；θ為無人艇最大舵角，取35°。

2.2.3路徑安全性

fit3=(1-0.1×interdots)×k

(5)

式(5)中：interdots為與障礙物有干涉路徑段個數；k為適應度權重調整因數；綜合適應度為Fit=fit3×(fit1+fit2)，即綜合適應度函數為

(1-0.1×interdots)×k

(6)

2.3 算法基本操作

2.3.1選擇操作

傳統遺傳算法采用輪盤賭方法[7]，根據個體適應度大小選擇優秀個體，為生成子代參與交叉變異操作。然而，交叉變異操作可能導致優秀個體流失。本文采用在父代與交叉變異后的個體之間同時進行選擇操作，從而獲得子代個體，以確保優秀個體能進化到下一代。

2.3.2交叉操作

采用單點交叉法對個體進行交叉[8]，以一定的概率選擇路徑A中某單個路徑點，將該點之后所有路徑與路徑B中相應路徑點交換，形成新的個體路徑。

2.3.3變異操作

變異操作在遺傳算法中的作用有：

(1) 增強遺傳算法的局部搜索能力，與選擇和交叉相互配合，可兼顧全局和局部搜所能力；

(2) 保持群體多樣性、避免早熟過早收斂，減少選擇和交叉操作造成的有用信息流失，保證遺傳算法搜索的有效性。[9]

采用自適應變異算子，根據各代路徑離散程度，動態調整變異概率。以相應概率選擇個體某一路徑點，隨機搜索坐標點進行替換來作為新個體路徑。其自適應調整公式為

Pm=e(-2×varfit)

(7)

式(7)中：varfit為各代適應度總體方差大小，以描述該代路徑離散程度。由于在離散程度趨近于0時，路徑適應度變化幅度減小，在相同代數里，總體適應度變化幅度較小，所以實現離散度逐漸接近0時，變異概率加速趨近1，以避免陷入局部最優解。同時，在變異概率內采取對與障礙物有干涉路徑段兩端點采取隨機變異和對隨機尋找的轉向點采取隨機變異等多種變異方式。其變異概率自適應調整函數見圖3。

2.4 動態變換網格密度

傳統遺傳算法搜索空間較大，限制了算法的運行效果，且接近最優解時，算法收斂速度降低，相同時間內路徑適應度增加不顯著。本文采用彈性網格概念，初步采用低密度網格坐標系，減少算法搜索空間；當算法接近當前最優解時，針對各轉向點增加局部網格密度，將該點的鄰近點構成的方形網格進一步劃分，且以該網格為新的變異空間，繼續進行算法尋優。例如初級密度網格見圖4，次級網格密度見圖5，圖中曲線為當前路徑，圖中B點為路徑各轉向點。

以上述操作為理念，根據實際地圖大小及其復雜程度自定義初始，而網格密度以及網格密度升級速度降低算法搜索空間，提升算法搜索速度，加強針對性，以更高效率尋求最優路徑。

3 仿真結果與分析

為驗證該算法的可行性，運用軟件仿真。利用簡單海洋環境地圖，視無人艇為一質點，起始點坐標為(0,0)，終點坐標為(40,40)。

3.1 自適應變異概率對比分析

為驗證自適應調整變異算子的可行性，實現標準遺傳算法，先取算法定網格密度，初始種群規模為30個個體，迭代次數為110代，交叉概率為0.9，變異概率為0.2，適應度函數中各變量分別取m=140,L=56,n=20,θ=35,k=0.75，即適應度函數為

(1-0.1×interdots)×0.75

(8)

再取變異概率根據種群情況自適應調整，其余參數均取相同。其適應度成長曲線對比見圖6，最終尋優路徑對比見圖7，其中自適應調整變異概率遺傳算法適應度成長較快，最終穩定于5.2左右，收斂效率稍有提高。

3.2 彈性網格概念對比分析

為驗證在標準遺傳算法中加入彈性網格概念的可行性，變異概率根據種群情況自適應調整，其他數值均與第3.1節所述相同，即適應度函數為

(1-0.1×interdots)×0.75

(9)

為更加直觀地了解算法運行結果，另取標準遺傳算法定網格密度，其余參數均取相同。適應度成長曲線對比見圖8，算法最終尋優結果對比見圖9。

其中改進遺傳算法于50代左右、80代左右兩次增加局部網格密度。由圖8和圖9可知：改進遺傳算法路徑適應度在兩次增加局部網格密度后進一步升高，最終適應度達到7.6左右，收斂效率有所提高。基本遺傳算法在接近最優解時適應度成長速度逐漸降低，適應度值于最優解附近趨于平穩，最終約為5.3。

為進一步驗證改進算法可行性，選用較為復雜的真實海洋環境地圖對改進算法進行仿真，算法于第50代、第80代左右增加局部網格密度。最終尋優結果見圖10。其適應度成長曲線見圖11。

由綜合仿真結果得，在復雜環境地圖下，路徑適應度于較少代數內部接近于當前網格密度下的最優路徑解，經過兩次增加網格密度后路徑適應度明顯進一步上升，最終達到6.4左右，且所得最終路徑顯然符合可行路徑標準。可知改進算法有一定的可行性和有效性，且較標準遺傳算法有較高的收斂效率與較好的尋優效果。

4 結束語

1) 本文在標準遺傳算法上做出改進，加入彈性網格概念，通過動態變換網格局部密度，達到減小算法搜索空間，以提高搜索效率的目的；

2) 設計了自適應調整變異概率公式，避免算法出現局部最優解；

3) 利用軟件仿真，試驗結果表明基于彈性網格的遺傳算法在無人艇路徑規劃方面有一定的可行性及有效性。