改进NSGA-Ⅱ算法的海上搜救调度方法.pdf

改进 NSGA-II 算法的海上搜救调度方法严梦迪,王海红(青岛科技大学信息科学与技术学院,青岛266061)通信作者:王海红,E-mail:摘要:针对海上搜救资源调度决策困难、干扰多、实时性差、难以实现全局最优问题,本文以黄渤海海域为例,采用改进的非支配排序遗传(NSGA-II)算法解决海上船舶搜救资源调度问题.首先,根据 AIS 以及北斗数据,建立了海上搜救资源的多目标优化模型;其次,改进的 NSGA-II 算法采用基于正态分布交叉(NDX)算子,在扩大搜索范围的基础上,避免陷入局部最优,得到多目标问题完整的 Pareto 解集;采用综合评价法(TOPSIS)从 Pareto 解集中求得折衷解,即最终设计的搜救调度方案;最后,在考虑船舶数量约束以及时间约束的条件下,采用改进的NSGA-II 算法分别与 NSGA-II 算法和贪婪算法进行对比,并采用黄渤海海域船舶采集数据进行仿真.结果表明该算法能够有效解决海上搜救资源调度优化问题.关键词:改进的非支配排序遗传;多目标优化模型;海上搜救;调度优化;全局最优引用格式:严梦迪,王海红.改进 NSGA-II 算法的海上搜救调度方法.计算机系统应用,2023,32(8):244249.http:/www.c-s- Search and Rescue Dispatching Method Based on Improved NSGA-II AlgorithmYANMeng-Di,WANGHai-Hong(CollegeofInformationScienceandTechnology,QingdaoUniversityofScienceandTechnology,Qingdao266061,China)Abstract:Tosolvetheproblemsofdifficultdecision-making,multipleinterferencefactors,poorreal-timeperformanceandtherealizationofglobaloptimizationinmaritimesearchandrescue(SAR)resourcescheduling,thisstudyemploysanimprovednon-dominatedsortinggenetic(NSGA-II)algorithmbytakingtheYellowSeaandtheBohaiSeaasanexample.Firstly,amulti-objectiveoptimizationmodelformaritimeSARresourcesisbuiltbasedonAISandBeiDoudata.Secondly,thenormaldistributioncrossover(NDX)-basedoperatorisadoptedbytheimprovedNSGA-IIalgorithmtoavoidfallingintolocaloptimumonthebasisofexpandingthesearchscope,andacompleteParetosolutionsetforthemulti-objectiveproblemisobtained.Thecomprehensiveevaluationmethod(TOPSIS)isappliedtoobtainacompromisesolutionfromtheParetosolutionset,namelytheoptimaldesignofthesearchandrescueschedulingscheme.Finally,whentheconstraintfactorssuchasthenumberofshipsandtimeareconsidered,theimprovedNSGA-IIalgorithmisemployedandcomparedwiththeNSGA-IIandgreedyalgorithms.ThesimulationsoftheresourceschedulingarecarriedoutusingthedatacollectedfromshipsintheYellowSeaandtheBohaiSea.TheresultsshowthatthealgorithmcaneffectivelysolvetheproblemofmaritimeSARresourceschedulingoptimization.Key words:improvednon-dominatedsortinggenetics;multi-objectiveoptimizationmodels;maritimesearchandrescue;schedulingoptimization;globaloptimum计算机系统应用ISSN1003-3254,CODENCSAOBNE-mail:ComputerSystems&Applications,2023,32(8):244249doi:10.15888/ki.csa.009187http:/www.c-s-中国科学院软件研究所版权所有.Tel:[phone]基金项目:山东省自然科学基金重大基础研究项目(ZR2021ZD12)收稿时间:2023-01-17;修改时间:2023-02-23,2023-03-03;采用时间:2023-03-08;csa 在线出版时间:2023-05-22CNKI 网络首发时间:2023-05-24244软件技术算法SoftwareTechniqueAlgorithm随着海上经济的发展,海上交通也日益复杂,海上事故后的海上搜救资源调度优化问题也一直是应急管理领域研究的研究热点.由于不同水域的特性不同,当人员落水后,受风、浪、流等环境因素的影响,处于动态漂移的状态,给海上搜救带来很大的困难,尤其是对搜救资源的合理调度及分配,能够影响搜救的成功率,因此需要计划、协调、控制和指挥搜救行动以应对紧急情况.目前,针对海上搜救资源调度的研究,主要可以分为单目标和多目标模型两个方向.针对单目标模型,主要是采用遗传算法、遗传模拟退火算法求解.文献 1以时间为目标建立海上搜寻船舶单目标模型,通过改进的遗传算法对模型进行求解.文献 2 在搜救成功率中加入救助概率设计目标函数,建立搜救调度单目标模型,采用遗传模拟退火算法求解.文献 3 分析在不同船舶数量限制情况下时间与搜救成本的关系,结合搜救力量覆盖待搜救区域的覆盖面积所用时间,得到经济可行的搜救力量方案.针对多目标模型,多采用 NSGA-II 算法求解,文献 4通过建立以搜救成功率和搜救成本的多目标模型,采用 NSGA-II 对模型进行求解.文献 5 通过以时间、成本为目标函数,建立多目标优化模型,采用 NSGA-II算法和多目标粒子群优化算法对模型进行求解.综上,目前大多采用遗传算法和 NSGA-II 算法进行求解,本文拟采用改进的 NSGA-II 算法进行求解.因此本文建立以搜救成功率和搜救成本为目标的多目标优化模型,设计基于改进 NSGA-II 算法的海上搜救调度方法,通过对黄渤海海域船舶事故案例进行分析验证,验证了所设计方法在海上搜救调度问题中的可行性和有效性.1海上搜救资源配置的多目标模型构建依据 AIS 及北斗数据,建立多目标优化模型,如图 1 所示,具体设计分为输入变量、决策变量、中间变量、目标函数以及约束条件设计.1.1 输入变量设计输入变量主要包括待搜寻区域面积,周围船舶数量,船舶距离事故点的距离,船舶的最大航速、扫海宽度、航线间距、搜救成本.具体设计如表 1 所示.1.2 决策变量设计根据 AIS 及北斗数据,设计多目标模型中的决策xii=1,2,3,Mxii变量为搜救资源选择(),其中,表示参与搜救资源 的数量,设计如下.xi=1,如果船舶i参与搜寻行动0,如果船舶i不参与搜寻行动(1)多目标优化模型决策变量目标函数约束条件搜救成功率搜救成本时间约束数量约束图 1多目标优化模型表 1输入变量符号及含义符号符号含义SS待搜寻区域面积(平方海里)MM待搜寻区域周边有艘搜救船舶DiiDi第 艘船舶距离事故地点的初始距离为(海里)ViiVi第 艘船舶的最大航速WiiWi第 艘船舶的扫海宽度RiiRi第 艘船舶的航线间距CiiCi第 艘船舶的搜救成本 1.3 中间变量设计T0iT根据对海上搜救资源已知信息进行分析,可以计算出一些后文可以用到的中间变量,搜救船舶赶往搜寻区域的时间,假设整个搜寻行动所用时间为,可以计算出搜寻船舶在待搜寻区域作业的时间以及在所完成搜寻区域面积.i(1)第 艘船舶赶往搜寻区域的时间:T0i=DiVi(2)i(2)第 艘船舶在搜寻区域作业的时间:Ti=T T0i(3)i(3)第 艘船舶所完成的搜寻面积:Si=TiWiVi(4)iii其中,搜救面积的为第 艘搜救船舶搜寻时间乘以第 艘搜救船舶的扫海宽度乘以第 艘船舶的最大航速.时间2023年第32卷第8期http:/www.c-s-计 算 机 系 统 应 用SoftwareTechniqueAlgorithm软件技术算法245乘以最大航速即为有效航程,有效航程乘以扫海宽度即为搜救面积.扫海宽度的物理意义指的是探测器能够发现搜救目标的有效距离,是船舶搜寻能力的一种衡量,因其受海洋环境、搜寻设备、遇险目标特征的影响,通常是根据大量的实验数据进行统计分析得出.1.4 目标函数设计搜救成功率的目标函数设计如下:f1=1POS(5)POSPOCPOD其中,表示搜救成功率,是搜救过程的主要衡量指标,通常由包含概率和发现概率所决定,这三者是海上搜寻理论中的 3 个重要部分.S nj=1Sj 0(6)POSj(A)=Mi=1POCiPODi(7)jjASjjPOSjjPOCiiPODii其中,表示当前处于第 阶段的搜寻,表示当前搜寻区域,表示第 个阶段的搜寻面积,表示第 个阶段的搜救成功率,表示第 个搜救资源的包含概率,表示第 个搜救资源的发现概率.成本的目标函数设计如下:f2=minnj=1Cj(A)(8)Cj(A)=Mi=1xiCiTi(9)Ti=SixiViRi(10)CjjxiiTiiSii其中,表示第 个阶段的搜救成本,表示参与搜救的搜救资源 的数量,表示第 个搜救资源的搜索时间,表示第 个搜救资源的搜寻面积.1.5 约束条件设计对所提出的海上搜救多目标模型,由于搜救资源本身存在一些限制,需要结合实际环境情况、搜救资源状况,算法设计需要满足以下约束条件.(1)搜救资源的数量小于能够在相应搜寻时间内完成搜寻任务的能力最弱搜救资源的数量.Mi=1xi ni(11)(2)搜救资源到达待搜寻区域的时间要小于总搜寻时间.T0i T(12)综上所述,考虑整个搜救过程搜寻对象受多种因素的影响具有动态性,因此把搜救过程划分为多个时段,通常情况下只考虑搜救成功率这一单目标问题,本文中加入搜救资源的总成本,但由于海上搜救具有强紧急性和弱经济性,因此搜救成功率和总成本之间存在优先级,在满足搜救成功率最优的情况去求总成本最低,建立了海上搜救资源多目标优化模型.2基于改进 NSGA-II 多目标优化算法的海上搜救资源调度设计 2.1 多目标优化求解对多目标模型的求解主要有 2 种方法,第 1 种是传统目标法,即转化法,利用加权和将多目标问题转化为单目标问题.第 2 种是对多目标直接求解,通过采用智能优化算法求解,例如 NSGA-II 算法,它克服了 NSGA计算复杂度高和缺乏精英策略的缺点6,是一种强大的、鲁棒的多目标进化算法,适用于解决具有 2 个或3 个目标的问题7.2.2 正态分布交叉(NDX)算子设计p1p2c1c2i传统的模拟二进制交叉算子(SBX)搜索能力较差,正态分布交叉(NDX)算子的搜索能力更强,能够跳出局部最优,达到一个全局最优的效果.同样假设两个父代个体和,使用 NDX 算子8产生两个子代个体和对于第 个变量,其交叉的过程为:c1,i=p1,i+p2,i21.481(p1,i p2,i)|N(0,1)|2,0.5c2,i=p1,i+p2,i21.481(p1,i p2,i)|N(0,1)|2,0.5(13)c1,ic2,iip1,ip2,ii|N(0,1)|其中,、代表子代染色体上对应的第 个变量;、代表父代染色体上对应的第 个变量;是均匀分布在区间(0,1)的随机数,代表正态分布随机变量.2.3 改进 NSGA-II 算法的海上搜救资源调度方法设计将 NDX 算子引入到 NSGA-II 算法中,得到改进的 NSGA-II 算法,利用改进的 NSGA-II 算法对多目标模型进行求解,最终得到多目标模型中的 Pareto 解集,计 算 机 系 统 应 用http:/www.c-s-2023年第32卷第8期246软件技术算法SoftwareTechniqueAlgorithm进而对 Pareto 解集采用 TOPSIS 方法9获取折衷解,即海上搜救调度方案.具体的算法流程图如图 2 所示.Gen=Gen+1初始化种群进化代数 Gen=2非支配排序正态分布交叉多项式变异正态分布交叉多项式变异生成第 1 代种群Gen 小于最大代数计算目标函数快速非支配排序计算拥挤度生成新父代个体生成新父种群父代、子代种群合并为新种群是是否是否开始结束否图 2改进 NSGA-II 算法的海上搜救调度资源方法流程(1)初始化种群设置进化代数 Gen=1,这里的初始种群即为所有的搜救船舶组合方案.(2)判断是否生成了第 1 代种群,如果是,则进化代数 Gen=2,否则对初始的种群采用非支配遗传排序和正态分布交叉多项式变异使得生成第 1 代种群,从而进化代数 Gen=2.(3)将父代、子代种群合并为新的种群.(4)判断是否生成新的父种群,如果是,则执行步骤(5),如果否,则计算新种群中个体的目标函数,并采用快速非支配排序并计算拥挤度生成新父代种群.(5)对生成的新父代种群采用正态分布交叉多项式变异生成子代种群.(6)判断 Gen 是否小于最大代数,如果是,Gen=Gen+1,继续执行步骤(3),否,运行结束.3仿真及结果分析青岛市海上搜救中心接到报警信息,黄海海域发生事故,两艘船舶相撞,船上共有 6 名船员逃生.海上搜救中心接到报警信息后划定搜救区域的面积为1000平方海里,船舶的搜寻航线间距统一设为 0.2海里.根据海上落水人员生存分析算法得出失事人员存活时间为 4h.根据当前时刻 AIS 及北斗信息显示,周边有 16 艘可用船舶,各船舶性能参数表如表 2 所示,考虑到面积为 1000平方海里的区域内最多可以同时容纳的船舶数量为 8 艘.综合上述信息,选择合适的搜救船舶组成最优海上搜救力量配置方案.表 2船舶性能参数表船舶编号船舶当前位置最大航速(节)扫海宽度(节)成本(元)12345678910111213141516122.0581E/36.9022N122.1259E/36.9365N122.3090E/36.2651N122.8462E/36.8639N119.7178E/35.1212N122.7431E/36.3709N121.2812E/37.7228N120.5044E/38.1546N119.6450E/38.0020N120.4950E/35.9903N119.7296E/37.6448N122.2920E/36.7938N122.7349E/37.4704N121.9730E/36.8319N122.4265E/36.8617N119.8269E/35.6411N0.83362.04372.1915.59388.77.56381.511.68660.73359.553414.011611.94.59570.4751012321916766420302613278018018010005305001008012080600900110070035050在 Windows10 操作系统下,软件平台为 MatlabR2019a,利用改进的 NSGA-II 算法对海上搜救调度进行优化,分别与 NSGA-II 算法和贪婪算法进行对比,算法具体的参数设置如表 3 所示.表 3算法参数设置初始种群交叉概率变异概率迭代次数2000.90.15002000.90.1500为了更好地进行对比实验,将表 2 数据代入多目标模型中的式(5)和式(8),在 3 个不同的时间段内,算法的参数设定一致,分别运行 3 种算法 10 次,记录下每种算法下的一个最优曲线.最佳搜救力量结果如表 4 所示,对应的 3 个时间段内进化曲线如图 3、图 4、图 5 所示.2023年第32卷第8期http:/www.c-s-计 算 机 系 统 应 用SoftwareTechniqueAlgorithm软件技术算法247表 4搜救力量方案对比时间段算法资源方案搜救力量组合船舶数量POS(%)C13:0015:00贪婪算法0,0,0,1,0,1,0,0,4,6,11,12486.180.600,0,1,1,0,0,0,0.NSGA-II0,0,0,1,0,1,1,0,4,6,7,12486.320.500,0,0,1,0,0,0,0.改进的NSGA-II0,0,0,1,0,1,1,0,4,6,7387.680.320,0,0,0,0,0,0,0.15:0017:00贪婪算法0,0,0,1,0,1,0,0,4,6,11,13485.290.640,0,1,0,1,0,0,0.NSGA-II0,0,0,1,0,1,1,0,4,6,7,13485.330.540,0,0,1,0,0,0,0.改进的NSGA-II0,0,0,1,0,1,1,0,4,6,7,12486.580.500,0,0,1,0,0,0,0.17:0019:00贪婪算法0,0,0,1,0,1,0,0,4,6,11,13,14585.120.780,0,1,0,1,1,0,0.NSGA-II0,0,0,1,0,1,1,0,4,6,7,12,14584.330.720,0,0,1,0,1,0,0.改进的NSGA-II0,0,0,1,0,1,1,0,4,6,7,12,13585.440.640,0,0,1,1,0,0,0.1.00.90.80.70.6f10.50.40.30.20.10050100 150 200 250迭代次数300 350 400 450 500贪婪算法改进 NSGA-IINSGA-II图 313:0015:00 进化曲线1.00.90.80.70.6f10.50.40.30.20.10050100 150 200 250迭代次数300 350 400 450 500贪婪算法改进 NSGA-IINSGA-II图 415:0017:00 进化曲线对表 4 的结果进行分析,在 13:0015:00 时之间,贪婪算法和 NSGA-II 算法得出需要 4 艘船舶,而改进NSGA-II 算法只需 3 艘船舶,对应的搜救成功率更高,成本更低;在 15:0017:00 时以及 17:0019:00 时之间,3 种算法得出的搜救力量组合数量相同,但改进 NSGA-II 算法所求得的搜救成功率更高,成本更低.1.00.90.80.70.6f10.50.40.30.20.10050100 150 200 250迭代次数300 350 400 450 500贪婪算法改进 NSGA-IINSGA-II图 517:0019:00 进化曲线从图 3、图 4 可以看出,改进 NSGA-II 算法的目标曲线值相比于贪婪算法和 NSGA-II 算法以较快的速度达到最优收敛解,并且 f1值低于贪婪算法和 NSGA-II,即搜救成功率高.从图 5 可以看出,虽然 3 种算法基本以相同的迭代次数达到收敛,搜索的速度基本相同,但是改进的 NSGA-II 算法达到的 f1最低,即搜救成功率最高,这证明了改进的 NSGA-II 算法引入了 NDX 算子具有良好的效果,相比于其他 2 种算法,提高了收敛速度,增加全局搜索能力,能够达到一个全局优化的效计 算 机 系 统 应 用http:/www.c-s-2023年第32卷第8期248软件技术算法SoftwareTechniqueAlgorithm果.综上,改进 NSGA-II 算法不仅保证了搜救成功率,也相对降低了一些经济成本,优化决策的结果更加合理,也验证了该算法在海上搜救调度中的合理性.4结论针对海上搜救调度建立多目标模型,建立以搜救成功率和搜救成本为目标函数,本文设计一种基于改进的 NSGA-II 算法的海上搜救调度方法,该方法中引入了 NDX 算子,扩大搜索能力和搜索范围,能够跳出局部最优,得到全局最优,基于最优 Pareto 解集得到最优海上搜救调度方案.通过实验验证分析,改进的 NSGA-II 算法相比于贪婪算法和 NSGA-II,能够以较快的速度达到收敛值,在保证搜索效率的同时达到全局优化的效果,在一定程度上提高了搜救成功率同时降低了搜救成本,得到了高效且经济可行的搜救决策方案,同时也验证了本文算法对于求解海上搜救多目标优化模型的可行性和有效性.参考文献于安民.海上捜寻船舶协同调度方法研究 硕士学位论文.大连:大连海事大学,2020.1李苯帅.基于最优搜寻理论的海上搜救方案规划方法研究 硕士学位论文.青岛:山东科技大学,2020.2邢胜伟,张英俊,李元奎,等.海上搜寻力量选择优化模型.3大连海事大学学报,2012,38(2):1518.doi:10.16411/ki.issn1006-7736.2012.02.026Xiong WT,van Gelder PHAJM,Yang KW.A decisionsupport method for design and operationalization of searchandrescueinmaritimeemergency.OceanEngineering,2020,207:107399.doi:10.1016/j.oceaneng.2020.1073994DeA,ChoudharyA,TiwariMK.Multiobjectiveapproachforsustainableshiproutingandschedulingwithdraftrestrictions.IEEETransactionsonEngineeringManagement,2019,66(1):3551.doi:10.1109/TEM.2017.27664435Yang MD,Chen YP,Lin YH,et al.Multiobjectiveoptimizationusingnondominatedsortinggeneticalgorithm-IIforallocationofenergyconservationandrenewableenergyfacilities in a campus.Energy and Buildings,2016,122:120130.doi:10.1016/j.enbuild.2016.04.0276钟佳淋,吴亚辉,邓苏,等.基于改进 NSGAGIII 的多目标联邦学习进化算法.计算机科学,2022:110.http:/ NSGA-II 算法的拖拉机 传 动 系 统 匹 配 优 化.农 业 机 械 学 报,2018,49(11):349357.doi:10.6041/j.issn.1000-1298.2018.11.0428王琳,柯琴,李炎隆,等.组合权重 TOPSIS 模型评价黄土高原小流域淤地坝系风险.应用力学学报,2022,39(4):698706.9(校对责编:牛欣悦)2023年第32卷第8期http:/www.c-s-计 算 机 系 统 应 用SoftwareTechniqueAlgorithm软件技术算法249