基于改進遺傳算法的島礁區(qū)航路規(guī)劃模型

高邈+史國友+李偉峰+王玉闖

摘要：為解決船舶穿過島礁區(qū)時危險度大、航行難、航路規(guī)劃復雜等問題，提出應用實數(shù)路徑點編碼配合采取精英保留策略的遺傳算法?？紤]船舶的轉向困難性、航程、人為指定經過路徑點以及船舶安全性，建立適應度函數(shù)評價模型。在電子海圖平臺上提取障礙物特征多邊形頂點坐標，規(guī)劃出最佳航路。該算法能解決多約束條件下的多目標優(yōu)化問題。對舟山島礁區(qū)進行實例驗證。結果表明，改進后的遺傳算法能夠解決島礁區(qū)的復雜航路規(guī)劃問題，且實現(xiàn)簡單，收斂速度較快，也不易陷入局部極小值。隨著自動控制技術的不斷發(fā)展，可為船舶在島礁區(qū)的自主航行提供理論支持。

關鍵詞：

遺傳算法； 島礁區(qū)； 航路規(guī)劃； 精英保留

中圖分類號： U692.31

文獻標志碼： A

Shipping route planning model based on improved genetic algorithm

in island and reef areas

GAO Miao， SHI Guoyou， LI Weifeng， WANG Yuchuang

（

a. Navigation College； b. Key Laboratory of Navigation Safety Guarantee， Dalian Maritime

University， Dalian 116026， Liaoning， China）

Abstract：

In order to solve the problems of high risk， difficult navigation and complicated route planning for ships through the island and reef areas， a genetic algorithm is proposed using the real path point coding and the elite reservation strategy. Considering the ship steering difficulty， sailing range， designated path points and ship safety， the fitness function evaluation model is established. Based on the electronic chart system， vertex coordinates of characteristic polygons of obstacles are extracted， and the optimal path is planned. The algorithm can solve the multiobjective optimization issues under multiconstraints. The Zhoushan island and reef area are taken for example. The results show that， the improved genetic algorithm is feasible for the complicated route planning problem of island and reef areas， is of easy implementation and faster convergence， and is not easy to be lost into the local minimum. With the development of automatic control technology， it can provide theoretical support for the autonomous navigation of ships through the island and reef areas.

Key words：

genetic algorithm； island and reef area； shipping route planning； elite reservation

0引言

隨著全球貿易的發(fā)展，水路運輸成為大宗貨物運輸?shù)闹饕绞剑劭谝?guī)劃建設者考慮到保護環(huán)境、節(jié)約運輸成本以及容納更多船舶等要求，將很多港口的建設地點逐步向海上延伸，以島礁區(qū)為基礎平臺建設多個小型港口。[1]以往船舶經過島礁區(qū)時單憑船長經驗，手動進行航路規(guī)劃，而如今船舶在島礁區(qū)航行頻率增加，對航海人員保障航行安全是一個巨大的挑戰(zhàn)。

有關航路規(guī)劃的研究主要集中在機器人、無人機以及導彈制導領域。孫樹棟等[2]運用遺傳算法解決機器人在離散空間的路徑尋優(yōu)問題，但對環(huán)境確定性的要求很高，必須將大量的有關聯(lián)的障礙物全部收納，但障礙物使用的效率卻很低。SUGIHARA等[3]使用二進制編碼，統(tǒng)一個體長度，通過隨機產生障礙物位置和數(shù)目的方式初始化尋優(yōu)問題，但使用格柵化處理必須把握好規(guī)劃精度。周明等[45]將遺傳算法與模擬退火算法結合在一起提出基于遺傳算法的機器人路徑規(guī)劃方法，先采用視覺法產生初始可航路徑，再使用遺傳算法進一步優(yōu)化調整路徑，但在環(huán)境復雜、障礙物數(shù)目較多的情況下，建立鏈接圖很困難。安柏義等[6]使用動態(tài)規(guī)劃法對無人機進行航路規(guī)劃，但其對戰(zhàn)場上環(huán)境的處理過于簡單，因此限制了很多實際上的可行路線。穆曉敏等[7]運用人工勢場的方法對無人機航路進行規(guī)劃，但是收斂速度隨著規(guī)劃空間復雜度的增加而變慢，并且對障礙物的形狀要求很高。

有關船舶的航路規(guī)劃尤其是在特殊的限制性水域進行航路規(guī)劃的研究相對較少，尚未形成體系，還不夠成熟。汪柱等[8]提出基于航路二叉樹的航線智能生成算法，彌補了以往航路生成中的不足，提高了航路規(guī)劃的質量，但其對障礙物二叉樹繞行方案的處理并不完善，計算效率過低。王瑩等[9]提出了基于改進蟻群算法的航路規(guī)劃方法，改進了人工繪制航線費時費力、不夠精確以及應用范圍受限等問題，但蟻群算法的計算成本太高，需要大量數(shù)據支持，還容易發(fā)生停滯現(xiàn)象。鄒春明等[10]提出了基于懲罰粒子群優(yōu)化（Particle Swarm Optimization， PSO）的群橋水域的多約束航路規(guī)劃，但其對障礙物的抽象化較為簡單，全部轉化成縱向間隔相等的圓柱體，簡單地將船舶的航路規(guī)劃問題轉換成求多維函數(shù)極值問題，但群橋障礙物的特點與航路平滑要求的沖突很容易使求解陷入局部極小值或尋優(yōu)停滯。endprint

算法選擇是航路規(guī)劃的核心問題，所選用的遺傳算法是一種啟發(fā)式的搜索尋優(yōu)方法，具有良好的全局尋優(yōu)能力和多目標并行優(yōu)化特性。多數(shù)優(yōu)化算法都是單點搜索算法，很容易陷入局部最優(yōu)解，而遺傳算法是一種多點搜索算法，更有可能搜索到全局最優(yōu)解。遺傳算法在整體搜索上不同于變形的貪婪算法，因此在進行優(yōu)化計算搜索時采用不依賴于梯度問題的振蕩搜索[11]。然而，傳統(tǒng)的遺傳算法存在早熟以及局部搜尋能力差等問題。針對這些問題，采用一種基于精英保留策略的遺傳算法，擴大尋優(yōu)種群數(shù)量，在初始化時隨機生成路徑解決過早成熟的問題，針對交叉算子對單一基因路徑同樣進行評價，保留優(yōu)良基因組，縮短尋優(yōu)時間，對變異算子進行改進，同時引入刪除和插入算子，提高局部搜索能力。

1問題描述

我國的島礁區(qū)大致分為兩類[12]，一類是由珊瑚蟲蛻殼后的遺體所構成的（例如南海島礁區(qū)），另一類是由土石質構成的（例如舟山群島）。本文以舟山群島為例，其特點為：（1）航道多，可選擇性大，超出人工規(guī)劃最優(yōu)能力；（2）航道狹窄、曲折，障礙物多，漁船密度大，需在適應度函數(shù)中加入轉向角因素；（3）障礙物距離較近，容易產生岸推、岸吸的問題[13]，需在適應度函數(shù)中加入安全距離因素；

（4）夜間對船員視覺的影響較大，容易造成船員心理上的恐懼感。

船舶航路規(guī)劃指在特定的條件下，找到一條從初始點A到終點B的最省時、耗油量最少的安全路徑。島礁區(qū)水域的復雜性

對船舶駕駛員的航路規(guī)劃以及操船能力都是不小的考驗[14]。在島礁區(qū)進行航路規(guī)劃是針對多物標、多障礙物的一個非線性優(yōu)化問題，要同時處理多個優(yōu)化目標，在確保航行安全的前提下，追求航程最短，還須考慮船舶實際情況、船舶操縱性能、值班駕駛員航海習慣等。因此，使用遺傳算法非常適合解決這類問題。

2數(shù)據準備及適應度函數(shù)評價模型

2.1數(shù)據準備

2.1.1障礙物數(shù)據準備

為使用遺傳算法計算島礁區(qū)的最優(yōu)路徑，首先需要將航行所涉及的所有障礙物和船舶不可航的淺水區(qū)域抽象成多邊形，并精確地提取出多邊形的頂點坐標。本文基于S57電子海圖平臺輸出多邊形的頂點坐標。為便于進行顯示和標記，將S57數(shù)據通過墨卡托投影變換公式轉換成平面直角坐標：

X=Klntanπ2+B21-esinB1+esinBe/2

（1）

Y=K（L-L0）

（2）

K=NB0cosB0

（3）

K=a′2b′1+e2cos2B0cosB0

（4）

式中：X為平面橫坐標；Y為平面縱坐標；B0為赤道緯度；L0為本初子午線坐標；B為空間緯度坐標；L為空間經度坐標；a′為地球長半軸；b′為地球短半軸；e為地球第一偏心率；NB0為赤道卯酉圈半徑。

基于S57電子海圖平臺，以舟山群島中的小五奎山作為研究對象，其被抽象化后的特征多邊形頂點見圖1。

圖1

小五奎山特征多邊形頂點

2.1.2安全距離確定

在航路規(guī)劃時，航路與障礙物之間需保持最小安全距離。為確保

最優(yōu)解是相對路徑最短的，規(guī)定一個最小安全距離R，使障礙物頂點到規(guī)劃路徑的最短距離大于等于R。圖2為下橫梁島最小安全距離R的確定方式。根據船員正常的航海習慣設定R。一般，在能見度好的情況下，船舶在礁盤的上風方向2～3 n mile處通過[15]。如果船舶在比較狹窄的水域航行，則盡量把定位點設置在水深點處，距離礁盤的最小安全距離不能小于1.5倍船長。

2.2適應度函數(shù)評價模型

2.2.1船舶操縱能力

考慮到利用遺傳算法尋優(yōu)所找出來的路徑有可能在轉角處超出船舶的操縱能力，不符合實際的操船避讓情況，因此在對路徑進行適應度計算時需加入轉向角這一評價指標。為防止因轉向過大而縮短舵機使用壽命，應避免‘S彎轉向，減小船舶在島礁區(qū)航行的操縱難度，將轉向角控制在40°以內[1617]，并且鼓勵多點逐步轉向，避

免大幅度、大角度、單一位置轉向。假定所規(guī)劃的航路存在n個航路點，除去固定設定的初始點和終點，中間包含n-2個航路點，因此就會產生n-2個轉向點。如圖3所示，根據所得的3個連續(xù)航路點坐標，通過式（5）～（7）計算兩兩之間的距離a，b，c，再求解夾角A。

a=（xi+1-xi-1）2+（yi+1-yi-1）2

（5）

b=（xi+1-xi）2+（yi+1-yi）2

（6）

c=（xi-xi-1）2+（yi-yi-1）2

（7）

sin A=absin B

（8）

夾角A越接近180°，船舶所需要的轉向角θi越小。當正弦函數(shù)分布在90°～180°之間時，正弦函數(shù)值與角度之間呈反比關系，因此利用正弦函數(shù)的倒數(shù)作為適應度函數(shù)來代表船舶的轉向角：

F1=n-2k=21sin Ak

（9）

2.2.2值班駕駛員主觀意愿

在航行中為滿足值班駕駛員的各種意愿和要求，可能需要使航路經過某幾個關鍵的點，從而可能導致航路總里程增加，因此在航路設定時，可依照駕駛員的意向加入必經點，并且提高其權值。假定選定的關鍵點為

P14，如果航路經過P14，則T（P14）=1，否則為0。式（10）表示航路是否經過值班駕駛員所設定的路徑點，如果全部符合則函數(shù)值為1，否則為0。

F2=T（Pi）T（Pk）L

（10）

2.2.3航程計算

航程是尋優(yōu)的關鍵性指標，一般情況下值班駕駛員當然希望航程越短越好，同時盡量多經過標注點使航路規(guī)劃時依據點更多，因此利用式（11）將經過的路徑點個數(shù)與航路總長度的比作為適應度函數(shù)進行計算。然而，利用遺傳算法在輸入數(shù)據后進行實際計算時，僅僅是將障礙物抽象成多邊形進行計算，各障礙物頂點之間還存在著是否互相連通的問題。有可能計算出的航程非常短，但進行實際驗證時會發(fā)現(xiàn)路徑穿越障礙物的情況。因此，在對航程進行加權計算時引入鄰接矩陣。用式（12）進行航程計算時引入鄰接判定，如果兩節(jié)點鄰接則=1，否則=10（這使計算出的這條航路的適應度值較小，從而不采納這條航路）。endprint

F3=nn-1i=1Di

（11）

Di=φ（xi-xi-1）2+（yi-yi-1）2

（12）

3島礁區(qū)航路規(guī)劃遺傳算法編寫

3.1實數(shù)路徑點編碼

根據島礁區(qū)障礙物所有頂點坐標的個數(shù)與人為選定的必經點的個數(shù)之和確定航路規(guī)劃的最大值，即航路的容量上限。每個基因都代表一條航路，按照從前至后的順序依次經過編碼中的路徑點，例如38→2→5→7代表從38經過2，然后經過5，最后到達7的路徑。初始路徑點和最后一個路徑點被鎖死，無法進行其他操作。

3.2航路初始化

障礙物的不規(guī)則性導致產生很多特征點。因此，在進行初始化時隨機產生100個初始種群。由于每個種群編碼的容量都是全部障礙物點的個數(shù)，而實際船舶不可能經過所有的點，所以設定50%的編碼位的數(shù)值為零。同時，將固定好的航路分成5個階段，對每個階段根據適應度值大小分別進行判斷排序。

3.3適應度函數(shù)編寫

適應度值的計算直接影響算法的計算時間和效率，因此在設計適應度函數(shù)時必須切合實際，同時考慮船舶操縱能力、值班駕駛員主觀意愿和航程最短這3個重要因素。本文采用加權評分法計算適應度值。這種方法以權值大小體現(xiàn)諸多因素在評價過程中的不同地位和作用。為避免因單位不同而導致適應度值僅由某一項決定，對

Fi（i=1，2，3）進行無量綱化處理：

F′i=Fi-Fi，minFi，max-Fi，min

（13）

獲得的適應度函數(shù)公式為

F=F′2（ω1F′1+ω3F′3）

（14）

3.4選擇算子輪盤賭編寫

利用輪盤賭編碼能使適應度值越大的種群留下來的概率越大。留存概率為

p（i）=F（i）ni=1F（i）

（15）

3.5算法改進核心

3.5.1選擇算子精英保留

相對最優(yōu)航路的可航性極為重要，如果全部隨機打破，將會延長尋優(yōu)時間，故采取精英保留策略，即對每次尋優(yōu)的最優(yōu)前5名，不打破其基因序列，直接保留至下一代。

3.5.2交叉算子

交叉在一定的概率Pc下發(fā)生，交叉形式分3種：

（1）挑選留存下來的兩條路徑，搜尋具有相同路徑點或鄰近路徑點的兩個種群，在重疊點處（交叉點）進行交叉操作。如

12→2→7→33→21→15→44→3和

19→3→22→33→5→21→23→7，

交叉后產生

19→3→22→33→21→15→44→3和

12→2→7→33→5→21→23→7。

（2）隨機挑選兩個種群，在隨機位上直接進行兩兩交叉，產生新種群。如

22→12→34→32→1→5→8→23和

54→2→14→16→5→7→8→33，

交叉后產生

54→2→14→32→1→5→8→23和

22→12→34→16→5→7→8→33。

（3）對評價度較高的基因片段采取保留策略，以免打破優(yōu)良基因。如

19→3→22→33→5→21→23→7和

22→12→34→16→5→7→8→33，

交叉后產生

19→3→22→7→8→33和

22→12→34→16→5→33→5→21→23→7。

3.5.3變異算子

變異在一定的概率Pm下發(fā)生，變異方式有4種：

（1）隨機選定某一種群的某一數(shù)值，對其進行隨機更改。如

12→2→7→33→21→15→44→3，變異后產生

12→2→7→2→21→15→44→3。

（2）隨機選定某一非零點，然后用零替代。如

54→2→14→16→5→7→8→33，變異后產生

54→2→14→0→5→7→8→33。

（3）隨機選定種群中兩個不為零的點進行位置互換。如

22→12→34→16→5→7→8→33，變異后產生

22→7→34→16→5→12→8→33。

（4）隨機選定種群中的某一位置插入一個隨機的鄰接點。如

19→3→22→33→5→21→23→7，變異后產生

19→3→22→24→33→5→21→23→7。

4遺傳算法驗證

選定舟山群島附近的一塊島礁區(qū)，該區(qū)域障礙物繁多，符合試驗要求。如圖4所示為舟山群島的部分區(qū)域。利用文中給出的遺傳算法，采用Visual Studio 2015 C++ 進行編碼運算，路徑初始點為A（29°58.443 7′N，122°02.992 9′E），終點為B（29°59.098 5′N，122°08.521 4′E），種群規(guī)模為150，ω1=0.223，ω3=0.928，Pc在（0.7，0.9）上隨機產生，Pm在（0.03，0.05）上隨機產生。

利用蟻群算法、模擬退火算法、標準遺傳算法和本文改進后的遺傳算法各進行兩次計算，并將結果進行對比來驗證本文算法的高效性和可靠性（見表1）。這些算法都具有隨機性。各算法種群數(shù)都為150個。

從表1可以得出：蟻群算法平均在經過13.760 5 s， 迭代28.5代后收斂，收斂的適應度平均值為0.009 520 125 7；模擬退火算法平均在經過35.003 2 s， 迭代64.5代后收斂；改進遺傳算法平均在經過19.168 6 s， 迭代40代后收斂，收斂的適應度值為0.017 578 231 1。經過對比可以看出：蟻endprint

群算法搜索效率較低，當信息素對蟻群的引導能力不足時很容易出現(xiàn)停滯現(xiàn)象；模擬退火算法頻繁地重新加溫才能避免陷入局部極小值，但不必要的回溫使搜索速度降低，收斂過程太漫長；標準遺傳算法局部尋優(yōu)能力很差，會在局部位置上搜索很久；改進后的遺傳算法在搜索效率和收斂速度上都具有一定的優(yōu)越性。

在實際航行中有船舶采用了圖4中利用改進遺傳算法得到的路徑航行，證明了路徑是可行、有效的。圖4中的其他路徑均有不同程度的缺陷，如路徑過長、轉向角過大、距離島礁區(qū)過近等。

5結束語

為提高船舶頻繁進出島礁區(qū)的安全性，以航路規(guī)劃為切入點，分析島礁區(qū)障礙物和水域環(huán)境等特征，建立適應度函數(shù)評價模型?；谶z傳算法，通過電子海圖平臺提取障礙物關鍵點，對進出島礁區(qū)的船舶進行航路規(guī)劃。該方法能減少以往單憑船長經

驗進行人工航路規(guī)劃的弊端，緩解值班駕駛人員的壓力。通過實際數(shù)據驗證了該方法切實可行，為未來路徑規(guī)劃與自動控制技術相結合，建立島礁區(qū)水域自主航行體系提供理論支持。

參考文獻：

[1]

熊海生. 島礁區(qū)通航環(huán)境安全評估研究[D]. 大連： 大連海事大學， 2014.

[2]孫樹棟， 曲彥賓. 遺傳算法在機器人路徑規(guī)劃中的應用研究[J]. 西北工業(yè)大學學報， 1998， 16（1）： 7983.

[3]SUGIHARA K， SMITH J. Genetic algorithms for adaptive motion planning of an autonomous mobile robot[C]//IEEE International Symposium on Computational Intelligence in Robotics and Automation， 1997. Proceedings IEEE， 1997： 138143. https：//doi.org/10.1109/cira.1997.613850.

[4]周明， 孫樹棟， 彭炎午. 使用遺傳算法規(guī)劃移動機器人路徑[J]. 西北工業(yè)大學學報， 1998， 16（4）： 580583.

[5]周明， 孫樹棟， 彭炎午. 基于遺傳模擬退火算法的機器人路徑規(guī)劃[J]. 航空學報， 1998， 19（1）： 118120. DOI： 10.3321/j.issn：10006893.1998.01.026.

[6]安柏義， 曹云峰. 基于動態(tài)規(guī)劃的無人機航路優(yōu)化問題研究[J]. 計算機測量與控制， 2008， 16（8）： 11771179， 1194. DOI： 10.16526/j.cnki.114762/tp.2008.08.002.

[7]穆曉敏， 姜智超， 包一鳴， 等. 低空突防最優(yōu)航路規(guī)劃算法與仿真[J]. 航天控制， 2005， 23（1）： 4550. DOI： 10.3969/j.issn.10063242.2005.01.011.

[8]汪柱， 李樹軍， 張立華， 等. 基于航路二叉樹的航線自動生成方法[J]. 武漢大學學報（信息科學版）， 2010， 35（4）： 407410. DOI： 10.13203/j.whugis2010.04.015.

[9]王瑩， 劉維亭. 基于改進蟻群算法的艦船航路規(guī)劃研究[J]. 現(xiàn)代電子技術， 2010， 33（21）： 186188， 196. DOI： 10.16652/j.issn.1004373x.2010.21.014.

[10]鄒春明， 趙俊超， 楊柯， 等. 基于懲罰PSO的群橋水域多約束航路規(guī)劃[J]. 中國航海， 2016， 39（2）： 6770. DOI： 10.3969/j.issn.10004653.2016.02.016.

[11]劉俊麗， 韓旭. 遺傳算法技術淺論[J]. 電腦學習， 2009（5）： 142143. DOI： 10.3969/j.issn.20952163.2009.05.070.

[12]徐建國. 島礁區(qū)航行方法與應急措施[J]. 中國水運， 1997（8）： 2930. DOI： 10.13646/j.cnki.421395/u.1997.08.015.

[13]呂呼平. 淺談大型船舶在舟山島礁區(qū)航行的方法[C]//中國航海學會優(yōu)秀論文文摘及學術會議論文目次匯編（1990—1991）. 上海， 1992： 2.

[14]張云鵬， 張吉平. 大型船舶沿岸航行富余水深的研究[J]. 大連海事大學學報， 2014， 40（3）： 3336. DOI： 10.16411/j.cnki.issn10067736.2014.03.017.

[15]欒法敏. 沿岸通航密集區(qū)航行風險識別、評估和控制[J]. 中國航海， 2014， 37（3）： 8084. DOI： 10.3969/j.issn.10004653.2014.03.019.

[16]張錫海. 曹妃甸港及其附近水域航路優(yōu)化的研究[D]. 大連： 大連海事大學， 2007. DOI： 10.7666/d.y1037209.

[17]馬全黨. 典型水域船舶航路動態(tài)規(guī)劃模型及其應用研究[D]. 武漢： 武漢理工大學， 2012. DOI： 10.7666/d.y2099337.

（編輯趙勉）endprint