基于混合粒子群的無人機對艦船搜索航路優化*

周 波 張尚悅

（1.海軍大連艦艇學院基礎部 大連 116018）（2.海軍大連艦艇學院航海系 大連 116018）

1 引言

隨著無人機技術的迅速發展，無人機在海上稽私、海事巡邏、海洋氣象監測、船舶遇險后事故救援等領域的應用越來越廣。尤其是隨著現代物流業的發展，在某些島嶼繁多、交通設施不完善、用郵不便的區域開展無人機航路運營，可兼顧時效性和便利性。

在軍事上，無人機以其造價低、體積小、非接觸、零傷亡等優勢也越來越受到各國的重視。無人機利用其攜帶的光電、紅外傳感器、攝像頭等多種機載設備，可以在大范圍內持續不斷地監視海洋或陸地。對于交通流量比較大的港口以及重要的交通要道，無人機在高風險環境下執行任務時，還可根據需要抵近偵察，在較短時間內初步判定目標的類型，一旦發現可疑目標，可及時回傳各種信息，為后續的進一步識別、跟蹤、搜索、查證做準備。由于無人機執行任務時受多種因素影響，其運動時間有限。因此，執行任務前首先要合理規劃飛行路線，獲取最優飛行路徑［1～3］。

2 無人機搜索問題基本理論

無人機從某個起點出發，對任務海域中各艘艦船進行搜索查證的問題，相當于典型的旅行商問題。需求解無人機飛到各艘目標艦船上空查證并最終返回到起點的最短路徑。根據算法實現原理不同，航路優化算法包括圖論中的A*算法［4］、Floyd算法［5］、Dijkstra算法等非進化型算法，以及粒子群優化、神經網絡算法、禁忌搜索法、遺傳算法、模擬退火［6］、蟻群算法等進化算法［1～2］。非進化型算法運算量小、易于實現、處理效率高，但不易產生最優路徑；進化型算法通常模擬生物進化特征，能夠及時更新、具有一定的記憶能力。

3 PSO算法

3.1 標準粒子群算法

粒子群優化（Particle Swarm Optimization，PSO）模擬鳥類覓食過程中的同伴協作下的運動過程，每個粒子都有一個速度向量，決定其下一步運動的方向和距離。鳥群尋找最優解的過程是通過整個群體的協作和信息共享來實現的，每個解都可以看作搜索空間中的一個多維粒子。根據適應度函數值的變化規律，所有粒子追隨當前的最優粒子在解空間中運動［2，7］。

在每一步迭代過程中，PSO粒子的速度受兩個因素影響：該粒子目前所找到的局部最優解向量Pbest和整個種群目前找到的全局最優解向量Gbest。標準PSO算法的基本流程如下。

1）粒子群初始化：隨機給定每一個多維粒子的初始位置和速度，粒子的維數就是需要搜索的目標數。

2）根據適應度函數公式計算出每個粒子的適應度函數值，從而確定每個粒子的優劣。

3）每一次迭代中，粒子xi(i=1，2，...，n)根據Pbesti和Gbest來更新vi：

式中，n是粒子總數，為第k次迭代第i個粒子運動速度矢量的第d維分量，為第k次迭代第i個粒子位置矢量的第d維分量，pid為第i個粒子最優位置pbest的第d維分量，pgd為群體最優位置gbest的第d維分量，c1、c2是權重因子［5～6］。

4）為防止粒子陷入局部最優解，引入適當的隨機干擾。

5）返回第2）步繼續執行，直到找到符合條件的解或者滿足終止條件為止。

從1）、2）可以看出，粒子運動的速度和方向受自身最優和群體目前最優兩個主要因素影響，在二者共同作用下向最優路徑進行動態調整。與其他的進化算法一樣，PSO也可能陷入局部極值，出現早熟問題。在式（1）中，如果某個粒子的xid與pid和pgd都十分接近，粒子的速度接近于零，在pgd附近的粒子可能無法跳出局部極值，導致算法收斂早熟［6］。可見，如果粒子的多樣性無法滿足，整個種群的適應度函數變化受限，無法跳出局部最優繼續進行搜索。目前有多種改進PSO方面的研究：比如修改粒子過去飛行速度對當前速度的影響因子，或者引入壓縮因子動態調整全局搜索能力和局部搜索的比例關系等。改進目標是增強全局優化能力的同時，加快算法的運行速度，提高收斂時最優解的精度。

3.2 PSO與遺傳算法的比較

遺傳算法（Genetic Algorithm，GA）模擬生物進化過程在解空間中進行最優搜索。遺傳算法三種主要的算子：交叉、變異、選擇。交叉和變異可以提高種群多樣性，通過選擇，適應值高的個體得到更多的復制機會，適應度低的個體在優勝劣汰過程中被淘汰。遺傳算法中的需要設定的參數主要有種群大小、染色體長度、交叉概率、變異概率、最大遺傳代數等。

PSO和GA都屬于生物進化算法，都具有并行性，都是全局優化算法，但PSO算法沒有染色體之間的交叉和變異操作，而且PSO與GA的信息共享機制不同。在GA中，所有染色體信息共享，整個種群均勻地向最優解集移動；在PSO中，只把Gbest（Pbest）的信息傳遞給其他的粒子，信息的傳遞方向是單方向的，整個種群的更新是密切跟隨當前最優解的過程。2000年，Lovbjerg、Rasmussen和Krink提出了混合型PSO，將遺傳算法中的交叉概念引入PSO中。從所有粒子中按照一定比例選取待交叉的粒子，然后兩個一組，隨機組合進行交叉操作產生新的后代粒子。可見，交叉型PSO不但要更新速度和位置，還要進行遺傳算法中的交叉操作，用新產生的后代粒子取代其父代粒子。與標準的PSO相比，混合PSO搜索速度快，收斂精度高。在無人機航路優化中，充分利用PSO和GA的各自的特點是一種可行的算法［8］。

3.3 航路規劃步驟

1）根據問題的復雜程度，確定種群的大小n（個體數）。

2）確定最大迭代次數、最大迭代次數、粒子移動速度等相關參數。

3）粒子群初始化，每個粒子代表一條初始路徑。

4）確定目標函數。

5）計算初始的隨機粒子的目標函數。

6）根據式（1）、（2）調整粒子的位置和速度。按照一定的交叉概率Pc，對個體極值和群體極值進行交叉來更新粒子。交叉方式有循環交叉、順序交叉、位置交叉等［9］。本文采用單點交叉。對于選定的兩個 父代個 體g1=x1x2......xn-1xn+2，g2=x'1x'2......x'n-1x'n+2。

隨機地選取第m個基因處為交叉點：

經過交叉運算后得到的新的子代粒子s1和s2。

計算新粒子s1和s2的適應度函數值，若新粒子的適應度函數值的小于歷史最優，則對歷史最優進行替換，若大于歷史最優，則繼續保持原來的歷史最優。

7）返回步驟5）重新執行，若達到最大迭代次數則退出循環，輸出最優路徑規劃結果［10～12］。

4 仿真實例

假定在某一港口處（坐標為原點）部署無人機起降平臺，無人機從此處出發，對橫向距離40km，縱向距離80km內的若干艦船目標進行搜索。共進行三次實驗，任務區的艦船目標數量分別為20、50、100。無人機運動速度為120km/h。分別用混合粒子群算法和遺傳算法求解最優路徑。實驗所用電腦配置為Windows7 64位系統，4GB內存，程序在MatlabR2015a平臺運行。仿真結果如圖1～3所示，最優路徑長度和算法執行時間如表1所示。

表1 不同算法運行結果比較

圖1 無人機對艦船的搜索路徑（20個目標）

圖2 無人機對艦船的搜索路徑（50個目標）

圖3 無人機對艦船的搜索路徑（100個目標）

從表1可以看出，本文算法求解的最優路徑長度明顯優于遺傳算法，從算法的運行時間看，在目標數量為20的時候，遺傳算法速度較快，但是當目標速度上升到50和100時，遺傳算法運行速度明顯落后于本文算法。混合粒子群算法能夠得到滿足要求的最優航跡，而且，在種群維度較高的情況下，也能夠保證快速完成航路規劃。

5 結語

在交通流量較大的港口，利用無人機對進出港艦船進行搜索可以大大提高海上巡查的效率。本文算法還可以用于無人船、無人艇的航路優化。下一步將繼續研究無人機集群的航路規劃，進一步提升檢測效率。