基于擬態物理學優化算法的船舶轉向避碰決策

于家根， 劉正江， 卜仁祥， 高孝日， 李偉峰

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

基于擬態物理學優化算法的船舶轉向避碰決策

于家根， 劉正江， 卜仁祥， 高孝日， 李偉峰

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

針對多船會遇態勢下的船舶避碰決策難題，提出一種基于擬態物理學優化算法的船舶轉向避碰決策方法。該算法將《國際海上避碰規則》相關條款作為約束條件限定問題的可行域空間，同時考慮基于最近會遇距離和航程損失的船舶避碰目標函數，通過迭代進化獲取全局范圍內的最優解。仿真結果表明：將擬態物理學優化算法應用于船舶轉向避碰決策中是可行、有效的，能為船舶駕駛員提供決策支持。

水路運輸；擬態物理學優化算法；多船會遇；轉向避碰決策

Abstract: The Artificial Physics Optimization (APO) algorithm with the feasible space constrained by The Rules from International Regulations for Preventing Collisions at Sea is introduced into the collision avoidance decision-making in multi-ship encounter situations. The objective function is constructed on the basis of the Distance of the Closest Point of Approach (DCPA) and the voyage losses, and solved through iterative evolution to obtain the optimal solution. The simulation of the process shows that APO algorithm works effectively in determining the course alteration for avoiding collision, therefore, can help marine officers in navigation practice.

Keywords: waterway transportation; APO algorithm; multi-ship encounter; course alteration for collision avoidance

在海上實踐中，船舶避碰決策的制定主要依賴于駕駛員的專業知識及其駕駛經驗，轉向避碰是最常見的行動方案。然而，當船舶處于復雜的多船會遇態勢時，駕駛員很難快速給出最佳避碰決策方案，且一旦作出錯誤決策將導致事故發生。對此，一些學者嘗試將進化算法、遺傳算法、蟻群算法和粒子群算法等人工智能優化算法應用于船舶避碰決策研究中，已取得一定的成果。[1-4]

擬態物理學優化算法(Artificial Physics Optimization Algorithm，APO Algorithm)[5-6]是一種基于種群的啟發式隨機搜索算法，同粒子群算法相比，其具有種群多樣性好、搜索效率高的優點。這里考慮多船會遇態勢下的轉向避碰決策，將避碰規則作為行動可行域的約束條件，利用擬態物理學優化算法，從可行域的空間中求出目標函數極小值，進而得到轉向避碰決策。

1 船舶避碰決策模型

船舶間會遇并構成碰撞危險時，本船需采取相應的避碰行動進行避讓。船舶避碰行動包括轉向和變速2種，設其二維解空間為Xi(t)=(xi1(t),xi2(t))，其中：Xi(t)為t時刻問題可行域的第i個解;xi1(t)和xi2(t)分別為該解的航向和航速值。

衡量解的優劣的指標是目標函數，設為f(Xi)=(f1(Xi),f2(Xi),…,fn(Xi))，表示船舶避碰決策同時考慮碰撞危險度和航程損失等多個子目標函數。目標函數取極小值時的解即為最優解。由此，建立船舶避碰決策模型，將船舶避碰決策問題轉化為在問題的可行域內使目標函數取極小值的尋最優解問題。

考慮船舶的操縱性能并綜合分析轉向和變速避讓行動的效果，若水域充足，則多采用轉向避碰行動，此時解空間由二維簡化為一維，即Xi(t)=(xi(t))，其中xi(t)為t時刻第i個解的航向值。考慮《國際海上避碰規則》(以下簡稱《避碰規則》)對轉向避碰的約束，各解的航向值區間為[xmin,xmax]，上下邊界值根據具體的會遇情況設定。

模型中選取碰撞危險度和航程損失作為子目標函數,其中：碰撞危險度受最近會遇距離DCPA、最近會遇時間TCPA、船舶操縱性能和外界環境等諸多因素的影響，根據研究問題的需要，選取適當的碰撞危險度模型[7-9]；航程損失則受轉向幅度等因素的影響。

2 基于APO算法的轉向避碰決策

2.1APO算法基本原理

APO算法[10-12]是通過模擬物理學原理及其規律而設計的基于種群優化算法的搜索策略。將各個樣本解看作是具有質量、速度和位置屬性的物理個體，個體的質量是用戶定義的與其目標函數值(適應值)相關的函數，個體的適應值越好，質量和個體間的虛擬作用力就越大。適應值較好的個體吸引適應值較差的個體，適應值較差的個體排斥適應值較好的個體，適應值最好的個體則不受其他個體的吸引或排斥。利用這種虛擬力作用規則更新種群個體的位置，通過迭代進化使整個種群向更好的搜索區域移動，進而得到滿意的最優解。

2.2避碰目標函數

2.2.1碰撞危險度目標函數

多船會遇轉向避碰情況下的碰撞危險度模型較多，必須根據所研究問題的需要進行選取。最小DCPA目標船的DCPA值越大，危險度就越低。因此，設碰撞危險度目標函數為

(1)

式(1)中：f1(xi)為種群中第i個個體的碰撞危險度函數值，其值域為(0,1];dCPAir為第i個個體與第r個目標船的最近會遇距離；N為目標船數。目標函數值越小，則第i個個體對所有目標船的最近會遇距離的絕對值的最小值就越大，碰撞危險度越小。

2.2.2航程損失目標函數

避碰實踐中，考慮到《避碰規則》對避碰行動 “大幅度”的要求，航向變化角至少為30°[13]；考慮到要減小航程損失，要求轉向幅度盡可能小。因此，設航程損失目標函數為

f2(xi)=(xi-30)/150

(2)

式(2)中：f2(xi)為種群中第i個個體的航程損失目標函數值，其值域為[0,1]；xi∈[30,180]。目標函數值越小，則轉向幅度和航程損失就越小。

上述2個目標函數的值域均在[0,1]內，若對這2個子目標分配權重7:3，則多目標函數可簡化為以下單目標函數。

f(xi)=0.7f1(xi)+0.3f2(xi)

(3)

2.3種群初始化

設種群數為Npop，Xi(t)=(xi(t))為種群中第i(i∈1,2,…,Npop)個個體在第t代的位置向量(即船舶轉向避碰決策中的航向值);設Vi(t)=(vi(t))為個體i在第t代的速度向量(即航向值更新的步長)。在位置約束[xmin,xmax]和速度約束[vmin,vmax]內隨機初始化種群。計算初始狀態下種群中所有個體的適應值，從中選出最優個體及其適應值。

2.4個體進化

2.4.1個體質量函數計算

(4)

式(4)中：f(xbest)為當前代內最優個體的適應值;f(xworst)為當前代內最差個體的適應值。該質量函數滿足2個性質:值域為(0,1]，且mbest=1；函數為非負單調有界函數。

2.4.2個體所受合力計算

(5)

(6)

式(5)～式(6)中：Fij為第j個個體對第i個個體的虛擬作用力；rij=xj-xi為個體i到個體j的距離;G為引力常數，可通過選擇參數G來控制種群中作收斂運動和發散運動的個體的數量[14]；Fi為個體i所受的虛擬作用力的合力;式(5)中,?i≠j,i=best;式(6)中,?i≠best。

2.4.3個體位置更新公式

種群個體在其所受虛擬作用力的合力作用下運動。個體在合力方向上的步長決定著其下一代的位置。最優個體不受外界引力的影響，進化中直接傳遞到下一代。除最優個體之外，任意個體i在第t+1代每一維的速度和位置進化方程如下。

(7)

式(7)中：a為服從(0,1)正態分布的隨機變量，即a～N(0,1)；w為慣性權重，且w∈(0,1);?i≠best。

2.5APO算法步驟

1) 初始化參數Npop，G，vmin，vmax，xmin及xmax;計數器t=0;最大迭代代數為tmax。

2) 隨機初始化種群：個體位置和速度。

3) 計算種群中所有個體的適應值(式(1)～式(3))；選出最優個體Xbest及其適應值f(Xbest)，最差個體Xworst及其適應值f(Xworst)。

4) 計算種群中所有個體的質量(式(4))。

5) 計算種群中各個個體所受虛擬作用力的合力(式(5)和式(6))。

6) 更新種群個體的位置(式(7))。

7) 計算更新位置之后種群中所有個體的適應值，更新最優個體Xbest及其適應值f(Xbest)。

8) 判斷是否滿足結束條件。若滿足，則停止計算，輸出最優個體Xbest及其適應值f(Xbest)；若不滿足，則進化代數t=t+1，返回至步驟“4)”。

3 實例仿真分析

3.1仿真實例

設本船的初始航向為000°，航速為15 kn；能見度不良且不在互見中；同時有5艘船舶(分別命名為TS1,TS2,TS3,TS4,TS5)會遇，存在碰撞危險。本船與目標船的會遇態勢見表1，其中：DCPA為正值表示目標船過本船艏部；DCPA為負值表示目標船過本船艉部。

表1 本船與目標船的會遇態勢

根據《避碰規則》第19條“船舶在能見度不良時的行動規則”中的第4款“轉向”要求的規定并考慮避碰“大幅度”的要求，將種群中個體位置的邊界設置為xi∈[30,180]。考慮到轉向避碰決策航向值的精度，設置種群中個體的速度邊界為vi∈[-1,1]。種群數量設置為50個，即Npop=50。為更好地驗證算法的收斂性，設置迭代代數為2 500代。引力常數G取0.1，慣性權重w的計算表達式[6]265為

(8)

式(8)中：t為當前代數;tmax為最大循環代數。

3.2結果分析

仿真結果見圖1和圖2，其中：圖1為各代個體的最優值，即船舶轉向避碰決策應駛的最佳航向;圖2為各代最優個體的適應值。

圖1 各代個體的最優值

圖2 各代最優個體的適應值

由圖1和圖2可知，結果最終收斂于某個固定值，500代內即趨于穩定，收斂速度快，算法執行耗時5～8 s，能快速給出轉向避碰決策。為驗證該算法的可行性和有效性，執行30次運算，得到個體最優值的范圍為[42.0,46.5]，最優個體適應值的范圍為[0.295 8,0.309 0]，說明該算法能獲得滿意的一致最優解。

結果表明，本船在該會遇態勢下應駛向的最佳航向角為44.3°(30次運算均值)，對應的適應值為0.300 4。該航向下，本船對各船(按TS1～TS5的順序)的DCPA值向量為(2.338 5，1.575 7，-2.343 2，-1.664 8，-1.737 1)，結果較為滿意。

4 結束語

當船舶間處于會遇態勢并有碰撞危險時，多采取轉向避碰決策；而當多船會遇時，局面較為復雜，對駕駛員的專業技能和經驗有較高要求，一旦決策失誤將導致碰撞事故發生。對此，在建立的船舶避碰決策模型的基礎上提出基于擬態物理學優化算法的船舶避碰決策方法，旨在利用APO算法的快速全局尋優能力為船舶駕駛員提供決策支持。針對多船會遇的復雜局面，考慮《避碰規則》的約束限制，建立基于最近會遇距離的避碰目標函數，通過迭代進化獲取最佳決策方案。結果表明：該算法可行、有效，能為船舶駕駛員提供決策支持。

[1] SMIERZCHALSKI R, MICHALEWICZ Z. Modeling of Ship Trajectory in Collision Situations by an Evolutionary Algorithm[J]. IEEE Transactions on Evolutionary Computation, 2000, 4(3): 227-240.

[2] TSOU Mingcheng, KAO Shenglong, SU Chienmin. Decision Support from Genetic Algorithms for Ship Collision Avoidance Route Planning and Alerts[J]. Journal of Navigation , 2010, 63(1): 167-182.

[3] JOSE B E, JUAN F J, JOSE M G S. Optimization of Autonomous Ship Maneuvers Applying Ant Colony Optimization[J]. Expert Systems with Applications, 2012, 39(11) : 10120-10139.

[4] 王得燕, 劉以安. 粒子群算法在多船避碰決策中的應用[J]. 計算機工程與設計, 2009, 30(14): 3380-3382.

[5] 謝麗萍,曾建潮. 基于擬態物理學方法的全局優化算法[J]. 計算機研究與發展, 2011, 48(5)：848-854.

[6] 曾建潮,崔志華. 自然計算[M].北京：國防工業出版社，2012:246-265.

[7] TAM C K, BUCKNALL R. Collision Risk Assessment for Ships[J]. Journal of Marine Science and Technology, 2010, 15(3): 257-270.

[8] 鄭中義, 吳兆麟. 船舶碰撞危險度新模型[J]. 大連海事大學學報, 2002, 28(2): 1-5.

[9] 劉茹茹,胡勤友. 一種主觀的船舶碰撞危險度評價模型[J]. 上海海事大學學報, 2012, 33(1): 41-44.

[10] XIE Liping, TAN Ying, ZENG Jianchao. The Convergence Analysis of Artificial Physics Optimization Algorithm[J]. International Journal of Intelligent Information and Database Systems, 2011, 5(6): 536-54.

[11] XIE Liping, TAN Ying, ZENG Jianchao. Artificial Physics Optimization: A Brief Survey[J]. International Journal of Bio-Inspired Computation, 2010, 2(5): 291-302.

[12] XIE Liping,TAN Ying, ZENG Jianchao. The Selection Strategy of Mass Functions in Artificial Physics Optimization Algorithm[J]. International Journal of Modeling, Identification and Control, 2013, 18(3): 226-233.

[13] ZHAO Yuelin. Collision Avoidance and Watch Keeping[M]. Dalian: Dalian Maritime University Press, 2010:101-102.

[14] 王艷. 多目標擬態物理學優化算法及其應用研究[D]. 蘭州: 蘭州理工大學, 2011.

Collision-AvoidingCourseAlterationOptimizationwithArtificialPhysicsAlgorithm

YUJiagen,LIUZhengjiang,BURenxiang,GAOXiaori,LIWeifeng

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

2015-11-12

國家自然科學基金(51379026)；中央高校基本科研業務費專項資金(3132016002;3132013004；3132013005；3132013015)

于家根(1984—)，男，黑龍江綏化人，講師，博士生，研究方向為船舶智能避碰。E-mail：yujiagen@dlmu.edu.cn 劉正江(1959—)，男，江蘇如皋人，教授，博士生導師，研究方向為海上交通安全。E-mail：liuzhengjiang@dlmu.edu.cn

1000-4653(2016)01-0036-03

U675.96

A