基于改進遺傳算法的島礁區航路規劃模型

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

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

關鍵詞：

遺傳算法； 島礁區； 航路規劃； 精英保留

中圖分類號： 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引言

隨著全球貿易的發展，水路運輸成為大宗貨物運輸的主要方式，港口規劃建設者考慮到保護環境、節約運輸成本以及容納更多船舶等要求，將很多港口的建設地點逐步向海上延伸，以島礁區為基礎平臺建設多個小型港口。[1]以往船舶經過島礁區時單憑船長經驗，手動進行航路規劃，而如今船舶在島礁區航行頻率增加，對航海人員保障航行安全是一個巨大的挑戰。

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

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

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

1問題描述

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

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

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

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

2數據準備及適應度函數評價模型

2.1數據準備

2.1.1障礙物數據準備

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

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安全距離確定

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

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

2.2適應度函數評價模型

2.2.1船舶操縱能力

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

免大幅度、大角度、單一位置轉向。假定所規劃的航路存在n個航路點，除去固定設定的初始點和終點，中間包含n-2個航路點，因此就會產生n-2個轉向點。如圖3所示，根據所得的3個連續航路點坐標，通過式（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越小。當正弦函數分布在90°～180°之間時，正弦函數值與角度之間呈反比關系，因此利用正弦函數的倒數作為適應度函數來代表船舶的轉向角：

F1=n-2k=21sin Ak

（9）

2.2.2值班駕駛員主觀意愿

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

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

F2=T（Pi）T（Pk）L

（10）

2.2.3航程計算

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

F3=nn-1i=1Di

（11）

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

（12）

3島礁區航路規劃遺傳算法編寫

3.1實數路徑點編碼

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

3.2航路初始化

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

3.3適應度函數編寫

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

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

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

（13）

獲得的適應度函數公式為

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

（14）

3.4選擇算子輪盤賭編寫

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

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

（15）

3.5算法改進核心

3.5.1選擇算子精英保留

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

3.5.2交叉算子

交叉在一定的概率Pc下發生，交叉形式分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）對評價度較高的基因片段采取保留策略，以免打破優良基因。如

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下發生，變異方式有4種：

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

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遺傳算法驗證

選定舟山群島附近的一塊島礁區，該區域障礙物繁多，符合試驗要求。如圖4所示為舟山群島的部分區域。利用文中給出的遺傳算法，采用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），種群規模為150，ω1=0.223，ω3=0.928，Pc在（0.7，0.9）上隨機產生，Pm在（0.03，0.05）上隨機產生。

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

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

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

5結束語

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

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

參考文獻：

[1]

熊海生. 島礁區通航環境安全評估研究[D]. 大連： 大連海事大學， 2014.

[2]孫樹棟， 曲彥賓. 遺傳算法在機器人路徑規劃中的應用研究[J]. 西北工業大學學報， 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]周明， 孫樹棟， 彭炎午. 使用遺傳算法規劃移動機器人路徑[J]. 西北工業大學學報， 1998， 16（4）： 580583.

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

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

[7]穆曉敏， 姜智超， 包一鳴， 等. 低空突防最優航路規劃算法與仿真[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]王瑩， 劉維亭. 基于改進蟻群算法的艦船航路規劃研究[J]. 現代電子技術， 2010， 33（21）： 186188， 196. DOI： 10.16652/j.issn.1004373x.2010.21.014.

[10]鄒春明， 趙俊超， 楊柯， 等. 基于懲罰PSO的群橋水域多約束航路規劃[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]徐建國. 島礁區航行方法與應急措施[J]. 中國水運， 1997（8）： 2930. DOI： 10.13646/j.cnki.421395/u.1997.08.015.

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

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

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

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

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

（編輯趙勉）endprint