基于粒子群-遗传优化算法的船舶避碰决策

曾 勇， 张金奋， 张明阳， 张 笛

(1.武汉理工大学 a.智能交通系统研究中心； b.国家水运安全工程技术研究中心，武汉 430063； 2.阿尔托大学工程学院 应用力学系, 芬兰 艾斯堡 02270)

船舶智能避碰决策是《智能船舶发展行动计划(2019—2021年)》的八大关键技术之一，为解决船舶避碰问题，许多专家学者将启发式算法应用到船舶避碰决策研究中。倪生科等[1]利用多种群的遗传算法(Genetic Algorithm，GA)对船舶进行避碰辅助决策，用算法中精英种群内最优个体的最少保持代数作为算法的终止条件来评价所建立的适应度函数，仿真结果显示多种群的GA可有效地为船舶避碰提供辅助决策。马文耀等[2-3]利用细菌觅食算法(Bacterial Foraging Algorithm，BFA)与人工鱼群算法(Artificial Fish Swarm Algorithm，AFSA)对船舶避碰进行航线优化，结果表明：BFA与AFSA算法能得到避碰路径和避碰参数，可为船舶规划出合理的避碰航线，但研究仅考虑单一目标船舶的避让。田雨波等[4]将免疫粒子群算法(Immune Particle Swarm Algorithm，IPSA)应用到船舶避碰研究中，仿真结果证明该算法可找到船舶避碰的最优转向幅度。XU[5]和白一鸣等[6]基于危险模式下的人工免疫算法(Danger Immune Algorithm，DIA)对船舶的避碰策略进行优化，仿真实例显示DIA能够在船舶会遇的情况下为驾驶员提供一定的避碰决策支持。于家根等[7-8]利用拟态物理学优化算法(Artificial Physics Optimization Algorithm，APOA)与社会情感优化算法(Social Emotional Optimization Algorithm，SEOA)来研究分析船舶在特定会遇情形下的转向避碰决策问题。杨柏丞等[9]对传统的模拟退火算法(Simulated Annealing，SA)进行改进，并将之应用到多船会遇的转向避碰决策中，结果证明改进的SA算法能满足避碰决策的实时性。

粒子群优化(Particle Swarm Optimization, PSO)算法与GA是经常被使用的启发式算法，但PSO算法在计算函数极值时，常常出现早熟现象，导致求解函数极值存在一定的误差，而GA算法对于函数寻优采用选择、交叉、变异的操作，直接以概率化的寻优方法将目标函数作为搜索信息。综合运用粒子群优化-遗传(PSO-GA)算法的特点，可增强全局寻优能力、加快算法的进化速度和提高收敛精度。本文利用PSO-GA的混合优化算法对避碰决策进行研究，同时对算法生成的避碰路径分别从安全性和经济性进行分析，综合考虑国际海上避碰规则(Convention on the International Regulations for Prerenting Collisions at Sea, COLREGs)和船员良好船艺的要求，利用船舶碰撞危险度模型和避碰的目标函数模型评价路径的安全性与经济性，通过设计的PSO-GA算法，不断地进行自适应调整，从而获得满足要求的避碰路径。算法过程见图1。

图1 避碰路径算法过程

1 船舶会遇局面划分

根据COLREGs的规定，首先根据会遇态势确定船舶之间的避让责任。船舶之间的会遇局面可分为交叉相遇(他船位于区域A、区域B和区域D)，追越(他船位于区域C)，对遇(他船位于区域E)等3种。船舶会遇局面划分见图2。

图2 船舶会遇局面划分

依据避碰规则第13～15条的规定:当船舶之间有碰撞风险，如果他船位于区域A、区域B或E时，本船为让路船舶，要进行避碰操作；而当他船位于区域C或区域D时，本船为直航船舶，只有当让路船舶没有进行避碰操作或形成紧迫局面时，本船才需要进行避碰操作;当他船位于区域A或区域E时，本船舶通常要右转向进行避碰操作，尽可能地从他船的艉部穿过；当他船位于区域B时，本船可减少船舶速度或左转向进行避碰。

2 船舶碰撞危险度

船舶碰撞危险度(Collision Risk Index，ICR)是船舶之间可能发生碰撞事故的度量[10-11]，其值域为[0,1]，当ICR=0，说明船舶之间不存在碰撞风险，可自由航行；当ICR=1,说明船舶必然会发生碰撞；当ICR达到或超过某个阈值时，本船或目标船就必须要采取避碰行动，否则将会发生碰撞事故。ICR通常具有不确定性和模糊性等特点，目前还没有公认的计算方法或模型。影响ICR大小的因素有很多个，本文采用最近会遇距离(Distance of Close Point of Approaching,dCPA)和最近小会遇时间(Time to Close Point of Approaching,tCPA)来确定ICR，从而确定避碰时机。

船舶在会遇与避碰阶段，可通过船舶自动识别系统(Automatic Identification System,AIS)、自动雷达标绘仪(Automatic Radar Plotting Aid,ARPA)等获得船舶的速度、位置坐标、航向、相对位置等避碰数据。假设本船的初始位置为(x0,y0)、船速为v0、航向为θ0，目标船的初始位置为(xT,yT)、航速为vT、航向为θT：

令

Δx=xT-x0,Δy=yT-y0

(1)

A=vTsin(θT)-v0sin(θ0)

(2)

B=vTcos(θT)-v0cos(θ0)

(3)

则任意时刻t两艘船舶之间的距离可表示为

[d(t)]2=[(xT-x0)+(vTsinθT-v0sinθ0)t]2+

[(yT-y0)+(vTcosθT-v0cosθ0)t]2

(4)

再代入Δx、Δy、A、B可得

(5)

式(5)为关于时间t的二次方程，其最小值就是dCPA的数值，再对时间t求一阶导数为

(6)

将其代入(5)中，就可求出dCPA。使用此方法可与船舶上的助航仪器衔接，并可依据求得的tCPA的数值确定本船与目标船是否存在碰撞风险，如求得tCPA<0，说明船舶之间的距离越来越大，船舶之间不存在碰撞风险。

将dCPA与tCPA作为数据输入，采用模糊综合评判建立ICR的计算方法[12-13]为

(7)

式(7)中：u(dCPA)与u(tCPA)分别为dCPA与tCPA所采用的隶属度函数，其表达式为

u(dCPA)=

(8)

(9)

式(8)和(9)中：d1和d2分别为船舶最小安全会遇距离和安全通过距离，通常d2=2d1,t1和t2分别为船舶碰撞时间和注意时间。[13]

当船舶做出避碰决策时，最重要的就是对避碰决策的安全性进行分析，而最有效的办法就是计算本船与所有会遇船舶的ICR值，当所有的ICR值在可接受的区间内，可认为决策是安全的。

3 基于PSO-GA混合优化算法的船舶避碰决策研究

3.1 PSO算法与GA算法概述

PSO算法起源于鸟类的觅食行为，将问题的搜索空间类比成鸟类的飞行空间，将每只鸟抽象成一个无质量与体积的微粒，用以表示问题的一个候选解，而鸟类寻找食物的过程则是优化所需要寻找最优解的过程。

在PSO算法中，粒子i在N维空间里的速度和位置都表示成一个矢量。N维目标搜索空间中第i个粒子的速度与位置分别表示成vi=[vi1,vi2,…,vid]与向量Xi=[xi1,xi2,…,xid]。在搜索迭代过程中，用目标函数评价各粒子，以确定t时刻每个粒子的最佳位置Pbest和群体所找到的最佳位置gbest，更新粒子的位置与速度为

vij(t+1)=vij(t)+c1r1(pi-xij(t))+

c2r2(pgj-xij(t)),j=1,2,…,d

(10)

xij(t+1)=xij(t)+vij(t+1),j=1,2,…,d

(11)

式(10)和式(11)中：c1和c2为学习因子；r1和r2为0到1均匀分布的随机数。在PSO算法中还需要设置粒子的速度范围[vmin,vmax]和位置区间[xmin,xmax]，从而对粒子的移动进行限制。

GA是一种借鉴生物进化规律(适者生存，优胜劣汰)演化而来的随机优化搜索技术。GA的主要特点是不存在求导和函数连续性的限定，而是直接对参数进行编码运算。为防止陷入局部最优的陷阱，GA会沿着多种路线进行平行搜索，从而具有内在的隐并行性和更好的全局寻优能力。GA的全局搜索能力强，可克服PSO算法容易陷入局部最优的缺点，基于PSO-GA的混合优化算法对于函数寻优具有加速的作用。

本文对PSO算法中粒子群寻优过程中引入GA中的交叉和变异操作。[14]交叉时，先随机确定一个位置进行交叉，然后比较新旧个体的适应值。若适应值好于原个体，则进行替换；否则保持原个体。而变异操作采用正态变异，首先确定一个要变异的位置，然后产生一个服从正态分布的点来取代原来的位置。因为正态分布变异是小概率变异，所以不会引起优势个体的丢失。

3.2 PSO-GA算法的参数编码

PSO-GA算法的参数空间是用编码空间来代替的，然后以适应度函数作为评价依据来完成种群的不断更新，从而建立起一个搜索寻优的过程，最终通过不断的迭代找到问题的最优解。

当船舶存在碰撞风险而进行避碰操作时，船舶可采用变速、转向以及两者相结合等3种避碰方式。据文献[15]的研究分析，在大多数情况下，即使是多船之间的会遇避碰，船舶都能够采用一次转向或变速的操作来成功完成避碰，而且使用最多的避碰操纵是转向，一般较少采用同时转向和变速的避碰操作措施。因此，本文采用转向避碰操纵来完成船舶避碰。为提高寻优速度，本文对转向避碰操作中的2个重要参数进行编码。

3.2.1船舶的转向幅度θ

为满足避碰规则“大幅度”的要求，转向的幅度通常要求至少为30°。但转向幅度过大，会使船舶大范围的偏离原始航线，增加不必要的能源消耗。可将转向幅度设定为[30°, 60°]。在转向避碰过程中，让路船舶通常通过右转向来避免碰撞，一般不建议船舶左转向。[16]因此,在PSO-GA算法避碰优化过程中右转向为优先操纵。因研究的范围是互见中的开阔水域，当船舶完成转向的避碰操纵后，船舶将返回原来的航向，但不会回到初始的航线上。

3.2.2船舶在新航向上的航行时间t

船舶在新航线上的航行时间，若过短会使其他目标船无法正确地判断本船下一步会让行动，同时也会增加船舶的操纵难度；若时间过长，则会使船舶严重的偏离原始航线，增加复航的难度,因此将其限定在区间[tmin,tmax] 。船舶在新航向上航行时间t后就执行复航操作，回到原始航向上。

3.3 初始种群的产生

根据COLREGs的要求和船员与专家的先验知识随机产生初始种群，并在速度约束和位置范围内初始化种群。

3.4 适应度函数

3.4.1安全性目标函数

在船舶决策过程中，决策的目标是在COLREGs的要求下，找到一条安全经济的避碰航线，而安全性是最重要的影响因素。在船舶会遇中，船舶可先确定dCPA值最小的目标船舶，采用避让重点船舶的方式进行避碰，即希望船舶在避碰的过程中能以相对较大的dCPA完成避碰。由此，可设安全性目标函数为

(12)

式(12)中：f1为种群中个体i的安全性目标函数值；N为目标船数目；dCPAir为种群中个体i与目标船舶r的最近会遇距离，安全性目标函数的值越大，碰撞风险也越就小。由式(4)和式(5)可知：dCPA为关于转向幅度与航行时间的函数。

3.4.2经济性目标函数

为降低经济损失，要求在新航向上的里程不能过长，并且船舶在转向避碰操纵中的幅度不能过大，但又要尽量保证避碰路径的平滑，可设经济性目标函数为

(13)

(14)

式(13)和式(14)中：f2、f3为种群中个体i的经济性目标的函数值；θi为转向幅度，将转向幅度设定为[30°, 60°] ,v0为船舶速度。由于上述3个适应度函数的值域相同，可将3个多目标函数分配权重化简为以下的单目标函数为

minf(x)=af1+bf2+cf3

(15)

式(15)中：a、b、c都为权重系数，a取0.6，b与c都取0.2。

3.4.3PSO-GA算法步骤

(1) 船舶相关数据初始化，获取本船舶与目标船舶的相关信息，如航向、航速、相对距离和相对速度等。

(2) 根据船舶运动与避碰的数学模型，分析船舶会遇情况，如果本船舶周围没有与之会遇的船舶，则本船舶保持原来的航速和航向自由航行，否则转步骤(3)。

(3) 计算ICR值，确定重点避让船并结合COLREGs的要求，分析船舶之间的避让责任：如果是直航船舶，则进行保向保速；如果是让路船舶，则转步骤(4)。

(4) 当船舶之间的ICR≥0.5时，船舶进入避碰程序，启动优化算法。

(5) 设置算法的相关参数，根据经验或规则要求产生初始种群。

(6) 计算每个粒子的适应值；根据粒子的适应值，得到粒子的个体最优位置和全局最优位置。

(7) 引入GA的变异交叉操作，对全部粒子进行变异交叉操作，再把每个粒子将其个体最优位置和全局最优位置进行比较，若较好，则作为当前全局最好位置。

(8) 更新粒子的速度和位置，同时为保证避碰路径的平滑，将船舶避碰路径的搜索中心区域的范围限定在个体粒子和全局粒子所找到的个体最优值与全体最优值的最大距离的中间位置，以此为依据完成对船舶避碰路径的智能搜索以获得最优避碰操作策略。

(9) 船舶避碰行动完结进行复航，回到初始航向。

4 仿真案例研究

4.1 数值仿真验证

为验证PSO-GA算法的有效性，选用经典的Ackley函数与Schaffer函数进行算法验证。这两类函数存在非常多的局部最优陷阱，搜索全局最优位置较为困难。两类函数图形形状与最优解情况见表1，其三维图见图3。

表1 经典测试函数

a) Ackley函数

b) Schaffer函数

设置种群数量为100个，粒子的更新速度范围为[-1,1]，学习因子c1与c2均设为2，交叉概率设为0.70，变异概率设置成0.01，算法的迭代次数设为50次。分别运用GA、PSO、PSO-GA算法对Ackley函数与Schaffer函数进行寻优计算，得到适应度曲线分别见图4。

a) Ackley函数的算法优化过程

b) Schaffer函数的算法优化过程

对比图4适应度曲线，相对于单纯的GA与PSO算法，基于PSO-GA混合优化算法的寻优在迭代收敛性、稳定性、精度上都是最佳的，能够以较快的速度与较少的种群规模进化得到最优解。

4.2 多船避碰仿真

本文对3艘船舶之间的会遇展开研究，每艘船舶的初始位置、航行速度、航行方向见表2，船舶的初始会遇态势见图5。

表2 船舶会遇态势设置

图5 船舶初始会遇态势

由表2和图5可知：假设3艘船舶都遵守COLREGs，则本船OS需要给两艘目标船都让路，而TS2要优先避让TS1，则问题转化为：当船舶之间达到一定的碰撞危险度(这里当ICR≥0.5)，启动PSO-GA算法，为本船找到一条最优避碰路径，使其成功避让目标船舶TS1和TS2；为目标船TS2找到一条最优避碰路径，使其成功避让本船OS与目标船舶TS1。3艘之间的相关数据见表3。

表3 船舶会遇相关数据

启动PSO-GA算法对本船OS与目标船TS2进行避碰路径规划，为保证算法的可行性和有效性，执行15次运算，得到本船舶OS的平均最优值为(30, 0.15)，即本船的最优避碰操作是：右转向30°，在新航向上航行0.15 h完成避碰，然后恢复到初始航向继续航行。算法的迭代过程与结果见图6。在此避碰路径下本船舶与目标船舶TS1、TS2的ICR值向量是(0.039, 0.023)，避碰效果良好，算法得到的结果可行。将PSO-GA得到的结果与PSO、GA进行对比见表4。

图6 本船OS算法迭代过程

表4 3种算法的最优解迭代比较

从得到的结果可看出:PSO-GA算法能够在约束条件下迅速地找到函数的极值点，全局搜索能力快，而且没有陷入局部最优，在50次内就能够收敛于最优值。同理，算法经过仿真得到目标船TS2平均最优值为(41, 0.18)，即TS2最佳转向幅度为右转41°，在新航向上航行0.18 h。在此转向幅度下TS1与本船OS、目标船舶TS2的ICR值向量是(0.033，0.057)，见图7。

图7 目标船TS2算法迭代过程

5 结束语

在综合考虑COLREGs和良好船艺要求的基础上，通过dCPA和tCPA来计算船舶碰撞危险度。对避碰操作过程中的转向幅度与在新航向航行时间2个重要参数进行编码，建立基于转向幅度与航行时间的避碰目标函数，利用PSO-GA算法能够有效地提高收敛精度和加速全局寻优速度的特点，获得最佳转向幅度及在新航向上所需的航行时间。仿真结果表明：PSO-GA算法能够得到满意的最优解，为船舶驾驶人员提供一定的避碰决策参考，有助于提升船舶驾驶员在机器辅助下的避碰决策化水平。假设所有船舶都遵守避碰规则，并且认为船舶之间都会实时地获得周围船舶的避让行动，但在实际海上多船会遇局面下可能会出现人为失误或会遇船舶之间避碰措施不协调等情况。因此，在未来的工作中，将进一步考虑COLREGs和船员良好船艺的要求，设置会遇船舶避碰措施不协调的场景，对避碰决策进行训练与学习，提高对避碰决策失误的认识水平，提升避碰决策算法的可靠性。[17-18]