船舶操纵性优化的约束多目标进化算法

刘冰洁，毕晓君

(1.哈尔滨工程大学 信息与通信工程学院，黑龙江 哈尔滨 150001；2.中央民族大学 信息工程学院，北京 100081)

随着造船和航运业的发展，船舶向着高速化、大型化、专用化发展，航道上船舶航运密集程度增加，船舶操纵与控制的难度加大，发生碰撞、触底等海难事故的概率及由此带来的危害增大，提高船舶固有操纵性日渐显示出其重要性，成为船型设计中至关重要的一环[1-2]。船舶操纵性优化是一个多变量、多约束的复杂多目标优化问题。传统的优化过程是定性分析比较和人工不断凑试的过程，这种半经验半理论的优化方法通常带有一定的盲目性，费时费力，很难为设计者提供多目标优化的设计方案。

随着人工智能的发展，群智能进化算法逐渐应用到船型优化设计中，取得了一定的成果[3]，但目前对船舶操纵性优化的研究仍旧相对较少，其中多数研究都是将船舶操纵性优化的多个目标转化成单目标后进行求解[4-6]，这些方法由于事先设定了偏好信息，所求得的解受设计者先验知识的影响，不能覆盖所有的解集，极易遗漏更好的解。还有学者研究利用多目标进化算法对此进行求解，文献[7]通过一种Pareto遗传算法得到均匀分布的Pareto解集，但约束条件仅为设计变量的上下限，对船舶操纵性优化数学模型的描述不够准确；文献[8] 将NSGA-II和MOPSO应用到船舶水动力性能综合优化当中，寻求适用于船舶水动力性能优化的多目标进化算法及其参数配置，但考虑的约束条件仅为设计变量的上下限，并未涉及约束处理技术；文献[9]采用解析目标分流法，实现快速性、操纵性等5个学科组成的船舶总体设计优化问题，较好地解决了船舶总体设计学科间复杂耦合所带来的计算困难，但其采用的约束处理技术为罚函数法，其中的参数较难设置，而且影响收敛精度；文献[10]通过在基于分解的多目标进化算法(multi-objective evolutionary algorithm based on decomposition, MOEA/D)中引入自适应约束处理技术和目标值归一化机制，获得船舶水动力性能优化的Pareto解集，但其可行度参数仅随种群中可行解比例变化，没有考虑到进化不同阶段对不可行解的重视程度不同，且其约束处理技术仅在个体选择阶段，无法有效利用优秀的不可行解，影响了优化的精度；不能兼顾良好的多样性和局部搜索能力，无法应对多约束条件导致的复杂空间拓扑结构，影响了优化的精度。

针对上述问题，本文建立了船舶操纵性优化问题的数学模型，并提出一种船舶操纵性优化的约束多目标进化的方法：采用MOEA/D作为进化算法框架，将差分进化(differential evolution, DE)策略引入到MOEA/D中，并充分利用优秀的不可行解对DE策略进行改进，增强各搜索方向间的信息交互，提高船舶操纵性设计方案的收敛性能；其次，充分利用优秀的不可行解，设计新的个体比较准则，提高种群的分布性，使得船舶操纵性设计方案集在具有较好收敛性的同时获得较好的分布性，给设计者提供多个不同需求下的优化结果，设计者可以根据对操纵性衡准指标的不同需求自行选择设计方案。

1 船舶操纵性优化的数学模型

船舶操纵性优化是一个多变量、多约束的复杂多目标优化问题，不失公平性，本文与文献[5]一致，以一艘载重量35 000 t原油船为例，讨论船舶的操纵性优化问题。

1.1 设计变量

选取目前船舶操纵性优化中常用的6个船型参数作为设计变量：船长L、船宽B、吃水T、方形系数CB、舵的展高hR和舵的弦长bR[5]。

1.2 目标函数

我国船舶标准化委员会操纵性分组通过的《海洋船舶操纵性标准》中，规定主要从船舶的回转性、直线稳定性和航向机动性3个性能指标来衡量船舶操纵性能[11]。由于航向机动性目前在国内外没有统一的评价标准，而且需要较多实验资料来表述，所以，与现有文献一致，在本优化模型中只选取相对回转直径D′和直线稳定性指数C′作为衡量指标[5]。

1)直线稳定性指数为：

(1)

2)相对回转直径D′的计算采用Lyster和Knights基于实船试验数据提出的相对回转直径回归公式：

D′=4.19-203CB/|δ|+47.4Trim/L-13B/L+

194/δ-3.82(hR×bR)/(L×T)+7.79Ab/(L×T)

(2)

式中：δ为舵角；Trim为船舶倾斜；Ab为艏部浸湿面积。

上述2个目标性能指标中，C′>0表示船舶在水平面内的运动具有直线稳定性，C′<0表示不足有直线稳定性。直线稳定性指数C′越大，表明船舶稳定性越好，相对回转直径D′越小，表示船舶回转性越好。

1.3 约束条件

根据文献[5]，船舶操作性优化的11个约束条件为：

(3)

式中：Δ=CBρLBd是排水量;ρ=1 025 kg/m3为海水密度。

1.4 船舶操纵性优化数学模型

综上所述，船舶操纵性优化数学模型描述为：

minF(X)=[f1(X)f2(X)]T=[-C′D′]T

s.tgj(X)>0,j=1,2,…,11

(4)

式中：X=[LBTCBhRbR]T为决策向量，F(X)为目标向量，由于直线稳定性指数C′越大越好，此处加上负号使其转化为最小化问题，gj(X)为式(3)所示的11个不等式约束条件。如果决策向量X满足所有约束条件，则称其为可行解；如果不完全满足式(3)中的约束条件，则称其为不可行解。根据这些约束条件计算个体的约束违反度函数，如式(5)所示，其值称为个体的约束违反度。

(5)

式中：当gj(X)≤0，〈gj(X)〉返回其绝对值；当gj(X)>0时，〈gj(X)〉返回0。因此，当X为可行解时，G(X)=0；当X为不可行解时，G(X)>0。

2 船舶操纵性优化的约束多目标进化算法

本文建立的船舶操纵性优化模型包含6个设计变量、2个目标函数，11个不等式约束条件，是一个多变量、多约束的非线性约束多目标优化问题。为解决此问题，本文提出一种船舶操纵性优化的约束多目标进化算法。采用MOEA/D作为多目标进化算法的框架，引入DE进化策略，并充分利用优秀的不可行解对DE变异算子进行改进，增强各搜索方向间的信息交互，提高船舶操纵性优化算法的收敛性能；其次，考虑到进化不同时期不可行解的重要程度，设计新的个体选择准则，提高种群的分布性，使得船舶操纵性优化的方案集在具有较好收敛性的同时获得较好的分布性，给设计者提供多个不同需求下的优化结果，设计者可以根据对C′和D′的不同需求自行选择设计方案。

2.1 基于分解的多目标进化算法框架

MOEA/D[12]能够产生均匀分布的Pareto最优解集，更有利于向设计者提供均匀的、适合不同需求的设计方案。因此，本文采用MOEA/D进化算法框架求解船舶操纵性优化问题。MOEA/D通过设定N个均匀分布的权重向量将一个m目标问题分解成m个单目标子问题，从而获得N个均匀分布的Pareto最优解。Tchebycheff 分解策略[12]是目前MOEA/D算法中最常用的一种分解策略，且该分解策略的收敛精度受Pareto前沿面形状的影响不大，适合船舶操纵性优化问题Pareto前沿未知的情况。因此，本文采用Tchebycheff分解策略，对于船舶操纵性优化问题，其数学表达式为：

(6)

2.2 改进差分变异策略

DE是目前在种群多样性和全局搜索能力方面效果较好的一种进化算法[13]，因此，本文将DE变异、交叉策略引入到MOEA/D框架中，用以求解船舶操纵性优化问题。考虑到原始的DE变异操作在处理设计变量维数较高、约束条件较多的约束优化问题时，存在着对可行域的探索能力不强，种群易陷入局部最优的缺点[14]，而船舶操纵性优化问题恰好是一个多变量、多约束的非线性约束多目标优化问题。因此，需对DE变异操作进行改进，以增强种群的搜索能力，从而提高船舶操纵性优化问题的求解精度。

船舶操纵性优化问题由于存在多个约束条件，其可行域的拓扑结构变得极为复杂，种群能否跨越孤立的可行域、探索可行域边界关系到船舶操纵性优化问题求解精度的高低。研究表明，进化过程中有效利用优秀不可行解所携带的有效信息，有助于种群跨越孤立的可行域，增强可行域边界的探索能力，提高种群的多样性和收敛性[15]。因此，本文利用优秀不可行解对DE变异策略进行改进，改进的差分变异操作为：

Vi=Xi+F1×(Xn-Xr1)+F2×(Xr3-Xr2)

(7)

式中：F1、F2为缩放因子;Xn为从当代优秀不可行解集A中随机选取的不可行解；Xr1、Xr2、Xr3为Xi对应的邻域中随机选择的可行解；r1～r3为1～N上互不相等的正整数。

在进化的前期，种群中可能只包含不可行解，在这种情况下，应使种群迅速探索可行域，找到更多的可行解。此时，侧重优秀不可行解可以扩大搜索的范围，提高种群的多样性，避免种群陷入局部最优，从而有助于搜索到更多的可行解。因此，缩放因子F1应该较大，而F2应该较小。在进化的后期，种群中存在较多的可行解，为引导种群向Pareto前沿收敛，变异操作应侧重可行解，加强对Pareto最优解附近区域的开发。因此，缩放因子F1应该较小，而F2应该较大。缩放因子及进化前期和进化后期的划分根据实际问题来确定，这里通过后边的实验来确定。

2.3 提出个体选择策略

虽然优秀的不可行解参与到种群的进化中，有助于扩大探索范围，提高种群的收敛性和多样性。但是参与进化的不可行解过多或者不够“优秀”，反而会影响种群收敛。因此，如何选择可行解与不可行解，从而在保证种群多样性的同时又能促使种群收敛到Pareto最优前沿显得尤为重要。

为了更有效地利用优秀的不可行解，兼顾种群的多样性和局部搜索能力，应对船舶操纵性优化问题中多约束条件导致的复杂空间拓扑结构，提高优化的精度，本文提出一种新的个体选择准则，进化不同阶段的选择准则对可行解和不可行解的侧重不同。首先，引入约束违反度最大扩增度ε(t)的概念，对个体需满足的约束条件进行松弛，让约束违反度小于ε(t)的不可行解有机会参与到进化中。接着，提出如式(8)所示的个体选择准则：如果2个个体的约束违反度均小于等于约束违反度最大扩增度ε(t)，或者2个个体的约束违反度相等，那么选择Tchebycheff函数值小的个体，否则选择约束违反度值小的个体。最后，提出如式(9)所示的“优秀”不可行解选择准则：如果2个个体的约束违反度均大于约束违反度最大扩增度ε(t)，那么将Tchebycheff函数值小且约束违反度值大的优秀不可行个体存储在外部归档集A中。

Ui,t代替Xi,t⟺

(8)

根据不同进化阶段，可行解与不可行解的重要性不同，本文引入的约束违反度最大扩增度ε(t)是一个随迭代次数动态变化的值，如式(10)所示。

Ui,t存储到A⟺

gte(Ui,t)G(Xi,t),

(9)

如果G(Ui,t),G(Xi,t)>ε(t)

(10)

式中：t为进化迭代次数；Gmax为最大进化迭代次数。ε(0)为初始值，其设置方式如式(11)所示。

(11)

式中：N为种群规模；G(Xi)为初始种群个体的约束违反度。

本文通过式(10)和式(11)动态调节ε(t)，逐渐加强对约束违反度扩增程度的限制，在进化初始，ε(t)为种群约束违反度的均值，种群中若只包含不可行解，或者不可行解距离可行域较远，则ε(t)很大，可以让更多的不可行解参与到进化中，扩大了搜索范围，提高了种群多样性。同时，在进化前期，ε(t)随进化迭代的进行逐渐减小，从而不断缩小满足约束条件的区域，使种群逐渐收缩到可行域内进行搜索。在种群进化的后期，约束违反度最大扩增度ε(t)为0，避免过多的不可行解参与进化，从而保障算法能够收敛到可行的Pareto前沿，使求得的解都是满足约束条件的。

2.4 船舶操纵性优化实现流程

基于上面的2个创新点，本文提出一种船舶操纵性优化的约束多目标进化算法，采用MOEA/D框架，有效利用优秀不可行解对DE变异操作进行改进，并提出一种个体选择策略，其实现步骤如下所示，算法流程如图1所示。

图1 船舶操纵性优化流程Fig.1 Flow chart of ship maneuverability optimization

1)初始化阶段。

①设置实验参数：种群大小N，权重邻域大小T，最大进化迭代次数Gmax，缩放因子F1、F2，交叉因子CR，确定船舶设计中变量的上限、下限；

②生成N个均匀分布的权重向量λ1,λ2,…,λN；

③根据任意2个权重向量之间的欧氏距离，求得距离每一个权重向量λi最近的T个权重向量的索引集合—邻域B(i)={i1,i2,…,iT}；

④随机生成初始种群{X1,X2,…,XN}；

2)进化阶段。

①种群开始进化，令迭代次数t=1。

②从每一个B(i) 中随机选取3个个体，从不可行解集A中随机选取一个个体，与Xi按照式(7)进行DE变异操作和交叉操作生成试验个体U；

③计算新生个体的目标函数值。

3)更新阶段。

②个体比较阶段：利用2.3节方法，若个体U与Xi比较，满足式(8)，则令Xi=U；若满足式(9)，将个体U与存储在优秀不可行解集A中。

4)判断终止条件。若t=Gmax，则算法停止并将种群中的Pareto最优解作为结果输出，否则，t=t+1，返回到2)。

5)输出。输出所求得的Pareto解集及对应的最优解集合。

3 仿真实验与结果分析

为了验证本文方法的有效性和先进性，将其与现有的求解船舶操纵性优化效果较好的算法：自适应加权算法[5]、Pareto遗传算法[7]和基于MOEA/D的算法[10]进行对比实验。所有实验在硬件配置为Intel(R) Core(TM)i7-7500U CPU@2.70 GHz 2.90 GHz、8G内存，win10 64位操作系统的计算机上进行，程序采用MATLAB R2016b编写。

3.1 实验参数设置

设置本文算的种群规模N=100，邻域大小T=20，最大迭代次数Gmax=2 500，为保证实验结果的公平性，3种对比算法的种群规模N与最大迭代次数Gmax与本文算法相等。交叉率CR=0.9。不考虑纵倾，艏部浸湿面积Ab=15 m2，舵角δ=35°。设计变量的上下限如表1所示。

表 1 决策变量的范围Table 1 The scope of decision variables

式(7)中缩放因子F1、F2需要人为设定，下面通过对其取不同的值对算法性能的影响来确定其取值。通过反复实验，发现F1、F2在进化前期取值对算法性能的影响，会随进化后期其取值的变化而变化，而F1、F2在进化后期取值对算法性能的影响，也会随着其在进化前期的变化而变化。因此，下面通过正交试验设计确定进化前、后期的缩放因子取值。固定进化后期的缩放因子，并保证F1≥F2的前提下，F1、F2以0.3为基准，0.1为步长，独立运行28次实验，选取Pareto解集不受其他解集支配的一组缩放因子(F1=0.8，F2=0.4)为最后的参数。其次，确定进化后期的缩放因子：固定进化前期的缩放因子，保证F1≤F2的前提下，F1、F2以0.3为基准，0.1为步长，独立运行28次实验，选取Pareto解集不受其他解集支配的一组缩放因子(F1=0.4，F2=0.8)为最后的参数。

3.2 对比结果分析

为验证本文算法的有效性和先进性，将其与3个目前求解船舶操纵性优化效果较优的算法：自适应加权算法[5]、Pareto遗传算法[7]和基于MOEA/D的算法[10]进行对比实验，3种对比算法与本文算法的实验对比结果分别如表2～4所示。需要注意的是，本文对Pareto最优解集不进行设计方案的决策，设计者可以根据对C′和D′的不同需求自行选择设计方案。

表2为本文算法和文献[5]求得设计方案的对比。文献[5]通过自适应加权系数，将2目标优化问题转化成单目标优化进行寻优，表2中列出的文献[5]方案是根据其给出的属性权重值得到的最终最优解，本文给出更多的设计方案，而且对文献[5]给出的效果最好的2个方案(方案1和方案2)，都能从本文方法求得的方案集中找到优于它们的方案，如表2所示。对于文献[5]给出的方案1，可从本文方案集中找到较其具有更大的直线稳定性和更小的相对回转直径的方案，如方案1和方案2；同样的对于文献[5]给出的方案2，可从本文方案集中找到较其具有更大的直线稳定性和更小的相对回转直径的方案，如方案3和方案4。由此可见，本文求得的船舶操纵性优化设计方案优于文献[5]自适应加权方法所求得的设计方案。

表 2 本文算法与文献[5]方法结果对比Table 2 The comparison between the results of this paper and reference [5]

表3为本文算法与文献[7]求得设计方案的对比。文献[7]没有应用约束处理技术，为了比较公平性，将用文献[7]方法求得的解集去除掉不满足约束条件的解再与本文算法进行比较。比较结果发现文献[7]求得的方案均受本文算法的支配，而本文算法求得的所有解均不受文献[7]的支配。为了比较的公平性，随机从文献[7]中选择3个方案。对于文献[7]求得的方案1，能从本文求得的方案集中找到方案1优于它，即同时具有更大的直线稳定性和更小的相对回转直径；而对于文献[7]的方案2，可以从本文求得的方案集中找到2个方案(方案2和方案3)优于它；对于文献[7]中的方案3，可以从本文方案集中找到2个方案(方案4和方案5)优于它。由此可见，本文提出的船舶操纵性优化设计方案优于文献[7]。

表3 本文算法与文献[7]方法对比Table 3 The comparison between the results of this paper and reference [7]

表 4 本文算法与文献[10]方法对比Table 4 The comparison between the results of this paper and reference [10]

表4为本文算法与文献[10]求得设计方案的对比。实验结果表明，对于文献[10]求得的设计方案中有28个能在本文求得的方案中找到优于他们的方案，而本文求得的所有方案都不差于文献[10]方案。表4为28个方案中随机选取的3个实例，从表中可以看出，本文求得的方案相比于文献[10]具有更好的直线稳定性和回转性。由此可见，本文提出的船舶操纵性设计方案优于文献[10]的。

图2为4种算法求得的Pareto最优前沿，从图2中可以看出，按照文献[7]求得的方案都受到本文方案的支配，而本文求得的所有方案都不受文献[7]方案的支配。文献[10]求得的方案部分被本文方案中找到支配，而本文求得的所有方案都不差于文献[10]方案，而且本文能求得更多的解，解集的分布性更好。

图2 4种算法Pareto最优前沿对比Fig.2 Comparison of the Pareto optimal front obtained by the 4 algorithms

为了比较本文算法与3个对比算法的优化效率，表5给出了4种算法独立运行10次的平均时间。从表中可以看出文献[5]、文献[10]和本文算法由于不需要Pareto非支配比较，因而具有更快的优化效率，但文献[5]需要依靠专家经验，而文献[10]对优秀不可行的利用不够充分，Pareto解集的收敛性没有本文算法高。

综上所述，本文提出的船舶操纵性优化方法求得的Pareto最优解集收敛性更好，能够使船舶具有更大的直线稳定性、更小的相对回转直径；而且可以给设计人员提供分布更加均匀的设计方案，使设计者可以根据自己的偏好进行选择。

4 结论

1)本文提出一种船舶操纵性优化的约束多目标进化算法，在优化过程发现船舶的直线稳定性和船舶的回转性2个目标是相互冲突的，多目标进化算法可以为设计者提供多种设计方案，供其根据不同的需求进行选择。

2)本文算法充分利用优秀不可行解，较对比算法的收敛性和分布性更好，可以给设计人员提供更多、更好的选择。