0 引　言

针对船舶航行过程中会经常由于航行路线不佳，出现船舶故障、损坏的情况^[1]。在船舶出发之前，经常会事先通过计算获得船舶航行的最优航线，计算过程除了要考虑海洋上千变万化的自然干扰因素之外，还需要考虑航行距离、能源消耗等数个因素影响问题，计算时需要优化航行距离、环境干扰等因素^[2-4]。常见的计算方法，经常会导致航线规划后航行出现偏差，出现无效航线规划的结果，既无法节约航行时消耗的成本，还导致计算成本上升，航行过程也无法正确避免海洋上的障碍物^[5-6]。为解决这一问题，众多研究者都作出相关研究：有学者提出以改进A～*算法作为基础的航线规划方法，构建水体环境的约束条件，利用代价函数优化A～*算法，规划航行的线路，该算法能够针对较为复杂的水体环境规划出船舶航行的路线，但是计算过程中可能丢失计划航线上的部分节点，经过反复验证，部分实验结果仍旧出现线路误差情况，仍旧需要进一步改进^[7]；还有学者使用改进人工势场法规划船舶的航行路线，先构建一个海洋环境的抽象力场，通过求和力场计算出船舶的路径寻优，通过路径寻优针对复杂环境规划航行路线，该方法稳定性较高，但是计算过程中会大致陷入局部极小值，计算时会出现引力与斥力，对于较为狭窄的海洋环境容易忽略，导致出现规划错误^[8]。

粒子群算法是一种全局搜索方法，通过鸟群觅食的习性，演化出计算方法，计算过程简单易懂，具有更高的计算效率。目前相关研究为提升粒子群算法的效率，提出诸多改进方法，主要防向都是避免算法过早收敛陷入局部最优。改进后的粒子群算法具有更加良好的择优效果，能够搜索出更加准确的结果，应用于船舶航线搜索，将会获得更加良好的效果。本文研究基于改进粒子群优化算法的船舶最优航线导航，通过路径寻优，计算出最合适的船舶航行路线。

1 船舶最优航线导航方法 1.1 基础粒子群算法

粒子群算法从自然中鸟群的飞行觅食状态中获得灵感，通过将随机粒子初始化并迭代探索出最优解。假设存在 $ n $ 个粒子 $ d $ 维空间中搜索，一个 $ d $ 维向量第 $ i $ 个粒子对应， $ {X_i} $ 代表粒子位置： $ {X_i} = \left( {{x_{i1}},{x_{i2}}, \cdots ,{x_{id}}} \right) $ ，其中 $ i = 1,2, \cdots ,n $ ，另一个 $ d $ 维向量与第 $ i $ 个粒子的飞行速度相对应， $ {V_i} $ 代表粒子速度： $ {V_i} = \left( {{v_{i1}},{v_{i2}}, \cdots ,{v_{id}}} \right) $ ，个体极值是第 $ i $ 个粒子所能检索到的最优位置： $ {P_{best}} = \left( {{p_{i1}},{p_{i2}}, \cdots ,{p_{id}}} \right) $ ，全局极值就是粒子群所能检索出的最佳位置： $ {g_{best}} = \left( {{p_{g1}},{p_{g2}}, \cdots ,{p_{gd}}} \right) $ ，确定2个极值后，通过式(1)与式(2)实现粒子的位置 $ {x_{id}} $ 与速度 $ {v_{id}} $ 更新：

$ {x_{id}} = {x_{id}} + {v_{id}}，$

(1)

$ {v_{id}} = \omega *{v_{id}} + {c_1}{r_1}\left( {{p_{id}} - {x_{id}}} \right) + {c_2}{r_2}\left( {{p_{gd}} - {x_{id}}} \right) 。$

(2)

式中： $ {c_1} $ 与 $ {c_2} $ 均代表加速度因子； $ \omega $ 为惯性权重； $ {r_1} $ ， $ {r_2} $ 属于 $ [0,1] $ 内的均匀随机数。

1.2 改进粒子群算法

1)更新粒子速度方式

粒子群算法迭代更新过程中对于位置、速度向量较为关注，这2个向量都能实现指标解代价 $ J $ 的评价。粒子运动过程中经常过早陷入局部最优，导致粒子动能消耗，熵值降低。本文以动能为基础，对于较差粒子群动能，使用式(3)表示整个粒子群中选取 $ {m_1} $ 个 $ J $ (评估解代价)较小的精英粒子群动能：

$ E_k^{{m_1}} = \sum\limits_{j = 1}^{{m_1}} {v_j^T{v_j}} ，$

(3)

其中， $ j $ 粒子的速度使用 $ {v_j} $ 描述， $ k $ 表示迭代次数。使用式(4)表示迭代后出现动能损失的精英粒子群：

$ \Delta E_k^{{m_1}} = E_k^{{m_1}} - E_{k - 1}^{{m_1}} ，$

(4)

在整个粒子群之中选取 $ {m_1} $ 个 $ J $ 较大同时也较差的粒子群，补偿该粒子群动能，更新该种群的位置与速度的更新：

$ x_{id}^{k + 1} = x_{id}^k + v_{id}^{k + 1} ，$

(5)

$ v_{id}^{k + 1} = wv_{id}^k + {c_1}{r_1}\left( {p_{id}^k - x_{id}^k} \right) + {c_2}{r_2}\left( {p_{gd}^k - x_{id}^k} \right) + {\Delta _{id}} 。$

(6)

式中， $ {\Delta _{id}} $ 代表受到精英粒子群诱导之后出现的较差粒子群惩罚系数。受到进化影响， $ {\Delta _{id}} $ 能够补偿较差粒子，迭代条件确定之下，粒子群中较差的一小部分群体呈现出较为活跃的状态，这些群体在 $ d $ 维空间中出现大范围移动，提升最优解找寻的效果。

2)以最差粒子为基础的速度更新方法

分析式(1)与式(2)能够看出，基础的粒子群算法中，粒子运动时一方面通过自身实现经验学习，另一方面还会从种群中获得粒子的行为经验，这种学习行为的参照物是种群内的最优粒子。

构建全新以最差粒子作为发点的位置与速度更新方式，更新结果见下式：

$ x_{id}^{k + 1} = x_{id}^k + v_{id}^{k + 1} ，$

(7)

$ \begin{split} x_{id}^{k + 1} =& x_{id}^k + v_{id}^{k + 1} + {c_1}{r_1}\left( {p_{id}^k - x_{id}^k} \right) + {c_2}{r_2}\left( {g_{id}^k - x_{id}^k} \right) - \\ &{w_1}{r_1}\left( {P_{id}^k - x_{id}^k} \right) - {w_2}{r_2}\left( {G_{id}^k - x_{id}^k} \right) 。\end{split} $

(8)

$ P_{id}^k $ 与 $ G_{id}^k $ 分别表示粒子与种群所能搜索的最差解位置； $ {w_1} $ 与 $ {w_2} $ 均表述全新的学习因子，该因子主要表示粒子速度更新时个体与全局最差解发挥的作用。

1.3 基于改进粒子群算法的船舶最优航线导航建模

船舶最优航线导航模型构建实际上就是先确定船舶的起点 $ S $ 与终点 $ D $ ，根据航行可能经过的各个坐标点，确定多个航行坐标点序列，也就是 $ N $ 个航迹点坐标，串联这些坐标点，形成船舶航行的航线。

使用式(9)表示 $ N $ 个航迹点坐标：

$ {X_i} = \left[ {{x_{i,1}},{x_{i,2}}, \cdots ,{x_{i,N}},{x_{i,N + 1}},{x_{i,N + 2}}, \cdots ,{x_{i,N + N}}} \right]，$

(9)

式中， $ N $ 个航迹点横坐标也是前 $ N $ 维分量， $ N $ 个航迹点纵坐标则是后 $ N $ 维分量。由此可以划分： $ \left( {{x_{i,1}},{x_{i,N + 1}}} \right) $ 表示起点后的第1个航迹点坐标； $ \left( {{x_{i,2}},{x_{i,N + 2}}} \right) $ 代表第2个航迹点； $ \left( {{x_{i,N}},{x_{i,N + N}}} \right) $ 代表第 $ N $ 个航迹点。

使用 $ 2N $ 维数的粒子在某个时刻时的位置描述航迹点坐标信息：

$ {X_i}\left( t \right) = \left[ {{X_{i,1}}\left( t \right),{X_{i,2}}\left( t \right), \cdots ,{X_{i,2N}}\left( t \right)} \right] ，$

(10)

设存在一个 $ M $ 大小的粒子群，则通过矩阵描述该粒子群， $ {X_i} = \left\{ {{X_1},{X_2}, \cdots ,{X_M}} \right\} $ ， $ 1 \leqslant i \leqslant M $ 。粒子群中的各个粒子均能当作一个船舶航线导航。经过以上分析可以使用 $ 2N $ 维度、 $ M $ 规模的粒子群表示船舶航线导航模型。约束条件和优化目标决定潜在船舶航线是否最优，通过代价函数描述这种关系，代价函数与粒子适应度值呈现出正比例关系。使用式(11)计算船舶可能发生的风险与潜在航线坐标 $ {X_i} $ 之间的代价：

$ {J_{threat}}\left( {{A_i}} \right) = \sum\limits_{l = 1}^L {\sum\limits_{j = 0}^N {{S_l}*{J_{l,j}}} }，$

(11)

$ {S_l} $ 为第个威胁强度系数，由于最优路径探索中需要考虑可能存在的障碍物，威胁强度系数可以直接取值为1； $ {J_{l,j}} $ 为第 $ j $ 段航线受到第 $ l $ 个潜在危险项的威胁程度。航线寻优主要就是计算障碍物对于船舶的威胁程度，所以使用式(12)计算 $ {J_{l,j}} $ ：

$ {J_{l,j}} = \left\{ \begin{gathered} 0,{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {b_{l,j}} > R，{\kern 1pt} {\kern 1pt} \hfill \\ \frac{R}{{{b_{l,j}}}} - 1{\kern 1pt} {\kern 1pt} ,{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} 0 < {b_{l,j}} \leqslant R，\hfill \\ \infty ,{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {b_{l,j}}{\text{ = }}0。\hfill \\ \end{gathered} \right. $

(12)

式中： $ R $ 为安全距离；第 $ j $ 段船舶航迹和第 $ l $ 个障碍物之间的最近距离描述为 $ {b_{l,j}} $ 。如果 $ {b_{l,j}} $ 的值为0，说明障碍物边界与船舶航线交错。全部航线距离即为潜在航线的长度代价：

$ \begin{split}{J_{length}}\left( {{X_i}} \right) =& {b_{i,0}} + {b_{i,N}}_{ + 1} + \sum\limits_{j = 1}^{N - 1}\times\\ &{\sqrt {{{\left( {{x_{i,j}} - {x_{i,j + 1}}} \right)}^2} + {{\left( {{x_{i,j + N}} - {x_{i,j + 1 + N}}} \right)}^2}} }。\end{split} $

(13)

式中： $ {b_{i,0}} $ 代表第一个航迹节点与第 $ i $ 条航线之间的距离； $ {b_{i,N}}_{ + 1} $ 为终点 $ D $ 和搜索到的最终航迹节点之间的距离。 $ j $ 是航迹节点序号。

船舶水平转角代价 $ {J_{angle}}\left( {{X_i}} \right) $ 也会影响船舶航线的规划：

$ {J_{angle}}\left( {{X_i}} \right) = \sum\limits_{j = 1}^N {{\theta _j}} ，$

(14)

式中第 $ j $ 段航迹向下个航迹转入的转角描述为 $ {\theta _j} $ 。

经过以上分析能够计算出粒子的适应度函数(航线优劣评价参数)为：

$ \begin{split}Fitness\left( {{X_i}} \right) = &{\omega _1}*{J_{threat}}\left( {{X_i}} \right) + {\omega _2}*{J_{length}}\left( {{X_i}} \right) +\\ &{\omega _3}*{J_{angle}}\left( {{X_i}} \right) 。\end{split}$

(15)

其中： $ {\omega _1} $ ， $ {\omega _2} $ ， $ {\omega _3} $ 都是权重系数，这3个系数相加，和为1，适应度函数计算结果越小证明航线导航更优。

2 仿真试验结果与分析

本文研究对象为双桨双舵柴油动力船，船长与船宽度分别为62.81 m和17.21 m，整体型深为6.41 m，设计夏季满载情况下的吃水水线为5.3 m，排水量为4287.8 t；空载时吃水接近2.744 m，排水量为1961.181 t，可参考载货量约为1343 t，构建材质为钢质。搭载G8300ZC31B-1主机，转速与功率分别为700 r/min和2317 kW，发电机组的功率为350 kW，应急配电形式为立式。试验过程中综合考虑船舶的性能参数，选取某海域地形图输入到模拟试验平台中，利用本文方法为该船舶搜索最优航线导航路径。初始化权重取值为1.0，2个加速度因子取值为2，这2个加速度因子分别反映出粒子对于自身的认知能力以及社会信息共享重要度，加速度因子会受到新学习因子的干扰，所以学习因子的取值设定为1，较差粒子个数设定为5。

需要通过对比体现出线路导航效果的优劣，所以分别使用改进A～*算法作为基础的航线导航方法以及改进人工势场法作为基础的航线导航方法，针对研究对象和海域同时在模拟试验平台中开展试验，这2个对比方法分别来自参考文献[7]与参考文献[8]。

收集航线中随机5个航迹点的经、纬度、航向角数据，分别使用3种方法计算这些数据内容，将计算结果与实际数据相对比，对比结果见表1。可以看出，改进A～*方法与改进人工势场方法与实际航行数据之间的差距较大，平均误差均超过4.9。本文方法计算后的航行数据与实际航迹点数据较为接近，平均误差只在0.5上下，说明使用本文方法计算航迹参数，准确效果较高，有利于为最优航线导航的确定打下良好基础。

根据航迹点会搜索出多条潜在船舶航线导航路径，各方法搜索结果见图1。可以看出，使用本文方法搜索的路径，未出现重复线路，能够极大程度节省航行时间消耗，降低航行过程中产生的不必要成本以及能源浪费，是一种比较优异的航行导航路径。

将某个实际海域资料导入到模拟试验平台之中，利用本文方法以及2种对比方法分别在该海域图像上搜索船舶航行最优航线导航路径，结果见图2。可以看出，对于较为复杂的凹形海洋障碍物，2种对比方法搜索的航线显示，在凹形海洋障碍物附近均出现错误搜索现象，航线在这附近出现重复绕行，而且2种对比方法尽管能够规避大多数海洋中的障碍物，但是绕行距离较远，耗费更多航行时间，不属于最优航线导航路径。本文方法能够搜索最短航线并且成功绕过难以识别的复杂地形，成功搜索出最优航线导航路径。

3 结　语

本文提出了改进粒子群优化算法的船舶最优航线导航方法，在基础粒子群算法的基础上使用精英粒子与较差粒子概念，补偿较差粒子，防止寻优提前陷入早熟，吸取最差粒子的经验，避免搜索最差解。将改进后的粒子群算法应用于复杂的海洋环境之中，实现船舶最优航线导航。经过实际试验发现，本文方法计算结果最为接近实际船舶数据，具有较高准确性，同时航线检索的时间最短，能源消耗最少，搜索成功后的航线能够规避海洋中的障碍物，航线导航效果最好。