基于記憶庫粒子群算法的海上協(xié)作搜尋計劃制定

呂進鋒，趙懷慈

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

0 引 言

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

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

海上搜尋理論起源于二戰(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包含的任務(wù)規(guī)劃模塊在獲取目標(biāo)位置信息基礎(chǔ)上，采用啟發(fā)式方法為搜尋設(shè)施制定搜尋計劃并確定搜尋路線。加拿大搜救計劃系統(tǒng)(CANadian Search And Rescue Program, CANSARP)采用Min/Max方法生成搜尋區(qū)域。我國于2014年提出建立“基于北斗的海上搜救系統(tǒng)”，旨在利用北斗導(dǎo)航定位功能，對海上事故進行快速定位和及時救援。

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

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

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

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

1 海上靜止目標(biāo)搜尋

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

圖1 概率分布圖示例

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

圖2 平行線搜尋方式

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

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

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

(1)

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

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

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

(2)

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

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

(3)

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

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

(4)

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

2 記憶庫粒子群算法

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

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

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

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

(5)

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

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

(6)

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

當(dāng)新的備選解生成以后，適應(yīng)度函數(shù)f對新的備選解進行評價。假設(shè)新的備選解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是記憶庫中適應(yīng)度值最小的備選解。

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

Pi=rand{Yj}

(8)

其中Yj∈MB。

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

(9)

(10)

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

綜上所述，應(yīng)用記憶庫粒子群算法制定海上協(xié)作搜尋計劃的主要步驟為：首先假設(shè)僅存在單個搜尋設(shè)施，確定相應(yīng)參數(shù)取值范圍，生成記憶庫；其次通過從記憶庫中學(xué)習(xí)或隨機生成兩種策略生成新的備選解，采用網(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]共同對海上靜止目標(biāo)協(xié)作搜尋問題進行仿真實驗。

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

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

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

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

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

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

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

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

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

圖4 四種算法收斂曲線

4 結(jié)語

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