楊帆， 王健宇,1b， 楊柯， 徐言民

(1. 武漢理工大學(xué) a. 航運(yùn)學(xué)院; b. 內(nèi)河航運(yùn)技術(shù)湖北省重點(diǎn)實(shí)驗(yàn)室, 武漢 430063;2. 安康市漢濱區(qū)交通運(yùn)輸局， 陜西 安康 725000)

0 引 言

近年來，自動(dòng)化技術(shù)被應(yīng)用到交通領(lǐng)域，無人機(jī)、無人艇、無人駕駛汽車等技術(shù)得到了飛速發(fā)展[1-2]。我國長江深水航道工程的實(shí)施和沿江港口的大規(guī)模建設(shè)，使交通流密度增大，局部通航條件更加復(fù)雜。目前船舶在群橋水域[3-4]航行時(shí)，仍然采用傳統(tǒng)的手動(dòng)操舵，而以往船撞橋事故主要是由人的失誤引起的，因此，實(shí)現(xiàn)船舶在多障礙物復(fù)雜水域的自主航行，既是減少船撞橋事故的有效手段，又是急需攻克的技術(shù)難題。

船舶航路規(guī)劃是實(shí)現(xiàn)船舶自主航行的重要前提。船舶航路規(guī)劃問題屬于多維非線性優(yōu)化問題。如果考慮通航水域的動(dòng)態(tài)障礙物，則船舶航路規(guī)劃問題屬于非線性時(shí)變函數(shù)優(yōu)化問題[5]，這對(duì)航路規(guī)劃求解算法的收斂性、時(shí)效性要求很高，傳統(tǒng)算法難以適用。現(xiàn)有群智能算法具有自適應(yīng)、自組織和自學(xué)習(xí)的特點(diǎn)，能夠解決傳統(tǒng)算法難以解決的非線性復(fù)雜問題，在航路規(guī)劃方面具有很好的應(yīng)用前景[6-7]，但運(yùn)用該算法求解得到的多維非線性函數(shù)優(yōu)化問題的解均為近似解，仍然有進(jìn)一步優(yōu)化的空間。

本文通過分析以長江武漢段群橋水域?yàn)榈湫痛淼膹?fù)雜水域通航特征，建立復(fù)雜水域通航環(huán)境模型，然后進(jìn)一步建立復(fù)雜水域航路規(guī)劃數(shù)學(xué)模型。為提高算法求解精度和求解速度，為動(dòng)態(tài)環(huán)境航路規(guī)劃研究奠定基礎(chǔ)，結(jié)合遺傳算法的全局搜索能力和模擬退火算法的局部搜索能力，設(shè)計(jì)了Memetic混合算法，對(duì)所建立的模型進(jìn)行求解，并對(duì)規(guī)劃航路進(jìn)行優(yōu)化處理。

1 航路規(guī)劃模型

1.1 復(fù)雜水域通航環(huán)境特征簡要分析

目前，學(xué)術(shù)界對(duì)于復(fù)雜水域并沒有明確定義。一般來講，復(fù)雜水域具有較為復(fù)雜的水文、交通流、通航條件、船舶狀況等。本文將以群橋水域?yàn)榇淼摹⒋嬖诮嚯x的多個(gè)障礙物的水域視為復(fù)雜水域。

通常情況下，橋區(qū)復(fù)雜水域的橋墩、淺點(diǎn)、沉船等障礙物間距小，障礙物分布無規(guī)律[8]；障礙物的挑流作用使得復(fù)雜水域的水流更加復(fù)雜；考慮安全水深因素，復(fù)雜水域內(nèi)供船舶航行的水域往往被限制；復(fù)雜水域交通流復(fù)雜，船舶操縱難度大，非常容易發(fā)生碰撞事故。

1.2 橋區(qū)復(fù)雜水域通航環(huán)境建模

如果不考慮動(dòng)態(tài)障礙物影響，則以橋區(qū)水域?yàn)榇淼膹?fù)雜水域最主要的障礙物是橋墩。本文假定研究水域障礙物為圓形。考慮障礙物的挑流作用和安全裕度，適當(dāng)?shù)財(cái)U(kuò)大障礙物尺寸，在水域一定范圍內(nèi)隨機(jī)生成大小不同的障礙物，見圖1。

為使規(guī)劃結(jié)果更加直觀，圖1中船舶被視為質(zhì)點(diǎn)，障礙物的半徑被等比例擴(kuò)展，這樣便可保證船舶與障礙物之間的距離仍符合要求。圖1橫、縱坐標(biāo)中的L為船長。

包括起點(diǎn)和終點(diǎn)的所有黑點(diǎn)按順序連接成的折線可表示搜索空間中的某一條路徑，路徑點(diǎn)與障礙物間的距離是判斷航路危險(xiǎn)性的主要依據(jù)。為便于在選取最優(yōu)路徑時(shí)進(jìn)行路徑長度計(jì)算，需要建立通航環(huán)境坐標(biāo)系，將坐標(biāo)系按如下關(guān)系進(jìn)行轉(zhuǎn)換：XOY為原坐標(biāo)系，新坐標(biāo)系為X′O′Y′，路徑點(diǎn)在原坐標(biāo)系和新坐標(biāo)系中的坐標(biāo)分別為(x,y)和(x′,y′)，在原坐標(biāo)系中起點(diǎn)和終點(diǎn)的坐標(biāo)分別為(xs,ys)和(xt,yt),θ為兩個(gè)坐標(biāo)系橫軸的夾角。坐標(biāo)轉(zhuǎn)換關(guān)系見圖2。

圖2 坐標(biāo)轉(zhuǎn)換關(guān)系

路徑點(diǎn)坐標(biāo)在兩個(gè)坐標(biāo)系中的轉(zhuǎn)化公式如下：

(1)

1.3 橋區(qū)復(fù)雜水域航路規(guī)劃數(shù)學(xué)模型

船舶航行最重要的原則是安全、經(jīng)濟(jì)、高效，因此最優(yōu)的航路規(guī)劃就是找到一條從起點(diǎn)(xs,ys)到終點(diǎn)(xt,yt)的與障礙物不相交且長度最短的路徑。本文先求出最短的路徑，再對(duì)其進(jìn)行實(shí)用化處理。按照文獻(xiàn)[9]，航路規(guī)劃數(shù)學(xué)模型為

(2)

式中：L為航路總長；J為航路跟蹤代價(jià)；J1為障礙物威脅代價(jià)；J2為航路長度代價(jià)；wt表示航路上各點(diǎn)的威脅代價(jià)；wl表示每條邊的長度代價(jià)；k為不同航路跟蹤代價(jià)所占的比例，設(shè)定路徑規(guī)劃中障礙物威脅代價(jià)與路徑長度代價(jià)同等重要，故本文k取0.5。

選取起點(diǎn)與終點(diǎn)之間線段的一部分(起始于M，終止于N)，分成10等份，在每個(gè)等分點(diǎn)(共9個(gè)等分點(diǎn))處作MN的垂線。在每條垂線上各選擇一個(gè)點(diǎn)，將這些點(diǎn)按從M到N的順序連成一條航路LMN。當(dāng)船舶沿著航路LMN航行時(shí)，威脅源(障礙物)個(gè)數(shù)為n，則總威脅代價(jià)為

(3)

為方便計(jì)算，在線段MN上取5個(gè)點(diǎn)(見圖3)，按下式計(jì)算航路的障礙物威脅代價(jià)：

(4)

d1,k、d3,k、d5,k、d7,k、d9,k分別表示MN上的第1、3、5、7、9個(gè)等分點(diǎn)與第k個(gè)障礙物中心的距離。

圖3 障礙物威脅代價(jià)示意圖

2 Memetic算法設(shè)計(jì)

2.1 Memetic算法概述

Pablo Moscato于1989年首次提出Memetic算法的概念[10]。Memetic一詞由meme而來，可理解為“文化基因”，因此Memetic算法可稱為文化基因算法[11]。Memetic算法最初的主要思想是在遺傳算法每次迭代后對(duì)所有種群進(jìn)行一次局部搜索，它實(shí)際上是一種混合算法。算法用局部啟發(fā)式搜索來模擬由大量專業(yè)知識(shí)支撐的變異過程，使得遺傳算法的變異得到有效的支撐，從而使算法在某些領(lǐng)域的搜索速度和計(jì)算精度有了極大提高。

2.2 Memetic算法設(shè)計(jì)

實(shí)際上，Memetic算法只是提供了一個(gè)算法框架，是全局搜索策略和局部搜索策略的有機(jī)結(jié)合。本文全局搜索策略采用遺傳算法，局部搜索策略采用模擬退火算法。有關(guān)遺傳算法和模擬退火算法的相關(guān)研究較多，這里不贅述。

通過代碼設(shè)計(jì)，種群在每次更新后都會(huì)在其個(gè)體領(lǐng)域進(jìn)行局部搜索，從而使得算法能夠快速收斂于最優(yōu)解。

遺傳算法中參數(shù)設(shè)置的相關(guān)研究已有很多，本文選擇較為常用的參數(shù)設(shè)置。降溫過程的快慢會(huì)影響模擬退火算法的全局搜索能力與局部搜索能力的平衡[12]。在計(jì)算機(jī)實(shí)現(xiàn)中，如果降溫速度慢，則會(huì)得到令人滿意的解，但如果降溫速度太慢，則其相較于其他簡單的搜索算法不具有明顯優(yōu)勢[13]；如果降溫速度快，則該算法更容易求得局部最優(yōu)解。初始溫度高低也會(huì)影響模擬退火算法運(yùn)行，較高的初始溫度更容易求得全局最優(yōu)解，但會(huì)大大增加算法復(fù)雜度，影響算法的求解時(shí)間。本文的算法更關(guān)注模擬退火算法的局部搜索能力，因此本文設(shè)置的初始溫度較低，降溫速度較快。

3 航路規(guī)劃

根據(jù)上述算法，本文給定障礙物坐標(biāo)分別為(21L，20L)，(26L，55L)，(40L，10L)，(55L，5L)，(55L，30L)，(55L，45L)，(55L，75L)，(73.3L，53.5L),(90.9L， 23.9L)。為增加航路規(guī)劃難度，將航路規(guī)劃的起點(diǎn)和終點(diǎn)設(shè)置在障礙物分布較為集中的連線上，起點(diǎn)坐標(biāo)設(shè)置為(5L，5L)，終點(diǎn)坐標(biāo)設(shè)置為(110L，70L)。分別使用遺傳算法、模擬退火算法和Memetic混合算法進(jìn)行航路規(guī)劃。Memetic混合算法迭代次數(shù)設(shè)置為300，其中模擬退火模塊內(nèi)部迭代次數(shù)設(shè)置為100。求解結(jié)果見圖4和5。

a)Memetic混合算法

b)遺傳算法

c)模擬退火算法圖4 3種算法航路規(guī)劃示意圖

a)Memetic混合算法

b)遺傳算法

c)模擬退火算法圖5 3種算法迭代曲線示意圖

由圖5可以看出，Memetic混合算法能更快地求出最優(yōu)解，算法大約在迭代次數(shù)為150時(shí)穩(wěn)定收斂。

Memetic混合算法既結(jié)合了遺傳算法的全局搜索能力，又在每次迭代過程中利用了模擬退火算法的局部搜索能力，使得算法收斂速度和求解精度有了極大的提高。

4 規(guī)劃航路優(yōu)化

針對(duì)D維優(yōu)化問題，本文設(shè)計(jì)的算法能夠?qū)ふ页鯠維最優(yōu)解。對(duì)應(yīng)本文所建立的規(guī)劃模型，規(guī)劃航路為D維向量加起始點(diǎn)的一組向量。為提高求解精度，常常將D取得比較大，最終求解的航路規(guī)劃問題維數(shù)較多，得到的航路呈現(xiàn)出曲線或者有較多段線段的形態(tài)。另外，由于本文設(shè)計(jì)的算法求解的是目標(biāo)函數(shù)的近似最優(yōu)解，從規(guī)劃結(jié)果圖上可以直接看到規(guī)劃航路在終點(diǎn)附近還存在一定的彎曲度，仍然有優(yōu)化的空間。

利用所建立的模型，所選取的航路為端點(diǎn)(M和N)與9個(gè)節(jié)點(diǎn)所組成的10條線段。一種很簡單的改進(jìn)思想是：所求得的航路是一個(gè)近似最優(yōu)解，在其附近的其他航路應(yīng)該也是相對(duì)較優(yōu)的。因此，可考慮在已經(jīng)規(guī)劃出來的10條線段中，以M點(diǎn)為第1個(gè)點(diǎn)，如果相鄰兩條線段的傾斜角差的絕對(duì)值小于一定的閾值，則可去掉相鄰兩條線段中間的點(diǎn)，兩條線段轉(zhuǎn)化為一條線段，否則這部分航路保持不變。依次進(jìn)行以上操作，直到算法歷經(jīng)所有的11個(gè)點(diǎn)為止。如圖6所示，假設(shè)第1個(gè)點(diǎn)為點(diǎn)k，由點(diǎn)k與k+1、點(diǎn)k+1與k+2，分別確定線段lk,k+1和lk+1,k+2。因?yàn)閘k,k+1與lk+1,k+2的傾斜角差小于給定閾值，所以挖去點(diǎn)k+1，由新的線段l1取代原來的兩條線段lk,k+1和lk+1,k+2，這樣就達(dá)到了減少轉(zhuǎn)向點(diǎn)的目的。接著對(duì)線段l1與線段lk+2,k+3的傾斜角差做上述比較，因?yàn)閘1與lk+2,k+3的傾斜角差值仍小于給定閾值，所以可用新的線段l2取代l1和lk+2,k+3兩條線段。

圖6 航路節(jié)點(diǎn)優(yōu)化示意圖

經(jīng)過試驗(yàn)，傾斜角差閾值的取值對(duì)最終結(jié)果有較大的影響。取閾值分別為5°、10°和15°進(jìn)行試驗(yàn)，發(fā)現(xiàn)當(dāng)閾值為10°時(shí)結(jié)果較為理想。取不同閾值時(shí)的優(yōu)化結(jié)果見圖7。

由圖7b可以看出，最終的優(yōu)化航路由起點(diǎn)、5個(gè)轉(zhuǎn)向點(diǎn)和終點(diǎn)組成，一共有6個(gè)航段。

5 結(jié) 論

針對(duì)復(fù)雜水域船舶航路規(guī)劃問題，建立了通航環(huán)境模型，基于遺傳算法和模擬退火算法設(shè)計(jì)了Memetic混合算法，對(duì)模型進(jìn)行了求解，并從航海實(shí)踐角度對(duì)優(yōu)化結(jié)果進(jìn)行了實(shí)用化處理。實(shí)例驗(yàn)證表明，本文設(shè)計(jì)的算法能夠快速規(guī)劃出給定環(huán)境下的最優(yōu)航路，并可以對(duì)航路進(jìn)行進(jìn)一步實(shí)用化處理，使航路規(guī)劃結(jié)果更具有實(shí)際意義。本文所建立的航路規(guī)劃數(shù)學(xué)模型是將船舶視為質(zhì)點(diǎn)，并未充分考慮船舶自身動(dòng)態(tài)變化，后期航路規(guī)則研究將設(shè)置船舶安全領(lǐng)域、氣象條件等約束條件。

a)閾值為5°

b)閾值為10°

c)閾值為15°圖7 取不同閾值時(shí)的優(yōu)化結(jié)果

參考文獻(xiàn)：

[1] 楊俊超, 史越, 馬海明. 一種人—自動(dòng)化系統(tǒng)協(xié)作的無人機(jī)航跡規(guī)劃方法[J]. 計(jì)算機(jī)測量與控制, 2015, 23(9): 3216-3218, 3224. DOI: 10.16526/j.cnki.11-4762/tp.2015.09.084.

[2] 吳博, 熊勇, 文元橋. 基于速度障礙原理的無人艇自動(dòng)避碰算法[J]. 大連海事大學(xué)學(xué)報(bào), 2014, 40(2): 13-16. DOI: 10.16411/j.cnki.issn1006-7736.2014.02.013.

[3] 徐言民, 楊柯, 關(guān)宏旭, 等. 基于SAPSO算法的群橋水域航路規(guī)劃[J]. 中國航海, 2015, 38(3): 37-40.

[4] 徐言民, 楊柯, 關(guān)宏旭, 等. 基于混合SAPSO算法的簡化群橋水域航路規(guī)劃研究[J]. 武漢理工大學(xué)學(xué)報(bào)(交通科學(xué)與工程版), 2015, 39(3): 455-458. DOI: 10.3963/j.issn.2095-3844.2015.03.001.

[5] 吳劍, 張東豪. 基于卡爾曼濾波和D*算法的動(dòng)態(tài)目標(biāo)航路規(guī)劃[J]. 電光與控制, 2014, 21(8): 50-53. DOI: 10.3969/j.issn.1671-637X.2014.08.011.

[6] 鄒春明, 趙俊超, 楊柯, 等. 基于懲罰-PSO的群橋水域多約束航路規(guī)劃[J]. 中國航海, 2016, 39(2): 67-70.

[7] 馬文耀, 吳兆麟, 楊家軒, 等. 人工魚群算法的避碰路徑規(guī)劃決策支持[J]. 中國航海, 2014, 37(3): 63-67.

[8] 徐言民, 楊柯, 關(guān)宏旭, 等. 群橋水域特征分析及建模研究[J]. 武漢理工大學(xué)學(xué)報(bào)(交通科學(xué)與工程版), 2015, 39(2): 250-253. DOI: 10.3963/j.issn.2095-3844.2015.02.005.

[9] 韓超, 王贏. 一種基于改進(jìn)PSO的無人機(jī)航路規(guī)劃方法[J]. 艦船電子工程, 2014, 34(4): 49-53. DOI: 10.3969/j.issn.1672-9730.2014.04.015.

[10] MOSCATO P. On evolution, search, optimization, genetic algorithms and martial arts: towards Memetic algorithms[R]. Pasadena, USA: California Institute of Technology, 1989.

[11] 劉漫丹. 文化基因算法(Memetic Algorithm)研究進(jìn)展[J]. 自動(dòng)化技術(shù)與應(yīng)用, 2007, 26(11): 1-4, 18.

[12] 姚新, 陳國良. 模擬退火算法及其應(yīng)用[J]. 計(jì)算機(jī)研究與發(fā)展, 1990(7): 1-6.

[13] 宋燕子. 基于模擬退火算法的啟發(fā)式算法在VRP中的應(yīng)用[D]. 武漢: 華中師范大學(xué), 2013.