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

李 林

（交通运输部水运科学研究院 北京 100088）

1 引言

以船舶为载体的海运经济网络，极大地促进了各国经济发展，具有不可替代的作用［1~2］。随着海上运输船舶数量的增长，船舶遇险事故数量也逐步增长［3］。船载救生装备往往会安装示位标［4~5］，示位标基于GNSS 能够提供准确的待救目标位置，便于搜救艇、直升机等救援设备快速、准确开展海上落水目标的搜救和打捞工作［6~7］。

海上落水目标的搜寻路径规划问题可以抽象为多旅行商（mTSP）问题，属于组合优化问题［8~9］，其求解过程包含了目标分组及组内遍历次序两个环节，是典型的NP-Hard问题［10］。对于多旅行商问题的研究主要集中在染色体的编码方式上［11~12］，不合理的编码策略将提高遗传算法的复杂度，产生大量冗余解，制约算法的求解效率。

本文提出一种多无人机协同的海上搜救目标分类与路径规划算法。该算法基于K-means 算法和遗传算法，采用均值-方差模型为作为最优路径的选择算子，具有算法简单、鲁棒性强、收敛速度快和全局搜索能力强等特点。

2 模型构建

2.1 变量定义

C={1,2,…,n}表示遍历目标集合，共有n个目标。其中第一个目标为无人机飞行起点；U={1,2,…,m}表示无人机集合，参与遍历的无人机数量为m个；(x,y)表示无人机经纬度坐标位置；sij表示无人机从目标i至目标j的路径长度；Sk表示第k个无人机的路径总长度；rijk表示第k个无人机从目标i飞行至目标j；wijk表示从第k个无人机从目标i飞行至目标j的权值。

2.2 前置条件

1）遍历所有目标

2）每个目标仅进过一次

3）其它约束

3 问题分析与算法实现

3.1 海上目标的漂移特征分析

海上目标在风、浪、流等自然因素的影响下［13］，会形成一个速度场，目标漂移运动的速度会随着这个速度场的变化而变化［14］，逐渐离开原落水地点。受到漂移目标自身性质影响，比如目标的大小、形状、浸没比例等也会影响物体的漂移方向。结合风压的特性，并利用线性回归的方式对不同状态的救生筏进行实验。实验结果表明，不同状态的救生筏会向不同方向漂移，最终形成位置差异相对较大的多个群体［15］。海上救生筏漂移方向矢量模型结果如图1所示。

图1 海上救生筏漂移方向矢量模型

3.2 海上搜救目标分类子算法

本节采用基于遗传算法的K-means 聚类方法求解，根据示位标输出位置实现目标分类。该算法以聚类中心位置作为染色体，并进行编码。利用K-means准则函数值进行择优选择，得到最终的聚类中心。

1）染色体编码

将集合C聚类成m个簇，聚类中心位置分别为(x1,y1)、(x2,y2)、…、(xm,ym)，则染色体编码为(x1,y1,x2,y2,…,xm,ym)。采用直接对问题解编码方式，提高了遗传算法的运行效率，便于处理复杂的变量约束条件。

2）基于K-means准则函数的适应度函数

利用准则函数构造适应度函数。适应度函数越大说明聚类结果越优，越小说明聚类结果越差，因此适应度函数为

3）遗传算子

（1）选择算子：采用最优保存策略和比例选择法相结合的方法。选择适应度高的个体，并采用轮盘赌的策略进行个体选择，最后将最优个体替换种群中最差个体。

（2）交叉算子：选取适合浮点数编码的算术交叉方式，将两条配对的染色体进行线性组合，产生两条新的染色体。

（3）变异算子：采用均匀变异算子，选定染色体的基因变异点，从取值范围内产生随机数，并替换原基因值。

3.3 海上目标路径规划子算法

本节采用基于均值-方差模型的多染色体遗传算法进行求解，实现海上目标路径规划。该算法突破了单染色体遗传进化的框架，引入多染色体优化搜索的思路［16］。有针对性的选择位置相邻目标，并对其进行基因段插入突变，进而改变了染色体基因数量，有利于获取全局最优解。下面以3 个无人机、15个目标为例介绍该算法。

1）多染色体编码

染色体每个基因表示一个目标，其中出发位置编号为0。多染色体编码方式如图2所示。

图2 多染色体编码方式示例

2）基于均值-方差模型的适应度函数

将搜寻设备行驶距离的均值作为主目标函数，选取设备形式距离的方差作为次目标函数，对方案按主次目标函数进行排序。则多搜寻设备协同的海上目标路径规划目标函数为

其中：

式中：μ为主目标函数；σ2为次目标函数，对方案主次目标函数进行排序，即设备行驶距离均值越小越好，行驶距离均值处于同一量级，方差越少越好。

3）遗传算子

（1）选择算子：采用最优保存策略和比例选择法相结合的方法。将适用度高的个体选择出来，并采用轮盘赌的策略选择个体，将最优个体替换种群中最差个体。

（2）交叉算子：采用排序交叉方式，随机选取基因片段进行交叉操作。如后代染色体中出现重复基因，则保留选择出来的交叉基因片段，其余部分基因按缺失顺序进行替换。排序交叉示例如图3所示。

图3 排序交叉示例

（3）变异算子：采用基因段插入突变方式。当两条染色体上目标位置距离较近时，将目标基因段标记为交换区基因。若变异后适应度值小于变异前，则执行变异操作。基因段插入突变方式的变异过程如图4所示。

图4 杂交突变算子变异过程

3.4 算法流程

本文提出的算法由目标分类和路径规划两个子算法组成，以主次目标函数方式建立比较准则，算法流程如图5所示。

图5 算法流程图

4 计算结果

采用面向对象的java语言编写程序，实现本文提出的算法。假设本次搜寻工作提供2 艘搜救船舶和1架搜救直升机，则搜寻设备总数量为3，海上漂移目标数量为30（不包含出发位置），设置算法种群规模为10，最大迭代次数为500，当迭代到100~200时即可获得最优解，计算结果如图6所示。

图6 本文算法计算结果

本文算法输出结果如表1 所示。从表中可以发现相对初始距离，每个搜寻设备行驶的距离明显减少，且三个搜寻设备的方差相对较小，避免了因个别搜寻设备遍历距离长而影响整体方案。同时，对于行驶距离较长的搜救路线，可选取速度相对较快的搜寻设备开展搜救工作。

表1 本文算法计算结果

5 结语

本文提出了一种海上落水目标协同搜寻路径规划算法，用于提高海上落水目标的搜寻能力。本文将问题求解拆分为目标分类和路径规划两个子算法。根据实际应用需要，设计了主次两个目标函数。计算结果分析表明，本文提出的多染色体遗传算法具有比当前解决同类问题较好的性能和结果，能够适应实际问题需要。今后研究中需要进一步对染色体编码方式进行研究，以提高算法精度和性能，并将该算法运用于更广泛的多旅行商问题求解之中。