基于记忆库粒子群算法的海上协作搜寻计划制定

吕进锋，赵怀慈

(1.中国科学院 沈阳自动化研究所，沈阳 110016； 2.中国科学院大学，北京100049； 3.光电信息处理重点实验室(中国科学院)，沈阳 110016；4.辽宁省图像理解与视觉计算重点实验室(中国科学院沈阳自动化研究所)，沈阳 110016)

0 引 言

海上搜寻是海上搜救的重要组成部分，也是军事领域和民事领域的常见问题。常见的搜寻目标包括：落水人员、航空器/船舶碎片等。海上搜寻任务就目标的运动状态可分为静止目标搜寻和运动目标搜寻。在整个搜寻任务过程中位置基本保持不变的目标可被视为静止目标。涉及生命救援的海上搜寻任务往往时间紧迫，如对救生筏、落水人员等目标的搜寻；同时，这类目标机动能力弱，在较短时间内由环境因素造成的位移(风、海流作用导致的漂移)可忽略不计。因此，此类任务通常被认为是静止目标搜寻任务。

多数海上事故发生地点和发生时间都无法准确获知，目标可能位置范围往往较大，在任务紧迫时搜寻设施只能选择部分区域进行搜寻，因此，海上静止目标搜寻问题实际为优化问题。本文研究目的为针对单个静止搜寻目标，为多个搜寻设施制定搜寻计划，使搜寻任务成功率尽可能达到最大。

海上搜寻理论起源于二战时期[1]，至今已有多个先进的海上搜救系统：如美国海上搜救最优规划系统(Search and Rescue Optimal Planning System, SAROPS)[2]、英国搜救信息系统(Search and Rescue Information System, SARIS)[3]。SAROPS包含的任务规划模块在获取目标位置信息基础上，采用启发式方法为搜寻设施制定搜寻计划并确定搜寻路线。加拿大搜救计划系统(CANadian Search And Rescue Program, CANSARP)采用Min/Max方法生成搜寻区域。我国于2014年提出建立“基于北斗的海上搜救系统”，旨在利用北斗导航定位功能，对海上事故进行快速定位和及时救援。

另有代表性的搜救方法有挪威搜救中心的Berger等[4-5]提出的混合整数规划方法(Mixed-Integer linear Programming, MIP)等。该方法可为搜寻设施生成精确的搜寻路径，但该方法生成的搜寻路径为不受约束的不规则路径，未考虑实际工作环境，搜寻设施在实际搜寻任务中难以按照其生成的搜寻路径执行搜寻。邢胜伟[6]提出一种凸搜寻区域剖分算法，将搜寻区域分割为不同部分，分配给多个搜寻设施，但实际搜救任务往往无法实现对目标所有可能位置范围进行覆盖式搜索。郑宏喆等[7]利用蒙特卡罗法模拟目标漂移轨迹，确定目标位置信息。王光源等[8]对目标漂移模型进行分析，并根据搜寻误差和搜寻安全系数进一步确定搜寻区域，其研究并未涉及为具体搜寻设施制定搜寻方案。

海上搜寻计划制定的主要难点在于目标可能位置范围较大，同时需考虑参与搜寻任务的搜寻设施之间的协作、冲突问题，影响任务成功率的因素较多且相互影响，因此搜寻计划制定是较复杂的优化问题，快速有效地为搜寻设施制定协作搜寻方案具有较大的难度。

启发式优化方法在多类任务规划问题上得到成功的应用，如刘勇等[9]将混沌粒子群算法应用于空间机器人轨迹优化，李洁等[10]将和声搜索算法应用于网络安全态势预测问题。粒子群算法由于其需要调节的参数较少、容易实现等优点得到了大量学者的关注。粒子群等启发式优化算法能够很好地利用种群对复杂解空间进行探测，实现对复杂问题的试探性求解。其不足通常表现为易陷入局部最优解，无法保证最终所得解的质量。常见的改进策略包括增加或改变种群进化方式，增加约束条件降低种群多样性下降速度等。这类方法在一定程度上可有效提高算法性能。文献[11]提出一种带动态实例学习能力的粒子群优化算法并将其应用于永磁同步电机(Permanent Magnet Synchronous Motor, PMSM)驱动系统参数估计，该算法可有效平衡种群全局探测能力和局部精细搜索能力。文献[12-13]分别引入基于高斯的动态反向学习策略和基于混沌逻辑的受体编辑策略使种群能够有效跳出局部最优。

针对海上静止目标搜寻问题，本文提出一种记忆库粒子群算法为搜寻设施制定协作搜寻计划。记忆库粒子群算法首先假设仅需为单个搜寻设施制定搜寻计划，通过借鉴和声搜索算法策略[14]，从记忆库中学习、随机生成产生新的备选解；同时采用网格法构造记忆库并进行更新，旨在使新的备选解同时有较好的质量和多样性。此过程可认为对解空间进行有效的全局搜索。最后，在记忆库稳定时，从记忆库中随机选择多个备选解组合成为所有搜寻设施的初始搜寻方案，采用粒子群算法策略[15-16]，粒子通过信息交换在解空间中进一步搜索最优解，最终生成高质量的搜寻计划。

1 海上静止目标搜寻

搜寻设施在获取目标位置信息的基础上制定计划展开搜寻。海上事故发生后，目标通常会离开事故发生位置。如航空器爆炸后飞行员会弃机跳伞逃生。搜寻设施需首先分析目标可能所在位置。实际搜寻任务中，事故位置及时间通常无法确定。飞行员在跳伞过程中会受高空风作用产生空中漂移，而现有技术手段无法获取足够精确的风场数据。搜寻设施通过估计相应参数可能范围来计算目标所在位置及相应概率。目标可能位置通常范围较大(可达104km2)，位于不同位置的概率也不同。目标位置信息通常用概率分布图(probability map)表示。概率分布图为栅格化的海图，栅格的灰度(数字)反映了目标位于相应海上区域的概率。静止目标在搜寻任务中位置信息保持不变，即相应的概率分布图保持不变。图1为一搜寻目标概率分布图示例[17]。图中椭圆区域表示目标可能位置范围，椭圆内栅格的灰度反映目标位于该区域的概率。栅格灰度值越大，目标位于相应区域的概率越小。

图1 概率分布图示例

搜寻设施对一广阔区域进行搜寻时，通常使用平行线搜寻方式，如图2所示[18]。搜寻区域通常为规则矩形，每条搜寻航线与矩形的长边平行，航线间距为S，由搜寻设施的续航能力、扫视宽度及实际搜寻环境决定。航线间距通常大于搜寻设施的扫视宽度。为避免航线冲突和资源浪费，不同的搜寻设施需在不同的分区内进行搜寻。

图2 平行线搜寻方式

搜寻扫视宽度(W)指搜寻设施利用视力或电子探测设备对一地区进行扫视的有效距离宽度，是发现目标能力的一种衡量。不同搜寻设施的理论扫视宽度值(Wu)可通过查表获得。实际任务中的扫视宽度需根据客观环境对理论值进行修正。实际扫视宽度计算公式为W=Wu×hw，其中hw为修正系数。

搜寻设施在执行搜寻任务时，天气情况对探测设备的影响很大。发现概率(探测概率)是衡量搜寻设施探测能力的指标。搜寻设施在不同的天气条件下发现目标的概率有很大差别。若目标在搜寻设施的扫视范围内，与搜寻设施距离为d，则搜寻设施的探测概率pd(probability of detection)通常可用式(1)表示：

pd=aexp(-bd2); 0≤d≤W/2

(1)

其中：a，b为探测概率修正系数，a，b由探测设备属性、搜寻速度、环境条件、目标尺寸等因素决定，00。W为搜寻设施的扫视宽度。

海上搜寻的目的是充分利用现有资源(物质资源、时间资源)最大化任务成功率。对特定搜寻设施，需考虑其搜寻能力及搜寻模式，根据目标的概率分布图确定搜寻区域，制定搜寻路线，使搜寻设施在任务时间内成功发现目标的可能性达到最大。

对实际海上搜寻任务，若一搜寻设施在区域X内进行搜寻，可得任务成功率(Possibility of success, Pos)为：

(2)

其中：(x,y)为X区域内的位置，pc(x,y)表示目标位于位置(x,y) 的概率，pd(x,y) 表示搜寻设施对位置(x,y)的探测概率，即若目标位于位置(x,y)，搜寻设施可成功发现目标的概率。

对整个搜寻任务，当区域R被两个搜寻设施A，B重复搜寻，则可获得任务成功率为：

(3)

若单个搜寻设施在任务时间T内对矩形区域进行搜寻，则相应的搜寻路线可用七维向量表示：P=(p1,p2,p3,p4,p5,p6,p7)。其中：p1、p2分别确定矩形搜寻区域的中心位置的横纵坐标；p3、p4分别表示矩形区域的长与宽；p5表示矩形区域相对于水平方向的倾斜方向；p6表示搜寻速度；p7表示搜寻起始点，为矩形四个顶点之一，搜寻航线的间距可通过 (p6×T)/p3求得。

在海上搜寻任务中，评价搜寻计划优劣的指标即该计划对应的任务成功率。若有n个搜寻设施，协作搜寻计划可表示为：C=(P1,P2,…,Pn)，其中，Pi为第i个搜寻设施的计划。所有搜寻设施的搜寻区域集合为CS，CS中的子区域可分为两类：{X1,X2, …,Xm}，{R1,R2, …,Rk}，其中m,k∈N。Xi被单个搜寻设施搜寻，Rj被多个搜寻设施搜寻，1≤i≤m，1≤j≤k，则评价该协作方案优劣的适应度函数f定义如下：

(4)

其中：Pos(Xi)、Pos(Rj)可通过式(2)、(3)求得。

2 记忆库粒子群算法

由问题特性决定，大多数海上搜寻目标的概率分布图呈现为不规则状态，影响任务成功率的因素较多，多数情况下海上协作搜寻计划制定问题相应的解空间为复杂的高维、多峰形态。大多数启发式优化算法用来求解多峰函数优化问题时常见的不足为收敛速度过高，随着迭代次数的增加丧失多样性，从而陷入局部最优解[19]。常见的策略是扩大种群规模，降低搜索步长，这种做法往往造成运行时间增加，导致算法可行性降低。实际海上搜寻任务时间资源宝贵，要求算法为搜寻设施快速制定高质量的搜寻计划。针对海上静止目标协作搜寻问题，本文提出一种记忆库粒子群算法。

当搜寻设施数量较多，则协作搜寻方案维度较高(每个搜寻设施的方案用七维向量表示)。直接初始化随机生成协作搜寻方案后进行迭代寻优的复杂度较大，且多数启发式优化算法生成最终解的质量很大程度上依赖于初始解质量。由式(3)可知，对海上协作搜寻问题，多个搜寻设施对同一区域重复搜寻获得的成功率通常小于对不同区域分别搜寻获得的成功率。因此记忆库粒子群优化算法首先假设只有一个搜寻设施，为单个搜寻设施生成多个较好且差异较大的备选方案，在此基础上从备选方案中随机组合生成协作搜寻方案。此时各个搜寻设施的方案差异较大，因此组合生成的协作方案对比随机生成的协作方案有更高质量。在此基础上利用一定策略进行迭代寻优，生成最终的协作搜寻计划。利用该方法可快速有效地为多个搜寻设施制定高质量的协作搜寻计划。

记忆库粒子群为单个搜寻设施生成搜寻计划时借鉴和声搜索算法策略，即建立记忆库(Memory Bank, MB)，通过从记忆库中学习、随机生成产生新的备选解。其次采用网格法对记忆库进行更新，即将解空间分割为多个子区域，每个子区域仅可能有至多一个备选解保存在记忆库中，采用网格法更新记忆库旨在使记忆库中的备选解有较好质量的同时有较好的多样性。最后，在记忆库稳定时，从记忆库中随机选择备选解组合成所有搜寻设施的协作搜寻方案。利用粒子群算法策略，个体通过进行信息交换在解空间中对全局最优解展开搜索。粒子群算法具有较高的收敛速度，对连续函数的优化有很好的适用性，种群可利用该策略围绕较好质量的解进行局部搜索。记忆库粒子群算法的详细阐述如下。

假设需为单个搜寻设施制定搜寻计划时，将问题空间映射至算法空间后，相应的解空间中的任一点均代表一个备选解，即问题的备选方案。对D维解空间，任一备选解可由D维向量表示，即Y=(y1,y2,…,yD)。为单个搜寻设施制定搜寻计划，解空间为7维。各维参量的取值范围由实际问题决定。评价备选方案优劣的适应度函数如式(2)所示。记忆库粒子群算法首先将解空间分割为多个等大的网格(当解空间为高维时，解空间被分割为多个等大的超立方体)，确定记忆库规模(Memory Bank Scale, MBS)，随机生成MBS个点填充到记忆库中。记忆库的结构为矩阵。对D维解空间，相应记忆库MB可表示为式(5):

(5)

其中：Y表示D维的备选解，MBS为记忆库的大小，f为评价备选解的适应度函数，由式(2)表示。

记忆库粒子群算法通过两种方式产生新的备选解：从记忆库中学习、随机生成。对任一新的备选解，首先生成在0和1之间均匀分布的随机数z1，若z1小于记忆库取值概率(Memory Considering Rate, MCR)，则从记忆库中随机选择相应的参数作为该备选解的各维参数；否则，随机生成该备选解的各维参数。新的备选解Ynew各维参数的生成策略如下：

(6)

其中：MCR为记忆库取值概率，Li是第i维参数的取值空间。此阶段旨在生成差异较大的备选解，因此，MCR取值较小。

当新的备选解生成以后，适应度函数f对新的备选解进行评价。假设新的备选解Ynew位于解空间中的网格G中，记忆库中的任意备选解Yi均不在网格G中，则若新的备选解优于记忆库中最差的备选解Yw，那么就用新的备选解取代记忆库中最差的备选解；若记忆库中已存在备选解Yi位于网格G中，且新的备选解优于该解，则将新的备选解取代Yi；否则，记忆库保持不变。更新记忆库可用式(7)表示：

Ynew∈G，若∀Yi∉G且f(Ynew)>f(Yw)，则：

Ynew∈MB，Yw∉MB；

否则，若∃Yi∈G且f(Ynew)>f(Yi)，则：

Ynew∈MB，Yi∉MB

(7)

其中：1≤i≤MBS，Yw是记忆库中适应度值最小的备选解。

当记忆库中备选解所在网格不再发生变化时，记忆库粒子群算法在记忆库的基础上生成协作搜寻计划并迭代寻优。对n个搜寻设施，任一协作搜寻方案C=(P1,P2,…,Pn)，Pi为第i个搜寻设施的计划。

Pi=rand{Yj}

(8)

其中Yj∈MB。

粒子个数为N，则初始化生成N个协作方案，每个粒子为7n维向量，n为搜寻设施数量。初始化生成协作搜寻计划后，记忆库粒子群算法利用种群对全局最优解展开搜索。评价粒子质量的适应度函数如式(4)所示。种群中个体按以下策略更新其位置及速度：

(9)

(10)

记忆库粒子群算法使个体之间通过进行信息交换，围绕高质量的备选解侧重于局部搜索。由于初始协作搜寻方案为记忆库中的备选解组合，记忆库采用网格法进行更新，因此可认为初始协作搜寻方案均具有较高的适应度值。此过程可被视为对解空间进行有效的全局搜索。在此基础上，记忆库粒子群算法借鉴粒子群算法更新策略，可有效地围绕高质量的备选解进行有效的局部搜索。

综上所述，应用记忆库粒子群算法制定海上协作搜寻计划的主要步骤为：首先假设仅存在单个搜寻设施，确定相应参数取值范围，生成记忆库；其次通过从记忆库中学习或随机生成两种策略生成新的备选解，采用网格法更新记忆库；最后组合记忆库中的备选解生成初始协作搜寻计划，并采用粒子群策略更新协作搜寻计划。记忆库粒子群算法的流程如图3所示。

图3 记忆库粒子群算法流程

3 实验结果及分析

为检验记忆库粒子群优化(Memory Bank Particle Swarm Optimization, MBPSO)算法的性能，本文将其与和声搜索算法(Harmony Search, HS)、粒子群优化(Particle Swarm Optimization, PSO)算法、蝙蝠算法(Bat Algorithm, BA)[20]共同对海上静止目标协作搜寻问题进行仿真实验。

实验环境为Windows 7 32 b，CPU 为Pentium Dual-core 2.70 GHz，内存为2.0 GB，Matlab 2014。实验输入包括静止目标的概率分布图、任务时间、搜寻设施数量及能力等。所有任务的搜寻目标是落水的飞行员，搜寻设施均是续航能力超过72 h的船舶。搜寻设施的航行速度最大可达为50n mile/h(1n mile=1.852 km)。概率分布图的比例尺为1∶200 000。搜寻方案的区域长宽精度为1 km，任务时间为24 h，搜寻设施数量从3～5不等。实验输出为协作搜寻方案，包括各个搜寻设施的搜寻区域、搜寻路线及总的任务成功率。在实际应用中，算法的运行时间往往是决定算法实用性的一个重要指标，因此，除任务成功率外，本文从算法的运行时间方面对所提方法与其余几种算法进行比较，以验证算法的可行性与有效性。

在所有实验中，记忆库大小为100，MCR取值为0.7，种群规模为150，ω取值为0.7。仿真实验结果如表1所示。其中，实际最佳方案成功率为穷举所有备选解得到的全局最优解代表的搜寻计划的成功率。针对每个搜寻任务，每个算法重复运行20次。每个算法的任务成功率均值即该算法所对应的20个任务成功率的平均值。对每个算法，其任务成功率均值越接近实际最佳方案成功率，代表该算法性能越好。

由以上实验结果可知，相较于其他几种算法，记忆库粒子群算法获得的搜寻方案最佳，相应的任务成功率均值最高。同时，记忆库粒子群算法的任务成功率与实际最佳方案的任务成功率的差距较小。由此可知，记忆库粒子群算法能为搜寻设施生成高质量的协作搜寻方案。除记忆库粒子群算法以外，蝙蝠算法生成的搜寻方案优于其余几种算法，和声搜索算法生成的搜寻方案与粒子群算法生成的方案质量相当。记忆库粒子群算法在生成单个搜寻设施的搜寻计划的基础上，组合生成协作搜寻计划，网格法更新记忆库策略使初始协作计划有较好的质量和多样性，对解空间进行有效的全局搜索，在此基础上粒子之间通过信息交流围绕较高质量的解展开搜索，进行有效的局部搜索，实验结果证明该策略一定程度上有效避免种群陷入局部最优，从而可生成质量更好的解。和声搜索算法、粒子群算法均会由于问题维度高、种群收敛速度高、种群多样性降低等因素陷入局部最优解，从而生成的搜寻方案质量较差。蝙蝠算法一定程度上结合粒子群搜索策略和局部搜索策略，较为有效地避免种群由于快速收敛而陷入局部最优解。因此，相较于粒子群算法、和声搜索算法，蝙蝠算法在海上搜寻问题上表现更优。

表1 平均任务成功率及运行时间对比

所有算法生成的搜寻方案质量会随问题复杂程度的上升而下降。在表1中表现为当搜寻设施数量较多时，所有算法相应的任务成功率与实际最佳方案任务成功率的差距较大。这主要是由于搜寻设施数量越多，相应解空间维度越高，问题往往具有较高的复杂程度。从表1中可知，针对任务三，搜寻设施为5个时，记忆库粒子群算法生成的协作搜寻方案平均任务成功率为36%，与实际最佳方案任务成功率(40%)的差距为4%，而其余几种算法的搜寻方案与实际最佳方案任务成功率的差距在6%以上(和声搜索算法相应的差距为8%)。由此可知相较于其余几种算法，针对复杂度较高的搜寻任务，记忆库粒子群算法仍可稳定地生成的高质量搜寻方案。针对每个搜寻任务，每个算法均重复运行20次，统计实验结果可知，记忆库粒子群算法相应的任务成功率方差最小，进一步验证了记忆库粒子群算法的稳定性。

就算法运行时间来看，蝙蝠算法的运行时间最短，和声搜索算法运行时间最长，记忆库粒子群算法的运行时间居中。经分析可知，记忆库粒子群算法采用网格法更新记忆库的策略在一定程度上耗费了时间。蝙蝠算法的更新策略相对较简单，运行速度最高。和声搜索算法生成新的备选解的策略较复杂，因而算法运行时间较长。

图4为对三个搜寻任务进行实验相应的收敛曲线。从图中可以看出：和声搜索算法和粒子群算法的收敛速度最高，但其相应的适应度值较低，可知这两种算法较容易陷入局部最优；蝙蝠算法收敛速度较低，同时可获得较好的适应度值；记忆库粒子群算法收敛速度居中，相应的适应度值最高。

分析实验结果可知，记忆库中保存的备选解有较高的适应度值，且备选解之间差异性较大(在解空间中距离较大)。引入记忆库策略使种群首先在整个解空间进行有效的全局搜索，在此基础上粒子通过与其他个体进行信息交换，围绕质量较好的解进行有效的局部搜索，基于此种群可实现从全局搜索向局部搜索过渡，种群多样性下降速度较低，从而避免种群陷入局部最优解。

总的来说，记忆库粒子群算法可以在较短的时间内为搜寻设施制定有效的协作搜寻计划，在海上搜寻问题上有较好的适用性。

图4 四种算法收敛曲线

4 结语

针对海上静止目标搜寻问题，本文提出一种记忆库粒子群优化算法，旨在快速有效地为搜寻设施制定高质量的协作搜寻计划。记忆库粒子群优化算法首先假设仅需为单个搜寻设施制定搜寻方案，通过从记忆库中学习、随机生成产生新的备选解；其次采用网格法更新记忆库，对解空间进行较好的全局搜索；最后利用记忆库中的备选解组合生成协作搜寻计划，使初始协作方案同时有较好的多样性和质量，最后采用粒子群算法策略，个体之间通过进行信息交换围绕质量较好的解展开搜索。记忆库粒子群算法有效利用组合优化策略和连续优化策略，记忆库的引入使种群能够首先进行有效的全局搜索，在此基础上利用粒子群策略可使种群围绕质量较高的解进行有效的局部搜索，同时种群多样性下降速度较低。本文在多个协作搜寻任务上对所提算法进行实验验证。实验结果表明相较于其余几种算法，记忆库粒子群算法可快速稳定地生成具有更高任务成功率的协作搜寻方案。