呂進鋒，趙懷慈

(1.中國科學院 沈陽自動化研究所，沈陽 110016； 2.中國科學院大學，北京100049； 3.光電信息處理重點實驗室(中國科學院)，沈陽 110016；4.遼寧省圖像理解與視覺計算重點實驗室(中國科學院沈陽自動化研究所)，沈陽 110016)

0 引 言

海上搜尋是海上搜救的重要組成部分，也是軍事領域和民事領域的常見問題。常見的搜尋目標包括：落水人員、航空器/船舶碎片等。海上搜尋任務就目標的運動狀態(tài)可分為靜止目標搜尋和運動目標搜尋。在整個搜尋任務過程中位置基本保持不變的目標可被視為靜止目標。涉及生命救援的海上搜尋任務往往時間緊迫，如對救生筏、落水人員等目標的搜尋；同時，這類目標機動能力弱，在較短時間內(nèi)由環(huán)境因素造成的位移(風、海流作用導致的漂移)可忽略不計。因此，此類任務通常被認為是靜止目標搜尋任務。

多數(shù)海上事故發(fā)生地點和發(fā)生時間都無法準確獲知，目標可能位置范圍往往較大，在任務緊迫時搜尋設施只能選擇部分區(qū)域進行搜尋，因此，海上靜止目標搜尋問題實際為優(yōu)化問題。本文研究目的為針對單個靜止搜尋目標，為多個搜尋設施制定搜尋計劃，使搜尋任務成功率盡可能達到最大。

海上搜尋理論起源于二戰(zhàn)時期[1]，至今已有多個先進的海上搜救系統(tǒng)：如美國海上搜救最優(yōu)規(guī)劃系統(tǒng)(Search and Rescue Optimal Planning System, SAROPS)[2]、英國搜救信息系統(tǒng)(Search and Rescue Information System, SARIS)[3]。SAROPS包含的任務規(guī)劃模塊在獲取目標位置信息基礎上，采用啟發(fā)式方法為搜尋設施制定搜尋計劃并確定搜尋路線。加拿大搜救計劃系統(tǒng)(CANadian Search And Rescue Program, CANSARP)采用Min/Max方法生成搜尋區(qū)域。我國于2014年提出建立“基于北斗的海上搜救系統(tǒng)”，旨在利用北斗導航定位功能，對海上事故進行快速定位和及時救援。

另有代表性的搜救方法有挪威搜救中心的Berger等[4-5]提出的混合整數(shù)規(guī)劃方法(Mixed-Integer linear Programming, MIP)等。該方法可為搜尋設施生成精確的搜尋路徑，但該方法生成的搜尋路徑為不受約束的不規(guī)則路徑，未考慮實際工作環(huán)境，搜尋設施在實際搜尋任務中難以按照其生成的搜尋路徑執(zhí)行搜尋。邢勝偉[6]提出一種凸搜尋區(qū)域剖分算法，將搜尋區(qū)域分割為不同部分，分配給多個搜尋設施，但實際搜救任務往往無法實現(xiàn)對目標所有可能位置范圍進行覆蓋式搜索。鄭宏喆等[7]利用蒙特卡羅法模擬目標漂移軌跡，確定目標位置信息。王光源等[8]對目標漂移模型進行分析，并根據(jù)搜尋誤差和搜尋安全系數(shù)進一步確定搜尋區(qū)域，其研究并未涉及為具體搜尋設施制定搜尋方案。

海上搜尋計劃制定的主要難點在于目標可能位置范圍較大，同時需考慮參與搜尋任務的搜尋設施之間的協(xié)作、沖突問題，影響任務成功率的因素較多且相互影響，因此搜尋計劃制定是較復雜的優(yōu)化問題，快速有效地為搜尋設施制定協(xié)作搜尋方案具有較大的難度。

啟發(fā)式優(yōu)化方法在多類任務規(guī)劃問題上得到成功的應用，如劉勇等[9]將混沌粒子群算法應用于空間機器人軌跡優(yōu)化，李潔等[10]將和聲搜索算法應用于網(wǎng)絡安全態(tài)勢預測問題。粒子群算法由于其需要調(diào)節(jié)的參數(shù)較少、容易實現(xiàn)等優(yōu)點得到了大量學者的關(guān)注。粒子群等啟發(fā)式優(yōu)化算法能夠很好地利用種群對復雜解空間進行探測，實現(xiàn)對復雜問題的試探性求解。其不足通常表現(xiàn)為易陷入局部最優(yōu)解，無法保證最終所得解的質(zhì)量。常見的改進策略包括增加或改變種群進化方式，增加約束條件降低種群多樣性下降速度等。這類方法在一定程度上可有效提高算法性能。文獻[11]提出一種帶動態(tài)實例學習能力的粒子群優(yōu)化算法并將其應用于永磁同步電機(Permanent Magnet Synchronous Motor, PMSM)驅(qū)動系統(tǒng)參數(shù)估計，該算法可有效平衡種群全局探測能力和局部精細搜索能力。文獻[12-13]分別引入基于高斯的動態(tài)反向?qū)W習策略和基于混沌邏輯的受體編輯策略使種群能夠有效跳出局部最優(yōu)。

針對海上靜止目標搜尋問題，本文提出一種記憶庫粒子群算法為搜尋設施制定協(xié)作搜尋計劃。記憶庫粒子群算法首先假設僅需為單個搜尋設施制定搜尋計劃，通過借鑒和聲搜索算法策略[14]，從記憶庫中學習、隨機生成產(chǎn)生新的備選解；同時采用網(wǎng)格法構(gòu)造記憶庫并進行更新，旨在使新的備選解同時有較好的質(zhì)量和多樣性。此過程可認為對解空間進行有效的全局搜索。最后，在記憶庫穩(wěn)定時，從記憶庫中隨機選擇多個備選解組合成為所有搜尋設施的初始搜尋方案，采用粒子群算法策略[15-16]，粒子通過信息交換在解空間中進一步搜索最優(yōu)解，最終生成高質(zhì)量的搜尋計劃。

1 海上靜止目標搜尋

搜尋設施在獲取目標位置信息的基礎上制定計劃展開搜尋。海上事故發(fā)生后，目標通常會離開事故發(fā)生位置。如航空器爆炸后飛行員會棄機跳傘逃生。搜尋設施需首先分析目標可能所在位置。實際搜尋任務中，事故位置及時間通常無法確定。飛行員在跳傘過程中會受高空風作用產(chǎn)生空中漂移，而現(xiàn)有技術(shù)手段無法獲取足夠精確的風場數(shù)據(jù)。搜尋設施通過估計相應參數(shù)可能范圍來計算目標所在位置及相應概率。目標可能位置通常范圍較大(可達104km2)，位于不同位置的概率也不同。目標位置信息通常用概率分布圖(probability map)表示。概率分布圖為柵格化的海圖，柵格的灰度(數(shù)字)反映了目標位于相應海上區(qū)域的概率。靜止目標在搜尋任務中位置信息保持不變，即相應的概率分布圖保持不變。圖1為一搜尋目標概率分布圖示例[17]。圖中橢圓區(qū)域表示目標可能位置范圍，橢圓內(nèi)柵格的灰度反映目標位于該區(qū)域的概率。柵格灰度值越大，目標位于相應區(qū)域的概率越小。

圖1 概率分布圖示例

搜尋設施對一廣闊區(qū)域進行搜尋時，通常使用平行線搜尋方式，如圖2所示[18]。搜尋區(qū)域通常為規(guī)則矩形，每條搜尋航線與矩形的長邊平行，航線間距為S，由搜尋設施的續(xù)航能力、掃視寬度及實際搜尋環(huán)境決定。航線間距通常大于搜尋設施的掃視寬度。為避免航線沖突和資源浪費，不同的搜尋設施需在不同的分區(qū)內(nèi)進行搜尋。

圖2 平行線搜尋方式

搜尋掃視寬度(W)指搜尋設施利用視力或電子探測設備對一地區(qū)進行掃視的有效距離寬度，是發(fā)現(xiàn)目標能力的一種衡量。不同搜尋設施的理論掃視寬度值(Wu)可通過查表獲得。實際任務中的掃視寬度需根據(jù)客觀環(huán)境對理論值進行修正。實際掃視寬度計算公式為W=Wu×hw，其中hw為修正系數(shù)。

搜尋設施在執(zhí)行搜尋任務時，天氣情況對探測設備的影響很大。發(fā)現(xiàn)概率(探測概率)是衡量搜尋設施探測能力的指標。搜尋設施在不同的天氣條件下發(fā)現(xiàn)目標的概率有很大差別。若目標在搜尋設施的掃視范圍內(nèi)，與搜尋設施距離為d，則搜尋設施的探測概率pd(probability of detection)通?？捎檬?1)表示：

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

(1)

其中：a，b為探測概率修正系數(shù)，a，b由探測設備屬性、搜尋速度、環(huán)境條件、目標尺寸等因素決定，00。W為搜尋設施的掃視寬度。

海上搜尋的目的是充分利用現(xiàn)有資源(物質(zhì)資源、時間資源)最大化任務成功率。對特定搜尋設施，需考慮其搜尋能力及搜尋模式，根據(jù)目標的概率分布圖確定搜尋區(qū)域，制定搜尋路線，使搜尋設施在任務時間內(nèi)成功發(fā)現(xiàn)目標的可能性達到最大。

對實際海上搜尋任務，若一搜尋設施在區(qū)域X內(nèi)進行搜尋，可得任務成功率(Possibility of success, Pos)為：

(2)

其中：(x,y)為X區(qū)域內(nèi)的位置，pc(x,y)表示目標位于位置(x,y) 的概率，pd(x,y) 表示搜尋設施對位置(x,y)的探測概率，即若目標位于位置(x,y)，搜尋設施可成功發(fā)現(xiàn)目標的概率。

對整個搜尋任務，當區(qū)域R被兩個搜尋設施A，B重復搜尋，則可獲得任務成功率為：

(3)

若單個搜尋設施在任務時間T內(nèi)對矩形區(qū)域進行搜尋，則相應的搜尋路線可用七維向量表示：P=(p1,p2,p3,p4,p5,p6,p7)。其中：p1、p2分別確定矩形搜尋區(qū)域的中心位置的橫縱坐標；p3、p4分別表示矩形區(qū)域的長與寬；p5表示矩形區(qū)域相對于水平方向的傾斜方向；p6表示搜尋速度；p7表示搜尋起始點，為矩形四個頂點之一，搜尋航線的間距可通過 (p6×T)/p3求得。

在海上搜尋任務中，評價搜尋計劃優(yōu)劣的指標即該計劃對應的任務成功率。若有n個搜尋設施，協(xié)作搜尋計劃可表示為：C=(P1,P2,…,Pn)，其中，Pi為第i個搜尋設施的計劃。所有搜尋設施的搜尋區(qū)域集合為CS，CS中的子區(qū)域可分為兩類：{X1,X2, …,Xm}，{R1,R2, …,Rk}，其中m,k∈N。Xi被單個搜尋設施搜尋，Rj被多個搜尋設施搜尋，1≤i≤m，1≤j≤k，則評價該協(xié)作方案優(yōu)劣的適應度函數(shù)f定義如下：

(4)

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

2 記憶庫粒子群算法

由問題特性決定，大多數(shù)海上搜尋目標的概率分布圖呈現(xiàn)為不規(guī)則狀態(tài)，影響任務成功率的因素較多，多數(shù)情況下海上協(xié)作搜尋計劃制定問題相應的解空間為復雜的高維、多峰形態(tài)。大多數(shù)啟發(fā)式優(yōu)化算法用來求解多峰函數(shù)優(yōu)化問題時常見的不足為收斂速度過高，隨著迭代次數(shù)的增加喪失多樣性，從而陷入局部最優(yōu)解[19]。常見的策略是擴大種群規(guī)模，降低搜索步長，這種做法往往造成運行時間增加，導致算法可行性降低。實際海上搜尋任務時間資源寶貴，要求算法為搜尋設施快速制定高質(zhì)量的搜尋計劃。針對海上靜止目標協(xié)作搜尋問題，本文提出一種記憶庫粒子群算法。

當搜尋設施數(shù)量較多，則協(xié)作搜尋方案維度較高(每個搜尋設施的方案用七維向量表示)。直接初始化隨機生成協(xié)作搜尋方案后進行迭代尋優(yōu)的復雜度較大，且多數(shù)啟發(fā)式優(yōu)化算法生成最終解的質(zhì)量很大程度上依賴于初始解質(zhì)量。由式(3)可知，對海上協(xié)作搜尋問題，多個搜尋設施對同一區(qū)域重復搜尋獲得的成功率通常小于對不同區(qū)域分別搜尋獲得的成功率。因此記憶庫粒子群優(yōu)化算法首先假設只有一個搜尋設施，為單個搜尋設施生成多個較好且差異較大的備選方案，在此基礎上從備選方案中隨機組合生成協(xié)作搜尋方案。此時各個搜尋設施的方案差異較大，因此組合生成的協(xié)作方案對比隨機生成的協(xié)作方案有更高質(zhì)量。在此基礎上利用一定策略進行迭代尋優(yōu)，生成最終的協(xié)作搜尋計劃。利用該方法可快速有效地為多個搜尋設施制定高質(zhì)量的協(xié)作搜尋計劃。

記憶庫粒子群為單個搜尋設施生成搜尋計劃時借鑒和聲搜索算法策略，即建立記憶庫(Memory Bank, MB)，通過從記憶庫中學習、隨機生成產(chǎn)生新的備選解。其次采用網(wǎng)格法對記憶庫進行更新，即將解空間分割為多個子區(qū)域，每個子區(qū)域僅可能有至多一個備選解保存在記憶庫中，采用網(wǎng)格法更新記憶庫旨在使記憶庫中的備選解有較好質(zhì)量的同時有較好的多樣性。最后，在記憶庫穩(wěn)定時，從記憶庫中隨機選擇備選解組合成所有搜尋設施的協(xié)作搜尋方案。利用粒子群算法策略，個體通過進行信息交換在解空間中對全局最優(yōu)解展開搜索。粒子群算法具有較高的收斂速度，對連續(xù)函數(shù)的優(yōu)化有很好的適用性，種群可利用該策略圍繞較好質(zhì)量的解進行局部搜索。記憶庫粒子群算法的詳細闡述如下。

假設需為單個搜尋設施制定搜尋計劃時，將問題空間映射至算法空間后，相應的解空間中的任一點均代表一個備選解，即問題的備選方案。對D維解空間，任一備選解可由D維向量表示，即Y=(y1,y2,…,yD)。為單個搜尋設施制定搜尋計劃，解空間為7維。各維參量的取值范圍由實際問題決定。評價備選方案優(yōu)劣的適應度函數(shù)如式(2)所示。記憶庫粒子群算法首先將解空間分割為多個等大的網(wǎng)格(當解空間為高維時，解空間被分割為多個等大的超立方體)，確定記憶庫規(guī)模(Memory Bank Scale, MBS)，隨機生成MBS個點填充到記憶庫中。記憶庫的結(jié)構(gòu)為矩陣。對D維解空間，相應記憶庫MB可表示為式(5):

(5)

其中：Y表示D維的備選解，MBS為記憶庫的大小，f為評價備選解的適應度函數(shù)，由式(2)表示。

記憶庫粒子群算法通過兩種方式產(chǎn)生新的備選解：從記憶庫中學習、隨機生成。對任一新的備選解，首先生成在0和1之間均勻分布的隨機數(shù)z1，若z1小于記憶庫取值概率(Memory Considering Rate, MCR)，則從記憶庫中隨機選擇相應的參數(shù)作為該備選解的各維參數(shù)；否則，隨機生成該備選解的各維參數(shù)。新的備選解Ynew各維參數(shù)的生成策略如下：

(6)

其中：MCR為記憶庫取值概率，Li是第i維參數(shù)的取值空間。此階段旨在生成差異較大的備選解，因此，MCR取值較小。

當新的備選解生成以后，適應度函數(shù)f對新的備選解進行評價。假設新的備選解Ynew位于解空間中的網(wǎng)格G中，記憶庫中的任意備選解Yi均不在網(wǎng)格G中，則若新的備選解優(yōu)于記憶庫中最差的備選解Yw，那么就用新的備選解取代記憶庫中最差的備選解；若記憶庫中已存在備選解Yi位于網(wǎng)格G中，且新的備選解優(yōu)于該解，則將新的備選解取代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是記憶庫中適應度值最小的備選解。

當記憶庫中備選解所在網(wǎng)格不再發(fā)生變化時，記憶庫粒子群算法在記憶庫的基礎上生成協(xié)作搜尋計劃并迭代尋優(yōu)。對n個搜尋設施，任一協(xié)作搜尋方案C=(P1,P2,…,Pn)，Pi為第i個搜尋設施的計劃。

Pi=rand{Yj}

(8)

其中Yj∈MB。

粒子個數(shù)為N，則初始化生成N個協(xié)作方案，每個粒子為7n維向量，n為搜尋設施數(shù)量。初始化生成協(xié)作搜尋計劃后，記憶庫粒子群算法利用種群對全局最優(yōu)解展開搜索。評價粒子質(zhì)量的適應度函數(shù)如式(4)所示。種群中個體按以下策略更新其位置及速度：

(9)

(10)

記憶庫粒子群算法使個體之間通過進行信息交換，圍繞高質(zhì)量的備選解側(cè)重于局部搜索。由于初始協(xié)作搜尋方案為記憶庫中的備選解組合，記憶庫采用網(wǎng)格法進行更新，因此可認為初始協(xié)作搜尋方案均具有較高的適應度值。此過程可被視為對解空間進行有效的全局搜索。在此基礎上，記憶庫粒子群算法借鑒粒子群算法更新策略，可有效地圍繞高質(zhì)量的備選解進行有效的局部搜索。

綜上所述，應用記憶庫粒子群算法制定海上協(xié)作搜尋計劃的主要步驟為：首先假設僅存在單個搜尋設施，確定相應參數(shù)取值范圍，生成記憶庫；其次通過從記憶庫中學習或隨機生成兩種策略生成新的備選解，采用網(wǎng)格法更新記憶庫；最后組合記憶庫中的備選解生成初始協(xié)作搜尋計劃，并采用粒子群策略更新協(xié)作搜尋計劃。記憶庫粒子群算法的流程如圖3所示。

圖3 記憶庫粒子群算法流程

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

為檢驗記憶庫粒子群優(yōu)化(Memory Bank Particle Swarm Optimization, MBPSO)算法的性能，本文將其與和聲搜索算法(Harmony Search, HS)、粒子群優(yōu)化(Particle Swarm Optimization, PSO)算法、蝙蝠算法(Bat Algorithm, BA)[20]共同對海上靜止目標協(xié)作搜尋問題進行仿真實驗。

實驗環(huán)境為Windows 7 32 b，CPU 為Pentium Dual-core 2.70 GHz，內(nèi)存為2.0 GB，Matlab 2014。實驗輸入包括靜止目標的概率分布圖、任務時間、搜尋設施數(shù)量及能力等。所有任務的搜尋目標是落水的飛行員，搜尋設施均是續(xù)航能力超過72 h的船舶。搜尋設施的航行速度最大可達為50n mile/h(1n mile=1.852 km)。概率分布圖的比例尺為1∶200 000。搜尋方案的區(qū)域長寬精度為1 km，任務時間為24 h，搜尋設施數(shù)量從3～5不等。實驗輸出為協(xié)作搜尋方案，包括各個搜尋設施的搜尋區(qū)域、搜尋路線及總的任務成功率。在實際應用中，算法的運行時間往往是決定算法實用性的一個重要指標，因此，除任務成功率外，本文從算法的運行時間方面對所提方法與其余幾種算法進行比較，以驗證算法的可行性與有效性。

在所有實驗中，記憶庫大小為100，MCR取值為0.7，種群規(guī)模為150，ω取值為0.7。仿真實驗結(jié)果如表1所示。其中，實際最佳方案成功率為窮舉所有備選解得到的全局最優(yōu)解代表的搜尋計劃的成功率。針對每個搜尋任務，每個算法重復運行20次。每個算法的任務成功率均值即該算法所對應的20個任務成功率的平均值。對每個算法，其任務成功率均值越接近實際最佳方案成功率，代表該算法性能越好。

由以上實驗結(jié)果可知，相較于其他幾種算法，記憶庫粒子群算法獲得的搜尋方案最佳，相應的任務成功率均值最高。同時，記憶庫粒子群算法的任務成功率與實際最佳方案的任務成功率的差距較小。由此可知，記憶庫粒子群算法能為搜尋設施生成高質(zhì)量的協(xié)作搜尋方案。除記憶庫粒子群算法以外，蝙蝠算法生成的搜尋方案優(yōu)于其余幾種算法，和聲搜索算法生成的搜尋方案與粒子群算法生成的方案質(zhì)量相當。記憶庫粒子群算法在生成單個搜尋設施的搜尋計劃的基礎上，組合生成協(xié)作搜尋計劃，網(wǎng)格法更新記憶庫策略使初始協(xié)作計劃有較好的質(zhì)量和多樣性，對解空間進行有效的全局搜索，在此基礎上粒子之間通過信息交流圍繞較高質(zhì)量的解展開搜索，進行有效的局部搜索，實驗結(jié)果證明該策略一定程度上有效避免種群陷入局部最優(yōu)，從而可生成質(zhì)量更好的解。和聲搜索算法、粒子群算法均會由于問題維度高、種群收斂速度高、種群多樣性降低等因素陷入局部最優(yōu)解，從而生成的搜尋方案質(zhì)量較差。蝙蝠算法一定程度上結(jié)合粒子群搜索策略和局部搜索策略，較為有效地避免種群由于快速收斂而陷入局部最優(yōu)解。因此，相較于粒子群算法、和聲搜索算法，蝙蝠算法在海上搜尋問題上表現(xiàn)更優(yōu)。

表1 平均任務成功率及運行時間對比

所有算法生成的搜尋方案質(zhì)量會隨問題復雜程度的上升而下降。在表1中表現(xiàn)為當搜尋設施數(shù)量較多時，所有算法相應的任務成功率與實際最佳方案任務成功率的差距較大。這主要是由于搜尋設施數(shù)量越多，相應解空間維度越高，問題往往具有較高的復雜程度。從表1中可知，針對任務三，搜尋設施為5個時，記憶庫粒子群算法生成的協(xié)作搜尋方案平均任務成功率為36%，與實際最佳方案任務成功率(40%)的差距為4%，而其余幾種算法的搜尋方案與實際最佳方案任務成功率的差距在6%以上(和聲搜索算法相應的差距為8%)。由此可知相較于其余幾種算法，針對復雜度較高的搜尋任務，記憶庫粒子群算法仍可穩(wěn)定地生成的高質(zhì)量搜尋方案。針對每個搜尋任務，每個算法均重復運行20次，統(tǒng)計實驗結(jié)果可知，記憶庫粒子群算法相應的任務成功率方差最小，進一步驗證了記憶庫粒子群算法的穩(wěn)定性。

就算法運行時間來看，蝙蝠算法的運行時間最短，和聲搜索算法運行時間最長，記憶庫粒子群算法的運行時間居中。經(jīng)分析可知，記憶庫粒子群算法采用網(wǎng)格法更新記憶庫的策略在一定程度上耗費了時間。蝙蝠算法的更新策略相對較簡單，運行速度最高。和聲搜索算法生成新的備選解的策略較復雜，因而算法運行時間較長。

圖4為對三個搜尋任務進行實驗相應的收斂曲線。從圖中可以看出：和聲搜索算法和粒子群算法的收斂速度最高，但其相應的適應度值較低，可知這兩種算法較容易陷入局部最優(yōu)；蝙蝠算法收斂速度較低，同時可獲得較好的適應度值；記憶庫粒子群算法收斂速度居中，相應的適應度值最高。

分析實驗結(jié)果可知，記憶庫中保存的備選解有較高的適應度值，且備選解之間差異性較大(在解空間中距離較大)。引入記憶庫策略使種群首先在整個解空間進行有效的全局搜索，在此基礎上粒子通過與其他個體進行信息交換，圍繞質(zhì)量較好的解進行有效的局部搜索，基于此種群可實現(xiàn)從全局搜索向局部搜索過渡，種群多樣性下降速度較低，從而避免種群陷入局部最優(yōu)解。

總的來說，記憶庫粒子群算法可以在較短的時間內(nèi)為搜尋設施制定有效的協(xié)作搜尋計劃，在海上搜尋問題上有較好的適用性。

圖4 四種算法收斂曲線

4 結(jié)語

針對海上靜止目標搜尋問題，本文提出一種記憶庫粒子群優(yōu)化算法，旨在快速有效地為搜尋設施制定高質(zhì)量的協(xié)作搜尋計劃。記憶庫粒子群優(yōu)化算法首先假設僅需為單個搜尋設施制定搜尋方案，通過從記憶庫中學習、隨機生成產(chǎn)生新的備選解；其次采用網(wǎng)格法更新記憶庫，對解空間進行較好的全局搜索；最后利用記憶庫中的備選解組合生成協(xié)作搜尋計劃，使初始協(xié)作方案同時有較好的多樣性和質(zhì)量，最后采用粒子群算法策略，個體之間通過進行信息交換圍繞質(zhì)量較好的解展開搜索。記憶庫粒子群算法有效利用組合優(yōu)化策略和連續(xù)優(yōu)化策略，記憶庫的引入使種群能夠首先進行有效的全局搜索，在此基礎上利用粒子群策略可使種群圍繞質(zhì)量較高的解進行有效的局部搜索，同時種群多樣性下降速度較低。本文在多個協(xié)作搜尋任務上對所提算法進行實驗驗證。實驗結(jié)果表明相較于其余幾種算法，記憶庫粒子群算法可快速穩(wěn)定地生成具有更高任務成功率的協(xié)作搜尋方案。