用于UAV運動目標搜索的自適應粒子群算法

楊鴻光，張宇輝，魏文紅

東莞理工學院 計算機科學與技術學院，廣東 東莞 523808

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

許多元啟發式算法由于其可以有效解決動態約束問題，能夠在復雜場景中找到全局最優解的能力，而被廣泛應用于路徑規劃中。這些啟發式算法可以有效地對動態目標進行路徑規劃，例如粒子群優化算法（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]、鯨魚優化算法（whale optimization algorithm，WOA）[9]，和其他可用于路徑規劃的新型智能優化算法[10]。其中，由于PSO 算法十分簡單有效，并且計算量小，得到了廣泛使用，并涌現出了許多改進措施。

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

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

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

1 目標函數

本章主要介紹目標函數。目標函數通過對目標、傳感器和信念圖建模來表示[12]，具體內容如下。

1.1 目標模型

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

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

1.2 傳感器模型

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

1.3 信念圖更新

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

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

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

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

其中，ηt是歸一化因子，將目標出現在搜索區域內的概率縮放為1，即，ηt由公式（4）表示：

1.4 搜索問題的目標函數

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

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

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

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

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

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

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

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

2 算法背景

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

2.1 粒子群算法

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

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

2.2 運動編碼粒子群算法

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

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代時某個粒子的自身歷史最優和全局最優位置向量集。圖1給出了具有三個運動段的路徑示例，其中，信念圖將概率值用顏色編碼并顯示在右邊。

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

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

通過公式（16）可以得到相對應于運動空間坐標的笛卡爾空間坐標，如公式（17）所示，

3 帶有自適應學習策略的運動編碼粒子群算法

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

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

3.1 初始化

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

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

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

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

3.2 子群動態劃分

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

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

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

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

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

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

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

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

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

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

3.3 粒子的學習策略

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

3.3.1 普通粒子的學習策略

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

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

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

3.3.2 局部最優粒子的學習策略

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

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

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

3.4 參數的自適應控制

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

3.4.1 進化狀態評估

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

其中，NP是種群大小。

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

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

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

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

從圖6 四種進化狀態的隸屬函數圖可以清楚地看出各個狀態所屬區域，從而根據成員函數值與規則庫決定此時的狀態。

圖6 四種進化狀態的隸屬函數圖Fig.6 Graphs of affiliation functions of four evolutionary states

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

表1 判定狀態的規則庫Table 1 Rule base for determining status

3.4.2 自適應參數

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

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

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

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

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

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

策略4在跳出狀態減小c1，增加c2：使全局最優粒子獲得更好的值，跳出當前最優，離開原來的聚類而邁向更優的區域。

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

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

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

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

圖8 參數自適應控制流程圖Fig.8 Parameter adaptive control flow chart

3.5 算法分析

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

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

4 實驗分析

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

4.1 復雜度分析

標準PSO 算法的時間復雜度主要由粒子初始化(Tini)，基于學習策略的更新(Tupd)和成本評估(Teva)三部分構成。設種群規模為p，問題維度為d，最大適應度評估次數為m，則標準PSO 算法的時間復雜度為T(d)=Tini+(Tupd+Teva)m=pd+(2pd+pd)m=pd(3m+1)，即O(pdm)。

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

4.2 種群多樣性分析

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

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

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

4.3 實驗場景設置

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

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

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

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

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

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

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

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

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

4.4 搜索路徑

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

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

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

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

表3是10次運行后，MPSO-ALS和其他PSO算法在累積檢測概率適應值上的平均值和標準差，加粗字體表示其適應值在對比算法中最優。由表可得，MPSO-ALS在所有6 個場景中的性能都是最好的，收斂也較為穩定，這說明初始化方案和自適應學習策略的有效性。例如，在場景1中，MPSO-ALS的適應值是0.204 7，而次優的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比次優MPSO的0.501 8提升了0.043 6，這說明對于突然折回探索的場景，MPSOALS 的性能是更優的，即相對于其他PSO 算法，MPSOALS的多樣性更好且收斂良好。MPSO和θ-PSO次之，并且結果相近，因為它們的編碼方式允許它們在運動空間中搜索。PSO和QPSO適應值最小，這是因為它們所使用的對節點的編碼方式無法保持粒子的動量而導致局部最優。

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

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

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

4.6 與其他啟發式優化算法的對比分析

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

算法的平均適應值和標準差如表4所示，加粗字體表示其適應值在對比算法中最優，圖14 顯示了其對應的收斂曲線圖。由表4 可知，MPSO-ALS 在6 個場景中都優于其他啟發式算法。TSA次優，其適應值與MPSOALS在除了場景5的其他場景中都有明顯差距。例如，在場景5中，MPSO-ALS僅僅比TSA的適應值多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和其他啟發式算法的適應值比較Table 4 Comparison of MPSO-ALS and other metaheuristic algorithms with respect to fitness

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

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

5 總結

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