一种改进的多船转向避碰决策算法.pdf

第3 1卷第2 期2023 年6 月广州航海学院学报JOURNAL OF GUANGZHOU MARITIME UNIVERSITYVol.31No.2Jun.2023一种改进的多船转向避碰决策算法胡文兴，朱金善，孙慧勇，秦兴奋（大连海事大学航海学院，辽宁大连116 0 2 6）摘要：针对开阔水域多船会遇场景下的船舶避碰决策问题,提出一种改进后的多目标麻雀搜索算法（ImprovedMulti-objective Sparrow SearchAlgorithm，IM O SSA）.为增强种群多样性，引入模拟退火算法中的退火策略更新麻雀种群位置；基于精英选择策略，对所有非支配解的拥挤度距离进行降序排列,剔除最小的解并重复直到保留前沿解个数，以提高算法的全局收敛性能，更快去除劣解.仿真结果表明，改进后的IMOSSA在ZDT1上的反世代距离和空间评价指标较MOSSA分别下降了9 4.5%和89.7%，在多船会遇局面中能够得到符合条件的最优避碰转向角，有助于提高船舶智能避碰决策水平。关键词：多船避碰；麻雀搜索算法；多目标优化;Pareto前沿；精英选择策略中图分类号：U675.96随着全球进入“工业4.0”时代，智能航运将成为未来航运业发展的必然趋势，而船舶智能避碰决策作为智能航运发展的关键技术，有助于提高船舶自动化水平和决策效率，减少船舶碰撞事故的发生。很多学者利用遗传算法、模拟退火算法等启发式算法对船舶避碰的智能决策进行了研究.杨柏丞等1对基础模拟退火算法进行改进,并将之运用到多船会遇的转向避碰决策中,结果证明,改进的SA算法能满足避碰决策的实时性,但其并未对目标函数的权重分配进行说明.曾勇等2 将避碰转向幅度和在新航向上的航行时间加权为单一目标函数，使用基于粒子群遗传算法的混合避碰决策算法进行求解，仿真结果表明，该算法可为船舶避碰提供辅助决策，但其把所有会遇局面下的转向角限定在，且其同样没有对各目标函数的权重进行说明，不符合海员通常做法.多船避碰决策是一个多目标优化问题，因此需要对多个要素进行优化.然而，将多个目标函数进行线性加权的方法很难确定权重，而且多个目标函数相互冲突，很难找到一个解使所有函数同时达到最优，得到的避碰决策往往不经济.故本文考虑在开阔水域的多船会遇态势下（暂不考虑风、浪、流等收稿日期：2 0 2 3-0 0-0 0基金项目：国家自然科学基金资助项目（52 17 8 0 6 7）第一作者简介：胡文兴(19 9 3 一）,男，硕士生，主要从事交通信息工程及控制研究通信作者：朱金善（19 7 1一），男，教授，船长，研究生导师，主要从事船舶智能避碰决策研究，E-mail:文献标志码：A文章编号：10 0 9-8 52 6(2 0 2 3)0 2-0 0 0 7-0 7因素对船舶操纵的影响），提出一种基于快速非支配排序的改进多目标麻雀搜索算法,以解决避碰时多个目标间存在的权重分配问题,求取符合避碰规则和海员通常做法的帕累托最优解集，得到船舶最优转向避让幅度.鉴于船舶在开阔水域航行时通常仅通过转舵执行避碰行动，故本文不对船舶变速进行研究.1船舶碰撞危险度和决策目标函数1.1船舶碰撞危险度船舶碰撞危险度（CollisionRiskIndex，I c r）用来衡量船舶间发生碰撞可能性的大小，其值介于0,1之间,当其值为0 时,表示船舶间不存在碰撞危险，当其值为1时，表明船舶将发生碰撞.船舶碰撞危险度是驾驶员衡量船舶间碰撞危险程度以及采取避让时机的重要依据，目前关于碰撞危险度的研究成果有很多.本文采用模糊数学综合评价法，综合考虑dcpA（最近会遇距离）、tcpA（最近会遇时间）、相对方位B、相对距离D、船速比K以及水域通航密度和能见度情况等因素确定船舶碰撞危险度3 。设u(dcpA,)、u(t c PA,)、u(B,)、u(D,)、u(K,)分8别为本船与目标船r关于dcpA、t c p A、相对方位、相对距离以及船速比的危险隶属度函数,且均属于0,1,r=1,2,3,n,则本船与各目标船r的碰撞危险度IcR,可表示为IcR,=W,u(depA,r)+wzu(tcpA,r)+w3u(B,)+Tu(dcpA,r)=J 0.5-0.5 sindcPA,d22-dj0，式中:dcpA,为本船与目标船r的最近会遇距离;d,为良好且操船者水平较好时,H1、H 2、H,均取1.船舶安全会遇领域值;d,为最小安全通过距离4,且相对方位危险隶属度函数u(B)为d,=2d.u(B,)=0.5 1B,0.2,180B,1.00.4,1801.0(360-B,)180(360-B,)1.1180最近会遇时间危险隶属度函数u(tcpA,r）为0，(t2-ItcPA,（t2-ti1，式中：tcpA,为本船与目标船r的最近会遇时间.t和t计算方法如下：D-do,2dcpA,D,Di-dcpA.dcpA,D,12-depA.2t2=式中：t为碰撞时间，表示让路船从最晚施舵点到最近会遇点的时间;t2为注意时间，表示当本船与来船相距12 nmile时来船到最近会遇点的时间;u,为两船相对速度;D,为最晚避让距离,表达式如下：D,=H,H,H,dLA式中：dLA为最晚施舵距离，一般取8 倍本船船长；H1、H 2、H,分别表示航行区域通航密度、能见度状况以及人为因素影响；当船舶处于开阔水域，能见度广州航海学院学报W4u(D,)+wsu(K,)式中：2 3 4s为参数权重,且满足+z+W3+W4+W,=1.式(1）中，最近会遇距离危险隶属度函数u(dcpA,r)为1，20B,112.5cos(B,-19)+289相对距离危险隶属度函数u(D)为112.5B,1800,0.4,180B,247.5u(D,):0.2,247.5B,360式中:D,为本船与目标船r的相对距离;Dzr为本船(3)与目标船r的可采取避让措施距离，且D2r=H,H,H,1.7 cos(B,-19)+t2ItcpA,r14.4+2.89 cos(B,-19)Jti ItcpA,I t2(4)0ItcPA,Iti(5)(6)第3 1卷(1)dcpA,d,d,dcpA,d,d,dcpA,440+cos(B,-19)(D2,-D,D2,-D.)1，船速比危险隶属度函数u(K,)为u(K,)=1+K,K,+1+2K,sinC式中:C为碰角(0 C180);K,为目标船r与本船船速之比.1.2返避碰决策目标函数根据国际海上避碰规则第八条第3 款，船舶在开阔水域下的避碰通常由转向避让来完成，本文综合考虑船舶航行安全性和经济性建立相应的多目标函数.根据国际海上避碰规则第八条第2 款及海员通常做法，本船转向幅度一般不小于3 0.同时为考虑航行经济性，转向幅度不宜过大，故限定本船转向幅度为3 0,18 0）.要求本船转向后与各目标船的碰撞危险度应尽可能小,且对于某一目标船r,转向后的碰撞危险度应小于转向前.安全性目标函数为minf 1 fi=Z ler.(2)(7)17D2,D,D,D,D2rD,D12r=1(8)(9)(10)(11)第2 期式中f为本船转向后与n个目标船碰撞危险度之和,其值域为0,1,安全性目标函数值越小,表明本船与各目标船的碰撞危险度越小,越安全.经济性目标函数为minf,Vf.=60(180-0)(0-30)式中:f为航程损失目标函数,其值域为0,1,为转向幅度,向右转向为“+”,向左转向为“-”.随着转向幅度的增加,经济性目标函数值增大,航程损失增大.经济性目标函数越小,则转向幅度和航程损失越小.2基于 IMOSSA 的多船避碰决策研究2.1麻雀搜索算法简介麻雀搜索算法（Sparrow Search Algorithm,SSA）是XUE等5 受麻雀的觅食行为和反捕食行为的启发而提出的新型启发式算法.该算法具有稳定性好、寻优能力强和参数少的优点，已被广泛应用于求解车间调度以及路径规划等问题6-8 .在SSA中,根据麻雀种群中个体能量的大小分为发现者和加人者,同时还增加了反捕食机制.将种群中能量较高的麻雀作为发现者寻找食物，其他个体作为加人者,同时选取一定比例的麻雀作为警戒者.发现者和加人者的身份是随个体能量的高低动态变化的，但两者占整个麻雀种群的比例是不变的.模型中麻雀个体能量的大小取决于所对应适应度值的大小.2.1.1更新发现者位置发现者9 具有较好的适应度值，可以优先获取食物来源.而且，由于发现者负责为整个种群寻找食物并为加人者指引捕食方向，因此可以获得比加人者更广的觅食搜索范围.在每次迭代过程中，发现者的位置更新公式如下：Xi;j,y exp(Xij.Y+1=Xi.j.y+Q Z,式中.Y为当前迭代数,j=1,2,3,;Xij.+表示种群中第i个个体的第维位置;为（0,1的随机数；Q为标准正态分布随机数；Ymx为最大迭代次数;R(R2=0,1)和 Vsafe(Vsafe=0.5,1.0)分别表示预警值和安全值;Z为1y的矩阵,该矩阵所有元素均为1.当R,fgXij.Y+I=X.lij.Y+E.(f.-f.)+8式中,是步长控制参数,服从标准正态分布;E为1,1 的均匀随机数;8 为避免分母为0 的最小常数;f为当前麻雀个体的适应度值;f。和f分别为当前全局最佳和最差的适应度值.2.2基于SA和精英选择策略的IMOSSA2.2.1林模拟退火算法模拟退火算法最早由Metropolis等9 提出，是基于Monte-Carlo迭代求解策略的一种随机搜索算R,号时，此时适应度值较低的第i个加入者没有2获得食物，处于饥饿状态，将飞往其它地方觅食以(IXij.-Xwost,yl)(15)，fi=f法，在迭代更新可行解时，以一定概率接受比当前更差的解，因此可以跳出局部最优而达到全局最优.SA算法的解更新公式如下：1,m=1F(xnew)-f(xold)1)exp0.95式中：new为新解；ola为当前解；Y为迭代次数或退火温度；为初始温度；为接受新解的概率；f(xnew）和f(old）)越接近,n越大.P2f(xnew)f(xold)其它(16)10在0,1之间随机生成数8,若,则接受f(xnew）;若8 n,则在f（old）附近重新生成解并重复下去.在算法搜索前期大一些，这样不容易丢解,后期应小一些,以便于精准搜索.2.2.2精英选择策略IMOSSA中的精英选择策略借鉴了轮盘赌算法中“个体被选中概率与个体适应度值成正比”的思想,将第代生成的子代和父代合并，去除重复解后生成新种群，对新种群进行快速非支配排序，计算所有非支配解的拥挤度.拥挤度比较是保证种群多样性的重要环节,拥挤度指种群中给定点的周围个体的密度.如图1所示，以6 点周围相邻的两个点为顶点构造长方形,b的拥挤度距离b.为第b-1个和第b+1个所有目标函数值之差除以第k个目标函数最大和最小值之差的总和.b-1b+10图1拥挤度距离示意图拥挤度距离伪代码如下：1)令每个点的拥挤度距离ba=0;2)针对各目标函数，对种群进行非支配排序，令边界的两个个体拥挤度为无穷；3)计算每个个体拥挤度：4)重复2、3 步,得到所有个体的拥挤度距离ba，优先选择拥挤度大的个体，将较小的个体剔除，直到保留种群个数以保持种群多样性，式(17)中:m为目标函数个数;fisb+1为第b+1个点的第k个目标函数值;fis.b-1为第6-1个点的第k个目标函数值;fma和fmi分别为第k个目标函数的最大和最小值.2.2.3IMOSSA本文对基础MOSSA进行改进，提出IMOSSA，主要从以下方面进行改进：首先，针对基础MOSSA在更新种群位置时易陷入贪心寻优的问题，引人模拟退火算法,以一定概率接受劣解；其次,在对新种广州航海学院学报群进行快速非支配排序后，引入精英选择策略，对所有非支配解的拥挤度进行比较，更快地去除劣解，保持种群的多样性.IMOSSA流程如下：1)导入目标相关数据，初始化麻雀种群，设置种群规模P、最大迭代次数、模拟退火温度、安全值Vsafe和警戒者M.对初始解进行快速非支配排序并更新外部Archive，记录最优解对应的信息;2)whileYYmax;3)使用MOSSA更新种群，从Archive中随机选择一个个体作为种群历史最优解,以第一前沿等级个体作为发现者;4)fori=1:q;5)使用公式(13)更新发现者位置,将非第一前沿解作为加人者;6)end for;7)fori=（q+1):P;8)使用公式(14)更新加人者位置;9)end for;10)fori=1:M;11）使用公式（15）更新警戒者位置;12）endfor;13）使用模拟退火算法公式（16)更新种群，替换掉差解，避免算法陷入局部最优，保留个体历史最O优值;14)将父代和子代种群合并，基于精英选择策略，使用公式(17)对个体拥挤度距离进行计算并降序排列，剔除拥挤度最小的解并重复保留前沿解个O数；15）对新麻雀种群进行快速非支配排序，合并Archive集和第一序列支配解；16）去除重复解并进行快速非支配排序，保留种群个体；17)Y=Y+1；18)endwhile;19)更新Archive并输出所有最优解.五3仿真实验与分析3.1 IMOSSA 性能测试为验证IMOSSA的性能,本文选取ZDT1、Z D T 2和ZDT3共3 个经典基准测试函数进行算法测试，并和MOSSA进行对比,测试函数定义如表1所示.(17)表1测试函数函数决策变名称量维数ZDT13030ZDT2ZDT3第3 1卷目标函数F,()=xiF,(x)=h(x)1-/F,(x)/h(x)h(x)=1+9(Z2)/(n-1)F,(x)=xiFz(x)=h(x)1-(Fi(x)/h(x)h(x)=1+9(-2)(n-1)F,(x)=X1F(x)=h(x)1-/F.(x)/h(x)30-F(x)/h(x)sin(10F,(x)h(x)=1+9(Z=2x)/(n-1)第2 期3.1.1性能指标本文引入反世代距离评价指标和空间评价指标对算法性能进行测试.1)反世代距离dicdic指标通过计算每个真实Paretofront上的个体到Pareto参考解集的平均最小距离来评价算法的收敛性和分布性，该值越小,算法的收敛性和分布性越好.dic的计算公式如下：dic(G,入*)=式中：G为真实Paretofront上的点集；入*为算法获取的Pareto最优解集；IGI为真实Paretofront上点集个数;d(*,入*）为个体*到种群入*的最小欧式距离.2)空间评价指标dspdsp通过计算每个解到其它相邻解最小距离的标准差来评价解集的均匀性，该值越小越好.dsp的计算公式如下：(19)=IGI-1式中：d为d,的平均值;d,为第i个个体到相邻个体的最小欧式距离.3.1.2测试结果分析设置MOSSA和IMOSSA种群规模为40，迭代次数10 0 次，退火温度由10 递减到0.1，网格密度设为5,安全值Vsafe为0.8，警戒者数量为种群规模的2 0%，前沿解个数保留为种群规模数，算法通过MATLABR2017a实现.实验环境为：Inteli5-2430，2.4GHz四核处理器,4GB内存，WIN10操作系统.图2 图4为MOSSA和IMOSSA分别在3 个测试函数上的Pareto前沿图.表2 为两种算法分别在3 个测试函数上的测试结果对比.IMOSSA在ZDT1上的1.2110.80.60.4胡文兴，等：一种改进的多船转向避碰决策算法(18)1 GIIGIZ(d-d.)?.MOSSA.IMOSSAx11收敛性指标dic和均匀性指标ds,较MOSSA分别下降了9 4.5%和8 9.7%，在ZDT2上的收敛性指标和均匀性指标较MOSSA则分别下降了7 7.5%和92.8%.相较于MOSSA,IMOSSA在收敛性、均匀性和稳定性上均有明显提升，改进算法有效.1.210.80.60.40.2%0.10.20.30.40.50.60.7F(x)图3ZDT2 Pareto前沿图1.210.80.60.430.20-0.2-0.4-0.6-0.800.10.20.30.40.50.60.70.80.9F(x)图4ZDT3 Pareto前沿图表2算法测试结果对比算法对比测试函数指标ZDT1dicdsp运行时间(s)7.158ZDT2dicdsp运行时间(s)7.115ZDT3dicdsp运行时间(s)6.756*MOSSA.IMOSSA0.80.91一*MOSSAIMOSSA*x：MOSSAIMOSSA1.05E-02 5.71E-041.03E-01 1.06E-024.03E-03 9.06E-048.92E-026.4E-027.8601.2E-027.22E-032.07E-01 7.05E-02：*下降率94.5%89.7%8.77177.5%92.8%40%66%8.0930.23.2多船会遇仿真设本船航行在开阔水域，能见度良好且驾驶员0.10.20.30.40.50.60.70.80.91F(x)图2ZDT1 Pareto前沿图操船水平较好，本船初始位置（0，4）,初始航向000,航速10 kn，本船与各目标船的初始会遇态势124320-1-2-3-4-5-4如图5所示，各目标船的初始位置、航向及航速如表3所示，本船与各目标船的初始会遇信息如表4所示.本船与各目标船的碰撞危险度分别为0.7 7 0 4、参数相对距离(n mile)OS 与 TS12.236 1OS 与 TS24.242 6OS 与 TS35.852 3OS 与 TS45.024 9OS 与 TS57.000 00.450.40.350.30.250.20.150.30.350.40.450.50.550.60.650.70.750.8图6目标函数Pareto前沿图转向幅OS 与 TS1度()dcpa(n mile)57.913 31.000 059.664 51.029 359.760 91.030 962.916 71.083 066.293 61.137 970.653 31.200 775.129 61.277 678.828 11.334 285.025 91.426 193.599 21.546 9广州航海学院学报TS50.6519、0.59 8 0、0.6 17 9 和0.547 2,根据避碰规则，本船应给各目标船让路，启动IMOSSA执行转向TS4TS3TS1OS-3-2图5多船会遇态势相对速度(kn)16.523.030.129.728.0表5车转向后相关运动参数OS 与 TS2OS 与 TS3IcRdepa(n mile)0.740 22.070 50.739 72.125 90.559 02.128 90.529 62.22750.499 52.33130.463 92.462.30.432 52.593 30.411 32.698 70.386 42.869 10.374 23.091 3第3 1卷避碰操作.设置IMOSSA种群规模为10,图6 为迭代100次的目标函数帕累托前沿图，图7 为转向幅度TS2迭代过程，表5为本船转向后与各目标船的相关参数计算.表3 目标船航行信息目标船位置坐标-10 x/n mile航向()1234表4目标船初始会遇信息相对方位()dcpA(n mile)63.40.016 845.00.065 320.00.001 75.70.112 800686664626058560图7转向幅度选代过程OS 与 TS4OS 与 TS5IcRdcPAA(n mile)0.421 12.834 90.256 62.912 80.256 62.917 10.256 03.055 70.255 43.201 40.25483.38550.254 43.569 30.254 13.717 10.254 03.956 00.255 54.267 3航速(kn)TS1(2,-3)TS2(3,-1)TS3(2,1.5)TS4(0.5,1)TS5(0,3)tcpa(n mile)8.11811.07611.67610.13415.0002040送代次数IcRdepA(n mile)0.210 92.681 20.211 02.750 80.211 12.754 60.211 42.878 20.211 83.007 90.212.43.17120.213 23.333 80.214 03.464 10.215 63.673 60.218 33.944 13002702201951806080IcRdcpA(n mile)0.231 33.861 10.231 43.966 40.231 43.972 20.231 74.159 20.232 14.355 40.232 84.602.40.233 74.848 10.234 65.044 70.236 55.360 30.239 85.765 41716.5161412IcR0.770 40.651 90.598 00.617 90.547 21001201cR0.174 80.175 00.175 00.175 50.176 10.177 10.178 30.179 50.181 80.186 1第2 期由表5和图7 可知，算法在10 代左右完成收敛，当本船右转57.9 13 3 后，能够与各目标船保持在1nmile以上通过,转向后与各目标船的碰撞危险度分别为0.7 40 2、0.42 11、0.2 10 9、0.2 3 13 和0.1748,此转向幅度能够在满足航行安全性的同时最大限度地减少航程损失.4结语本文为解决多船会遇态势下船舶转向避碰问题,将基础多目标麻雀搜索算法和模拟退火算法以及精英选择策略相结合，提出一种改进后的多目标麻雀搜索算法，提高了算法的收敛速度和全局寻优能力，通过对算法性能进行测试，验证了算法的有效性；根据国际海上避碰规则和海员通常做法，将船舶航行安全性和经济性视作多目标优化问题，利用IMOSSA求解船舶最佳转向幅度.结果表明，IMOSSA可以找到令人满意的解，可以为船舶智能避碰决策提供一定的参考.胡文兴，等：一种改进的多船转向避碰决策算法(02):171-177.8张伟康,刘升,任春慧混合策略改进的麻雀搜索算法J.计算机工程与应用,2 0 2 1（2 4）：7 4-8 1.9胡大伟，朱志强，胡勇车辆路径问题的模拟退火算法J.中国公路学报,2 0 0 6(0 4)：12 3-12 6.13参考文献：1林杨柏丞，赵志垒.基于改进模拟退火算法的多船会遇避碰决策J.大连海事大学学报,2 0 18（0 2）：2 2-2 6.2曾勇，张金奋，张明阳，等基于粒子群遗传优化算法的船舶避碰决策J中国航海,2 0 2 0(0 1）:1-6,2 8.3周江华，吴春杰船舶碰撞危险度模型的构建J宁波大学学报（理工版）,2 0 0 4（0 1）：6 1-6 5.4关郑中义，吴兆麟船舶碰撞危险度的新模型J大连海事大学学报,2 0 0 2(0 2):1-5.5XUE J,SHEN B.A Novel Swarm Intelligence Optimization Approach:Sparrow Search Algorithm J.Systems Science&ControlEngineering An Open Access Journal,2020(01):22-34.6刘丽娜，南新元，石跃飞改进麻雀搜索算法求解作业车间调度问题J计算机应用研究，2 0 2 1（12：3 6 3 4-3 6 3 9.7 熊智，李欣童，熊骏，等.基于改进麻雀搜索算法的无人机集群置信传播协同定位方法J中国惯性技术学报，2 0 2 1An Improved Decision Algorithm for Multi-ship Steering Collision AvoidanceHU Wen-xing,ZHU Jin-shan,SUN Hui-yong,QIN Xing-fen(Navigation College,Dalian Maritime University,Dalian Liaoning 116026,China)Abstract:Aiming at the decision problem of ship collision avoidance in the scenario of multi-ship encounter inopen water,an improved multi-objective sparrow search algorithm is proposed.Introduction of an annealing strategyin the simulated annealing algorithm to update the sparrow population location to enhance population diversity.Based on the elite selection strategy,the crowd distance of all non-dominant solutions is sorted in descending order,the smallest solution is eliminated and repeated until the number of leading solutions is retained,so as to improvethe global convergence performance of the algorithm and remove the inferior solution faster.The simulation resultsshow that compared with MOSSA,the IGD and SP indexes of IMOSSA on ZDT1 decreased by 94.5%and 89.7%,and can obtain the optimal collision avoidance steering angle that meets the conditions in the multi-ship encountersituation,which is conducive to improve the intelligent collision avoidance decision-making level of ships.Key words:multi-ship collision avoidance;sparrow search algorithm;multi-objective optimization;pareto front;elite selection strategy