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

倪生科 劉正江 蔡垚 王欣

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

關鍵詞：遺傳算法; 非線性規劃; 實數編碼; 避碰

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

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

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

1 會遇局面的定量劃分

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

3.2 必要性分析

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

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

4 結 論

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

參考文獻：

[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]畢京強. 內河船舶自動避碰決策研究[D]. 大連： 大連海事大學， 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]李剛. 面向危險環境的UUV動礙航物規避方法研究[D]. 哈爾濱： 哈爾濱工程大學， 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]李瑤. 遺傳算法在船舶避碰行動決策中的應用研究[D]. 大連： 大連海事大學， 2013.

[16]劉佳男. 基于進化遺傳算法的無人艇避碰系統研究[D]. 大連： 大連海事大學， 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]王得燕. 粒子群算法在多船轉向避碰中的研究[D]. 無錫： 江南大學， 2009.

[22]潘朋朋. 基于粒子群優化算法的船舶避碰研究[D]. 鎮江： 江蘇科技大學， 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]. 哈爾濱： 哈爾濱工程大學， 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]. 北京： 北京航空航天大學出版社， 2011： 17-25.

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

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

（編輯 趙勉）