0 引　言

随着海洋运输在国际商品交换中所占比重越来越大，船舶航线优化被提到了重要的地位。该领域研究的问题是在考虑风浪环境条件的情况下，寻找给定航行的最优路径和航速，目标通常考虑最小航行时间、燃油消耗或通行风险^[1]。

近年来，多目标航线优化得到了较多关注，它可以同时针对多个目标进行优化，进而产生大量的权衡解，决策者可根据当前的需要确定最终的航行方案。目前，进化算法在解决该问题上取得了广泛应用^[2-3]，主要包括经典算法SPEA2^[4]、NSGA-Ⅱ^[5]以及一些改进的算法NMOEA^[6]、SPEA2+^[7]。然而，由于规划过程中存在庞大的样本量和优化空间，收敛效率慢成为普遍现象。特别是随着迭代步长的增加，搜索样本量的限制还可能导致算法陷入局部最优。

本文针对SPEA2在解决多目标航线优化问题中存在的收敛速度慢和易陷入局部最优的现象进行改进。通过Dijkstra算法搜索的可行解加入到初始种群中作为引导以加快算法寻优的效率；采用更精细化的选择过程保证精英个体可继续参与进化；提出新的交叉和变异策略，有效提升了种群质量。

1 SPEA2算法改进 1.1 SPEA2的基本思想

Zitzler^[4]提出的强度Pareto进化算法（SPEA2）是一种多目标进化算法，具有良好的搜索性能，它包含一些重要的操作，例如在适应度分配策略中，同时考虑了种群中的显性个体和隐性个体，提高了全局搜索能力；计算最近相邻个体的密度提高搜索精度；采用新的存档截断方法，保证边界解得以保留。

1.2 改进工作的动机

大多数优化算法无法找到更高质量的解，主要因为它们工作效率较低。例如，当种群中的大多数解处于非支配阶段时，粗糙的选择方法将剥夺优势精英继续参与进化的机会，导致优化结果停滞或更差。同时，交叉机制作为进化算法中生成新个体和扩展解空间的一种有效方法，还尚未被有效探索。尤其当种群中个体间差异较小时，算法易进入停滞状态，这时应增大变异概率，通过改变种群内个体的部分基因形成新的个体，以跳出局部最优。

1.3 SPEA2方法的改进

在种群更新阶段，改进后的算法只允许非支配个体加入到外部归档集 $ A $ ，位于Pareto前沿端点上的2个解被强制保留，防止算法陷入局部最优。并且从第 $ T\left( {T \geqslant 2} \right) $ 代开始，将种群 $ P $ 中所有非支配个体与 $ {A_{T - 1}} $ 中的个体进行比较，支配 $ {A_{T - 1}} $ 中任何一方的个体将被迁移到 $ {A_T} $ 中。

在交叉和变异阶段，事先给出比较值 $ K $ ，并与选中个体的相似度 $ r $ 进行比较， $ K $ 的计算公式为：

$ \left\{ \begin{gathered} K = \frac{{\sum\limits_{t = 2}^{N - 1} {U\left( {I{D_1}\left( t \right),I{D_2}\left( t \right),...,I{D_n}\left( t \right)} \right)} }}{{n \times \left( {N - 2} \right)}} 。\\ 1 \leqslant U\left( {I{D_1}\left( t \right),I{D_2}\left( t \right),...,I{D_n}\left( t \right)} \right) \leqslant n 。\end{gathered} \right. $

(1)

式中： $ I{D_i} $ 为组成个体 $ i $ 的基因序列； $ N $ 为序列的长度； $ t $ 表示基因值的位置，函数 $ U $ 表示 $ n $ 个个体的基因序列在 $ t $ 位置的非重复值的数量。因此，当种群内个体的基因序列都相同时， $ K = 1 $ ；基因序列都不同时， $K = 1/n$ 。相似度 $ r $ 的计算公式为：

$ \left\{ \begin{gathered} r = \frac{{\sum\limits_{t = 2}^{N - 1} {I{D_1}\left( t \right) - I{D_2}\left( t \right)} }}{{N - 2}}，\\ I{D_1}\left( t \right) - I{D_2}\left( t \right) = 0,1 。\\ \end{gathered} \right. $

(2)

若2个个体的基因值在 $ t $ 位置相等，则 $ I{D_1}\left( t \right) - I{D_2}\left( t \right) = 0 $ ，否则为 $ 1 $ 。当 $ r \geqslant K $ ，个体间差异较大，利用交叉操作进行个体间有用信息的交换，产生更多较好的个体。相反，当 ${{r < K}}$ 时，个体相似度较高，互相值得学习的信息较少，需要对二者进行变异操作以跳出局部最优，增大搜索空间。

2 基于改进SPEA2的船舶航线优化 2.1 航线优化相关模型的构建 2.1.1 航行环境建模

本文采用大圆航线作为网格系统的参考路径扩展航路点，从出发点开始，在大圆航线上每隔距离 $ \varepsilon $ 记录一次参考点，其中 $ \varepsilon $ 代表天气预报的空间分辨率。以每个参考点为垂足，生成垂直于当前大圆路线方向的其他路径点，航路点应只覆盖在船舶可能行驶的区域内。为避免船舶大幅度转弯和前往无效的航路点而造成不必要的成本消耗，需在系统中构建连接关系来保证船舶只能在相邻2个阶段中指定的航路点间移动。本文规定船舶的航行方向分为直行、左转和右转，因此系统中从任意一个路径点出发有可能到达下一阶段的3个不同航路点。

2.1.2 目标函数设计

目标函数是反映航线质量的性能指标，是优化的最终目的。本文以船舶航行时间 $ T $ 和燃油消耗 $ F $ 为优化目标，建立多目标优化函数：

$ {\rm{min}}T = \sum\limits_{i = 1}^{n - 1} {\frac{{{S_i}}}{{{v_i}}}}，$

(3)

${\rm{ min}}F = \sum\limits_{i = 1}^{n - 1} {{{\left( {{T_e}} \right)}_i}} \times {S_i}。$

(4)

式中： $n - 1$ 为航段总数； ${S_i}$ 、 ${V_i}$ 、 ${\left( {{T_e}} \right)_i}$ 分别为船舶在第 $i$ 阶段的航行距离、实际航行速度和主机有效推力。在动力不变的情况下，由于风浪的干扰，船舶实际航行速度较静止状态下的速度有所下降，本文采用文献[8]中的经验公式，计算在特定的气象环境和设定的服务航速下船舶的失速损失。

2.2 创建初始种群

初始种群 $ {P_0} $ 在求解的质量和效率上起着很大作用，如果 $ {P_0} $ 包含尽可能多的有利个体，它们可以在迭代过程中不断引导结果靠近帕累托边界，同时迭代次数会在大程度上减少。为保证解的多样性和优良性，采用以下3种方式来生成 $ {P_0} $ ：一是采用随机遍历的方法，在航行区域内随机生成一条满足网格系统连接关系的航线，并随机赋予一个船舶主机功率。二是采用大圆航线作为一部分初始种群，并同样赋予不同的船舶主机功率。三是采用Dijkstra算法寻找单目标优化下的最佳航线。

2.3 种群更新

种群中个体质量的好坏通过适应度函数评定。SPEA2采用细粒度的适应度分配策略，在计算种群 $ P $ 中个体的适应度 $ R\left( i \right) $ 时，种群和外部归档集 $ A $ 的个体都考虑在内。而且 $ R $ 值越小，说明支配该个体的个体越少， $ R\left( i \right) = 0 $ 表示个体 $ i $ 为非支配解，适应度计算方法为：

$ S\left( i \right) = |\{ j|j \in {P_T} + {A_T} \wedge i > j\} | ，$

(5)

$ R\left( {\text{i}} \right) = \sum\limits_{j \in {P_t} + {A_t},j > i} {S(j)} 。$

(6)

当外部归档集 $|{A_T}| < {{Q}}$ (预设值)时，通过 $ k $ 临近算法估算个体密度值，并将特征空间最邻近的个体逐个剔除，直至 $|{A_T}| = {{Q}}$ ；相反，若外部归档集 $|{A_T}| < {{Q}}$ ，则根据适应度排序选择前 ${{Q}} - |{A_T}|$ 个支配解，直至 $|{A_T}| = {{Q}}$ 。

2.4 交叉、变异操作

交叉通过随机选择2个个体共同经过的航路点 $ a $ （起终点除外），将父代1从第1个至第 $ a $ 个航路点的位置信息都复制到子代，第 $ a + 1 $ 至最后1个航路点的位置信息从父代2上复制。在变异个体上随机选择一个变异点，使该变异点处的船舶路径随机发生改变。操作后的子代和父代共同组成新的种群继续参与进化。

2.5 检查终止条件

随着迭代步数的增加，与最大迭代次数进行比较。如果超过最大迭代次数，则终止算法，否则返回种群更新继续完成种群进化。

3 仿真实验与分析

仿真实验设定的航线起点为横滨附近（35.25N，141.75E），终点为旧金山附近（37N，122W），分别在3个月份下进行多目标航线优化实验，航行环境比较结果如表1所示。

船舶出发时间设定为每月6号上午11：00，选择3500 TEU的集装箱船进行仿真，其标准排水量为47202.48 t。为验证算法的性能，将本文算法与Dijkstra、NMOEA和SPEA2进行比较，其中针对3种进化算法，设定初始种群容量为34，外部种群容量6，交叉概率0.8，变异概率0.2，最大迭代次数100，求解出的Pareto前沿面如图1～图3所示。

实验结果显示，进化算法求得的解在时间和油耗上均优于Dijkstra算法得到的结果。另一方面，本文提出的算法在收敛性上优于NMOEA和SPEA2，且随着气象的变差，优势表现越明显。从多目标进化算法性能评价指标-超体积（HV）^[9]的角度对结果进行数学分析。表2比较了3种进化算法求得解的HV值，HV值越高，群体中个体的综合表现越好。将（1120，260）作为参考点进行HV的计算，结果显示本文提出的算法综合性能最高，其次SPEA2，最差的是NMOEA。

图4～图6分别展示了3个月份下的Pareto航线集，对于海况较好的7月和4月，该月份下的航线集主要是以Dijkstra求得的航线为基础并对其优化。优化部分主要集中在航线的后半段，但在海况较差的1月份，它的Pareto航线集不仅包含Dijkstra的结果，还包括随机路线，这些路线光滑度较低，但在省油和省时方面仍优于Dijkstra结果。

4 结　语

针对多目标航线优化问题，本文构建了燃油成本和航行时间最小的双目标优化模型，并设计了基于SPEA2的引导性多目标进化算法。通过在初始种群中加入Dijkstra算法得到的单目标优化结果，以此作为引导，并在种群更新阶段进行改进，保证了具有代表性的精英个体继续参与进化。为避免种群优良基因的破坏以及陷入局部最优，对交叉和变异机制进行改进。最后以太平洋航线为例，在不同海况条件下进行仿真实验，验证了算法的高效性。与NMOEA和SPEA2 多目标进化算法的求解结果进行对比，证明本文算法具有较好的收敛性和全局寻优能力。