謝玉龍，王 直

(江蘇科技大學(xué) 電子信息學(xué)院，江蘇 鎮(zhèn)江 212003)

0 引 言

隨著船舶智能化的發(fā)展，人們對(duì)船舶路徑規(guī)劃和動(dòng)態(tài)避障的要求越來(lái)越高。由于海洋環(huán)境的復(fù)雜性(包括風(fēng)浪、船舶、危險(xiǎn)海域等)，船舶在海上航行可能會(huì)出現(xiàn)各種各樣的危險(xiǎn)，所以路徑規(guī)劃是船舶航行過(guò)程的重要環(huán)節(jié)。船舶路徑規(guī)劃是在一定的障礙環(huán)境中，按照一定的性能指標(biāo)(距離最短、時(shí)間最短或者消耗最少等)，為船舶規(guī)劃出從起點(diǎn)到終點(diǎn)的最優(yōu)無(wú)碰撞路徑[1]。

路徑規(guī)劃是近年來(lái)的研究熱點(diǎn)，比較流行的路徑規(guī)劃方法有：蟻群算法、人工場(chǎng)勢(shì)法、神經(jīng)網(wǎng)絡(luò)、遺傳算法等。每一種算法都有各自的優(yōu)缺點(diǎn)。例如，遺傳算法是一種全局尋優(yōu)算法，具有魯棒性、適應(yīng)能力強(qiáng)等優(yōu)點(diǎn)，而標(biāo)準(zhǔn)遺傳算法又存在早熟、陷入局部最優(yōu)、尋優(yōu)時(shí)間長(zhǎng)等問(wèn)題，輸出的最優(yōu)解有時(shí)不能完美地應(yīng)用到實(shí)際中[2]，同時(shí)保證不了對(duì)路徑規(guī)劃的計(jì)算效率和可靠性的要求[3]。為了提高路徑規(guī)劃問(wèn)題的求解質(zhì)量和求解效率，文中在傳統(tǒng)遺傳算法的基礎(chǔ)上，提出了一種改進(jìn)的遺傳算法，即在原有遺傳算法五元素(選擇操作、交叉操作、變異操作、編碼解碼、適應(yīng)度評(píng)價(jià))的基礎(chǔ)上增加了復(fù)原操作、重構(gòu)操作和錄優(yōu)操作。另外，在傳統(tǒng)遺傳算法基礎(chǔ)上增加了新的基本操作，又增加了插入和刪除算子來(lái)降低尋優(yōu)時(shí)間和減少搜索空間，并在此基礎(chǔ)上對(duì)生成的路徑進(jìn)行平滑處理[4]。最后通過(guò)仿真實(shí)驗(yàn)來(lái)驗(yàn)證該算法的有效性和可行性。

1 改進(jìn)型遺傳算法

標(biāo)準(zhǔn)遺傳算法GA包括以下五個(gè)元素：GA={Se,Cr,Mu,Ed,fv}，其中Se為選擇操作，Cr為交叉操作，Mu為變異操作，Ed為編碼、解碼操作，fv為適應(yīng)度評(píng)價(jià)。

新的遺傳算法加入了新的元素：GA={Se,Cr,Mu,Ri,Rd,Rs,Rc,Rb,Rm,Ed,fv}。

適應(yīng)度表示：

f(i,t)=f(xi(t))表示第i個(gè)個(gè)體xi(t)的適應(yīng)度；

fm(t)=max{f(i,t)}表示t時(shí)刻的最優(yōu)適應(yīng)度；

fm為計(jì)算機(jī)中存儲(chǔ)的錄優(yōu)適應(yīng)度。

新增元素的含義如下：

插入操作Ri：初始化種群后，通過(guò)插入操作生成連續(xù)的可行路徑。

刪除操作Rd：在保證種群連續(xù)性的基礎(chǔ)上，刪除重復(fù)冗余的路徑。

復(fù)原操作Rs：由于交叉和突變操作有一定的隨機(jī)性，當(dāng)交叉和突變失敗時(shí)，恢復(fù)到操作之前的種群狀態(tài)。

重構(gòu)操作Rc：當(dāng)交叉和變異操作出現(xiàn)多次失敗時(shí)，證明初始化生成種群的質(zhì)量不高，則重新構(gòu)造質(zhì)量不高的種群。

錄優(yōu)操作Rb：當(dāng)交叉和突變操作成功時(shí)，利用較優(yōu)適應(yīng)度代替存儲(chǔ)的原有適應(yīng)度，保證種群朝著最優(yōu)解的方向進(jìn)化。

平滑操作Rm：使最終生成的最優(yōu)路徑變得平滑，路徑的轉(zhuǎn)彎角度盡可能小，這樣最優(yōu)路徑在船舶實(shí)際航行時(shí)具有一定的現(xiàn)實(shí)意義。

其中，Ri、Rd是為了生成連續(xù)的路徑，并使路徑朝著目標(biāo)點(diǎn)方向運(yùn)動(dòng)；Rs、Rc是為了促進(jìn)搜索的遍歷性，增加算法的搜索范圍，盡可能搜索到全局路徑；Rb的作用是取代計(jì)算機(jī)中存儲(chǔ)的錄優(yōu)適應(yīng)度值，即fm:fm(t)→fm；Rm的作用是使生成的最優(yōu)路徑具有現(xiàn)實(shí)意義。

2 遺傳算法船舶路徑規(guī)劃

這里障礙船的速度位置信息和個(gè)數(shù)可以由激光雷達(dá)和機(jī)器視覺(jué)確定；在局部的動(dòng)態(tài)路徑規(guī)劃中，假設(shè)船舶的當(dāng)前速度保持不變，而各障礙船也是以當(dāng)前速度做勻速直線運(yùn)動(dòng)，由于在局部路徑規(guī)劃中，控制周期很小，所以在路徑規(guī)劃過(guò)程中，可以把障礙船看作勻速直線運(yùn)動(dòng)，那么船舶與障礙船的相遇點(diǎn)就能提前確定，并將該點(diǎn)設(shè)為障礙點(diǎn)。

所以，文中船舶的路徑規(guī)劃是在一張障礙物分布和海拔高度都已知的一幅二維地圖上進(jìn)行的，在該地圖上尋找一條路徑最短，同時(shí)又能夠避開(kāi)障礙物的一條平滑航線。為了簡(jiǎn)化討論，將船舶看做一個(gè)無(wú)體積的質(zhì)點(diǎn)來(lái)處理，同時(shí)障礙物周?chē)鷶U(kuò)展船舶的半徑加上船舶能夠安全航行的最大距離為d。

2.1 路徑編碼

在遺傳算法中，編碼是生成初始化群體的基礎(chǔ)，編碼長(zhǎng)度是影響算法收斂速度和搜索時(shí)間的重要因素[5-6]，因此文中選擇一種簡(jiǎn)化的編碼技術(shù)。船舶航線可以看作由起點(diǎn)、終點(diǎn)以及一系列中間點(diǎn)組成的一維路徑，編碼技術(shù)如圖1所示。起始點(diǎn)即船舶航行的初始位置為O，目標(biāo)點(diǎn)是船舶要到達(dá)的目的地，路徑規(guī)劃的路線就是在起始點(diǎn)和目標(biāo)點(diǎn)之間，在約束范圍內(nèi)確定中間點(diǎn)時(shí)序的坐標(biāo)，其結(jié)構(gòu)為：(x0,y0)→(x1,y1)…(xi,yi)→(xn,yn)。其中，(x0,y0)是起點(diǎn)坐標(biāo)，(xi,yi)(i=1,2,…,n-1)是終點(diǎn)坐標(biāo)，(xi,yi)(i=1,2,…,n-1)是起點(diǎn)和終點(diǎn)之間的一系列中間點(diǎn)，路徑的起點(diǎn)和終點(diǎn)是固定的，只需要對(duì)中間點(diǎn)進(jìn)行編碼。在大地坐標(biāo)系xoy中，路徑點(diǎn)坐標(biāo)是二維的，為了降低編碼復(fù)雜度，對(duì)坐標(biāo)進(jìn)行變換，新坐標(biāo)系為XOY[7]。在新的坐標(biāo)系中，將起點(diǎn)到終點(diǎn)的連線作為X軸，然后在起點(diǎn)和終點(diǎn)之間把X軸平分為X1,X2,…,Xn-1，則在新的坐標(biāo)系XOY中，路徑點(diǎn)就簡(jiǎn)化為一維的Y軸編碼問(wèn)題。

圖1 編 碼

2.2 初始化種群

對(duì)遺傳算法進(jìn)行最優(yōu)航線設(shè)計(jì)時(shí)，首先要初始化種群，初始化種群是在全局范圍內(nèi)隨機(jī)搜索轉(zhuǎn)向點(diǎn)，隨機(jī)產(chǎn)生航線路徑。其中，該路徑包括可行路徑和不可行路徑，這樣增加了最優(yōu)路徑的搜索范圍和時(shí)間。由于前面改變了路徑的編碼方式，將xoy坐標(biāo)映射到XOY上，X軸的路經(jīng)點(diǎn)已經(jīng)全部確定，即X1,X2,…,Xn，所以只需在Y軸坐標(biāo)隨機(jī)產(chǎn)生路經(jīng)點(diǎn)即可。另外，環(huán)境越復(fù)雜，轉(zhuǎn)向點(diǎn)越多，產(chǎn)生的航向越復(fù)雜，因此就采用變長(zhǎng)的編碼技術(shù)，編碼的長(zhǎng)度確定了對(duì)初始化種群操作的速度和時(shí)間。當(dāng)編碼長(zhǎng)度過(guò)長(zhǎng)時(shí)，轉(zhuǎn)向點(diǎn)數(shù)目會(huì)占用太多的資源，因此要設(shè)定一個(gè)最大的編碼長(zhǎng)度Nmax，種群中產(chǎn)生的每個(gè)個(gè)體最大長(zhǎng)度m必須滿足：2≤m≤Nmax。

初始化種群步驟如下：

(1)隨機(jī)生成n條染色體，保證開(kāi)頭和結(jié)尾在路徑上，障礙物柵格不在規(guī)劃路徑上；

(2)對(duì)生成的每條染色體進(jìn)行插入操作；

(3)對(duì)完成插入操作后的染色體進(jìn)行刪除操作；

(4)選擇所有生成連續(xù)路徑的染色體。

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

適應(yīng)度函數(shù)是影響算法的收斂性和穩(wěn)定性的重要因素，適應(yīng)度函數(shù)的選擇決定了種群的進(jìn)化方向和進(jìn)化效率，所以，適應(yīng)度函數(shù)的選擇就顯得至關(guān)重要。船舶的路徑規(guī)劃就是在起點(diǎn)和終點(diǎn)之間找到一條最短的、安全的路徑。評(píng)價(jià)該路徑優(yōu)劣的標(biāo)準(zhǔn)有多種，其中一條安全無(wú)碰撞路徑是航線的前提，同時(shí)還受船舶自身體積的限制，航線應(yīng)盡可能短，轉(zhuǎn)角盡可能少，轉(zhuǎn)彎角度也要盡可能小。因此，文中對(duì)適應(yīng)度函數(shù)的選擇考慮三個(gè)因素：路徑長(zhǎng)度、轉(zhuǎn)向個(gè)數(shù)和轉(zhuǎn)向角度大小[8-9]。

2.3.1 路徑安全性評(píng)價(jià)

路徑的安全性是為了保證船舶航線不與障礙物碰撞，即船舶和障礙物保證在安全距離以外。假設(shè)船舶到障礙物的距離為d,船舶航行的安全半徑為r，路徑安全性的評(píng)價(jià)函數(shù)為：

(1)

其中

(2)

即船舶與障礙物之間的距離大于安全距離。

2.3.2 路徑總長(zhǎng)度L

路徑總長(zhǎng)度是船舶從起點(diǎn)到終點(diǎn)的路徑長(zhǎng)度之和。

(3)

其中，d(pi-1pi)是兩轉(zhuǎn)向點(diǎn)pi-1,pi之間的距離，另外也引入了懲罰因子ε，即如果兩轉(zhuǎn)向點(diǎn)不相鄰則對(duì)適應(yīng)度值進(jìn)行懲罰，懲罰函數(shù)如下:

(4)

其中，c=0表示兩轉(zhuǎn)向路點(diǎn)不相鄰，c=1表示兩轉(zhuǎn)向點(diǎn)相鄰，所以評(píng)價(jià)函數(shù)可以表示為：

(5)

2.3.3 路徑平滑度

船舶航行的時(shí)候轉(zhuǎn)彎會(huì)消耗極大的能量，并且在海上以大的拐角轉(zhuǎn)向一般不能實(shí)現(xiàn)，因此設(shè)計(jì)航線時(shí)要考慮船舶航線的平滑度，并且拐角要盡可能小[10]。假設(shè)最大拐角為α/2,路徑平滑度可以用平均拐角M來(lái)衡量。

(6)

其中，αi(i=2,3,…,n-1)表示兩向量(xi-1,yi-1)和(xi,yi)之間的夾角，如圖2所示，α為兩航路點(diǎn)之間的夾角，當(dāng)兩相鄰航路點(diǎn)之間無(wú)拐角時(shí)α=0。所以M越小，表示路徑的平滑度越好，則被選中的概率越大。

圖2 轉(zhuǎn)向角

以上三個(gè)因素都會(huì)影響生成航線的質(zhì)量，所以，對(duì)三個(gè)因素加權(quán)求和來(lái)確定適應(yīng)度函數(shù)。由于加權(quán)系數(shù)并不是恒定的，而是隨著航海環(huán)境的變化不斷變化的，這種情況各個(gè)系數(shù)的加權(quán)系數(shù)就很難確定，因此要盡量減少適應(yīng)度函數(shù)的項(xiàng)數(shù)[11]，又要把各個(gè)條件融合進(jìn)適應(yīng)度函數(shù)，所以選擇以下適應(yīng)度函數(shù)：

f=S/(M·L)

(7)

2.4 遺傳算子

選擇算子：采用輪盤(pán)賭法進(jìn)行選擇。即計(jì)算每條路徑的適應(yīng)度函數(shù)的值fi,fi值越大該路徑越接近最優(yōu)。利用輪盤(pán)賭法選擇出一定的個(gè)體，對(duì)于父代的優(yōu)秀個(gè)體可以采用精英保留策略，來(lái)增加種群的優(yōu)越性。

交叉算子：交叉操作的方法包括單點(diǎn)交叉、多點(diǎn)交叉、均勻交叉等，文中選擇單點(diǎn)交叉的方法，把選擇的染色體序號(hào)打亂，使染色體能夠隨機(jī)分配，然后把相鄰的兩個(gè)染色體根據(jù)交叉概率進(jìn)行交叉，交叉的時(shí)候選擇兩條染色體的相同基因。如果只有一個(gè)基因相同，直接進(jìn)行交叉；如果有多個(gè)基因相同，隨機(jī)選擇一個(gè)基因進(jìn)行交叉[12]。交叉產(chǎn)生的個(gè)體長(zhǎng)度不能超過(guò)Nmax，不能產(chǎn)生回路，如果不符合要求，重新選擇交叉點(diǎn)。

插入算子：插入操作是讓生成的初始路徑變?yōu)檫B續(xù)的路徑。如果生成的初始路徑是連續(xù)路徑，則選擇一條航線的網(wǎng)絡(luò)節(jié)點(diǎn)，然后把節(jié)點(diǎn)周?chē)尚芯W(wǎng)格點(diǎn)插入航線，比較插入之前和之后適應(yīng)度函數(shù)值的大小，若適應(yīng)度值變高，則用新生成航線代替插入前的航線，否則取消插入操作。

刪除算子：刪除操作是在保證路徑可行的基礎(chǔ)上，檢查生成航線是否有重復(fù)行駛的路經(jīng)點(diǎn)，如果存在，則刪除相同序號(hào)航路點(diǎn)之間的冗余序號(hào)[13]，也要把相同節(jié)點(diǎn)中的一起去掉，使網(wǎng)格點(diǎn)變少，適應(yīng)度函數(shù)值提高。

平滑算子：平滑操作只對(duì)可行航線中有拐角的路徑進(jìn)行操作，如圖3所示，a,b,c為航路點(diǎn)，原始航線拐角為β，在執(zhí)行平滑操作時(shí)，選擇a,b和b,c航路點(diǎn)的中點(diǎn)a'和c'，連接a'c'，做第一次平滑操作時(shí)的航線變?yōu)閍a'→c'c，可以看出轉(zhuǎn)向角明顯變小。同理，做第二次平滑操作的航線變?yōu)閍a''→b'→c''c，按照此方法循環(huán)五次可以得到一條平滑的航線a→b'→c。

圖3 平滑操作

2.5 終止條件

終止條件的設(shè)定遵循以下規(guī)則：

(1)強(qiáng)制終止。即當(dāng)進(jìn)化代數(shù)達(dá)到設(shè)定的進(jìn)化代數(shù)T時(shí)，迭代操作被強(qiáng)制終止。

(2)條件終止。即得到的最優(yōu)航線的適應(yīng)度函數(shù)的值趨于恒定值時(shí)，迭代操作被終止[14-15]。

2.6 算法流程

(1)初始化種群，在已知環(huán)境地圖上選取N×N個(gè)網(wǎng)格點(diǎn)，路徑均經(jīng)過(guò)網(wǎng)格點(diǎn)的中心，障礙物網(wǎng)格點(diǎn)除外。

(2)檢查生成路徑是否連續(xù)，如果不連續(xù)執(zhí)行插入使路徑連續(xù)，在保證路徑連續(xù)的基礎(chǔ)上執(zhí)行刪除操作，刪除冗余的路經(jīng)點(diǎn)。

(3)采用輪盤(pán)賭法執(zhí)行選擇操作，計(jì)算種群中個(gè)體適應(yīng)度。

(4)檢查是否滿足終止條件，如果滿足執(zhí)行步驟8，否則執(zhí)行步驟5。

(5)進(jìn)行交叉、變異操作，檢查交叉是否成功，如果成功進(jìn)行錄優(yōu)操作，然后執(zhí)行步驟4。

(6)檢查是否達(dá)到復(fù)原操作的最大次數(shù)，如果是執(zhí)行步驟5，否則執(zhí)行步驟7。

(7)進(jìn)行重構(gòu)操作，跳轉(zhuǎn)到步驟2。

(8)進(jìn)行平滑操作，輸出最優(yōu)路徑。

算法流程如圖4所示。

3 仿真結(jié)果

船舶航行的環(huán)境信息包括在航行區(qū)域內(nèi)的各種障礙物信息(如島嶼，暗礁，禁航區(qū)域，沉船等)和海圖獲得的水的深淺信息。在航行區(qū)域內(nèi)把障礙物信息和航行的淺水區(qū)分別用不同規(guī)則的多邊形表示。為了驗(yàn)證改進(jìn)算法的可行性和有效性，在Visual Studio C++環(huán)境下對(duì)算法進(jìn)行仿真實(shí)驗(yàn)。遺傳參數(shù)設(shè)置為：種群大小100，交叉概率和變異概率分別為0.7和0.01。

圖4 算法流程

根據(jù)不同的海域，選取兩種航海環(huán)境，分別對(duì)傳統(tǒng)遺傳算法和改進(jìn)后的遺傳算法進(jìn)行仿真，結(jié)果如圖5和圖6所示。

圖5 環(huán)境a仿真結(jié)果

圖6 環(huán)境b仿真結(jié)果

可以看出，在不同的航海環(huán)境中，改進(jìn)的遺傳算法均能找到可行的最優(yōu)平滑路徑。對(duì)兩種算法進(jìn)行大量的實(shí)驗(yàn)，運(yùn)行結(jié)果如表1、表2所示。從兩種環(huán)境的運(yùn)行結(jié)果可以看出，改進(jìn)后遺傳算法，無(wú)論在路徑搜索時(shí)間還是路徑長(zhǎng)度都優(yōu)于傳統(tǒng)遺傳算法。

表1 環(huán)境a運(yùn)行結(jié)果

表2 環(huán)境b運(yùn)行結(jié)果

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

文中對(duì)遺傳算法進(jìn)行擴(kuò)展和改進(jìn)，增加了復(fù)原操作、重構(gòu)操作、錄優(yōu)操作，以避免種群陷入局部最優(yōu)解，使算法盡早收斂于全局最優(yōu)解。引入插入算子、刪除算子和平滑算子，提高種群的進(jìn)化效率，增加算法的現(xiàn)實(shí)意義。將改進(jìn)后的算法應(yīng)用于船舶的路徑規(guī)劃，仿真實(shí)驗(yàn)證明，改進(jìn)遺傳算法在不同的環(huán)境中都能快速收斂于最優(yōu)解，并且生成路徑的標(biāo)準(zhǔn)明顯優(yōu)于傳統(tǒng)遺傳算法。