倪生科 劉正江 蔡垚 王欣

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

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

中圖分類(lèi)號(hào)： ?U675.96

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

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

1 會(huì)遇局面的定量劃分

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

3.2 必要性分析

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

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

4 結(jié) 論

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

參考文獻(xiàn)：

[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]畢京強(qiáng). 內(nèi)河船舶自動(dòng)避碰決策研究[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]李剛. 面向危險(xiǎn)環(huán)境的UUV動(dòng)礙航物規(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]李瑤. 遺傳算法在船舶避碰行動(dòng)決策中的應(yīng)用研究[D]. 大連： 大連海事大學(xué)， 2013.

[16]劉佳男. 基于進(jìn)化遺傳算法的無(wú)人艇避碰系統(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]. 無(wú)錫： 江南大學(xué)， 2009.

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

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

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

[25]林曉杰. 基于改進(jìn)勢(shì)場(chǎng)法的受限水域中船舶自動(dòng)避碰模型研究[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個(gè)案例分析[M]. 北京： 北京航空航天大學(xué)出版社， 2011： 17-25.

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

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

（編輯 趙勉）