海上落水目标协同搜寻路径规划算法研究.pdf

第 51 卷收稿日期：2022年12月8日，修回日期：2023年1月14日基金项目：国家重点研发计划（编号：2017YFC1404700）资助。作者简介：李林，男，硕士，工程师，研究方向：交通信息化。1引言以船舶为载体的海运经济网络，极大地促进了各国经济发展，具有不可替代的作用12。随着海上运输船舶数量的增长，船舶遇险事故数量也逐步增长3。船载救生装备往往会安装示位标45，示位标基于GNSS能够提供准确的待救目标位置，便于搜救艇、直升机等救援设备快速、准确开展海上落水目标的搜救和打捞工作67。海上落水目标的搜寻路径规划问题可以抽象为多旅行商（mTSP）问题，属于组合优化问题89，其求解过程包含了目标分组及组内遍历次序两个环节，是典型的NP-Hard问题10。对于多旅行商问题的研究主要集中在染色体的编码方式上1112，不合理的编码策略将提高遗传算法的复杂度，产生大量冗余解，制约算法的求解效率。本文提出一种多无人机协同的海上搜救目标分类与路径规划算法。该算法基于K-means算法和遗传算法，采用均值-方差模型为作为最优路径的选择算子，具有算法简单、鲁棒性强、收敛速度快和全局搜索能力强等特点。2模型构建2.1变量定义C=12n表示遍历目标集合，共有 n个目标。其中第一个目标为无人机飞行起点；U=1海上落水目标协同搜寻路径规划算法研究李林（交通运输部水运科学研究院北京100088）摘要海上落水目标协同搜寻路径规划与多旅行商问题相似。论文所提出的算法由待救目标分类和搜寻路径规划两个子算法组成。首先经过基于遗传算法的K-means目标聚类，确定染色体数量及长度，解决海上搜救目标分类问题。然后经过多染色体遗传算法，获得多种搜救设备协同的海上搜救最优路径。计算结果表明，论文提出的海上落水目标协同搜寻路径规划算法，能够有效降低算法的搜索范围，提高算法的运行速度和全局搜索能力，提高海上落水目标搜救效率。关键词海上搜寻；路径规划；K-means；遗传算法；均值-方差模型中图分类号TP391DOI：10.3969/j.issn.1672-9722.2023.06.017Research on Path Planning Algorithm for Collaborative Search ofFalling into Water Targets on the SeaLI Lin（China Waterborne Transport Research Institute，Beijing100088）AbstractThe path planning of cooperative search for falling into water targets is similar to the mTSP.The algorithm proposedin this paper consists of two sub algorithms，which are targets classification and search path planning.Firstly，through K-means targets clustering based on genetic algorithm，the number and length of chromosomes are determined to solve the problem of maritimesearch and rescue targets classification.Then，through the multi chromosome genetic algorithm，the optimal search and rescue pathis obtained.The calculation results show that the proposed algorithm can effectively reduce the search range，improve the operationspeed and global search ability of the algorithm，and improve the search and rescue efficiency of the underwater targets.Key Wordsmaritime search，path planning，K-means，genetic algorithm，mean variance modelClass NumberTP391总第 404 期2023 年第 6 期计算机与数字工程Computer&Digital EngineeringVol.51 No.613062023 年第 6 期计算机与数字工程2m表示无人机集合，参与遍历的无人机数量为m个；(xy)表示无人机经纬度坐标位置；sij表示无人机从目标i至目标j的路径长度；Sk表示第k个无人机的路径总长度；rijk表示第k个无人机从目标i飞行至目标j；wijk表示从第k个无人机从目标i飞行至目标j的权值。2.2前置条件1）遍历所有目标j=1nk=1mr1jk=m（1）j=1nk=1mrj1k=m（2）2）每个目标仅进过一次j=0nk=1mrijk=1i=2n（3）j=0nk=1mrijk=1j=2n（4）3）其它约束1in1jnijrijk01wijk(011km（5）3问题分析与算法实现3.1海上目标的漂移特征分析海上目标在风、浪、流等自然因素的影响下13，会形成一个速度场，目标漂移运动的速度会随着这个速度场的变化而变化14，逐渐离开原落水地点。受到漂移目标自身性质影响，比如目标的大小、形状、浸没比例等也会影响物体的漂移方向。结合风压的特性，并利用线性回归的方式对不同状态的救生筏进行实验。实验结果表明，不同状态的救生筏会向不同方向漂移，最终形成位置差异相对较大的多个群体15。海上救生筏漂移方向矢量模型结果如图1所示。3.2海上搜救目标分类子算法本节采用基于遗传算法的K-means聚类方法求解，根据示位标输出位置实现目标分类。该算法以聚类中心位置作为染色体，并进行编码。利用K-means准则函数值进行择优选择，得到最终的聚类中心。100806040200-20下风方向风压矢量/（cm/s）0510152025海面10米高处风速/（m/s）无海锚，轻载无海锚，重载有海锚，轻载有海锚，重载图1海上救生筏漂移方向矢量模型1）染色体编码将集合C聚类成m个簇，聚类中心位置分别为()x1y1、()x2y2、()xmym，则 染 色 体 编 码 为()x1y1x2y2xmym。采用直接对问题解编码方式，提高了遗传算法的运行效率，便于处理复杂的变量约束条件。2）基于K-means准则函数的适应度函数利用准则函数构造适应度函数。适应度函数越大说明聚类结果越优，越小说明聚类结果越差，因此适应度函数为max f=11+E（6）3）遗传算子（1）选择算子：采用最优保存策略和比例选择法相结合的方法。选择适应度高的个体，并采用轮盘赌的策略进行个体选择，最后将最优个体替换种群中最差个体。（2）交叉算子：选取适合浮点数编码的算术交叉方式，将两条配对的染色体进行线性组合，产生两条新的染色体。（3）变异算子：采用均匀变异算子，选定染色体的基因变异点，从取值范围内产生随机数，并替换原基因值。3.3海上目标路径规划子算法本节采用基于均值-方差模型的多染色体遗传算法进行求解，实现海上目标路径规划。该算法突破了单染色体遗传进化的框架，引入多染色体优化搜索的思路16。有针对性的选择位置相邻目标，并对其进行基因段插入突变，进而改变了染色体基因数量，有利于获取全局最优解。下面以 3 个无人机、15个目标为例介绍该算法。1）多染色体编码染色体每个基因表示一个目标，其中出发位置编号为0。多染色体编码方式如图2所示。1307第 51 卷搜寻设备搜寻线路设备-1设备-2设备-3021214605151117803481013图2多染色体编码方式示例2）基于均值-方差模型的适应度函数将搜寻设备行驶距离的均值作为主目标函数，选取设备形式距离的方差作为次目标函数，对方案按主次目标函数进行排序。则多搜寻设备协同的海上目标路径规划目标函数为min f(2)（7）其中：=i=0nj=0nsijk=1mrijkwijkm2=k=1m(Sk)2m（8）式中：为主目标函数；2为次目标函数，对方案主次目标函数进行排序，即设备行驶距离均值越小越好，行驶距离均值处于同一量级，方差越少越好。3）遗传算子（1）选择算子：采用最优保存策略和比例选择法相结合的方法。将适用度高的个体选择出来，并采用轮盘赌的策略选择个体，将最优个体替换种群中最差个体。（2）交叉算子：采用排序交叉方式，随机选取基因片段进行交叉操作。如后代染色体中出现重复基因，则保留选择出来的交叉基因片段，其余部分基因按缺失顺序进行替换。排序交叉示例如图3所示。设备-2 亲代1设备-2 亲代2设备-2 后代2051511178011151587011511187图3排序交叉示例（3）变异算子：采用基因段插入突变方式。当两条染色体上目标位置距离较近时，将目标基因段标记为交换区基因。若变异后适应度值小于变异前，则执行变异操作。基因段插入突变方式的变异过程如图4所示。021214605151117803481013021248146051511178031013设备-3261241483设备-11310设备-3261241483设备-11310交换区交换区图4杂交突变算子变异过程3.4算法流程本文提出的算法由目标分类和路径规划两个子算法组成，以主次目标函数方式建立比较准则，算法流程如图5所示。4计算结果采用面向对象的java语言编写程序，实现本文提出的算法。假设本次搜寻工作提供2艘搜救船舶和1架搜救直升机，则搜寻设备总数量为3，海上漂移目标数量为30（不包含出发位置），设置算法种群规模为 10，最大迭代次数为 500，当迭代到100200时即可获得最优解，计算结果如图6所示。李林：海上落水目标协同搜寻路径规划算法研究13082023 年第 6 期计算机与数字工程图5算法流程图本文算法输出结果如表1所示。从表中可以发现相对初始距离，每个搜寻设备行驶的距离明显减少，且三个搜寻设备的方差相对较小，避免了因个别搜寻设备遍历距离长而影响整体方案。同时，对于行驶距离较长的搜救路线，可选取速度相对较快的搜寻设备开展搜救工作。表1本文算法计算结果初始距离最短距离迭代次数设备127781645120设备223821678147设备323731650113平均最短距离1658方差3165结语本文提出了一种海上落水目标协同搜寻路径规划算法，用于提高海上落水目标的搜寻能力。本设备-2-9设备-2-4设备-2-5设备-2-8设备-2-7设备-2-6设备-2-3设备-2-2设备-2-1设备-3-1设备-3-2设备-3-3设备-3-4设备-3-10设备-3-9设备-3-5设备-3-7设备-3-8设备-3-6设备-1-1设备-1-2设备-1-3设备-1-4设备-1-5设备-1-6设备-1-9设备-1-8设备-1-7设备-1-11设备-1-10图6本文算法计算结果文将问题求解拆分为目标分类和路径规划两个子算法。根据实际应用需要，设计了主次两个目标函数。计算结果分析表明，本文提出的多染色体遗传算法具有比当前解决同类问题较好的性能和结果，能够适应实际问题需要。今后研究中需要进一步对染色体编码方式进行研究，以提高算法精度和性能，并将该算法运用于更广泛的多旅行商问题求解之中。参 考 文 献1贾大山.“十三五”经济社会发展对海运的需求 J.中国远洋航务，2015，114（10）：40-42.JIA Dashan.The demand of the economic and social development in the 13th five year plan for sea transportationJ.COSCO Shipping，2015，114（10）：40-42.2管振.中国海运经济发展：模式与竞争力研究 J.管理观察，2015，588（25）：25-44.GUAN Zhen.Chinas maritime economic development：mode and competitiveness J.Management Observation，2015，588（25）：25-44.3尚红波，苏开熙.海上落水遇险人员救助技术研究 J.中国水运，2019，639（12）：29-30.SHANG Hongbo，SU Kaixi.Research on rescue technology for people in distress at sea J.China Shipping，2019，639（12）：29-30.4肖方兵.海上搜救决策支持系统关键技术的研究 D.（下转第1358页）1309第 51 卷16Lea C，Flynn M D，Vidal R，et al.Temporal Convolutional Networks for Action Segmentation and DetectionC/Proceedings of the IEEE Conference on ComputerVision and Pattern Recognition，2017：156-165.17Hara L，Kataoka H，Satoh Y.Learning spatiotemporalfeatures with 3D residual networks for action recognitionC/Proceeding of IEEE International Conference onComputerVisionWorkshop（ICCVW），2017：3154-3160.18Cao W，Watson D，Bakke M，et al.Detection of Glutenduring the Fermentation Process to Produce Soy SauceJ.Journal of Food Protection，2017，80（5）：799.19黄友文，万超伦，冯恒.基于卷积神经网络与长短期记忆神经网络的多特征融合人体行为识别算法 J.激光与光电子学进展，2019，56（07）：243-249.HUANGYouwen，WANChaolun，FENGHeng.Multi-Feature Fusion Human Behavior Recognition Algorithm Based on Convolutional Neural Network andLong Short Term Memory Neural Network，2019，56（07）：243-29.大连：大连海事大学，2011.XIAO Fangbing.Research on Key Technologies of maritime search and Rescue Decision Support SystemD.Dalian：Dalian Maritime University，2011.5谈星余.海上作业遇险？小小示位标 海救“大功臣”J.珠江水运，2013，334（09）：48-49.ON Xingyu.Maritime operation in distress？Small position indicator to save great hero J.Pearl River Shipping，2013，334（09）：48-49.6李超.直升机海上救援技术的思考 J.科技风，2019，392（24）：239.LI Chao.Thinking on helicopter maritime rescue technologyJ.Science and Technology Wind，2019，392（24）：239.7郝瑞.新型快艇实施海上多目标搜救的优化模型 J.火力与指挥控制，2013，224（11）：81-83.HAO Rui.Optimization model of maritime multi-targetsearch and rescue for new type speedboatsJ.Firepowerand Command and Control，2013，224（11）：81-83.8叶多福，刘刚，何兵.一种多染色体遗传算法解决多旅行商问题 J.系统仿真学报，2019，31（01）：36-42.YE Duofu，LIU Gang，HE Bing.A multi chromosome genetic algorithm for solving multi traveling salesman problemJ.Journal of System Simulation，2019，31（01）：36-42.9Hu J，Xie L，Lum K Y，et al.Multiagent Information Fusion and Cooperative Control in Target Search J.IEEETransactions on Control Systems Technology，2013，21（4）：1223-1235.10余梦珺，张韧，高顶，等.基于蚁群算法的西北航道海上救援路径规划 J.海洋预报，2019，36（06）：62-72.YU Mengjun，ZHANG Ren，GAO Ding，et al.Maritimerescue path planning of Northwest channel based on antcolony algorithmJ.Ocean Forecast，2019，36（06）：62-72.11魏铁涛，屈香菊.多机协同与多目标分配任务规划方法J.北 京 航 空 航 天 大 学 学 报，2009，35（08）：917-920，924.WEI Titao，QU Xiangju.Task planning method for multiaircraft cooperation and Multi-objective AssignmentJ.Journal of Beijing University of Aeronautics and Astronautics，2009，35（08）：917-920，924.12唐哲.一种基于遗传算法的 k均值聚类分析 D.长沙：长沙理工大学，2014.TANG Zhe.A k-means clustering analysis based on genetic algorithmD.Changsha：Changsha University ofTechnology，2014.13谭鹏，谭乐祖，张峥，等.海上自由物体漂移轨迹预测方法 J.计算机与数字工程，2021，49（1）：105-110.TAN Peng，TAN Lezu，ZHANG Zheng，et al.Predictionmethod for drift trajectory of free objects at seaJ.Computer and Digital Engineering，2021，49（1）：105-110.14亓振武.海上自由物体漂移模型的研究 D.大连：大连海事大学，2016.QI Zhenwu.Study on drift model of free objects at seaD.Dalian：Dalian Maritime University，2016.15Dong-Xia Chang，Xian-Da Zhang，Chang-Wen Zheng.AgeneticalgorithmwithgenerearrangementforK-means clustering J.Pattern Recognition，2009，42（7）：1210-122.16Wang J，Zhou Y，Wang Y，et al.Multiobjective Vehicle Routing Problems With Simultaneous Delivery andPickup and Time Windows：Formulation，Instances，and Algorithms J.IEEE Transactions on Cybernetics，2015：1.（上接第1309页）余思成等：基于边界敏感网络的时序行为定位研究1358