用于UAV運動目標(biāo)搜索的自適應(yīng)粒子群算法

楊鴻光，張宇輝，魏文紅

東莞理工學(xué)院 計算機科學(xué)與技術(shù)學(xué)院，廣東 東莞 523808

近年來，無人機（unmanned aerial vehicle，UAV）的低成本、便攜性等特性使得其在攝影、勘探、巡檢等許多場景中有著廣泛應(yīng)用，特別是在搜索和救援這些尋找動態(tài)目標(biāo)的任務(wù)[1]。值得注意的是，在事故發(fā)生后的最初72小時內(nèi)是搜索救援的“黃金時間”，在這期間找到目標(biāo)的概率是最大的，是營救目標(biāo)最關(guān)鍵的時間，在這之后的概率會由于各種因素而變得越來越小[2]。因此，無人機路徑規(guī)劃在搜索運動目標(biāo)的任務(wù)中至關(guān)重要。找到一條最大化檢測概率的無人機路徑，有助于提升目標(biāo)搜尋任務(wù)的成功率。

許多元啟發(fā)式算法由于其可以有效解決動態(tài)約束問題，能夠在復(fù)雜場景中找到全局最優(yōu)解的能力，而被廣泛應(yīng)用于路徑規(guī)劃中。這些啟發(fā)式算法可以有效地對動態(tài)目標(biāo)進行路徑規(guī)劃，例如粒子群優(yōu)化算法（particle swarm optimization，PSO）[3]、人工蜂群算法（artificial bee colony，ABC）[4]、蟻群算法（ant colony optimization，ACO）[5]、遺傳算法（genetic algorithm，GA）[6]、差分進化算法（differential evolution，DE）[7]、樹種算法（tree-seed algorithm，TSA）[8]、鯨魚優(yōu)化算法（whale optimization algorithm，WOA）[9]，和其他可用于路徑規(guī)劃的新型智能優(yōu)化算法[10]。其中，由于PSO 算法十分簡單有效，并且計算量小，得到了廣泛使用，并涌現(xiàn)出了許多改進措施。

PSO算法[3]是由Eberhart和Kennedy于1995年提出的全局隨機搜索算法，是進化計算的一個重要分支。PSO 模擬自然界鳥類活動，具有“自我認知”和“全局認知”兩個群體智能特性。自我認知表示粒子自身經(jīng)驗的影響，全局認知表示粒子之間的信息共享與協(xié)作，從而各個粒子能利用個體認知和社會引導(dǎo)來搜索到全局最優(yōu)解。同時，PSO 對初始條件和目標(biāo)函數(shù)都不太敏感，僅通過一個慣性權(quán)重和兩個加速因子就能適用于各種環(huán)境，在較短的計算時間內(nèi)找到能穩(wěn)定收斂的全局解。簡單高效的PSO 使其被廣泛應(yīng)用于無人機路徑規(guī)劃中，并產(chǎn)生了基于編碼方式的改進，基于參數(shù)的改進，基于變異機制的改進，混合其他算法的改進等多種變體[11]，如經(jīng)典粒子群算法[3]、運動編碼粒子群算法（motionencoded PSO，MPSO）[12]、角度編碼粒子群算法（phase angle-encoded PSO，θ-PSO）[13]、量子行為粒子群算法（quantum-behaved PSO，QPSO）[14]。PSO 將無人機搜索路徑編碼為笛卡爾空間的一組節(jié)點；MPSO采用包含大小和方向的運動段代替節(jié)點，將搜索路徑表示為一組運動段；θ-PSO用代表路徑出現(xiàn)方向的相位角編碼粒子位置，將n個節(jié)點的搜索路徑表示為2n個角度的向量；QPSO 假設(shè)粒子具有量子行為，對粒子的編碼方式與PSO 類同，即其搜索路徑也是一組坐標(biāo)節(jié)點。其中，MPSO 和θ-PSO 的更新方程與PSO 類似，但QPSO 采用了一個新的隨機更新方程。這些變體對粒子編碼的形式不一，故在相同的約束及目標(biāo)函數(shù)下可能會產(chǎn)生不同的解。在不同的場景中比較這些變體哪些更加適應(yīng)于無人機的路徑規(guī)劃，能產(chǎn)生更大概率的運動目標(biāo)搜索路徑，具有重要的研究意義。

已有的文獻結(jié)果表明MPSO 在各種搜索場景中性能卓越[12]，但有時候MPSO會被兩個不同概率的區(qū)域混淆，不能識別到概率最大的正確目標(biāo)區(qū)域。θ-PSO 與MPSO面臨著相同的困境。PSO無法保持粒子動量，故不能很好地應(yīng)用于路徑規(guī)劃中。QPSO 在實際應(yīng)用中不可避免地會陷入局部最優(yōu)[15]。

受MPSO 算法思想的啟發(fā)，本文針對MPSO 算法進行了改進，提出了帶有自適應(yīng)學(xué)習(xí)策略的運動編碼粒子群算法（motion-coded PSO with adaptive learning strategy，MPSO-ALS），在保證識別到概率最大的目標(biāo)區(qū)域，不被較低概率目標(biāo)區(qū)域吸引的前提下，獲得更大搜索概率的路徑，提升性能。本文的主要貢獻如下：（1）設(shè)計了新的初始化方法，從而確保能識別到概率較高的正確目標(biāo)區(qū)域；（2）融合了子群動態(tài)劃分策略和自適應(yīng)學(xué)習(xí)策略，在保證收斂速度的同時，收斂到概率更高的路徑；（3）改進了針對不同類型粒子的更新方程，更好地適應(yīng)路徑規(guī)劃中子群粒子的學(xué)習(xí)策略，提高搜索概率。

1 目標(biāo)函數(shù)

本章主要介紹目標(biāo)函數(shù)。目標(biāo)函數(shù)通過對目標(biāo)、傳感器和信念圖建模來表示[12]，具體內(nèi)容如下。

1.1 目標(biāo)模型

在搜索問題中，由未知變量x∈X來描述目標(biāo)位置，基于可用信息（目標(biāo)丟失信號前的最后已知位置）采用概率分布函數(shù)對目標(biāo)位置進行建模，概率分布采用以最后已知位置為中心的正態(tài)分布。由網(wǎng)格圖形式的信念圖b(x0)來表示概率分布圖，信念圖中的每個單元格的值與目標(biāo)在該單元格中的概率一一對應(yīng)。最后將搜索空間S離散化，劃分成由Sr×SC個單元格組成的網(wǎng)格，并將目標(biāo)在該單元格的概率與每個單元格相關(guān)聯(lián)，即可創(chuàng)建搜索圖。對于目標(biāo)所在的搜索圖，有

在搜索過程中，目標(biāo)以一定的模式移動，以馬爾科夫過程來對該隨機過程建模，在條件確定性目標(biāo)的特殊情況下，該模式僅取決于目標(biāo)的初始位置x0。在這種情況下，表示目標(biāo)從單元格xt-1到xt的概率由轉(zhuǎn)移函數(shù)p(xt|xt-1)表示，該轉(zhuǎn)移函數(shù)對于所有單元格xt∈S都是已知的。因此，如果目標(biāo)的初始位置已知，則該目標(biāo)的移動路徑就將完全已知。

1.2 傳感器模型

通過在無人機上安裝傳感器，可以尋找和發(fā)現(xiàn)目標(biāo)。在每個時間步長t進行一次觀測zt，每次觀測互不影響。每次觀察只有兩個結(jié)果，檢測到目標(biāo)zt=Dt，或未檢測到目標(biāo)，Dt表示在時刻t的檢測事件。但由于傳感器和檢測算法的不完善性，觀測到目標(biāo)zt=Dt并不能確保目標(biāo)一定存在于xt處。給定傳感器模型知識，目標(biāo)存在于xt處的可能性可由觀測概率p(Zt|Xt)反映出來。故在給定目標(biāo)位置xt的情況下，未檢測到目標(biāo)的概率由公式（1）所示：

1.3 信念圖更新

當(dāng)初始分布b(x0)初始化后，傳感器就能夠基于貝葉斯方法和觀察序列z1:t={z1,z2,…,zt}，產(chǎn)生目標(biāo)在t時的信念圖b(xt)。這通過預(yù)測和更新兩個階段遞歸進行。

預(yù)測時，信念圖根據(jù)目標(biāo)運動模型隨時間傳播。假設(shè)之前的信念圖b(xt-1)在t時可用，則預(yù)測信念圖可由公式（2）計算：

其中，信念圖b(xt-1)實際上是目標(biāo)在從時間1 觀察到t-1時，目標(biāo)在xt-1的條件概率，即b(xt-1)=p(xt-1|z1:t-1)。

對信念圖的更新，只需當(dāng)觀測值zt可用時，將預(yù)測的信念圖乘以新的條件觀測概率即可，更新信念圖可由公式（3）計算：

其中，ηt是歸一化因子，將目標(biāo)出現(xiàn)在搜索區(qū)域內(nèi)的概率縮放為1，即，ηt由公式（4）表示：

1.4 搜索問題的目標(biāo)函數(shù)

根據(jù)貝葉斯理論，目標(biāo)在t時未被檢測到的概率取決于兩個因素：（1）公式（2）得到的最新預(yù)測信念圖；（2）公式（1）得到的目標(biāo)未被檢測到的概率。針對整個搜索區(qū)域，該概率可由公式（5）表示：

由公式（5）可知，rt是公式（4）歸一化因子的倒數(shù)，即rt=1/ηt（對于未被檢測到的事件，），故rt小于1。

通過將未被檢測到的概率rt隨時間相乘，可以得到從時間1到t時未能檢測到目標(biāo)的聯(lián)合概率該概率如公式（6）所示：

由公式（5）和公式（6）可得目標(biāo)在t時第一次被檢測到的概率，如公式（7）所示：

對公式（7）中的pt隨時間t求和，可得到在時間1到t檢測到目標(biāo)的累積概率，如公式（8）所示：

值得注意的是，累積概率和公式（6）從時間1到t時未能檢測到目標(biāo)的聯(lián)合概率Rt有如下公式（9）的關(guān)系：

同時，隨著時間t增加，由于在之前的搜索步驟中檢測到目標(biāo)的機會增大了，故第一次檢測到目標(biāo)的概率pt會變小。由此可得累積概率Pt有界，并且隨時間t趨于無窮時向1增加。

綜上，搜索問題的目標(biāo)函數(shù)可以由給定有限搜索時間的公式（8）或公式（9）的累積概率Pt表示。假設(shè)搜索時間為{1,2,…,N}，搜索策略的目標(biāo)是確定一條可以最大化累積概率Pt的搜索路徑O=(o1,o2,…,oN)，則目標(biāo)函數(shù)可由公式（10）表示：

2 算法背景

本章主要介紹PSO和MPSO的主要步驟，具體內(nèi)容如下。

2.1 粒子群算法

PSO 算法[3]是一種基于群體智能的隨機優(yōu)化方法。在PSO 中，粒子群模擬鳥群行為在搜索空間中探索（全局搜索）和開發(fā)（局部搜索），最終找到全局最優(yōu)解。粒子的速度和位置更新方程如公式（11）、公式（12）所示：

其中，k表示第k代，lbk是自身歷史最優(yōu)位置，gbk是群體最佳位置，ω是慣性權(quán)重，c1和c2分別是個體認知系數(shù)和社會引導(dǎo)系數(shù)，r1和r2是從[0，1]內(nèi)采樣的兩個均勻概率分布的隨機序列。

2.2 運動編碼粒子群算法

運動編碼粒子群算法MPSO[12]保留了PSO的更新機制，但相對于笛卡爾空間，MPSO允許粒子在運動空間中搜索，將粒子移動限制在其相鄰單元，從而保證路徑中相鄰節(jié)點之間的距離在無人機移動能力范圍內(nèi)，保持路徑節(jié)點的可達性，使得每一代進化后的路徑總是有效的。

MPSO 將每條搜索路徑視為一組無人機運動段，若定義t時某運動段的大小和方向分別為ρt和αt，該運動段則為ut=(ρt,αt)，從而搜索路徑為向量集Uk=(uk,1,uk,2,…,uk,N)。使用Uk作為每個粒子的位置，則MPSO的更新方程如公式（13）和公式（14）所示：

其中，ω、c1、c2、r1、r2的作用與PSO 算法中的一致，LBk=(lbk,1,lbk,2,…,lbk,N)和GBk=(gbk,1,gbk,2,…,gbk,N)分別是第k代時某個粒子的自身歷史最優(yōu)和全局最優(yōu)位置向量集。圖1給出了具有三個運動段的路徑示例，其中，信念圖將概率值用顏色編碼并顯示在右邊。

圖1 具有三個運動段的運動編碼路徑Fig.1 Motion coded paths with three motion segments

在搜索過程中，為了評估與路徑Uk相關(guān)的成本，需要將路徑從運動空間映射到笛卡爾空間。如圖1所示，映射過程通過將每條無人機路徑的每個運動段約束到其8個鄰居之一來執(zhí)行，從而t時的運動幅度ρt可以歸一化且運動角度αt可以量化，如公式（15）和公式（16）所示：

通過公式（16）可以得到相對應(yīng)于運動空間坐標(biāo)的笛卡爾空間坐標(biāo)，如公式（17）所示，

3 帶有自適應(yīng)學(xué)習(xí)策略的運動編碼粒子群算法

本章詳細介紹所提出的MPSO-ALS 算法。如圖2所示，該算法首先通過初始化方案生成原始粒子后，然后根據(jù)粒子分布進行子群體動態(tài)劃分，接著在每個子群中采用普通粒子學(xué)習(xí)策略和局部最優(yōu)粒子學(xué)習(xí)策略指導(dǎo)不同類型粒子的搜索方向，同時進行參數(shù)自適應(yīng)控制。在代數(shù)1（a），算法首先通過初始化機制生成隨機分散在搜索空間的原始粒子，隨后根據(jù)粒子的分布找到幾個中心粒子作為聚類中心，并劃分子群，如代數(shù)1（b）。接著，在每次迭代中，將每個子群中的中心粒子當(dāng)作局部最優(yōu)粒子，子群中的其他粒子作為普通粒子，每個子群的普通粒子向著該子群的普通粒子引導(dǎo)方向移動，從而增加整個種群的多樣性；子群中的局部最優(yōu)粒子向著局部最優(yōu)粒子引導(dǎo)方向移動，使得局部最優(yōu)粒子學(xué)習(xí)了子群間一些最優(yōu)粒子的信息，在增加種群多樣性的同時，引導(dǎo)該子群收斂到真正的全局最優(yōu)位置；另一方面，在每次迭代中還要進行參數(shù)的自適應(yīng)控制，如代數(shù)i。粒子群在子群動態(tài)劃分，參數(shù)自適應(yīng)控制，不同類型粒子迭代更新三種方案下持續(xù)迭代，不斷向著全局最優(yōu)方向收斂，如代數(shù)j。直到滿足收斂條件，找到全局最優(yōu)位置，即概率較高的正確搜索路徑，如代數(shù)G。

圖2 MPSO-ALS算法主要過程圖Fig.2 MPSO-ALS algorithm main process diagram

3.1 初始化

在有多個不同概率目標(biāo)區(qū)域的情況下初始化路徑時，為了避免粒子因在搜索空間任意方向隨意運動，而導(dǎo)致其向較低概率區(qū)域探索開發(fā)，最終收斂到低概率區(qū)域（局部最優(yōu)），故重新規(guī)劃了初始化方法。

圖3給出了某次初始化路徑示例，由圖可知，初始化路徑位置時，將搜索空間分為8個區(qū)域，每個粒子隨機在某個區(qū)域生成一條向外延伸的路徑（超出搜索空間則將路徑限制在搜索空間內(nèi)），這些路徑就能覆蓋或盡量接近目標(biāo)的移動路徑和最終位置，從而粒子能根據(jù)目標(biāo)函數(shù)向較高概率的正確目標(biāo)區(qū)域探索開發(fā)，最終收斂到全局最優(yōu)。同時，為了保持良好的種群多樣性，每個粒子都有較小概率ri生成每個運動段方向任意的隨機路徑。

圖3 八個方向之一的初始化路徑Fig.3 Initialization path in one of eight directions

粒子初始化的質(zhì)量對粒子群算法的性能至關(guān)重要。若粒子搜索路徑的運動段數(shù)目為N，粒子第一次可以運動到其相鄰的8 個網(wǎng)格之一，之后每次運動都只能運動到相鄰的7 個網(wǎng)格之一（即不退回前一個位置），則粒子總共有8+7N-1條運動路徑，這在運動段數(shù)多（問題維數(shù)多），且相對運動段而言種群規(guī)模不夠大的情況下，難以均勻初始化。新型初始化方法基于偽隨機初始化方法改進，相對于混沌初始化、均勻初始化、反向?qū)W習(xí)初始化等其他初始化方法[16]，僅需添加一些限制與隨機因子，就能有效地應(yīng)用于該問題中，獲得良好的效果。與傳統(tǒng)的偽隨機初始化方法相比，該方法生成的種群在搜索空間內(nèi)是較為均勻且有效的，一般不會集中在低概率區(qū)域，導(dǎo)致收斂到局部最優(yōu)。與混沌初始化策略相比，該方法不太會被問題維度限制，無需設(shè)置初值和其他參數(shù)，也不會因為吸引子的存在而影響算法效果。由于有8+7N-1種可能的結(jié)果，并且粒子是以搜索路徑的形式產(chǎn)生，均勻初始化方法[17]較難實現(xiàn)。較之反向?qū)W習(xí)初始化方案，不用消耗額外的評估次數(shù)。相比于準(zhǔn)隨機序列方法，也不用引入數(shù)值算法用以度量差異?？偨Y(jié)而言，與其他的初始化方案相比，該初始化方法實現(xiàn)簡單，在不引入其他開銷與負擔(dān)的情況下達到良好的效果。

3.2 子群動態(tài)劃分

子群可以保持種群多樣性，避免過早收斂。通過文獻[18]中的高性能聚類方法，可以給粒子群的學(xué)習(xí)策略提供更精確的基礎(chǔ)。該聚類方法能自動找到聚類中心，并且可以對任意形狀的數(shù)據(jù)集進行有效聚類，從而提高子群劃分的適應(yīng)性。

聚類算法首先要確定一個好的聚類中心，該聚類中心要滿足兩點：（1）中心粒子本身的局部密度大，即中心粒子應(yīng)被局部密度較低的鄰居包圍；（2）與其他局部密度較高的粒子相距較遠。為此給每個粒子定義了兩個量：局部密度ρi和距離偏量δi。

局部密度ρi表示粒子i一定距離內(nèi)的粒子個數(shù)，采用高斯核函數(shù)來定義，如公式（18）所示：

粒子的位置可以取其在笛卡爾空間的路徑中各坐標(biāo)的均值，dij表示粒子i和粒子j之間的歐氏距離，dc是截斷距離，是預(yù)先設(shè)定的一個值，可以取所有粒子間的距離升序排序后第2%位置的距離值，I是所有粒子的集合。

距離偏量δi是粒子i與其他密度大于該粒子的粒子間的最小距離，對于密度最高的粒子，將其距離偏量設(shè)置為所有距離中的最大值，該值本身并無意義，但可讓密度最大的粒子的距離偏量也為最大，從而被選為中心粒子之一，距離偏量δi如公式（19）所示：

對于局部密度ρi相同的粒子，可以所有ρi進行降序排序，使得ρi相同的粒子也有先后順序，從而計算相應(yīng)的距離偏量δi。

基于公式（18）和公式（19），就可以將具有高ρi和相對高δi的粒子選為中心粒子，如公式（20）所示：

其中，在計算γi時，為避免ρi值和δi值處于不同數(shù)量級而出現(xiàn)偏重，可對其進行歸一化處理后再計算γi值。

確定所有子群的中心粒子后，就可以一次將其余每個粒子都分配到與之距離偏量δi最小的更高密度的鄰居的相同子群中。該一次分配的方法與迭代優(yōu)化的方法相比，提高了子群劃分的效率。另外，區(qū)別于傳統(tǒng)的基于噪聲信號截止的分配方法，該方法引入了一個邊界區(qū)域，防止低密度子群被歸類為噪聲。子群的邊界區(qū)域由這樣的一組粒子構(gòu)成，在它們的距離為截至距離dc的領(lǐng)域內(nèi)，存在其他子群的粒子。對每個子群，令ρˉ=(ρi+ρj)/2，i指本子群的點，j是與i的距離不超過dc的其他子群的點，計算所有這樣的跨子群的粒子對的平均局部密度，取其最大值作為該子群的ρˉ上界，從而子群中密度高于ρˉ的粒子被認為在該子群中，而其余粒子則標(biāo)記為噪聲子群，每個噪聲子群都由一個粒子構(gòu)成。子群劃分過程如圖4所示。

圖4 子群劃分過程流程圖Fig.4 Flow chart of subswarm division process

3.3 粒子的學(xué)習(xí)策略

在每個子群中，有兩類粒子：（1）子群中的最好粒子，稱為局部最優(yōu)粒子；（2）剩余的粒子，稱為普通粒子。MPSO-ALS 使用基于文獻[19]改進的不同的學(xué)習(xí)策略對兩類粒子進行更新，以保持種群多樣性，避免陷入局部最優(yōu)。

3.3.1 普通粒子的學(xué)習(xí)策略

子群中的普通粒子負責(zé)利用搜索空間來增強種群多樣性，其位置更新方程同公式（14）一致，速度更新方程如公式（21）所示：

其中，ω、c1、c2、r1、r2的作用與MPSO 算法中的一致，LBk=(lbk,1,lbk,2,…,lbk,N)是第k代時某個粒子的自身歷史最優(yōu)向量集，普通粒子引導(dǎo)是第k代時子群c中目標(biāo)函數(shù)適應(yīng)度值排序前100p%（p∈(0,1]，是給定的比例）的粒子的自身歷史最優(yōu)向量集均值，若某子群的粒子數(shù)少于100p%，則取其所有粒子的均值。需要注意的是，普通粒子有微小概率rm突變，重新初始化。

傳統(tǒng)的粒子更新方式是所有粒子都基于相同的全局最優(yōu)粒子來迭代更新，這樣僅使用全局最優(yōu)粒子的搜索信息容易失去多樣性，從而陷入局部最優(yōu)，故在公式（24）中采用了子群中前100p%的粒子信息來更新同一子群中的其他普通粒子，使用粒子能學(xué)習(xí)到多樣化的搜索信息，并有微小概率突變后重新初始化，增加種群多樣性。

3.3.2 局部最優(yōu)粒子的學(xué)習(xí)策略

子群中的局部最優(yōu)粒子負責(zé)引導(dǎo)普通粒子的學(xué)習(xí)，并探索其他子群的信息以進一步增加種群多樣性，其位置更新方程同公式（14）一致，速度更新方程如公式（22）所示：

其中，ω、c1、c2、r1、r2、LBk、的作用與普通粒子中的一致，C是子群的數(shù)量。

對比公式（21）和公式（22）可知，局部最優(yōu)粒子引導(dǎo)是各子群中普通粒子引導(dǎo)的平均值，這對進一步增大種群多樣性，并加快收斂速度十分重要。首先，局部最優(yōu)粒子引導(dǎo)增加了子群間的信息交流，使局部最優(yōu)粒子可以學(xué)習(xí)到更多的路徑信息，從而可以增強種群多樣性，避免陷入局部最優(yōu)。其次，局部最優(yōu)粒子引導(dǎo)考慮了適應(yīng)值最優(yōu)的一些粒子的平均信息，這在加快收斂速度的同時，為找到真正的全局最優(yōu)解提供了有力指導(dǎo)。

3.4 參數(shù)的自適應(yīng)控制

參考了文獻[20]中的參數(shù)自適應(yīng)方案，計算粒子間的距離評估此時的狀態(tài)，調(diào)整參數(shù)，讓參數(shù)與進化狀態(tài)相匹配，以提升搜索效率，加快收斂速度，爭取收斂到概率更高的路徑。通過取粒子在笛卡爾空間的路徑中各坐標(biāo)的均值作為其位置的代表，粒子間的距離也能體現(xiàn)其進化狀態(tài)。

3.4.1 進化狀態(tài)評估

首先，計算每個粒子i相對于其余所有粒子的距離的均值，如公式（23）所示：

其中，NP是種群大小。

其次，取di中的最大距離為dmax，最小距離為dmin，用dg表示全局最優(yōu)粒子的距離，計算進化因子，如公式（24）所示：

由此可以初步知道粒子的狀態(tài)分布。粒子分布信息如圖5 所示，dpi表示除了全局最優(yōu)的其余每個粒子的平均距離。當(dāng)dg≈dpi，表示所有粒子的平均距離差不多，種群多樣性良好，在剛開始的探索階段；當(dāng)dg?dpi，表示全局最優(yōu)粒子逐漸被其余粒子包圍，處于開發(fā)或收斂階段；當(dāng)dg?dpi表示全局最優(yōu)粒子找到一個適應(yīng)值更好的位置，遠離原來的位置，其他粒子之后會逐漸往這個更好的值收斂，狀態(tài)改變順序為S1→S2→S3→S4→S1→…。

圖5 粒子分布信息圖Fig.5 Particle distribution information map

最后，采用隸屬函數(shù)判斷此刻的進化狀態(tài)，四個狀態(tài)由成員函數(shù)μ判斷，如公式（25）所示：

從圖6 四種進化狀態(tài)的隸屬函數(shù)圖可以清楚地看出各個狀態(tài)所屬區(qū)域，從而根據(jù)成員函數(shù)值與規(guī)則庫決定此時的狀態(tài)。

圖6 四種進化狀態(tài)的隸屬函數(shù)圖Fig.6 Graphs of affiliation functions of four evolutionary states

決定粒子所屬狀態(tài)的規(guī)則庫如表1所示，其中第一行表示當(dāng)前狀態(tài)，第一列表示先前狀態(tài)，一開始的狀態(tài)為S1。假如當(dāng)前狀態(tài)為S1，則判定狀態(tài)屬于S1，如若下一個當(dāng)前狀態(tài)為S3&S2，則判定狀態(tài)屬于S2。

表1 判定狀態(tài)的規(guī)則庫Table 1 Rule base for determining status

3.4.2 自適應(yīng)參數(shù)

借助有效的初始化機制，算法可以快速到達收斂狀態(tài)。由于種群多樣性的維持，一開始到達收斂狀態(tài)后，粒子群還能在探索和開發(fā)狀態(tài)間不斷切換，以快速尋找更適宜的路徑，此時算法處于全局搜索階段，慣性權(quán)重ω通常較大。粒子群最終會較為穩(wěn)定地保持在收斂狀態(tài)，并依舊有一定的種群多樣性，有時會轉(zhuǎn)換到其他三個狀態(tài)，從而不斷找到更貼合目標(biāo)運動路徑并最終找到目標(biāo)的概率更高的搜索路徑。此階段要求粒子群不斷減小ω，從而能不斷找到更高概率的路徑，并最終收斂到概率最高的路徑。ω根據(jù)進化代數(shù)線性遞減與問題更為貼合，若采用激活函數(shù)，則ω會在到達收斂狀態(tài)時就保持在一個較小的值，不利于粒子的搜索。故慣性權(quán)重ω根據(jù)進化代數(shù)線性遞減即可，g是當(dāng)前代數(shù)，G是總迭代次數(shù)。

加速因子c1代表個體認知，促進粒子獲得自身最好位置，有利于開發(fā)局部最優(yōu)，增加多樣性；c2代表社會認知，推動粒子向全局最優(yōu)區(qū)域收斂，加快收斂速度。故其加速策略如表2所示。

表2 c1 和c2 的控制策略Table 2 Control strategies for c1 and c2

策略1在探索狀態(tài)增加c1，減小c2：強調(diào)個體認知，幫助粒子探索自身最優(yōu)個體，避免過早聚集，陷入局部最優(yōu)。

策略2在開發(fā)狀態(tài)輕微增加c1，輕微減小c2：輕微增加c1可以使c1維持在一個較大的值，利用局部信息，在個體最優(yōu)周圍探索和開發(fā)；此時全局最優(yōu)粒子不一定在其真正的最優(yōu)區(qū)域，輕微減小c2可避免算法過早收斂，陷入局部最優(yōu)。

策略3在收斂狀態(tài)輕微增加c1，輕微增加c2：此時群體可能已經(jīng)找到全局最優(yōu)區(qū)域，c1應(yīng)該減小，同時增加c2才有利于引領(lǐng)其他粒子向可能的全局最優(yōu)收斂。但經(jīng)過實驗測試，此時減小c1并增加c2會使這兩個因子的值過早到達上下邊界，可能會使局部最優(yōu)區(qū)域被當(dāng)成全局最優(yōu)區(qū)域而快速收斂，所以應(yīng)該對c1和c2都輕微增加。

策略4在跳出狀態(tài)減小c1，增加c2：使全局最優(yōu)粒子獲得更好的值，跳出當(dāng)前最優(yōu)，離開原來的聚類而邁向更優(yōu)的區(qū)域。

為了使c1和c2每一代平穩(wěn)變化，不過于突兀，c1和c2增加與減小的值從加速率?=[0.01,0.05]間隔中隨機產(chǎn)生，而策略2和策略3中的輕微改變從0.5?中隨機產(chǎn)生。需要注意的是，如果c1和c2的和超過了5.0（c1和c2的初始值為2.5），要對之進行歸一化處理，限制在邊界內(nèi)，即

在策略3 的收斂狀態(tài)時，對于最優(yōu)粒子，隨機對其某一個維度加入高斯擾動，令其獲得跳出當(dāng)前最優(yōu)位置，離開當(dāng)前聚類，得到更好的值的能力。只選擇一個維度是因為當(dāng)前最優(yōu)可能具有全局最優(yōu)的一些良好結(jié)構(gòu)，故應(yīng)保護好它。具體如公式（26）所示：

圖7 展示了優(yōu)化過程中加速因子c1和c2的自適應(yīng)變化情況，結(jié)果取自10次運行的平均值?？梢钥闯?，在初始探索、開發(fā)階段，粒子利用局部信息，在個體最優(yōu)周圍探索和開發(fā)，c1數(shù)值增加。同時，控制策略為了避免收斂到局部最優(yōu)，出現(xiàn)無法很好地跟蹤目標(biāo)的運動路徑，目標(biāo)函數(shù)評估值較小的情況，減小了c2。隨著群體達到收斂狀態(tài)，粒子群已經(jīng)找到了能夠較好地跟蹤并找到運動目標(biāo)的路徑，應(yīng)引領(lǐng)其他粒子向可能的全局最優(yōu)搜索路徑收斂，c1和c2方向反轉(zhuǎn)，c1減小而c2增加。由于子群體多樣性的維持，粒子有時會轉(zhuǎn)換到其他三個狀態(tài)，故有時出現(xiàn)c1突然增加而c2減小的情況。最終，粒子群對全局最優(yōu)搜索路徑不斷細化，提高目標(biāo)函數(shù)評估值，所以c1和c2回到初始值2.5附近。加速因子c1和c2平均值的變化表明，進化狀態(tài)評估確實能夠識別粒子群的進化狀態(tài)，并進行參數(shù)自適應(yīng)控制來提高算法性能。相對于標(biāo)準(zhǔn)PSO，參數(shù)自適應(yīng)控制加快了收斂速度，彌補了子群體維護帶來的收斂速度較慢的缺陷，使其能夠細化解，提高所找到的路徑的搜索成功概率。參數(shù)自適應(yīng)流程圖如圖8所示。

圖7 加速因子c1 和c2 的平均值Fig.7 Average of acceleration factors c1 and c2

圖8 參數(shù)自適應(yīng)控制流程圖Fig.8 Parameter adaptive control flow chart

3.5 算法分析

帶有自適應(yīng)學(xué)習(xí)策略的運動編碼粒子群算法的流程圖如圖9 所示。其中，新的初始化機制相對于混沌化、均勻化等初始化策略，實現(xiàn)簡便，可以在不引入其他開銷的情況下，保證粒子識別到概率最高的正確目標(biāo)區(qū)域，避免粒子陷入局部最優(yōu)。另外，結(jié)合粒子群動態(tài)劃分機制，改進了不同類型粒子的更新方程以適應(yīng)子群策略。其中，普通粒子由子群c中目標(biāo)函數(shù)適應(yīng)度值排序前100p%的粒子的自身歷史最優(yōu)向量集均值代替全局最優(yōu)粒子作為社會引導(dǎo)，從而使粒子可以學(xué)習(xí)到搜索空間中多樣化的搜索信息，保持各子群的種群多樣性，避免陷入局部最優(yōu)；局部最優(yōu)粒子由各子群中普通粒子引導(dǎo)的平均值代替全局最優(yōu)粒子作為社會引導(dǎo)，使該粒子可以學(xué)習(xí)到子群間最優(yōu)的一些路徑的平均信息，從而局部最優(yōu)粒子在保持多樣性的同時，能有效指導(dǎo)普通粒子的學(xué)習(xí)，找到真正的全局最優(yōu)解。不同類型粒子的學(xué)習(xí)策略在保持種群多樣性的同時很好地提高了搜索概率。最后，根據(jù)進化狀態(tài)進行相應(yīng)的參數(shù)ω、c1和c2自適應(yīng)控制[20]，加快收斂速度以彌補劃分子群所導(dǎo)致的收斂速度較慢的缺陷，提高算法的運動目標(biāo)搜索成功率。另一方面，子群劃分引入了局部密度ρi和距離偏量δi，參數(shù)自適應(yīng)引入了加速率?和高斯擾動標(biāo)準(zhǔn)差σ，這些參數(shù)求解或設(shè)置簡單，可以在不引入巨大負擔(dān)的情況下提升搜索性能。

圖9 MPSO-ALS流程圖Fig.9 MPSO-ALS flow chart

4 實驗分析

本章分析MPSO-ALS 的復(fù)雜度和種群多樣性，并通過與其他啟發(fā)式算法進行實驗對比，評估MPSO-ALS的性能。

4.1 復(fù)雜度分析

標(biāo)準(zhǔn)PSO 算法的時間復(fù)雜度主要由粒子初始化(Tini)，基于學(xué)習(xí)策略的更新(Tupd)和成本評估(Teva)三部分構(gòu)成。設(shè)種群規(guī)模為p，問題維度為d，最大適應(yīng)度評估次數(shù)為m，則標(biāo)準(zhǔn)PSO 算法的時間復(fù)雜度為T(d)=Tini+(Tupd+Teva)m=pd+(2pd+pd)m=pd(3m+1)，即O(pdm)。

相對的，MPSO-ALS算法的時間復(fù)雜度主要由粒子初始化(Tini)，計算粒子位置(Tcp)，子群動態(tài)劃分(Tsdd)，普通粒子和局部最優(yōu)粒子基于學(xué)習(xí)策略的更新（Tupd-op和Tupd-lbp），進化狀態(tài)評估(Tese) 和成本評估(Teva) 組成。其中Tsdd包括距離矩陣計算(Tdis)，局部密度ρ計算(Tρ)，距離偏量δ計算(Tδ) 和劃分子群(Tds) 四部分。算法各部分所需花費的計算時間如下，粒子位置需要計算其在笛卡爾空間的路徑中各坐標(biāo)的均值，即Tcp=p；由粒子位置可計算每兩個粒子之間的距離得到距離矩陣，即Tdis=p2d；由距離矩陣計算每個粒子的局部密度，即Tρ=p2；由局部密度計算每個粒子的距離偏量，即Tδ=p2；由局部密度和距離偏量進行子群劃分，即Tds=p；粒子更新需要獲得適應(yīng)度值排序前幾名的粒子的自身歷史最優(yōu)向量集均值來引導(dǎo)更新，則Tupd-op=Tupd-lbp=p+2pd；進化狀態(tài)評估主要計算每個粒子相對于其余所有粒子的距離的均值，具體只要在粒子的距離矩陣上進行求和及平均，即Tese=p2。故T(d)=Tini+[Tcp+(Tdis+Tρ+Tδ+Tds)+(Tupd-op+Tupd-lbp)+Tese+Teva]m=pd+[p+(p2d+p2+p2+p)+2(p+2pd)+p2+pd]m=pd+(p2d+3p2+5pd+4p)m，即MPSO-ALS 的時間復(fù)雜度為O(p2dm)。

4.2 種群多樣性分析

MPSO-ALS 部分典型迭代時刻的個體分布圖如圖10所示，圖中白色圓圈表示無人機初始位置；紅色、綠色和青藍色粒子表示三個粒子子群，粒子位置取其在笛卡爾空間的路徑中各坐標(biāo)的均值；三個白色星號表示各個子群中的局部最優(yōu)粒子搜索路徑的最終位置；采用顏色編碼的信念圖是更新后的信念圖，表示目標(biāo)最終運動到位置（10，10）附近，并且在（10，10）位置的可能性最大。

圖10 MPSO-ALS典型迭代時刻的個體分布圖Fig.10 Distribution of individuals at typical iteration moment of MPSO-ALS

代數(shù)1 為初始化后的粒子，從圖10（a）可以看到粒子分布在初始位置四周，表示粒子群以初始位置為起點不斷向四周延伸的狀態(tài)，從而能盡量接近目標(biāo)的移動路徑和最終位置，確保粒子向高概率的正確目標(biāo)區(qū)域收斂。代數(shù)4 時粒子群已經(jīng)處于收斂狀態(tài)（圖10（b）），某一子群的局部最優(yōu)粒子已經(jīng)到了目標(biāo)位置附近，但其搜索路徑不一定很好地跟蹤了目標(biāo)運動，搜索概率并不是很高。由圖可知，直到27代前，由于子群動態(tài)劃分策略和子群中不同粒子的學(xué)習(xí)策略增加并保持了種群多樣性，粒子群不斷在探索和開發(fā)狀態(tài)間切換，尋找并跟蹤著目標(biāo)。27代后，粒子才基本保持在收斂狀態(tài)，并且找到了（10，10）這個可能性最大的位置。之后每一代，粒子群在利用子群策略維持多樣性的同時，通過參數(shù)自適應(yīng)控制加快收斂速度，不斷迭代，在收斂狀態(tài)下去尋找概率更高的搜索路徑，在70 代時找到了概率較高的搜索路徑，到100 代時找到了概率更高的搜索路徑。

4.3 實驗場景設(shè)置

實驗采用了文獻[12]中的場景設(shè)置，使用6 種搜索場景來表示不同的搜索情況，以達到覆蓋作用，從而可以很好地分析MPSO-ALS的性能。如圖11所示，6個場景的地圖大小都為Sr=SC=40，但無人機的初始位置、初始信念圖b(x0)和目標(biāo)運動模型p(xt|xt-1)不同。其中，信念圖采用顏色編碼，用白色箭頭表示目標(biāo)動態(tài)，用白色圓圈表示無人機初始位置。

圖11 6個不同的實驗場景Fig.11 Six different experimental scenarios

場景1：有兩個高概率區(qū)域，它們彼此相鄰并向東移動，但在位置和概率值上略有不同，有一定的混淆作用，可能導(dǎo)致難以找到更好的區(qū)域來搜索目標(biāo)。

場景2：在無人機上下相對位置有兩個彼此分離的高概率目標(biāo)區(qū)域，它們向西南方向移動，算法需快速識別要搜索和跟蹤的區(qū)域。

場景3：有一個小型密集區(qū)域向東南方向快速移動，需要算法有良好的探索和適應(yīng)能力。

場景4：與場景3類似，但目標(biāo)區(qū)域向無人機起始位置移動，進一步測試算法的探索和適應(yīng)能力。

場景5：在無人機左右相對位置有兩個彼此分離的目標(biāo)區(qū)域向北移動，它們與無人機距離時刻相等，但右側(cè)區(qū)域的概率較高，算法需識別到正確的高概率目標(biāo)區(qū)域。

場景6：與場景5類似，但無人機位于目前潛在區(qū)域的下方，而目標(biāo)區(qū)域向東北方向移動，檢驗了算法在對角線方向上搜索到正確目標(biāo)區(qū)域的能力。

MPSO-ALS的參數(shù)設(shè)置如下：慣性權(quán)重ω=1，加速因子c1=c2=2.5，子群數(shù)c=3，粒子選取比例p=0.003，初始化突變概率ri=0.1，普通粒子突變概率rm=0.001。種群大小為1 000個粒子，迭代次數(shù)100次，搜索路徑為20個節(jié)點。算法獨立運行10次以找到每種場景下的均值和標(biāo)準(zhǔn)差。

4.4 搜索路徑

圖12 是MPSO-ALS 在6 個場景中的搜索路徑和累積概率值，其概率圖僅反映最后一步的目標(biāo)信念，而無人機搜索路徑則反映了隨時間變化的對高概率正確目前區(qū)域的跟蹤路徑。無論在哪個場景中，該算法都能找到概率最高的正確目標(biāo)區(qū)域，并生成能適應(yīng)目標(biāo)動態(tài)以最大化檢測概率的搜索路徑。需要注意的是，場景3和場景4中的累積概率值大于其他場景，這是因為這兩個場景都只有一個高概率的目標(biāo)區(qū)域，所以找到目標(biāo)的機會不會擴散到其他混淆區(qū)域中。

圖12 MPSO-ALS在每個場景的搜索路徑和累積概率值Fig.12 MPSO-ALS search paths and cumulative probability values in each scenario

4.5 與其他PSO算法的對比分析

這一部分主要描述PSO 算法相對于其他PSO 變體的優(yōu)勢，這些PSO變體在引言和2.2節(jié)都已有描述，其結(jié)果從文獻[12]中獲得。

表3是10次運行后，MPSO-ALS和其他PSO算法在累積檢測概率適應(yīng)值上的平均值和標(biāo)準(zhǔn)差，加粗字體表示其適應(yīng)值在對比算法中最優(yōu)。由表可得，MPSO-ALS在所有6 個場景中的性能都是最好的，收斂也較為穩(wěn)定，這說明初始化方案和自適應(yīng)學(xué)習(xí)策略的有效性。例如，在場景1中，MPSO-ALS的適應(yīng)值是0.204 7，而次優(yōu)的MPSO 是0.187 6，θ-PSO 是0.186 9，PSO 和QPSO 分別是0.147 6 和0.119 8，故MPSO-ALS 提升了0.017 1 以上。在場景2、3、5、6中也有類似的提升。特別的，在場景4中，MPSO-ALS的0.545 4比次優(yōu)MPSO的0.501 8提升了0.043 6，這說明對于突然折回探索的場景，MPSOALS 的性能是更優(yōu)的，即相對于其他PSO 算法，MPSOALS的多樣性更好且收斂良好。MPSO和θ-PSO次之，并且結(jié)果相近，因為它們的編碼方式允許它們在運動空間中搜索。PSO和QPSO適應(yīng)值最小，這是因為它們所使用的對節(jié)點的編碼方式無法保持粒子的動量而導(dǎo)致局部最優(yōu)。

表3 MPSO-ALS和其他PSO變體的適應(yīng)值比較Table 3 Comparison of MPSO-ALS and other PSO variants with respect to fitness

從圖13中10次運行后各類PSO算法的平均適應(yīng)值收斂曲線圖也可知，MPSO-ALS 較之MPSO，在除了場景5 的其他場景中都有明顯的性能提升，而場景5 只有微小提升。另一方面，可以注意到在場景1和場景6中，MPSO-ALS 的收斂速度非?？?，分別在第9 代和第8 代就超越了次優(yōu)的MPSO的最終收斂值，并逐漸收斂到更優(yōu)的路徑，說明其不會被其他高概率區(qū)域混淆且在對角線方向上的探索開發(fā)能力較強，但在其余4個場景中的探索能力則很弱，這可能是子群部分在早期容易被局部最優(yōu)區(qū)域吸引導(dǎo)致。MPSO 性能次之，但在場景2 到場景5 中的探索開發(fā)能力強于MPSO-ALS，這些場景中，MPSO-ALS分別需要37代、33代、48代、39代才能超過MPSO 的最終收斂值，且超過MPSO 最終收斂值前的收斂速度基本低于MPSO。θ-PSO 稍弱于MPSO。而PSO和QPSO則很容易陷入局部最優(yōu)，與其他算法差距較大。

圖13 MPSO-ALS和其他PSO變體的收斂曲線圖Fig.13 Convergence curves of MPSO-ALS and other PSO variants

4.6 與其他啟發(fā)式優(yōu)化算法的對比分析

這部分將MPSO-ALS 與其他元啟發(fā)式算法進行比較以進一步評估其性能。用于比較的算法是ABC，ACO，GA，DE 和TSA 算法，其結(jié)果從文獻[12]中獲得。ABC 將人工蜂群分為雇傭蜂、觀察蜂和偵察蜂三種蜜蜂。在進化過程中，雇傭蜂和觀察蜂負責(zé)開采過程，而偵察蜂負責(zé)隨機搜索蜜源，最終將解決方案表示為一組由運動段組成的搜索路徑。ACO通過螞蟻信息素通信來找到從蟻穴到食物源的最短路徑，由最大最小蟻群和文獻[21]中的“ACO-Node+H”方法實現(xiàn)。GA 模擬物競天擇的自然進化過程，通過個體的選擇、交叉和變異獲得最優(yōu)染色體，由文獻[22]中的“EA-Dir”方法和兩種變異技術(shù)“flip”和“pull”實現(xiàn)。DE 通過對種群進行變異、交叉和選擇三種操作來獲得最優(yōu)解，是基于種群的群體進化算法。TSA基于樹木生長衍化，同時探索和開發(fā)并利用樹群種子傳播解決優(yōu)化問題。

算法的平均適應(yīng)值和標(biāo)準(zhǔn)差如表4所示，加粗字體表示其適應(yīng)值在對比算法中最優(yōu)，圖14 顯示了其對應(yīng)的收斂曲線圖。由表4 可知，MPSO-ALS 在6 個場景中都優(yōu)于其他啟發(fā)式算法。TSA次優(yōu)，其適應(yīng)值與MPSOALS在除了場景5的其他場景中都有明顯差距。例如，在場景5中，MPSO-ALS僅僅比TSA的適應(yīng)值多0.004 3，但在場景1 中卻相差0.017 4，場景2、場景6 與場景1 類似。特別的，在場景3 中，MPSO-ALS 的0.680 2 比TSA的0.623 6 高了0.056 6；而在場景4 中，MPSO-ALS 的0.545 4則遠高于TSA的0.462 6，相差0.082 8。GA性能最差。

表4 MPSO-ALS和其他啟發(fā)式算法的適應(yīng)值比較Table 4 Comparison of MPSO-ALS and other metaheuristic algorithms with respect to fitness

圖14 MPSO-ALS和其他啟發(fā)式算法的收斂曲線圖Fig.14 Convergence curves of MPSO-ALS and other metaheuristic algorithms

從圖14 可以明顯看出各算法間的區(qū)別。MPSOALS 以高適應(yīng)值優(yōu)于其他算法，但在場景3 和場景4 中的收斂速度明顯弱于大部分算法，這表明其在對較小的高概率區(qū)域的探索能力的不足。TSA 開發(fā)能力有限以至于最終收斂值弱于MPSO-ALS。與最終收斂值基本處于次優(yōu)的TSA 相比，MPSO-ALS 在場景1 和場景6中分別只用了9 代和11 代就超過了TSA 的最終收斂值。在場景2 到場景5 中則分別需要25 代、24 代、35代、39 代來超過TSA 的最終收斂值。需要注意的是，MPSO-ALS 對場景3 和場景4 中的較小高概率區(qū)域的探索能力不足，故在分別到達24 代、35 代前，收斂速度慢于其他對比算法。ABC 和ACO 性能良好。DE 的探索、開發(fā)和收斂能力都較弱，很久才達到其收斂值。GA 性能最弱，可能是因為交叉和變異操作會產(chǎn)生許多無效的搜索路徑，導(dǎo)致其容易陷入局部最小值。

5 總結(jié)

為了提高無人機搜索運動目標(biāo)的累積檢測概率，受MPSO算法思想的啟發(fā)，提出了帶有子群體動態(tài)劃分策略和自適應(yīng)學(xué)習(xí)策略的運動編碼粒子群算法MPSOALS。該算法規(guī)劃了新的初始化機制，使其更容易跳出局部最優(yōu)。另一方面，改進了不同類型粒子的更新方程，使得算法在采用子群劃分來保持多樣性的同時，能賦予子群中的普通粒子和局部最優(yōu)粒子不同的學(xué)習(xí)策略。最后在迭代過程中對參數(shù)進行自適應(yīng)控制，以加快收斂速度。實驗結(jié)果表明，MPSO-ALS不會陷入用于混淆的目標(biāo)區(qū)域中，并且在所有搜索場景中的搜索性能都有所提升。在未來的研究中，會專注于提升MPSO-ALS的性能并將其應(yīng)用到多運動目標(biāo)搜索領(lǐng)域。