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

第45卷第16 期2023年8 月舰船科学技术SHIP SCIENCEANDTECHNOLOGYVol.45,No.16Aug.,2023基于改进SPEA2算法的多目标航线优化王军，蒋金阳，牛壮(大连海事大学交通运输工程学院，辽宁大连116 0 2 6)摘要：船舶航线优化是一个复杂的过程，其目的是在考虑动态变化的天气条件下，以燃油消耗、航行时间、安全性或二者及以上的组合为目标寻找给定航程的最优路径。传统的航线优化算法无法同时优化多个目标且鲁棒性较差，而进化算法非常有利于解决与动态天气变化相关的航线多目标优化问题。因此，在SPEA2的基础上进行算法的改进并应用于多目标航线优化中，针对算法收敛慢的问题，借助Dijkstra算法生成初始种群。此外，对算法的种群更新策略和交叉、变异算子进行改进，提高了种群的质量和防止陷入局部最优。与其他进化算法进行比较，证明改进后的算法能更好地应用于多目标航线优化并获得更优秀的Pareto前沿。关键词：船舶航线优化；多目标优化；进化算法；Pareto最优中图分类号：U692.3+1；T P30 1.6文章编号：16 7 2-7 6 49(2 0 2 3)16-0 12 5-0 4Multi-objective ship route optimization based on improved SPEA2 algorithm(College of Transportation Engineering Dalian Maritime University,Dalian 116026,China)Abstract:Ship route optimization is a complex process whose purpose is to find the optimal route for a given voyagebased on fuel consumption,duration time,safety,or a combination of the two or more under dynamic weather conditions.The traditional route optimization algorithm cannot simultaneously optimize multiple objectives and with poor robustness,while the evolutionary algorithm has a great advantage to solve the multi-objective route optimization problem related to dy-namic weather change.Therefore,the algorithm is improved based on SPEA2 and applied to multi-objective route optimiza-tion.Aiming at the problem of slow convergence of the algorithm,the Dijkstra algorithm is used to generate the initial popu-lation.In addition,a new population renewal strategy and crossover and mutation operator are proposed to improve the qual-ity of the population and prevent the population from falling into local optimum.Compared with other evolutionary al-gorithms,it is proved that the improved algorithm can be better applied to multi-objective route optimization and obtain abetter Pareto frontier.Key words:ship route optimization;multi-objective optimization;evolutionary algorithm;Pareto optimal0引言随着海洋运输在国际商品交换中所占比重越来越大，船舶航线优化被提到了重要的地位。该领域研究的问题是在考虑风浪环境条件的情况下，寻找给定航行的最优路径和航速，目标通常考虑最小航行时间、燃油消耗或通行风险。近年来，多目标航线优化得到了较多关注，它可以同时针对多个目标进行优化，进而产生大量的权衡解，决策者可根据当前的需要确定最终的航行方案。收稿日期：2 0 2 2-12-30作者简介：王军（19 6 3），男，博士，教授，研究方向为航运管理与海运风险工程。文献标识码：Adoi:10.3404/j.issn.1672-7649.2023.16.025WANG Jun,JIANG Jin-yang,NIU Zhuang目前，进化算法在解决该问题上取得了广泛应用2-31,主要包括经典算法SPEA24、NSG A-II5 以及一些改进的算法NMOEA(6、SPE A 2+7 。然而，由于规划过程中存在庞大的样本量和优化空间，收敛效率慢成为普遍现象。特别是随着迭代步长的增加，搜索样本量的限制还可能导致算法陷入局部最优。本文针对SPEA2在解决多目标航线优化问题中存在的收敛速度慢和易陷人局部最优的现象进行改进。通过Dijkstra算法搜索的可行解加人到初始种群中作为引导以加快算法寻优的效率；采用更精细化的选择过126程保证精英个体可继续参与进化；提出新的交叉和变异策略，有效提升了种群质量。1SSPEA2算法改进1.1SSPEA2的基本思想Zitzler4I提出的强度Pareto进化算法（SPEA2）是一种多目标进化算法，具有良好的搜索性能，它包含一些重要的操作，例如在适应度分配策略中，同时考虑了种群中的显性个体和隐性个体，提高了全局搜索能力；计算最近相邻个体的密度提高搜索精度；采用新的存档截断方法，保证边界解得以保留。1.2改进工作的动机大多数优化算法无法找到更高质量的解，主要因为它们工作效率较低。例如，当种群中的大多数解处于非支配阶段时，粗糙的选择方法将剥夺优势精英继续参与进化的机会，导致优化结果停滞或更差。同时，交叉机制作为进化算法中生成新个体和扩展解空间的一种有效方法，还尚未被有效探索。尤其当种群中个体间差异较小时，算法易进人停滞状态，这时应增大变异概率，通过改变种群内个体的部分基因形成新的个体，以跳出局部最优。1.3SPEA2方法的改进在种群更新阶段，改进后的算法只允许非支配个体加人到外部归档集A，位于Pareto前沿端点上的2 个解被强制保留，防止算法陷入局部最优。并且从第T(T2)代开始，将种群P中所有非支配个体与AT-1中的个体进行比较，支配AT-1中任何一方的个体将被迁移到AT中。在交叉和变异阶段，事先给出比较值K，并与选中个体的相似度r进行比较，K的计算公式为：N-1Z U(IDi(t),ID2(t),.,IDn(t)t=2K=(1 U(IDi(t),ID2(t),.,IDn(t)n。式中：ID;为组成个体的基因序列；N为序列的长度；t表示基因值的位置，函数U表示n个个体的基因序列在t位置的非重复值的数量。因此，当种群内个体的基因序列都相同时，K=1；基因序列都不同时，K=1/n。相似度r的计算公式为：N-12,IDi(t)-ID2(t)r=2(IDi(t)-ID2(t)=0,1。舰船科学技术若2 个个体的基因值在t位置相等，则IDi(t)-ID2(t)=0，否则为1。当rK，个体间差异较大，利用交叉操作进行个体间有用信息的交换，产生更多较好的个体。相反，当r jl,R(i)=jePi+At.ji当外部归档集IArlQ(预设值)时，通过k临近算法估算个体密度值，并将特征空间最邻近的个体逐个剔除，直至IAl=Q；相反，若外部归档集IAlQ，则根据适应度排序选择前Q-IATl个支配解，直至ATl=Q。2.4交叉、变异操作交叉通过随机选择2 个个体共同经过的航路点a（起终点除外），将父代1从第1个至第a个航路点的位置信息都复制到子代，第a+1至最后1个航路点的位置信息从父代2 上复制。在变异个体上随机选择一个变异点，使该变异点处的船舶路径随机发生改变。操作后的子代和父代共同组成新的种群继续参与进化。2.5检查终止条件随着迭代步数的增加，与最大迭代次数进行比较。如果超过最大迭代次数，则终止算法，否则返回种群更新继续完成种群进化。3仿真实验与分析仿真实验设定的航线起点为横滨附近（35.2 5N，141.75E），终点为旧金山附近（37 N，12 2 W），分别在3个月份下进行多目标航线优化实验，航行环境比较结果如表1所示。船舶出发时间设定为每月6 号上午11：0 0，选择3500TEU的集装箱船进行仿真，其标准排水量为47202.48t。为验证算法的性能，将本文算法与Dijk-stra、NM O E A 和SPEA2进行比较，其中针对3种进化王军，等：基于改进SPEA2算法的多目标航线优化2018年7 月平均浪高/m1.7147220210-200-(5)190180S(i)。(6)127算法，设定初始种群容量为34，外部种群容量6，交叉概率0.8，变异概率0.2，最大迭代次数10 0，求解出的Pareto前沿面如图1 图3所示。表1不同月份下航行环境的比较Tab.1Comparison of sailing conditions in different months月份2018年4月2.982.53.8724*DijkstraNMOEA&SPEA2公本文算法170+85090095010001050110011501200图12 0 18 年7 月的Pareto前沿面Fig.1 Pareto frontier in July 20182401230220210200190-180-17085090095010001050110011501200燃油消耗/图2 2 0 18 年4月的Pareto前沿面Fig.2IPareto frontier in April 2018260*Dijkstra8250240230220200190-1801701000102010401060108011001120图32 0 18 年1月的Pareto前沿面Fig.3 Pareto frontier in January 2018实验结果显示，进化算法求得的解在时间和油耗上均优于Dijkstra算法得到的结果。另一方面，本文提出的算法在收敛性上优于NMOEA和SPEA2，且随着气象的变差，优势表现越明显。从多目标进化算法性2018年4月燃油消耗/*Dijkstra.NMOEA&SPEA2公本文算法NMOEA&SPEA2公本文算法米燃油消耗/参考文献：128能评价指标-超体积（HV）9 的角度对结果进行数学分析。表2 比较了3种进化算法求得解的HV值，HV值越高，群体中个体的综合表现越好。将（112 0，2 6 0）作为参考点进行HV的计算，结果显示本文提出的算法综合性能最高，其次SPEA2，最差的是NMOEA。表2 进化算法的HV结果比较Tab.2 Comparison of HV results of evolutionary algorithms比较算法2018年1月NMOEA22.538.42SPEA222.561.66本文算法22.692.70图4 图6 分别展示了3个月份下的Pareto航线集，对于海况较好的7 月和4月，该月份下的航线集主要是以Dijkstra求得的航线为基础并对其优化。优化部分主要集中在航线的后半段，但在海况较差的1月份，它的Pareto航线集不仅包含Dijkstra的结果，还包括随机路线，这些路线光滑度较低，但在省油和省时方面仍优于Dijkstra结果。52N48N44N40N36N140E52N48N44N40N36N140E52N48N44N40N36N+140E图6 2 0 18 年1月的Pareto航线集Fig.6Pareto route set in January 20184结语针对多目标航线优化问题，本文构建了燃油成本舰船科学技术和航行时间最小的双目标优化模型，并设计了基于SPEA2的引导性多目标进化算法。通过在初始种群中加入Dijkstra算法得到的单目标优化结果，以此作为引导，并在种群更新阶段进行改进，保证了具有代表性的精英个体继续参与进化。为避免种群优良基因的破坏以及陷入局部最优，对交叉和变异机制进行改进。最后以太平洋航线为例，在不同海况条件下进行仿真实验，验证了算法的高效性。与NMOEA和SPEA2多2018年7 月2018年4月18 232.2520408.5120819.79160E180图42 0 18 年7 月的Pareto航线集Fig.4 Pareto route set in July 2018160E图52 0 18 年4月的Pareto航线集Fig.5Pareto route set in April 2018160E180第45卷目标进化算法的求解结果进行对比，证明本文算法具11 844.27有较好的收敛性和全局寻优能力。1200.3212.998.35160W140W180160W160W1 WALTHER L,RIZVANOLLI A,WENDEBOURG M,et al.Modeling and optimization algorithms in ship weatherroutingJJ.International Journal of e-Navigation and MaritimeEconomy,2016,4:31-45.2蒋美芝，吕靖.基于Pareto 蚁群算法的船舶风险规避路径优化1.交通运输系统工程与信息，2 0 19,19(1):19 2-19 9.3李鹏飞.多目标船舶气象航线优化算法的研究与仿真D.吉林：吉林大学，2 0 19.4 ZITZLER E,LAUMANNS M,THIELE L.SPEA2:Improv-ing the strength Pareto evolutionary algorithmJJ.TIK-report,2001,103.120W5 DEB K,PRATAP A,AGARWAL S,et al.A fast and elitistmulti-objective genetic algorithm:NSGA-IIJ.IEEE transac-tions on evolutionary computation,2002,6(2):182-197.【6】李密青，郑金华,罗彪,等.一种基于邻域的多目标进化算法.计算机应用,2 0 0 8(6)：157 0-157 4.7 KIM M,HIROYASU T,MIKI M,et al.SPEA2+:improvingthe performance of the strength pareto evolutionary algorithm2CJ/International Conference on Parallel Problem Solving140W120W140W120Wfrom Nature,2004:742-751.8 LI X,WANG H,WU Q.Multi-objective optimization in shipweather routingC/2017 Constructive Nonsmooth Analysisand Related Topics(dedicated to the memory of VF Demya-nov)(CNSA),IEEE,2017:1-4.9 ZITZLERE,THIELE L.Multiobjective evolutionary algo-rithms:a comparative case study and the strength Pareto ap-proachJ.IEEE transactions on Evolutionary Computation,1999,3(4):257-271.10 VENETI A,KONSTANTOPOULOS C,PANTZIOU G.Evo-lutionary computation for the ship routing problem in:Model-ingJJ.Computing and Data Handling Methodologies for Mar-itime Transportation,2018:95-115.