基于過渡粒子群算法的搜尋方案

呂進鋒 賈曉洪 王明昌

摘要：為有效搜尋墜毀航空器及失聯(lián)飛行員，本文提出一種過渡粒子群算法，為搜尋設(shè)施制訂高質(zhì)量的搜尋計劃。針對搜尋區(qū)域范圍較大，過渡粒子群算法首先對解空間進行有效的全局搜索。其在構(gòu)建記憶庫的基礎(chǔ)上通過學(xué)習(xí)、隨機生成的方式生成初始解。為保證備選解的多樣性，將解空間分割為多個網(wǎng)格，每個網(wǎng)格至多有一個備選解保存在記憶庫中。當記憶庫中備選解所在網(wǎng)格不再發(fā)生變化時，利用粒子群策略對解空間進行有效的局部搜索，種群中的個體通過信息交換在解空間中展開搜索。試驗結(jié)果表明，相較其余幾種啟發(fā)式算法，過渡粒子群算法可制訂具有更高任務(wù)成功率的搜尋計劃。

關(guān)鍵詞：搜尋計劃；粒子群；記憶庫；全局搜索；局部搜索

中圖分類號：TP18文獻標識碼：ADOI：10.19452/j.issn1007-5453.2020.10.011

隨著我國航空業(yè)的高速發(fā)展、航空器數(shù)量穩(wěn)步增長，航空器事故時有發(fā)生。利用搜尋救助設(shè)施對航空器、飛行員進行有效救援是減小航空器事故造成的生命財產(chǎn)損失的最后一道防線[1]。多數(shù)航空器事故無法獲取救援目標的準確位置，飛行員在航空器墜毀時若跳傘自救，其在空中的漂移軌跡受風(fēng)場、跳傘高度等多個因素影響，搜尋范圍通常較大。此時有效的搜尋是進行救援的前提，決定了整個救援任務(wù)是否成功。

常見的航空器訓(xùn)練作戰(zhàn)環(huán)境包括山區(qū)及近海區(qū)域。此類環(huán)境地形通常較為復(fù)雜，投入大量的專業(yè)搜救人員及設(shè)備進行搜尋難度較大。同時，在環(huán)境惡劣的情況下飛行員存活的時間較短（如在20°C的海水中飛行員的存活時間約16h），因此涉及生命救援的航空器搜尋任務(wù)往往時間緊迫。無人機、直升機是航空器事故中常用的搜尋設(shè)施。

搜救指揮中心接到事故報告后，需要首先確定航空器/飛行員可能著陸區(qū)域。搜尋指揮中心需要根據(jù)航空器性能、風(fēng)場、地理信息等估算航空器/飛行員的著陸位置概率?？紤]到搜尋任務(wù)時間緊任務(wù)重，搜救資源有限，在給定任務(wù)時間內(nèi)無法對所有區(qū)域進行覆蓋式搜尋，只能選擇部分區(qū)域進行搜尋。本文研究目的為針對航空器/飛行員搜救任務(wù)，制訂有效搜尋計劃，確定搜尋區(qū)域及方式，盡可能最大化任務(wù)成功率。

根據(jù)工作環(huán)境，航空器搜尋任務(wù)可分為海上搜尋及陸地搜尋。海上搜尋理論起源較早[2]，至今已有多個具有成熟的搜救系統(tǒng)[3]，如美國的最優(yōu)搜救規(guī)劃系統(tǒng)（search and rescue optimal planning system， SAROPS）[4]，加拿大的搜救信息系統(tǒng)（CANSARP）[5]，英國的搜救信息系統(tǒng)（search and rescue information system， SARIS）等[6]。SAROPS采用啟發(fā)式方法制訂搜尋計劃，并確定搜尋路線。CANSARP采用Min/ Max方法為航空器等搜救設(shè)施規(guī)劃搜尋區(qū)域。SARIS主要包含搜索區(qū)域決策（search area determination， SAD）以及搜索區(qū)域覆蓋（search area coverage， SAC）兩大模塊。SAD生成目標位置可能區(qū)域，SAC為搜尋設(shè)施確定搜尋區(qū)域。Jean Berger等針對海上目標搜尋任務(wù)提出混合整數(shù)規(guī)劃方法（mixed integer programming， MIP）等[7-8]。該方法未考慮實際任務(wù)環(huán)境，搜尋路線不規(guī)則，在實際任務(wù)中難以執(zhí)行。

除在地形復(fù)雜的區(qū)域?qū)娇掌?飛行員進行搜尋外，陸地搜尋同時包括針對地震、山體滑坡等地質(zhì)災(zāi)害造成的事故，利用航空器、地面搜救、無線通信設(shè)備等對遇險人員進行救助。

針對目標為航空器/飛行員的搜尋問題，本文提出一種搜尋方案制訂方法，利用群智能算法生成搜尋計劃，使任務(wù)成功率盡可能達到最大。過渡粒子群為保證備選解的質(zhì)量和多樣性，首先引入和聲搜索算法策略[9]，通過從記憶庫中學(xué)習(xí)、隨機生成等方式產(chǎn)生初始解及新的備選解，同時構(gòu)造記憶庫，并采用網(wǎng)格法進行更新。在此基礎(chǔ)上引入粒子群算法策略[10-11]，使個體通過信息交換在解空間進行搜索?；诖耍N群可對解空間進行較好的全局搜索和局部搜索，獲得較高的任務(wù)成功率。

1航空器搜尋

對目標為航空器/飛行員的搜尋任務(wù)，其著陸位置范圍通常較大，獲得目標位于特定位置的概率是制訂搜尋方案的必要條件。實際搜救任務(wù)中，目標位于不同區(qū)域的概率可用概率分布圖表示。表1為一航空器位置概率分布圖示例[12]。

在實際搜尋任務(wù)中，搜尋設(shè)施利用一定的探測設(shè)備（如紅外、可見光、雷達等探測設(shè)備）對目標進行探測。為方便搜尋設(shè)施執(zhí)行任務(wù)，搜尋區(qū)域常為矩形，搜尋路線常為等長等距的平行線，搜尋航線與矩形的長邊平行，如圖1所示[12]。航線間距為S，在實際搜尋任務(wù)中由設(shè)施的搜尋能力、掃視寬度等因素決定。航線間距通常大于搜尋設(shè)施的掃視寬度。搜尋設(shè)施的掃視寬度（W）由實際環(huán)境條件（能見度）及目標特征（如尺寸、顏色等）等因素決定。

探測概率是衡量搜尋設(shè)施搜尋能力的一個重要指標。若目標在搜尋設(shè)施掃視范圍內(nèi)，搜尋設(shè)施可成功發(fā)現(xiàn)目標的概率即為探測概率。對任意搜尋設(shè)施，若目標與搜尋設(shè)施的橫向距離x，探測概率pd可用式（1）表示：

2過渡粒子群算法

目標為航空器/飛行員的搜尋任務(wù)，通常具有待搜尋區(qū)域大、任務(wù)時間緊迫等特點。制訂搜尋方案意味著需根據(jù)目標的位置概率信息、環(huán)境狀況、搜尋設(shè)備能力等確定搜尋路線及搜尋速度，使在相應(yīng)的任務(wù)時間內(nèi)成功發(fā)現(xiàn)目標的概率達到最大。應(yīng)用常見的啟發(fā)式優(yōu)化方法解決該問題時，通常會產(chǎn)生算法收斂速度過快而陷入局部最優(yōu)，或算法運行時間過長而降低其適用性[13-15]。針對航空器搜尋問題，本文旨在提出一種改進的群智能算法，在解空間進行有效的全局搜索與局部搜索，使生成的方案同時具有較高的任務(wù)成功率及較短的運行時間。

針對航空器搜尋計劃制訂問題，本文提出一種過渡粒子群算法，旨在利用和聲搜索策略和粒子群搜索策略，使種群進行有效的全局搜索及局部搜索，快速獲得高質(zhì)量的解。過渡粒子群優(yōu)化算法首先構(gòu)造記憶庫，

通過隨機生成備選解存入記憶庫中，同時通過學(xué)習(xí)、隨機生成等策略更新記憶庫。為保證記憶庫中的備選解的多樣性，過渡粒子群算法將解空間分割為多個網(wǎng)格，每個網(wǎng)格僅可能有至多一個備選解保存在記憶庫中，此時記憶庫中的解具有較好的質(zhì)量及多樣性，基于此種群可對解空間進行有效的全局搜索。在記憶庫中備選解所在網(wǎng)格不再變動時，利用粒子群算法策略，將種群重置為記憶庫中的備選解，種群中圍繞具有較高質(zhì)量的備選解展開搜索。利用該策略可使種群具有較高的收斂速度，同時可對解空間進行有效的局部搜索。過渡粒子群算法的詳細闡述如下。

過渡粒子群算法采用網(wǎng)格法對記憶庫進行更新，因此記憶庫中的備選解具有較高的適應(yīng)度值和較好的多樣性。在此基礎(chǔ)上，種群重置為記憶庫中的解，利用粒子群更新策略可有效地對全局最優(yōu)解進行搜索，種群同時具備較快的收斂速度。

綜上所述，應(yīng)用過渡粒子群算法制訂搜尋方案的流程為：

（1）確定搜尋方案各個參數(shù)的上下界，設(shè)定記憶庫規(guī)模及其他參數(shù)，根據(jù)式（4）生成初始記憶庫；

（2）根據(jù)式（5）構(gòu)造新的備選解，利用式（3）計算備選解適應(yīng)度值，利用式（6）更新記憶庫直至記憶庫中備選解所在網(wǎng)格不再發(fā)生變化；

（3）將種群重置為記憶庫中的解；

（4）根據(jù)式（7）、（8）進行迭代計算，更新粒子位置和速度直至算法結(jié)束；

（5）輸出算法所得的搜尋方案及任務(wù)成功率。

3試驗結(jié)果及分析

為檢驗過渡粒子群算法（transition particle swarm optimization， TPSO）的性能，本文將其與粒子群算法（particle swarm optimization，PSO）和聲搜索算法（harmony search， HS）、蝙蝠算法[16]（bat algorithm， BA）共同對航空器搜尋問題進行仿真試驗。

試驗平臺為Matlab 2014。試驗中搜尋目標為航空器。試驗輸入包括探測概率修正系數(shù)、目標的位置信息、任務(wù)時間等。搜尋設(shè)施速度上界為40m/h，概率分布圖的比例尺為1∶200000。搜尋方案的區(qū)域長寬精度為1km，任務(wù)時間為12～24h。試驗輸出即相應(yīng)的搜尋方案，包括搜尋區(qū)域、路線等。為驗證算法的可行性與有效性，除任務(wù)成功率外，考慮實際搜救任務(wù)時間資源寶貴，本文同時給出所提算法與對比算法的運行時間。

試驗中參數(shù)設(shè)置如下：MBS=50，MCR=0.6，種群規(guī)模為100，ω= 0.7。試驗結(jié)果見表2。其中，實際最佳方案成功率為窮舉所有備選解得到的全局最佳搜尋方案相應(yīng)的成功率。針對每個搜尋任務(wù)，每個算法重復(fù)運行20次。表2給出每個算法的任務(wù)成功率均值，該值越接近實際最佳方案成功率，代表算法性能越好。

由表2可知，相較HS、PSO、BA，TPSO獲得的搜尋方案相應(yīng)的任務(wù)成功率均值最高。同時，TPSO的任務(wù)成功率與實際最佳方案的任務(wù)成功率的差距較?。ㄋ@方案與最佳方案成功率的平均差距小于0.01）。除TPSO以外，BA生成的搜尋方案優(yōu)于和聲搜索算法及粒子群算法。TPSO利用相應(yīng)的策略從全局搜索到局部搜索有效過渡，試驗結(jié)果證明該策略的有效性。HS、PSO均存在收斂速度快、種群多樣性降低從而陷入局部最優(yōu)解。BA結(jié)合利用個體對解空間進行較為有效的局部搜索，避免種群多樣性快速下降。相較PSO、HS，BA在航空器搜尋問題上表現(xiàn)更優(yōu)。

從表2中可看出，當概率分布圖較大、任務(wù)時間較長時，所有算法相應(yīng)的成功率均值與實際最佳方案成功率相差較大，且相應(yīng)的方差較大。分析原因為較大的概率分布圖意味著問題具有較高的復(fù)雜程度。從表2可知，針對任務(wù)3，TPSO相應(yīng)的平均任務(wù)成功率為16.4%，與實際最佳方案任務(wù)成功率（17.9%）的差距為1.5%，低于PSO、HS，BA。由此可知針對復(fù)雜度較高的搜尋任務(wù)，TPSO仍可有效生成高質(zhì)量搜尋方案。對每個搜尋任務(wù)，TPSO相應(yīng)的任務(wù)成功率方差最小，表明TPSO具有較好的穩(wěn)定性。

為驗證算法的實用性，表2給出算法針對各個任務(wù)的平均運行時間。BA耗時最短，HS最長。TPSO在種群優(yōu)化過程中，采用網(wǎng)格法更新記憶庫，該步驟較為耗時，TPSO的算法運行時間居中。HS生成新的備選解的策略較復(fù)雜，因而算法運行時間較長。

總的來說，針對航空器搜尋任務(wù)，相較其余幾種算法，TPSO可在較短的運行時間內(nèi)穩(wěn)定地生成高質(zhì)量的搜尋計劃，且隨著問題復(fù)雜程度的上升，TPSO優(yōu)越性更加明顯。因此可知，TPSO在航空器搜尋問題上有較好的適用性。

4結(jié)論

針對航空器搜尋問題，本文提出一種過渡粒子群優(yōu)化算法。過渡粒子群優(yōu)化算法首先通過從記憶庫中學(xué)習(xí)、隨機生成產(chǎn)生新的備選解；其次采用網(wǎng)格法更新記憶庫；最后采用粒子群算法策略，將種群重置為記憶庫中的備選解，使個體通過進行信息交換在解空間中進行搜索，基于此對解空間進行有效的全局與局部搜索。為驗證所提方法有效性，本文在多個航空器搜尋任務(wù)上進行仿真試驗。由試驗結(jié)果可知，過渡粒子群算法可在較短時間內(nèi)生成最佳的搜尋方案，在航空器搜尋問題上具有較好的適用性。

參考文獻

[1]方芳，楊航，李偉，等.一種基于北斗的航空搜救機載指揮系統(tǒng)設(shè)計[J].航空科學(xué)技術(shù)，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]呂進鋒，趙懷慈.基于記憶庫粒子群算法的海上協(xié)作搜尋計劃制定[J].計算機應(yīng)用， 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].控制理論與應(yīng)用，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熵的多目標粒子群優(yōu)化算法[J].軟件學(xué)報， 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參數(shù)優(yōu)化及應(yīng)用[J].計算機應(yīng)用研究， 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]劉勇，賈慶軒，陳鋼，等.基于多目標粒子群優(yōu)化算法的自由漂浮空間機器人負載最大化軌跡優(yōu)化[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]陳志敏，薄煜明，吳盤龍，等.基于自適應(yīng)粒子群優(yōu)化的新型粒子濾波在目標跟蹤中的應(yīng)用[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神經(jīng)網(wǎng)絡(luò)和遺傳算法的超聲速Licher雙翼優(yōu)化設(shè)計研究[J].航空科學(xué)技術(shù)， 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].智能系統(tǒng)學(xué)報， 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）

（責(zé)任編輯王為）

作者簡介

呂進鋒（1990-）女，博士后，講師。主要研究方向：人工智能、模式識別和導(dǎo)航制導(dǎo)。

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