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

呂進鋒 賈曉洪 王明昌

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

關鍵詞：搜尋計劃；粒子群；記憶庫；全局搜索；局部搜索

中圖分類號：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]，使個體通過信息交換在解空間進行搜索?；诖耍N群可對解空間進行較好的全局搜索和局部搜索，獲得較高的任務成功率。

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