倪生科， 劉正江， 蔡垚， 王欣

(大連海事大學 航海學院，遼寧 大連 116026)

基于遺傳算法的船舶避碰決策輔助

倪生科， 劉正江， 蔡垚， 王欣

(大連海事大學 航海學院，遼寧 大連 116026)

針對海上船舶避碰問題，提出一種基于多種群遺傳算法(Genetic Algorithm,GA)自動生成最優(yōu)避碰路徑的船舶避碰輔助決策方法.該算法采用多種群協(xié)同進化的方式，通過建立移民算子和人工選擇算子保持種群之間的聯(lián)系.這種改進的GA不僅能解決標準GA中遺傳算子參數(shù)設(shè)定的問題，而且能提高算法的有效性和效率.利用船舶避碰方面的知識和啟發(fā)式方法生成初始路徑，使其決策方向符合避碰規(guī)則的要求，并對種群中的個體進行適應(yīng)度評價與優(yōu)化.以精英種群中最優(yōu)個體的最少保持代數(shù)作為算法終止條件，這種判據(jù)充分利用GA在進化過程中的知識積累，比最大遺傳代數(shù)判據(jù)更為合理.仿真結(jié)果證明了多種群GA在輔助船舶避碰決策方面的可行性和優(yōu)越性.

多種群遺傳算法(GA)； 啟發(fā)式方法； 移民算子； 人工選擇算子

0 引 言

船舶避碰決策系統(tǒng)研究一直以來都是船舶航行安全領(lǐng)域的熱點和難點課題.早期，船舶避碰采用幾何方法確定兩船最近會遇距離和到達最近會遇點時間來評價船舶間的碰撞危險.20世紀80年代后，學者們在避碰幾何理論的基礎(chǔ)上提出了船舶領(lǐng)域和避碰危險度的概念，并把其作為確定采取避碰行動的時機和幅度的依據(jù).進入21世紀后，控制論、信息論、系統(tǒng)論等學科的出現(xiàn)為船舶避碰決策提供了新的思想和方法論，同時，心理學、社會心理學等理論方面的突破也為研究人類決策過程、創(chuàng)新思維等增加了新的可能.[1]近年來快速發(fā)展的人工智能技術(shù)與方法克服了早期用確定性方法解決避碰決策問題時遇到的抽象因素眾多、量化困難等難題.[2]目前，對船舶避碰決策的研究方法逐漸由最初的數(shù)學計算模型過渡到人工智能方法，如進化算法[3]、神經(jīng)網(wǎng)絡(luò)[4-5]、模糊邏輯[6]、專家系統(tǒng)[7]、遺傳算法(Genetic Algorithm，GA)[8-12]、蟻群算法[13]等.GA對全局優(yōu)化問題具有很強的魯棒性并且在機器人路徑規(guī)劃領(lǐng)域取得了重大突破，因此許多學者將GA應(yīng)用于船舶避碰決策中.例如：TAM等[8]強調(diào)了優(yōu)化指標及環(huán)境條件對算法生成路徑的影響，通過引入避碰影響區(qū)域來控制GA輸出結(jié)果的一致性；王則勝[9]在GA中對轉(zhuǎn)向點坐標采用實數(shù)編碼方式對船舶避碰路徑進行規(guī)劃；TSOU等[12]以避碰轉(zhuǎn)向角度、復航時機和復航角度作為變量進行編碼優(yōu)化，將得到的結(jié)果在地理信息顯示系統(tǒng)中進行仿真.

目前，船舶避碰決策的研究大都以標準GA為基礎(chǔ)，但標準GA本身的缺陷使其在實際船舶會遇局面中發(fā)揮的作用有限.例如，標準GA在對某一特定船舶會遇態(tài)勢進行避碰決策時，需要提前試驗遺傳(交叉、變異)算子參數(shù)的最優(yōu)組合，才能保證得到有效的避碰路徑，同時標準GA容易出現(xiàn)過早收斂的情況.因此，本文提出以多種群GA代替標準GA進行船舶避碰決策，通過含有不同遺傳算子參數(shù)組合的多種群協(xié)同進化方式解決參數(shù)設(shè)定問題以及單種群進化時存在的過早收斂問題，同時通過移民算子和人工選擇算子保證種群間的信息交換.最后，應(yīng)用精英種群中最優(yōu)個體的最少保持代數(shù)作為GA的終止條件，這充分利用了GA在進化過程中的知識積累，比傳統(tǒng)最大遺傳代數(shù)判據(jù)更為合理.

1 船舶會遇態(tài)勢劃分

在進行船舶避碰決策時，首先需要對船舶會遇態(tài)勢進行劃分.通過對避碰規(guī)則、航行習慣和自動避碰方法的分析將船舶間的會遇態(tài)勢分為對遇(F)、交叉(A，B，E)和追越(C，D)[1]，如圖1所示.圖1中：對位于A，B區(qū)域的他船，本船為讓路船；對位于E區(qū)域的他船，本船為直航船，這意味著，通常本船不采取任何避碰行動，只有在形成緊迫局面而他船仍不采取任何避碰行動時，本船才采取必要的避碰行動；對位于C，D區(qū)域的他船，本船為被追越船，通常本船具有保向保速的義務(wù)，只有與他船形成緊迫局面時，才采取相應(yīng)的避碰行動；對位于F區(qū)域的來船，本船與他船各自采取向右轉(zhuǎn)向方式，以“左對左”方式安全駛過.

圖1 基于相對方位角劃分 的船舶會遇態(tài)勢

2 基于多種群GA的路徑規(guī)劃實現(xiàn)

GA是一種基于自然選擇和基因遺傳學原理的搜索方法，其基本原理就是自然界的“優(yōu)勝劣汰、適者生存”的演化規(guī)則.[14]通過把問題編碼為不同類型的染色體參數(shù)，再利用選擇、交叉、變異等遺傳算子對染色體中的編碼信息不斷進行優(yōu)化，直到達到優(yōu)化門限條件，迭代過程才終止.本文通過多種群協(xié)同進化的方式解決標準GA中存在的參數(shù)設(shè)定和過早收斂問題.圖2為多種群GA的流程.

圖2 多種群GA流程

2.1 編碼方式

在GA中，編碼技術(shù)、編碼串的長度及搜索空間對系統(tǒng)的運行速度非常重要.本文采用實數(shù)編碼技術(shù)簡化GA的計算復雜度和處理復雜的決策變量約

圖3 染色體編碼方式

束條件.圖3為染色體編碼方式,其中φi(i=1,2,…,n)為本船在各對應(yīng)路段上的航向.

2.2 遺傳操作

選擇操作.選擇操作是在群體中選擇生命力強的個體產(chǎn)生新的群體的過程.本文采用輪盤賭選擇法，即種群中個體i被選中的概率為

(1)

式中:Fi為個體i的適應(yīng)度值(i=1,2,…,N).

交叉操作.交叉操作是把兩個同源染色體通過重組形成新的染色體從而產(chǎn)生新的個體或物種的過程.由于本文采用實數(shù)編碼方式，所以單點交叉操作后基因位上基因值為

(2)

(3)

式中：akj和alj分別為第k個和第l個染色體上第j個基因位上的基因值；b是[0,1]上的隨機數(shù).

變異操作.變異操作是以較小的概率改變個體編碼串上某些基因位上的基因值.本文采用高斯變異算子，通過MATLAB中函數(shù)指令生成符合正態(tài)分布的隨機數(shù)來替換原有基因位上的基因值.

2.3 初始化種群

為使隨機生成的初始路徑滿足《1972年國際海上避碰規(guī)則公約》(簡稱《避碰規(guī)則》)的要求，利用船舶避碰方面的知識和啟發(fā)式方法生成初始路徑，并對種群中的個體進行適應(yīng)度評價與優(yōu)化.例如，在船舶路徑初始化過程中，首先計算分析出船舶間會遇態(tài)勢及避讓責任，假設(shè)分析出本船為讓路船，為滿足《避碰規(guī)則》中對讓路船的避讓行動早、大、寬、清的要求，在初始化種群操作過程中加入限制條件，即各個體初始基因位的變量下限值大于15°[15]，這就保證了讓路船按規(guī)則要求的轉(zhuǎn)向方向和幅度進行避讓，并且種群中各個體的初始基因不參與優(yōu)化過程中的交叉、變異操作，保證優(yōu)化后的路徑始終滿足良好船藝的要求，同時在適應(yīng)度函數(shù)中引入船舶領(lǐng)域，保證船舶在生成的避碰路徑上自動避碰以及復航過程的安全.

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

以船舶安全性和航線航程作為約束條件構(gòu)造適應(yīng)度函數(shù)

(4)

通過分析適應(yīng)度函數(shù)可知，當D與Dt-D′同時趨近0時，得到的路徑適應(yīng)度最好，兩者屬于同一數(shù)量級.通過試驗方法得到α和β的值分別為0.4和0.6.當Dt

3 基于多種群GA的船舶避碰路徑規(guī)劃仿真

表1為3種會遇態(tài)勢下本船和目標船的初始狀態(tài)，包括初始坐標、航速和航向.在追越態(tài)勢下，為快速完成追越過程，給定本船初始速度為11.0 m/s.運用多種群GA分別對3種會遇態(tài)勢下的船舶進行路徑規(guī)劃，得到的結(jié)果見圖4～6.

表1 3種會遇態(tài)勢下本船和目標船的初始狀態(tài)

a)本船最優(yōu)路徑

b)兩船距離

a)本船最優(yōu)路徑

b)兩船距離

a)本船最優(yōu)路徑

b)兩船距離

圖4～6中：虛線為本船以初始航速和航向航行時的運動軌跡，點劃線為本船優(yōu)化路徑，直線為目標船運動軌跡；t為航行時間.從仿真結(jié)果看，在整個避讓過程中，本船與目標船的距離都大于船舶領(lǐng)域半徑，同時優(yōu)化路徑滿足船舶安全性、航線平滑度和航線航程的要求.

分別利用多種群GA和標準GA對3種船舶會遇態(tài)勢進行仿真，得到這兩種算法的收斂曲線，見圖7.通過對比圖7a)和7b)可以看出，多種群GA在收斂的迭代次數(shù)和收斂的適應(yīng)度方面都要優(yōu)于標準GA，即用多種群GA得到的最優(yōu)路徑要優(yōu)于用標準GA得到的最優(yōu)路徑.

a)標準GA

b)多種群GA

4 結(jié) 論

本文采用多種群遺傳算法(GA)對船舶進行避碰輔助決策.多種群GA解決了標準GA在船舶路徑規(guī)劃中出現(xiàn)的遺傳算子參數(shù)設(shè)置問題和過早收斂問題.最后，分別利用多種群GA和標準GA對3種船舶會遇態(tài)勢進行仿真，得到的收斂曲線證明了多種群GA在船舶避碰決策方面的有效性和優(yōu)越性.

[1]鄭中義. 船舶自動避碰決策系統(tǒng)的研究[D]. 大連: 大連海事大學, 2000.

[2]康與濤, 朱大奇, 陳偉炯. 船舶避碰路徑規(guī)劃研究綜述[J]. 船海工程, 2013, 42(5): 141-145. DOI: 10.3963/j.issn.1671-7953.2013.05.038.

[3]MIERZCHALSKI R, MICHALEWICZ Z. Modeling of a ship trajectory in collision situations at sea by evolutionary algorithm[J]. IEEE Transaction on Evolutionary Computation, 2000, 4(3): 227-241.

[4]ZHU Xiaolin, XU Hanzhen, LIN Junqing. Domain and its model based on neural networks[J]. Journal of Navigation, 2001, 54(1): 97-103. DOI: 10.1017/S0373463300001247.

[5]陳建華, 陳紅衛(wèi), 劉科. 基于模糊神經(jīng)網(wǎng)絡(luò)的一種船舶碰撞危險度計算方法[J]. 艦船科學技術(shù), 2008, 30(2): 135-138. DOI: 10.3404/j.issn.1672-7649.2008.02.027.

[6]LEE S, KWON K, JOH J. A fuzzy logic for autonomous navigation of marine vehicles satisfying COLREG guidelines[J]. International Journal of Control Automation and Systems, 2004, 2(2): 171-181.

[7]EFSTATHIOU J. Expert systems, fuzzy logic and rule-based control explained at last[J]. Transactions of the Institute Of Measurement and Control, 1988, 10(4): 198-206.

[8]TAM C, BUCKNALL R. Path-planning algorithm for ship in close-range encounters[J]. Journal of Marine Science and Technology, 2010, 15(4): 395-407. DOI: 10.1007/s00773-010-0094-x.

[9]王則勝. 基于遺傳算法的船舶避碰決策研究[D]. 上海: 上海海事大學, 2005.

[10]唐琳, 蔡德榮, 黃猛. 基于改進遺傳算法的艦船路徑規(guī)劃[J]. 計算機工程與設(shè)計, 2009, 30(6): 1452-1457.

[11]田鶴, 李啟華, 孟一鳴. 基于改進型遺傳算法的艦艇航路規(guī)劃研究[J]. 艦船電子工程, 2011, 31(10): 46-48.

[12]TSOU M, KAO S, SU C. Decision support form genetic algorithms for ship collision avoidance route planning and alerts[J]. Journal of Navigation, 2010, 63(1): 167-182. DOI: 10.1017/S037346330999021X.

[13]王瑩. 綜合船橋系統(tǒng)航跡規(guī)劃技術(shù)研究[D]. 江蘇: 江蘇科技大學, 2011.

[14]雷英杰, 張善文, 李續(xù)武, 等. MATLAB遺傳算法工具箱及應(yīng)用[M]. 西安: 西安電子科技大學出版社, 2005: 1-10.

[15]SZLAPCZYNSKI R. A unified measure of collision risk derived from the concept of a ship domain[J]. Journal of Navigation, 2006, 59(3): 477-490. DOI: 10.1017/S0373463306003833.

[16]孫立成. 船舶避碰數(shù)學模型的研究[D]. 大連: 大連海事大學, 2000.

(編輯 趙勉)

Ship collision avoidance decision aids based on genetic algorithm

NI Shengke, LIU Zhengjiang, CAI Yao, WANG Xin

(Navigation College, Dalian Maritime University, Dalian 116026, Liaoning, China)

For the ship collision avoidance problem at sea, a method to ship collision avoidance decision aids is presented, where the multi-population Genetic Algorithm(GA) is adopted to automatically generate the optimal path of collision avoidance. In the algorithm, multiple populations evolve simultaneously, and the immigration operator and the artificial selection operator are established to keep relationships among populations. The improved GA can not only solve the problem of parameter settings for genetic operators in the traditional GA, but also improve the algorithm’s effectiveness and efficiency. The knowledge of ship collision avoidance and the heuristic method are used to generate the initial path whose decision direction meets the requirements of collision avoidance rules, and to carry out the fitness evaluation and optimization for individuals of the populations. The termination condition of the algorithm is the minimum iteration times predefined that the optimal individual is kept in the elite population, which makes full use of the knowledge accumulation in the iteration process of GA, and is more reasonable than the criterion of the maximum genetic iteration times. Simulation results demonstrate the feasibility and superiority of the multi-population GA in aiding ship collision avoidance decision.

multi-population Genetic Algorithm (GA); heuristic method; immigration operator; artificial selection operator

10.13340/j.jsmu.2017.01.003

1672-9498(2017)01-0012-04

2016-08-09

2016-11-10

國家自然科學基金(51179019)；工業(yè)及信息化部高技術(shù)船舶科研項目(9014491)

倪生科(1990—)，男，遼寧大連人，博士研究生，研究方向為交通信息工程及控制，(E-mail)863369021@qq.com； 劉正江(1959—)，男，江蘇如皋人，教授，博導，博士，研究方向為交通信息工程及控制，(E-mail)liuzhengjiang@dlmu.edu.cn

U675.96

A