基于改进SPEA2 算法的多目标航线优化

王 军，蒋金阳，牛 壮

(大连海事大学 交通运输工程学院, 辽宁 大连 116026)

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(T≥2) 代开始，将种群P中所有非支配个体与AT-1中的个体进行比较，支配AT-1中任何一方的个体将被迁移到AT中。

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

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

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

2 基于改进SPEA2 的船舶航线优化

2.1 航线优化相关模型的构建

2.1.1 航行环境建模

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

2.1.2 目标函数设计

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

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

2.2 创建初始种群

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

2.3 种群更新

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

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

2.4 交叉、变异操作

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

2.5 检查终止条件

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

3 仿真实验与分析

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

表1 不同月份下航行环境的比较Tab.1 Comparison of sailing conditions in different months

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

图1 2018 年7 月的Pareto 前沿面Fig.1 Pareto frontier in July 2018

图2 2018 年4 月的Pareto 前沿面Fig.2 Pareto frontier in April 2018

图3 2018 年1 月的Pareto 前沿面Fig.3 Pareto frontier in January 2018

实验结果显示，进化算法求得的解在时间和油耗上均优于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 2018 年7 月的Pareto 航线集Fig.4 Pareto route set in July 2018

图5 2018 年4 月的Pareto 航线集Fig.5 Pareto route set in April 2018

图6 2018 年1 月的Pareto 航线集Fig.6 Pareto route set in January 2018

表2 进化算法的HV 结果比较Tab.2 Comparison of HV results of evolutionary algorithms

4 结 语

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