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

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

基于擬態(tài)物理學(xué)優(yōu)化算法的船舶轉(zhuǎn)向避碰決策

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

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

針對(duì)多船會(huì)遇態(tài)勢(shì)下的船舶避碰決策難題，提出一種基于擬態(tài)物理學(xué)優(yōu)化算法的船舶轉(zhuǎn)向避碰決策方法。該算法將《國(guó)際海上避碰規(guī)則》相關(guān)條款作為約束條件限定問題的可行域空間，同時(shí)考慮基于最近會(huì)遇距離和航程損失的船舶避碰目標(biāo)函數(shù)，通過迭代進(jìn)化獲取全局范圍內(nèi)的最優(yōu)解。仿真結(jié)果表明：將擬態(tài)物理學(xué)優(yōu)化算法應(yīng)用于船舶轉(zhuǎn)向避碰決策中是可行、有效的，能為船舶駕駛員提供決策支持。

水路運(yùn)輸；擬態(tài)物理學(xué)優(yōu)化算法；多船會(huì)遇；轉(zhuǎn)向避碰決策

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

在海上實(shí)踐中，船舶避碰決策的制定主要依賴于駕駛員的專業(yè)知識(shí)及其駕駛經(jīng)驗(yàn)，轉(zhuǎn)向避碰是最常見的行動(dòng)方案。然而，當(dāng)船舶處于復(fù)雜的多船會(huì)遇態(tài)勢(shì)時(shí)，駕駛員很難快速給出最佳避碰決策方案，且一旦作出錯(cuò)誤決策將導(dǎo)致事故發(fā)生。對(duì)此，一些學(xué)者嘗試將進(jìn)化算法、遺傳算法、蟻群算法和粒子群算法等人工智能優(yōu)化算法應(yīng)用于船舶避碰決策研究中，已取得一定的成果。[1-4]

擬態(tài)物理學(xué)優(yōu)化算法(Artificial Physics Optimization Algorithm，APO Algorithm)[5-6]是一種基于種群的啟發(fā)式隨機(jī)搜索算法，同粒子群算法相比，其具有種群多樣性好、搜索效率高的優(yōu)點(diǎn)。這里考慮多船會(huì)遇態(tài)勢(shì)下的轉(zhuǎn)向避碰決策，將避碰規(guī)則作為行動(dòng)可行域的約束條件，利用擬態(tài)物理學(xué)優(yōu)化算法，從可行域的空間中求出目標(biāo)函數(shù)極小值，進(jìn)而得到轉(zhuǎn)向避碰決策。

1 船舶避碰決策模型

船舶間會(huì)遇并構(gòu)成碰撞危險(xiǎn)時(shí)，本船需采取相應(yīng)的避碰行動(dòng)進(jìn)行避讓。船舶避碰行動(dòng)包括轉(zhuǎn)向和變速2種，設(shè)其二維解空間為Xi(t)=(xi1(t),xi2(t))，其中：Xi(t)為t時(shí)刻問題可行域的第i個(gè)解;xi1(t)和xi2(t)分別為該解的航向和航速值。

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

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

模型中選取碰撞危險(xiǎn)度和航程損失作為子目標(biāo)函數(shù),其中：碰撞危險(xiǎn)度受最近會(huì)遇距離DCPA、最近會(huì)遇時(shí)間TCPA、船舶操縱性能和外界環(huán)境等諸多因素的影響，根據(jù)研究問題的需要，選取適當(dāng)?shù)呐鲎参ｋU(xiǎn)度模型[7-9]；航程損失則受轉(zhuǎn)向幅度等因素的影響。

2 基于APO算法的轉(zhuǎn)向避碰決策

2.1APO算法基本原理

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

2.2避碰目標(biāo)函數(shù)

2.2.1碰撞危險(xiǎn)度目標(biāo)函數(shù)

多船會(huì)遇轉(zhuǎn)向避碰情況下的碰撞危險(xiǎn)度模型較多，必須根據(jù)所研究問題的需要進(jìn)行選取。最小DCPA目標(biāo)船的DCPA值越大，危險(xiǎn)度就越低。因此，設(shè)碰撞危險(xiǎn)度目標(biāo)函數(shù)為

(1)

式(1)中：f1(xi)為種群中第i個(gè)個(gè)體的碰撞危險(xiǎn)度函數(shù)值，其值域?yàn)?0,1];dCPAir為第i個(gè)個(gè)體與第r個(gè)目標(biāo)船的最近會(huì)遇距離；N為目標(biāo)船數(shù)。目標(biāo)函數(shù)值越小，則第i個(gè)個(gè)體對(duì)所有目標(biāo)船的最近會(huì)遇距離的絕對(duì)值的最小值就越大，碰撞危險(xiǎn)度越小。

2.2.2航程損失目標(biāo)函數(shù)

避碰實(shí)踐中，考慮到《避碰規(guī)則》對(duì)避碰行動(dòng) “大幅度”的要求，航向變化角至少為30°[13]；考慮到要減小航程損失，要求轉(zhuǎn)向幅度盡可能小。因此，設(shè)航程損失目標(biāo)函數(shù)為

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

(2)

式(2)中：f2(xi)為種群中第i個(gè)個(gè)體的航程損失目標(biāo)函數(shù)值，其值域?yàn)閇0,1]；xi∈[30,180]。目標(biāo)函數(shù)值越小，則轉(zhuǎn)向幅度和航程損失就越小。

上述2個(gè)目標(biāo)函數(shù)的值域均在[0,1]內(nèi)，若對(duì)這2個(gè)子目標(biāo)分配權(quán)重7:3，則多目標(biāo)函數(shù)可簡(jiǎn)化為以下單目標(biāo)函數(shù)。

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

(3)

2.3種群初始化

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

2.4個(gè)體進(jìn)化

2.4.1個(gè)體質(zhì)量函數(shù)計(jì)算

(4)

式(4)中：f(xbest)為當(dāng)前代內(nèi)最優(yōu)個(gè)體的適應(yīng)值;f(xworst)為當(dāng)前代內(nèi)最差個(gè)體的適應(yīng)值。該質(zhì)量函數(shù)滿足2個(gè)性質(zhì):值域?yàn)?0,1]，且mbest=1；函數(shù)為非負(fù)單調(diào)有界函數(shù)。

2.4.2個(gè)體所受合力計(jì)算

(5)

(6)

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

2.4.3個(gè)體位置更新公式

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

(7)

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

2.5APO算法步驟

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

2) 隨機(jī)初始化種群：個(gè)體位置和速度。

3) 計(jì)算種群中所有個(gè)體的適應(yīng)值(式(1)～式(3))；選出最優(yōu)個(gè)體Xbest及其適應(yīng)值f(Xbest)，最差個(gè)體Xworst及其適應(yīng)值f(Xworst)。

4) 計(jì)算種群中所有個(gè)體的質(zhì)量(式(4))。

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

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

7) 計(jì)算更新位置之后種群中所有個(gè)體的適應(yīng)值，更新最優(yōu)個(gè)體Xbest及其適應(yīng)值f(Xbest)。

8) 判斷是否滿足結(jié)束條件。若滿足，則停止計(jì)算，輸出最優(yōu)個(gè)體Xbest及其適應(yīng)值f(Xbest)；若不滿足，則進(jìn)化代數(shù)t=t+1，返回至步驟“4)”。

3 實(shí)例仿真分析

3.1仿真實(shí)例

設(shè)本船的初始航向?yàn)?00°，航速為15 kn；能見度不良且不在互見中；同時(shí)有5艘船舶(分別命名為TS1,TS2,TS3,TS4,TS5)會(huì)遇，存在碰撞危險(xiǎn)。本船與目標(biāo)船的會(huì)遇態(tài)勢(shì)見表1，其中：DCPA為正值表示目標(biāo)船過本船艏部；DCPA為負(fù)值表示目標(biāo)船過本船艉部。

表1 本船與目標(biāo)船的會(huì)遇態(tài)勢(shì)

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

(8)

式(8)中：t為當(dāng)前代數(shù);tmax為最大循環(huán)代數(shù)。

3.2結(jié)果分析

仿真結(jié)果見圖1和圖2，其中：圖1為各代個(gè)體的最優(yōu)值，即船舶轉(zhuǎn)向避碰決策應(yīng)駛的最佳航向;圖2為各代最優(yōu)個(gè)體的適應(yīng)值。

圖1 各代個(gè)體的最優(yōu)值

圖2 各代最優(yōu)個(gè)體的適應(yīng)值

由圖1和圖2可知，結(jié)果最終收斂于某個(gè)固定值，500代內(nèi)即趨于穩(wěn)定，收斂速度快，算法執(zhí)行耗時(shí)5～8 s，能快速給出轉(zhuǎn)向避碰決策。為驗(yàn)證該算法的可行性和有效性，執(zhí)行30次運(yùn)算，得到個(gè)體最優(yōu)值的范圍為[42.0,46.5]，最優(yōu)個(gè)體適應(yīng)值的范圍為[0.295 8,0.309 0]，說(shuō)明該算法能獲得滿意的一致最優(yōu)解。

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

4 結(jié)束語(yǔ)

當(dāng)船舶間處于會(huì)遇態(tài)勢(shì)并有碰撞危險(xiǎn)時(shí)，多采取轉(zhuǎn)向避碰決策；而當(dāng)多船會(huì)遇時(shí)，局面較為復(fù)雜，對(duì)駕駛員的專業(yè)技能和經(jīng)驗(yàn)有較高要求，一旦決策失誤將導(dǎo)致碰撞事故發(fā)生。對(duì)此，在建立的船舶避碰決策模型的基礎(chǔ)上提出基于擬態(tài)物理學(xué)優(yōu)化算法的船舶避碰決策方法，旨在利用APO算法的快速全局尋優(yōu)能力為船舶駕駛員提供決策支持。針對(duì)多船會(huì)遇的復(fù)雜局面，考慮《避碰規(guī)則》的約束限制，建立基于最近會(huì)遇距離的避碰目標(biāo)函數(shù)，通過迭代進(jìn)化獲取最佳決策方案。結(jié)果表明：該算法可行、有效，能為船舶駕駛員提供決策支持。

[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] 王得燕, 劉以安. 粒子群算法在多船避碰決策中的應(yīng)用[J]. 計(jì)算機(jī)工程與設(shè)計(jì), 2009, 30(14): 3380-3382.

[5] 謝麗萍,曾建潮. 基于擬態(tài)物理學(xué)方法的全局優(yōu)化算法[J]. 計(jì)算機(jī)研究與發(fā)展, 2011, 48(5)：848-854.

[6] 曾建潮,崔志華. 自然計(jì)算[M].北京：國(guó)防工業(yè)出版社，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] 鄭中義, 吳兆麟. 船舶碰撞危險(xiǎn)度新模型[J]. 大連海事大學(xué)學(xué)報(bào), 2002, 28(2): 1-5.

[9] 劉茹茹,胡勤友. 一種主觀的船舶碰撞危險(xiǎn)度評(píng)價(jià)模型[J]. 上海海事大學(xué)學(xué)報(bào), 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] 王艷. 多目標(biāo)擬態(tài)物理學(xué)優(yōu)化算法及其應(yīng)用研究[D]. 蘭州: 蘭州理工大學(xué), 2011.

Collision-AvoidingCourseAlterationOptimizationwithArtificialPhysicsAlgorithm

YUJiagen,LIUZhengjiang,BURenxiang,GAOXiaori,LIWeifeng

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

2015-11-12

國(guó)家自然科學(xué)基金(51379026)；中央高校基本科研業(yè)務(wù)費(fèi)專項(xiàng)資金(3132016002;3132013004；3132013005；3132013015)

于家根(1984—)，男，黑龍江綏化人，講師，博士生，研究方向?yàn)榇爸悄鼙芘?。E-mail：yujiagen@dlmu.edu.cn 劉正江(1959—)，男，江蘇如皋人，教授，博士生導(dǎo)師，研究方向?yàn)楹Ｉ辖煌ò踩?。E-mail：liuzhengjiang@dlmu.edu.cn

1000-4653(2016)01-0036-03

U675.96

A