基于彈性網(wǎng)格的改進(jìn)遺傳算法在無(wú)人艇路徑規(guī)劃中的研究

余文曌， 佘航宇， 歐陽(yáng)子路

(1. 武漢理工大學(xué) a. 交通學(xué)院; b. 物流工程學(xué)院，武漢 430063; 2. 上海交通大學(xué) a. 海洋工程國(guó)家重點(diǎn)實(shí)驗(yàn)室； b. 海洋智能裝備與系統(tǒng)教育部重點(diǎn)實(shí)驗(yàn)室， 上海 200240)

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

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

1 環(huán)境模型的建立

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

2 遺傳算法的改進(jìn)及實(shí)現(xiàn)方法

2.1 路徑編碼

對(duì)于個(gè)體路徑采用十進(jìn)制橫、縱坐標(biāo)簡(jiǎn)單獨(dú)立編碼，其具體結(jié)構(gòu)為

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

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

(1)

式(1)中：Xi為第i條路徑全部橫坐標(biāo)編碼；Yi為該路徑全部縱坐標(biāo)編碼。示例路徑見圖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為路徑轉(zhuǎn)向點(diǎn)。

2.2 適應(yīng)度函數(shù)

在全局路徑規(guī)劃過(guò)程中需選取合適的適應(yīng)度函數(shù)，即將目標(biāo)函數(shù)作為評(píng)價(jià)群體中路徑優(yōu)劣的標(biāo)準(zhǔn)和依據(jù)。[6]適應(yīng)度函數(shù)的建立應(yīng)綜合考慮安全性與經(jīng)濟(jì)性，需滿足以下條件：與障礙物無(wú)干涉、路徑長(zhǎng)度盡可能短和各轉(zhuǎn)向角要盡可能小。這里綜合考慮3個(gè)條件作為適應(yīng)度函數(shù)的評(píng)價(jià)標(biāo)準(zhǔn)。

2.2.1路徑長(zhǎng)度

(3)

式(3)中：len為個(gè)體路徑總長(zhǎng)度；m為權(quán)重因子，用以調(diào)整路徑長(zhǎng)度評(píng)價(jià)在總體適應(yīng)度評(píng)價(jià)中的權(quán)重大??；L為起始點(diǎn)到目標(biāo)點(diǎn)直線近似距離。

2.2.2路徑轉(zhuǎn)角

(4)

式(4)中：n為權(quán)重因子用以調(diào)整路徑轉(zhuǎn)角評(píng)價(jià)在總體適應(yīng)度評(píng)價(jià)中的權(quán)重大??；aveangle為路徑平均轉(zhuǎn)角；θ為無(wú)人艇最大舵角，取35°。

2.2.3路徑安全性

fit3=(1-0.1×interdots)×k

(5)

式(5)中：interdots為與障礙物有干涉路徑段個(gè)數(shù)；k為適應(yīng)度權(quán)重調(diào)整因數(shù)；綜合適應(yīng)度為Fit=fit3×(fit1+fit2)，即綜合適應(yīng)度函數(shù)為

(1-0.1×interdots)×k

(6)

2.3 算法基本操作

2.3.1選擇操作

傳統(tǒng)遺傳算法采用輪盤賭方法[7]，根據(jù)個(gè)體適應(yīng)度大小選擇優(yōu)秀個(gè)體，為生成子代參與交叉變異操作。然而，交叉變異操作可能導(dǎo)致優(yōu)秀個(gè)體流失。本文采用在父代與交叉變異后的個(gè)體之間同時(shí)進(jìn)行選擇操作，從而獲得子代個(gè)體，以確保優(yōu)秀個(gè)體能進(jìn)化到下一代。

2.3.2交叉操作

采用單點(diǎn)交叉法對(duì)個(gè)體進(jìn)行交叉[8]，以一定的概率選擇路徑A中某單個(gè)路徑點(diǎn)，將該點(diǎn)之后所有路徑與路徑B中相應(yīng)路徑點(diǎn)交換，形成新的個(gè)體路徑。

2.3.3變異操作

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

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

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

采用自適應(yīng)變異算子，根據(jù)各代路徑離散程度，動(dòng)態(tài)調(diào)整變異概率。以相應(yīng)概率選擇個(gè)體某一路徑點(diǎn)，隨機(jī)搜索坐標(biāo)點(diǎn)進(jìn)行替換來(lái)作為新個(gè)體路徑。其自適應(yīng)調(diào)整公式為

Pm=e(-2×varfit)

(7)

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

2.4 動(dòng)態(tài)變換網(wǎng)格密度

傳統(tǒng)遺傳算法搜索空間較大，限制了算法的運(yùn)行效果，且接近最優(yōu)解時(shí)，算法收斂速度降低，相同時(shí)間內(nèi)路徑適應(yīng)度增加不顯著。本文采用彈性網(wǎng)格概念，初步采用低密度網(wǎng)格坐標(biāo)系，減少算法搜索空間；當(dāng)算法接近當(dāng)前最優(yōu)解時(shí)，針對(duì)各轉(zhuǎn)向點(diǎn)增加局部網(wǎng)格密度，將該點(diǎn)的鄰近點(diǎn)構(gòu)成的方形網(wǎng)格進(jìn)一步劃分，且以該網(wǎng)格為新的變異空間，繼續(xù)進(jìn)行算法尋優(yōu)。例如初級(jí)密度網(wǎng)格見圖4，次級(jí)網(wǎng)格密度見圖5，圖中曲線為當(dāng)前路徑，圖中B點(diǎn)為路徑各轉(zhuǎn)向點(diǎn)。

以上述操作為理念，根據(jù)實(shí)際地圖大小及其復(fù)雜程度自定義初始，而網(wǎng)格密度以及網(wǎng)格密度升級(jí)速度降低算法搜索空間，提升算法搜索速度，加強(qiáng)針對(duì)性，以更高效率尋求最優(yōu)路徑。

3 仿真結(jié)果與分析

為驗(yàn)證該算法的可行性，運(yùn)用軟件仿真。利用簡(jiǎn)單海洋環(huán)境地圖，視無(wú)人艇為一質(zhì)點(diǎn)，起始點(diǎn)坐標(biāo)為(0,0)，終點(diǎn)坐標(biāo)為(40,40)。

3.1 自適應(yīng)變異概率對(duì)比分析

為驗(yàn)證自適應(yīng)調(diào)整變異算子的可行性，實(shí)現(xiàn)標(biāo)準(zhǔn)遺傳算法，先取算法定網(wǎng)格密度，初始種群規(guī)模為30個(gè)個(gè)體，迭代次數(shù)為110代，交叉概率為0.9，變異概率為0.2，適應(yīng)度函數(shù)中各變量分別取m=140,L=56,n=20,θ=35,k=0.75，即適應(yīng)度函數(shù)為

(1-0.1×interdots)×0.75

(8)

再取變異概率根據(jù)種群情況自適應(yīng)調(diào)整，其余參數(shù)均取相同。其適應(yīng)度成長(zhǎng)曲線對(duì)比見圖6，最終尋優(yōu)路徑對(duì)比見圖7，其中自適應(yīng)調(diào)整變異概率遺傳算法適應(yīng)度成長(zhǎng)較快，最終穩(wěn)定于5.2左右，收斂效率稍有提高。

3.2 彈性網(wǎng)格概念對(duì)比分析

為驗(yàn)證在標(biāo)準(zhǔn)遺傳算法中加入彈性網(wǎng)格概念的可行性，變異概率根據(jù)種群情況自適應(yīng)調(diào)整，其他數(shù)值均與第3.1節(jié)所述相同，即適應(yīng)度函數(shù)為

(1-0.1×interdots)×0.75

(9)

為更加直觀地了解算法運(yùn)行結(jié)果，另取標(biāo)準(zhǔn)遺傳算法定網(wǎng)格密度，其余參數(shù)均取相同。適應(yīng)度成長(zhǎng)曲線對(duì)比見圖8，算法最終尋優(yōu)結(jié)果對(duì)比見圖9。

其中改進(jìn)遺傳算法于50代左右、80代左右兩次增加局部網(wǎng)格密度。由圖8和圖9可知：改進(jìn)遺傳算法路徑適應(yīng)度在兩次增加局部網(wǎng)格密度后進(jìn)一步升高，最終適應(yīng)度達(dá)到7.6左右，收斂效率有所提高?；具z傳算法在接近最優(yōu)解時(shí)適應(yīng)度成長(zhǎng)速度逐漸降低，適應(yīng)度值于最優(yōu)解附近趨于平穩(wěn)，最終約為5.3。

為進(jìn)一步驗(yàn)證改進(jìn)算法可行性，選用較為復(fù)雜的真實(shí)海洋環(huán)境地圖對(duì)改進(jìn)算法進(jìn)行仿真，算法于第50代、第80代左右增加局部網(wǎng)格密度。最終尋優(yōu)結(jié)果見圖10。其適應(yīng)度成長(zhǎng)曲線見圖11。

由綜合仿真結(jié)果得，在復(fù)雜環(huán)境地圖下，路徑適應(yīng)度于較少代數(shù)內(nèi)部接近于當(dāng)前網(wǎng)格密度下的最優(yōu)路徑解，經(jīng)過(guò)兩次增加網(wǎng)格密度后路徑適應(yīng)度明顯進(jìn)一步上升，最終達(dá)到6.4左右，且所得最終路徑顯然符合可行路徑標(biāo)準(zhǔn)。可知改進(jìn)算法有一定的可行性和有效性，且較標(biāo)準(zhǔn)遺傳算法有較高的收斂效率與較好的尋優(yōu)效果。

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

1) 本文在標(biāo)準(zhǔn)遺傳算法上做出改進(jìn)，加入彈性網(wǎng)格概念，通過(guò)動(dòng)態(tài)變換網(wǎng)格局部密度，達(dá)到減小算法搜索空間，以提高搜索效率的目的；

2) 設(shè)計(jì)了自適應(yīng)調(diào)整變異概率公式，避免算法出現(xiàn)局部最優(yōu)解；

3) 利用軟件仿真，試驗(yàn)結(jié)果表明基于彈性網(wǎng)格的遺傳算法在無(wú)人艇路徑規(guī)劃方面有一定的可行性及有效性。