基于过渡粒子群算法的搜寻方案

吕进锋 贾晓洪 王明昌

摘要：为有效搜寻坠毁航空器及失联飞行员，本文提出一种过渡粒子群算法，为搜寻设施制订高质量的搜寻计划。针对搜寻区域范围较大，过渡粒子群算法首先对解空间进行有效的全局搜索。其在构建记忆库的基础上通过学习、随机生成的方式生成初始解。为保证备选解的多样性，将解空间分割为多个网格，每个网格至多有一个备选解保存在记忆库中。当记忆库中备选解所在网格不再发生变化时，利用粒子群策略对解空间进行有效的局部搜索，种群中的个体通过信息交换在解空间中展开搜索。试验结果表明，相较其余几种启发式算法，过渡粒子群算法可制订具有更高任务成功率的搜寻计划。

关键词：搜寻计划；粒子群；记忆库；全局搜索；局部搜索

中图分类号：TP18文献标识码：ADOI：10.19452/j.issn1007-5453.2020.10.011

随着我国航空业的高速发展、航空器数量稳步增长，航空器事故时有发生。利用搜寻救助设施对航空器、飞行员进行有效救援是减小航空器事故造成的生命财产损失的最后一道防线[1]。多数航空器事故无法获取救援目标的准确位置，飞行员在航空器坠毁时若跳伞自救，其在空中的漂移轨迹受风场、跳伞高度等多个因素影响，搜寻范围通常较大。此时有效的搜寻是进行救援的前提，决定了整个救援任务是否成功。

常见的航空器训练作战环境包括山区及近海区域。此类环境地形通常较为复杂，投入大量的专业搜救人员及设备进行搜寻难度较大。同时，在环境恶劣的情况下飞行员存活的时间较短（如在20°C的海水中飞行员的存活时间约16h），因此涉及生命救援的航空器搜寻任务往往时间紧迫。无人机、直升机是航空器事故中常用的搜寻设施。

搜救指挥中心接到事故报告后，需要首先确定航空器/飞行员可能着陆区域。搜寻指挥中心需要根据航空器性能、风场、地理信息等估算航空器/飞行员的着陆位置概率。考虑到搜寻任务时间紧任务重，搜救资源有限，在给定任务时间内无法对所有区域进行覆盖式搜寻，只能选择部分区域进行搜寻。本文研究目的为针对航空器/飞行员搜救任务，制订有效搜寻计划，确定搜寻区域及方式，尽可能最大化任务成功率。

根据工作环境，航空器搜寻任务可分为海上搜寻及陆地搜寻。海上搜寻理论起源较早[2]，至今已有多个具有成熟的搜救系统[3]，如美国的最优搜救规划系统（search and rescue optimal planning system， SAROPS）[4]，加拿大的搜救信息系统（CANSARP）[5]，英国的搜救信息系统（search and rescue information system， SARIS）等[6]。SAROPS采用启发式方法制订搜寻计划，并确定搜寻路线。CANSARP采用Min/ Max方法为航空器等搜救设施规划搜寻区域。SARIS主要包含搜索区域决策（search area determination， SAD）以及搜索区域覆盖（search area coverage， SAC）两大模块。SAD生成目标位置可能区域，SAC為搜寻设施确定搜寻区域。Jean Berger等针对海上目标搜寻任务提出混合整数规划方法（mixed integer programming， MIP）等[7-8]。该方法未考虑实际任务环境，搜寻路线不规则，在实际任务中难以执行。

除在地形复杂的区域对航空器/飞行员进行搜寻外，陆地搜寻同时包括针对地震、山体滑坡等地质灾害造成的事故，利用航空器、地面搜救、无线通信设备等对遇险人员进行救助。

针对目标为航空器/飞行员的搜寻问题，本文提出一种搜寻方案制订方法，利用群智能算法生成搜寻计划，使任务成功率尽可能达到最大。过渡粒子群为保证备选解的质量和多样性，首先引入和声搜索算法策略[9]，通过从记忆库中学习、随机生成等方式产生初始解及新的备选解，同时构造记忆库，并采用网格法进行更新。在此基础上引入粒子群算法策略[10-11]，使个体通过信息交换在解空间进行搜索。基于此，种群可对解空间进行较好的全局搜索和局部搜索，获得较高的任务成功率。

1航空器搜寻

对目标为航空器/飞行员的搜寻任务，其着陆位置范围通常较大，获得目标位于特定位置的概率是制订搜寻方案的必要条件。实际搜救任务中，目标位于不同区域的概率可用概率分布图表示。表1为一航空器位置概率分布图示例[12]。

在实际搜寻任务中，搜寻设施利用一定的探测设备（如红外、可见光、雷达等探测设备）对目标进行探测。为方便搜寻设施执行任务，搜寻区域常为矩形，搜寻路线常为等长等距的平行线，搜寻航线与矩形的长边平行，如图1所示[12]。航线间距为S，在实际搜寻任务中由设施的搜寻能力、扫视宽度等因素决定。航线间距通常大于搜寻设施的扫视宽度。搜寻设施的扫视宽度（W）由实际环境条件（能见度）及目标特征（如尺寸、颜色等）等因素决定。

探测概率是衡量搜寻设施搜寻能力的一个重要指标。若目标在搜寻设施扫视范围内，搜寻设施可成功发现目标的概率即为探测概率。对任意搜寻设施，若目标与搜寻设施的横向距离x，探测概率pd可用式（1）表示：

2过渡粒子群算法

目标为航空器/飞行员的搜寻任务，通常具有待搜寻区域大、任务时间紧迫等特点。制订搜寻方案意味着需根据目标的位置概率信息、环境状况、搜寻设备能力等确定搜寻路线及搜寻速度，使在相应的任务时间内成功发现目标的概率达到最大。应用常见的启发式优化方法解决该问题时，通常会产生算法收敛速度过快而陷入局部最优，或算法运行时间过长而降低其适用性[13-15]。针对航空器搜寻问题，本文旨在提出一种改进的群智能算法，在解空间进行有效的全局搜索与局部搜索，使生成的方案同时具有较高的任务成功率及较短的运行时间。

针对航空器搜寻计划制订问题，本文提出一种过渡粒子群算法，旨在利用和声搜索策略和粒子群搜索策略，使种群进行有效的全局搜索及局部搜索，快速获得高质量的解。过渡粒子群优化算法首先构造记忆库，

通过随机生成备选解存入记忆库中，同时通过学习、随机生成等策略更新记忆库。为保证记忆库中的备选解的多样性，过渡粒子群算法将解空间分割为多个网格，每个网格仅可能有至多一个备选解保存在记忆库中，此时记忆库中的解具有较好的质量及多样性，基于此种群可对解空间进行有效的全局搜索。在记忆库中备选解所在网格不再变动时，利用粒子群算法策略，将种群重置为记忆库中的备选解，种群中围绕具有较高质量的备选解展开搜索。利用该策略可使种群具有较高的收敛速度，同时可对解空间进行有效的局部搜索。过渡粒子群算法的详细阐述如下。

过渡粒子群算法采用网格法对记忆库进行更新，因此记忆库中的备选解具有较高的适应度值和较好的多样性。在此基础上，种群重置为记忆库中的解，利用粒子群更新策略可有效地对全局最优解进行搜索，种群同时具备较快的收敛速度。

综上所述，应用过渡粒子群算法制订搜寻方案的流程为：

（1）确定搜寻方案各个参数的上下界，设定记忆库规模及其他参数，根据式（4）生成初始记忆库；

（2）根据式（5）构造新的备选解，利用式（3）计算备选解适应度值，利用式（6）更新记忆库直至记忆库中备选解所在网格不再发生变化；

（3）将种群重置为记忆库中的解；

（4）根据式（7）、（8）进行迭代计算，更新粒子位置和速度直至算法结束；

（5）输出算法所得的搜寻方案及任务成功率。

3试验结果及分析

为检验过渡粒子群算法（transition particle swarm optimization， TPSO）的性能，本文将其与粒子群算法（particle swarm optimization，PSO）和声搜索算法（harmony search， HS）、蝙蝠算法[16]（bat algorithm， BA）共同对航空器搜寻问题进行仿真试验。

试验平台为Matlab 2014。试验中搜寻目标为航空器。试验输入包括探测概率修正系数、目标的位置信息、任务时间等。搜寻设施速度上界为40m/h，概率分布图的比例尺为1∶200000。搜寻方案的区域长宽精度为1km，任务时间为12～24h。试验输出即相应的搜寻方案，包括搜寻区域、路线等。为验证算法的可行性与有效性，除任务成功率外，考虑实际搜救任务时间资源宝贵，本文同时给出所提算法与对比算法的运行时间。

试验中参数设置如下：MBS=50，MCR=0.6，种群规模为100，ω= 0.7。试验结果见表2。其中，实際最佳方案成功率为穷举所有备选解得到的全局最佳搜寻方案相应的成功率。针对每个搜寻任务，每个算法重复运行20次。表2给出每个算法的任务成功率均值，该值越接近实际最佳方案成功率，代表算法性能越好。

由表2可知，相较HS、PSO、BA，TPSO获得的搜寻方案相应的任务成功率均值最高。同时，TPSO的任务成功率与实际最佳方案的任务成功率的差距较小（所获方案与最佳方案成功率的平均差距小于0.01）。除TPSO以外，BA生成的搜寻方案优于和声搜索算法及粒子群算法。TPSO利用相应的策略从全局搜索到局部搜索有效过渡，试验结果证明该策略的有效性。HS、PSO均存在收敛速度快、种群多样性降低从而陷入局部最优解。BA结合利用个体对解空间进行较为有效的局部搜索，避免种群多样性快速下降。相较PSO、HS，BA在航空器搜寻问题上表现更优。

从表2中可看出，当概率分布图较大、任务时间较长时，所有算法相应的成功率均值与实际最佳方案成功率相差较大，且相应的方差较大。分析原因为较大的概率分布图意味着问题具有较高的复杂程度。从表2可知，针对任务3，TPSO相应的平均任务成功率为16.4%，与实际最佳方案任务成功率（17.9%）的差距为1.5%，低于PSO、HS，BA。由此可知针对复杂度较高的搜寻任务，TPSO仍可有效生成高质量搜寻方案。对每个搜寻任务，TPSO相应的任务成功率方差最小，表明TPSO具有较好的稳定性。

为验证算法的实用性，表2给出算法针对各个任务的平均运行时间。BA耗时最短，HS最长。TPSO在种群优化过程中，采用网格法更新记忆库，该步骤较为耗时，TPSO的算法运行时间居中。HS生成新的备选解的策略较复杂，因而算法运行时间较长。

总的来说，针对航空器搜寻任务，相较其余几种算法，TPSO可在较短的运行时间内稳定地生成高质量的搜寻计划，且随着问题复杂程度的上升，TPSO优越性更加明显。因此可知，TPSO在航空器搜寻问题上有较好的适用性。

4结论

针对航空器搜寻问题，本文提出一种过渡粒子群优化算法。过渡粒子群优化算法首先通过从记忆库中学习、随机生成产生新的备选解；其次采用网格法更新记忆库；最后采用粒子群算法策略，将种群重置为记忆库中的备选解，使个体通过进行信息交换在解空间中进行搜索，基于此对解空间进行有效的全局与局部搜索。为验证所提方法有效性，本文在多个航空器搜寻任务上进行仿真试验。由试验结果可知，过渡粒子群算法可在较短时间内生成最佳的搜寻方案，在航空器搜寻问题上具有较好的适用性。

参考文献

[1]方芳，杨航，李伟，等.一种基于北斗的航空搜救机载指挥系统设计[J].航空科学技术，2018，29（10）：48-52. Fang Fang， Yang Hang， Li Wei， et al. Design of airborne search and rescue command system based on Beidou satellite[J]. Aeronautical Science & Technology， 2018， 29（10）：48-52. （in Chinese）

[2]Koopman B O. The theory of search. III. The optimum distribution of searching effort[J]. Operations Research，1957，5（5）：613-626.

[3]吕进锋，赵怀慈.基于记忆库粒子群算法的海上协作搜寻计划制定[J].计算机应用， 2018， 38（9） ： 2477-2482. Lyu Jinfeng， Zhao Huaici. Maritime cooperative search planning based on memory bank particle swarm optimization[J]. Journal of Computer Applications， 2018， 38（9） ： 2477-2482. （in Chinese）

[4]Thomas M K，Lawrence D S，John R F. Search and rescue optimal planning system[C]// 13th Conference on Information Fusion，2010.

[5]Canadian C G. National search and rescue manual [M]. Ottawa：Department of National Defence/Canadian Coast Guard，2000.

[6]BMT Cordah. Search and rescue information system（SARIS）[EB/OL].（2008-09-10）. http：//www.bmtcordah.com/.

[7]Jean B，Nassirou L，Martin N. A new multi-target，multi-agent search-and-rescuepathplanningapproach[J].International Journal of Computer，Information，Systems and Control Engineering，2014，8（6）：902-912.

[8]Jean B，Nassirou L. An innovative multi-agent search-andrescue path planning approach[J]. Computers & Operations Research，2015，53：24-31.

[9]歐阳海滨，高立群，邹德旋，等.和声搜索算法探索能力研究及其修正[J].控制理论与应用，2014， 31（1）：57-65. Ouyang Haibin， Gao Liqun， Zou Dexuan， et al. Exploration ability study of harmony search algorithm and its modification[J]. Control Theory & Applications， 2014， 31（1）： 57-65. （in Chinese）

[10]胡旺，Gary G Y，张鑫.基于Pareto熵的多目标粒子群优化算法[J].软件学报， 2014，25（5）：1025-1050. Hu Wang， Gary G Y， Zhang Xin. Multiobjective particle swarm optimization based on pareto entropy[J]. Journal of Software， 2014， 25（5）：1025-1050. （in Chinese）

[11]匡芳君，徐蔚鸿，张思扬.基于改进混沌粒子群的混合核SVM参数优化及应用[J].计算机应用研究， 2013，31（3）： 671-674. Kuang Fangjun， Xu Weihong， Zhang Siyang. Parameter optimization and application of SVM with mixtures kernels based on improved chaotic particle swarm optimization[J]. Application Research of Computers， 2013，31（3）： 671-674. （in Chinese）

[12]国际海事组织.国际航空和海上搜寻救助手册[M].北京：人民交通出版社，2002. International Maritime Organization. International aeronautical and maritime search and rescue manual[M]. Beijing： Peoples Communications Press， 2002. （in Chinese）

[13]刘勇，贾庆轩，陈钢，等.基于多目标粒子群优化算法的自由漂浮空间机器人负载最大化轨迹优化[J].机器人， 2014， 36（4）：402-410. Liu Yong， Jia Qingxuan， Chen Gang， et al. Load maximization trajectory optimization for free-floating space robot using multi-objectiveparticleswarmoptimizationalgorithm[J]. Robot， 2014， 36 （4）：402-410. （in Chinese）

[14]陈志敏，薄煜明，吴盘龙，等.基于自适应粒子群优化的新型粒子滤波在目标跟踪中的应用[J].控制与决策， 2013， 28（2）： 193-200. Chen Zhimin， Bo Yuming， Wu Panlong， et al. Novel particle filter algorithm based on adaptive particle swarm optimization and its application to radar target tracking[J]. Control and Decision， 2013， 28（2）：193-200. （in Chinese）

[15]马博平，王刚，叶坤，等.基于RBF神经网络和遗传算法的超声速Licher双翼优化设计研究[J].航空科学技术， 2019， 30（9）：73-80. Ma Boping， Wang Gang， Ye Kun， et al. Supersonic licher biplane optimization using radial-basis function neural network and genetic algorithm[J]. Aeronautical Science & Technology， 2019， 30（9）：73-80. （in Chinese）

[16]劉长平，叶春明.具有Lévy飞行特征的蝙蝠算法[J].智能系统学报， 2013， 3（8）：240-246. Liu Changping， Ye Chunming. Bat algorithm with the characteristics of Lévy flights[J]. CAAI Transactions on Intelligent Systems， 2013， 3（8）：240-246. （in Chinese）

（责任编辑王为）

作者简介

吕进锋（1990-）女，博士后，讲师。主要研究方向：人工智能、模式识别和导航制导。

Tel：15565340921E-mail：jinfengnn@163.com

Search Plan Based on Transition Particle Swarm Optimization

Lyu Jinfeng1，2，*，Jia Xiaohong2，Wang Mingchang2，3

1. Henan University of Science and Technology，Luoyang 471000，China

2. China Airborne Missle Academay，Luoyang 471009，China

3. Aviation Key Laboratory of Science and Technology on Airborne Guided Weapons，Luoyang 471009，China

Abstract： In order to search crashed aircraft and lost pilots effectively， a transition particle swarm optimization algorithm（TPSO） is proposed to make high quality search plans for search units. Considering that the search area is large， TPSO makes an effective global search at first. It constructs a memory bank and generates new candidate solutions based on memory consideration and random selection. In order to ensure the good diversity of candidate solutions， the solution space is segmented into multi lattices， and for each lattice there is one solution stored in the memory bank at most. When the memory bank is stable， effective local search is made by making use of particles swarm optimization strategy， and particles exchange information to search the solution space. The experimental results show that compared with other heuristic algorithms， TPSO can generate better search plans with higher possibility of success.

Key Words： search plan； particle swarm； memory bank； global search； local search