基于混合遺傳算法的船舶避碰路徑規(guī)劃

倪生科 劉正江 蔡垚 王欣

摘要：針對不同會遇態(tài)勢下的船舶避碰路徑規(guī)劃問題，建立一種基于遺傳算法和非線性規(guī)劃理論的避碰路徑規(guī)劃模型。該模型結(jié)合遺傳算法全局搜索能力強與非線性規(guī)劃方法局部搜索能力強的特點，使混合后的遺傳算法在性能和效率上都得到提高。綜合考慮船舶安全性、路徑平滑度和路徑長度等因素的影響建立避碰目標函數(shù)，采用基于實數(shù)編碼方式的輪盤賭選擇算子、算術(shù)交叉算子和高斯變異算子，通過迭代獲取全局范圍內(nèi)的最優(yōu)解。通過仿真對模型進行可行性驗證和必要性分析。

關(guān)鍵詞：遺傳算法; 非線性規(guī)劃; 實數(shù)編碼; 避碰

中圖分類號： ?U675.96

文獻標志碼： ?A

Abstract：For ship collision avoidance path planning issue in different encounter situations， a collision avoidance path planning model is proposed based on the genetic algorithm and the nonlinear programming theory. This model combines the strong global search ability of the genetic algorithm and the strong local search ability of the nonlinear programming method， which greatly improves the performance and efficiency of the hybrid genetic algorithm. Considering the influence of ship safety， path smoothness and path length， an objective function of collision avoidance is established. The roulette selection operator， arithmetic crossover operator and Gaussian mutation operator based on real number encoding are adopted. The optimal solution in the global range is obtained through iteration. The feasibility and necessity of the model are verified through simulation.

Key words：genetic algorithm; nonlinear programming; real number encoding; collision avoidance

0 引 言

為減輕船舶駕駛?cè)藛T在海上工作的負擔(dān)和避免避碰過程中的操作失誤，可利用現(xiàn)代化的科學(xué)手段和方法進行智能決策。大數(shù)據(jù)、互聯(lián)網(wǎng)、人工智能等技術(shù)和理論的快速發(fā)展為船舶智能避碰決策的研究提供了強有力的技術(shù)和硬件支撐。船舶避碰路徑規(guī)劃是實現(xiàn)船舶智能避碰決策的關(guān)鍵技術(shù)之一，它經(jīng)過大半個世紀的發(fā)展，從早期的經(jīng)典數(shù)學(xué)理論逐漸過渡到基于人工智能和學(xué)科交叉的路徑規(guī)劃研究，取得了一定的研究成果。TAM等[1]將避碰路徑規(guī)劃的研究方法歸納為確定性算法和啟發(fā)式算法：確定性算法是遵循一定的計算流程來確定最終方案的，主要包括專家系統(tǒng)[2-4]、模糊邏輯[5-8]、人工勢場法[9-11]等;啟發(fā)式算法是在一個搜索區(qū)域的子空間內(nèi)尋找一個滿足設(shè)計要求的優(yōu)化方案的，主要包括遺傳算法[12-17]、蟻群算法[18-20]、粒子群優(yōu)化算法[21-22]等。不同方法具有各自獨特的優(yōu)勢，但都存在一定的缺陷。例如：專家系統(tǒng)的重點是建立避碰知識庫和推理機制，可是存在知識獲取困難，完備、簡練的知識庫難以形成，系統(tǒng)實時性較差，智能學(xué)習(xí)的能力不具備等問題[23];雖然模糊邏輯在船舶避碰領(lǐng)域的應(yīng)用能在一定程度上實現(xiàn)對避碰這種非確定性問題的推理，但模糊推理的輸出依賴于事先設(shè)定的參數(shù)，目前對模糊控制量的設(shè)定均使用經(jīng)驗參數(shù)，對環(huán)境因素考慮較少，環(huán)境自適應(yīng)性有待提高[24];基于人工勢場法對船舶進行避碰決策具有計算簡潔、實時性強、便于數(shù)學(xué)描述等優(yōu)點，但是存在局部極小值導(dǎo)致的陷阱區(qū)域、在礙航物前發(fā)生振蕩、在鄰近礙航物間不能發(fā)現(xiàn)路徑等固有缺陷[25]。用確定性算法對船舶避碰路徑進行規(guī)劃的特點是計算量小、收斂速度快，但是往往基于其他變量確定的假設(shè)對某一變量進行確定，實際上船舶避碰路徑規(guī)劃是一個包含避碰規(guī)則、動態(tài)障礙避讓、船舶操縱性能等多方面的決策優(yōu)化問題。因此，很多專家學(xué)者轉(zhuǎn)向基于啟發(fā)式算法的船舶避碰路徑規(guī)劃研究，取得了一定的研究成果。然而啟發(fā)式算法經(jīng)常存在早熟收斂的問題，致使得到的決策方案不符合要求，因此采用不同的混合方式對各種技術(shù)進行優(yōu)勢互補以獲得求解能力更強的路徑規(guī)劃模型成為一種新的趨勢。

遺傳算法具有對可行解編碼的廣泛性和易于與其他人工智能技術(shù)混合等特點，在船舶避碰路徑規(guī)劃領(lǐng)域受到廣泛關(guān)注。本文基于遺傳算法和非線性規(guī)劃理論建立船舶避碰路徑規(guī)劃模型，解決遺傳算法的早熟收斂問題，使混合后的算法在性能和效率方面都得到提高，為駕駛員的避碰決策提供科學(xué)依據(jù)和支撐。

1 會遇局面的定量劃分

從運動路徑可以看出，船舶的避讓路徑滿足平滑度的要求。從兩船距離變化曲線可以看出，船舶間距離滿足船舶安全參數(shù)（船舶領(lǐng)域）的要求。在t2時刻，船舶的最近會遇距離（distance to closest point of approach， DCPA）接近船舶領(lǐng)域半徑。船舶間距離變化曲線是一條光滑的曲線，表明船舶間的距離是均勻變化的，故避碰路徑滿足避碰過程中船舶安全性和路徑長度的要求。因此，利用混合遺傳算法可以得到有效的船舶避碰路徑。

3.2 必要性分析

船舶避碰路徑規(guī)劃是避碰決策中最關(guān)鍵的問題，需要綜合考慮船舶安全性、路徑平滑度和路徑長度的影響。本文使用混合遺傳算法不但提高了對避碰路徑的搜索能力，而且極大地提高了避碰路徑的質(zhì)量。為證明混合遺傳算法在避碰路徑規(guī)劃方面相對于標準遺傳算法的優(yōu)越性，分別利用兩種算法對表3中的案例進行仿真，圖7為這兩種算法的適應(yīng)度曲線。

由圖7可知：混合遺傳算法的適應(yīng)度曲線在迭代25次后達到了相對穩(wěn)定的狀態(tài)，比標準遺傳算法的適應(yīng)度曲線達到相對穩(wěn)定時的迭代次數(shù)大約少了10次;混合遺傳算法的適應(yīng)度曲線的斜率在迭代大約20次時有明顯的跳躍，其最終的適應(yīng)度值也明顯更優(yōu)。因此，在同等條件下，基于混合遺傳算法的路徑規(guī)劃方法在收斂速度和求解結(jié)果上都優(yōu)于基于標準遺傳算法的路徑規(guī)劃方法。

4 結(jié) 論

本文首先對船舶會遇局面及避讓責(zé)任進行判斷，通過一維真值實數(shù)編碼方式對避碰路徑進行編碼并根據(jù)轉(zhuǎn)向避讓方向和良好船藝對避碰路徑進行初始化操作;再綜合考慮船舶安全性、路徑平滑度和路徑長度對船舶避碰路徑規(guī)劃的影響，提出分類評價的方式，以此建立適應(yīng)度函數(shù)模型;然后，基于遺傳算法和非線性規(guī)劃理論建立避碰路徑規(guī)劃模型，消除以往遺傳算法在路徑規(guī)劃方面局部優(yōu)化能力弱的缺陷;最后，通過船舶避碰仿真對混合遺傳算法的有效性和必要性進行驗證。

參考文獻：

[1]TAM C K， BUCKNALL R， GREIG A. Review of collision avoidance and path planning methods for ships in close range encounters[J]. The Journal of Navigation， 2009， 62（3）： 455-476.

[2]畢京強. 內(nèi)河船舶自動避碰決策研究[D]. 大連： 大連海事大學(xué)， 2016.

[3]LEE Han-Jin， RHEE Key-Pyo. Development of collision avoidance system by using expert system and search algorithm[J]. International Shipbuilding Progress， 2001， 48（3）： 197-210.

[4]AHN Jin-Hyeong， RHEE Key-Pyo， YOU Young-Jun. A study on the collision avoidance of a ship using neural networks and fuzzy logic[J]. Applied Ocean Research， 2012， 37（4）： 162-173.

[5]HWANG Cheng-Neng， YANG Joe-Ming， CHIANG Chung-Yen. The design of fuzzy collision-avoidance expert system implemented by H∞-autopilot[J]. Journal of Marine Science and Technology， 2001， 9（1）： 25-37.

[6]KAO Sheng-Long， LEE Kuo-Tien， CHANG Ki-Yin， et al. A fuzzy logic method for collision avoidance in vessel traffic service[J]. The Journal of Navigation， 2007， 60（1）： 17-31.

[7]PERERA L P， CARVALHO J P， SOARES C G. Fuzzy logic based decision making system for collision avoidance of ocean navigation under critical collision conditions[J]. Journal of Marine Science and Technology， 2011， 16（1）： 84-99. DOI： 10.1007/s00773-010-0106-x.

[8]BRCKO T， VETAK J. Fuzzy reasoning as a base for collision avoidance decision support system[J]. Promet - Traffic & Trasportation， 2013， 25（6）： 555-564.

[9]XUE Yanzhuo， CLELLAND D， LEE B S， et al. Automatic simulation of ship navigation[J]. Ocean Engineering， 2011， 38（17/18）： 2290-2305.

[10]NAEEM W， HENRIQUE S C， HU Liang. A reactive COLREGs-compliant navigation strategy for autonomous maritime navigation[C]//IFAC-PapersOnLine， 2016， 49（23）： 207-213.

[11]李剛. 面向危險環(huán)境的UUV動礙航物規(guī)避方法研究[D]. 哈爾濱： 哈爾濱工程大學(xué)， 2015.

[12]TSOU Ming-Cheng， KAO Sheng-Long， SU Chien-Min. Decision support from genetic algorithms for ship collision avoidance route planning and alerts[J]. The Journal of Navigation， 2010， 63（1）： 167-182. DOI： 10.1017/S037346330999021X.

[13]TAM C K， 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.

[14]SZLAPCZYNSKI R， SZLAPCZYNSKA J. On evolutionary computing in multi-ship trajectory planning[J]. Applied Intelligence， 2012， 37（2）： 155-174. DOI： 10.1007/s10489-011-0319-7.

[15]李瑤. 遺傳算法在船舶避碰行動決策中的應(yīng)用研究[D]. 大連： 大連海事大學(xué)， 2013.

[16]劉佳男. 基于進化遺傳算法的無人艇避碰系統(tǒng)研究[D]. 大連： 大連海事大學(xué)， 2015.

[17]TSOU Ming-Cheng. Multi-target collision avoidance route planning under an ECDIS framework[J]. Ocean Engineering， 2016， 121： 268-278.

[18]TSOU Ming-Cheng， HSUEH Chao-Kuang. The study of ship collision avoidance route planning by ant colony algorithm[J]. Journal of Marine Science and Technology， 2010， 18（5）： 746-756.

[19]LAZAROWSKA A. Ships trajectory planning for collision avoidance at sea based on ant colony optimisation[J]. The Journal of Navigation， 2015， 68（2）： 291-307.

[20]LAZAROWSKA A. Method of considering the dynamics of a ship in the process of determining a safe trajectory using an algorithm based on ant colony optimization[C]//International Conference on Methods and Models in Automation and Robotics. IEEE， 2016.

[21]王得燕. 粒子群算法在多船轉(zhuǎn)向避碰中的研究[D]. 無錫： 江南大學(xué)， 2009.

[22]潘朋朋. 基于粒子群優(yōu)化算法的船舶避碰研究[D]. 鎮(zhèn)江： 江蘇科技大學(xué)， 2010.

[23]呂紅光， 尹勇， 尹建川， 等. 基于人工智能和軟計算的船舶自動避碰決策算法[J]. 中國航海， 2016， 39（3）： 35-40.

[24]謝朔， 初秀民， 柳晨光， 等. 船舶智能避碰研究綜述及展望[J]. 交通信息與安全， 2016（1）： 1-9. DOI： 10.3963/j.issn1674-4861.2016.01.001.

[25]林曉杰. 基于改進勢場法的受限水域中船舶自動避碰模型研究[D]. 哈爾濱： 哈爾濱工程大學(xué)， 2015.

[26]TAM C K， BUCKNALL R. Collision risk assessment for ships[J]. Journal of Marine Science and Technology， 2010， 15（3）： 257-270. DOI： 10.1007/s00773-010-0089-7.

[27]史峰， 王輝， 郁磊， 等. MATLAB智能算法30個案例分析[M]. 北京： 北京航空航天大學(xué)出版社， 2011： 17-25.

[28]孫立成. 船舶避碰數(shù)學(xué)模型的研究[D]. 大連： 大連海事大學(xué)， 2000.

[29]唐沖. 基于MATLAB的非線性規(guī)劃問題的求解[J]. 計算機與數(shù)字工程， 2013， 41（7）： 1100-1102.

（編輯 趙勉）