一種基于改進粒子群算法的機載多傳感器任務分配方法

史國慶, 武凡, 張林, 張舒楊, 郭操

(1.西北工業大學 電子信息學院, 陜西 西安 710072; 2.沈陽飛機設計研究所, 遼寧 沈陽 110035)

機載多傳感器探測可以使感知能力達到最大化，然而，復雜的傳感器資源環境容易存在以下幾項問題：①資源閑置或浪費；②資源重用率過高；③任務遺漏。為解決上述問題，需要實現任務的有效分配和資源的充分合理調用。

傳感器任務分配的起源可以追溯到20世紀70年代，Zeng D采用線性規劃的方法研究單平臺傳感器追蹤多目標的分配問題[1]；Yan T以線性規劃理論為基礎，使用布爾矩陣定義了一種圍繞傳感器能力和有效性開展規劃的目標配對方法，利用傳感器性能模型預測傳感器對目標執行能力[2]；Ramdaras提出了一種以最大檢測概率為目標的傳感器動態規劃管理方法[3]；吳巍采用目標與資源的配對函數和目標優先級兩部分作為效能函數基本組成，最后以效能函數作為目標函數來實現規劃[4]。

隨著傳感器與目標數量逐漸增多，傳統的數學規劃算法難以獲得最優解，學者們開始考慮將智能搜索類優化算法[5-6]引入傳感器管理規劃領域，如朱衛宵將蟻群算法引入到傳感器管理領域取得了良好的管理效果[7]。隨著智能優化算法被引入任務規劃領域，研究人員們發現對算法進行改進有助于提高規劃效率與規劃能力，如楊嘯天將遺傳算法與粒子群算法應用于傳感器目標分配，提高了穩定性并加快了收斂速度[8]；劉文凱提出一種遠離最差解的粒子群算法，在搜索速度、精度等多個方面均起到了顯著的優化效果[9]。針對機載多傳感器任務分配問題的特點，本文在借鑒傳統粒子群算法的基礎上對其進行適當改進，有效提高了機載多傳感器任務分配的效率。

1 問題描述

1) 傳感器與任務數量已知,傳感器數量為m,任務數量為n;

2) 傳感器執行任務能力有限,單次規劃每個傳感器最大執行任務數量為2個;

3) 傳感器與目標空間位置固定且空間坐標已知。

2 基于改進粒子群算法的機載多傳感器任務分配建模

粒子群算法是由Eberhart和Kennedy于1995年提出的一種全局搜索算法[10],它源于對鳥類捕食行為的模擬,進化規則是群體向著當前最優狀態前進,但與此同時,由于粒子的優化方向是歷史最優粒子方向,迭代容易陷入局部最優中造成過早收斂而無法找到全局最優,因此算法的全局搜索能力易受到限制。針對傳統粒子群算法的這一不足,在機載多傳感器任務分配問題中,對粒子群算法作如下改進設計:

1) 采取十進制粒子編碼,粒子向量Xi(第i個粒子向量)中的分量依序代表分配給該任務的資源,若粒子所屬為R維空間,則

Xi=[x1i,x2i,…,xRi],i=1,2,…,M

式中,M為種群規模;

面部激素依賴性皮炎主要是由于長期使用糖皮質激素引起的。近年來，其發病率逐年上升[1]。激素依賴性皮炎是由不適當的局部外用糖皮質激素制劑引起的炎性皮膚病，其導致皮膚屏障功能受損，出現紅斑、色素沉著過度、毛細血管擴張等癥狀，治療難度大。本研究分析了面部激素依賴性皮炎治療中清邁解毒飲的應用及觀察，報道如下。

2) 尋找并記錄歷史個體最劣解和全局最劣解,分別記為Pworsti和Gworsti,使粒子在向著最優狀態前進的同時可以遠離最劣解;

3) 引入個體遠離因子和全局遠離因子用于控制粒子遠離最劣解和接近最優解快慢的程度,引入方向系數作為遠離因子的參數,用于控制粒子的遠離方向,同時將遠離因子與學習因子和隨機參數聯系起來,這樣既可以有效避開由局部最優解造成的收斂盲區,又可以防止粒子運動過于發散而錯過最優解。

2.1 粒子群算法改進

基于上述改進設計,構造改進粒子群算法(improved particle swarm optimization,簡稱IMPSO算法)。首先,定義方向系數:

(1)

式中，Nd為最大迭代次數,t為當前迭代次數,通過方向系數的調節使仿真在初始階段的搜索范圍較大,尾聲階段搜索范圍較小,防止搜索過程中粒子運動過于發散。

結合群體向最優粒子進化的加速常數sp和sg以及屬于[0,1]的隨機常數rp(t)和rg(t),計算個體遠離因子b1

b1=h·sp·rp(t)

(2)

全局遠離因子b2

(3)

在粒子群算法基礎上改進的第i個粒子速度Vi和位置Xi更新方法為:

公式(4)中w為慣性權重,用來控制算法的收斂程度,一般取0.8到1.2之間,此時有較快的收斂速度,且具有均衡的全局收斂和局部收斂能力。Pbesti為個體最優解,Gbesti為全局最優解。

2.2 多傳感器任務分配建模

采用改進后的粒子群算法解決機載多傳感器任務分配問題,建立粒子模型與目標函數模型。

2.2.1 粒子模型

本文將粒子的建模分為兩部分,一是粒子編碼,二是初始種群建模。

首先,本文中粒子編碼采用整數編碼的方式,由于本文問題背景要求每個任務必須要有與其匹配的傳感器資源,同時還要滿足傳感器資源的最大任務執行數量限制,因此建立粒子模型的維數等于任務總數,每個分量由從左至右按順序排列的分量編號對應為任務編號,每個分量值對應該任務被分配的資源編號,若同一個分量下的值不同則視為不同的規劃方案,即當有m個資源,n個任務時,第j個粒子向量表示為:

pj=[s1,s2,s3,…,sn]

si∈{1,2,3,…,m}

(6)

(6)式表示1號任務由s1傳感器執行,2號任務由s2傳感器執行,以此類推,n號任務由sn傳感器執行。除此之外,粒子模型應滿足單個傳感器資源執行的任務總數不超過其最大任務能力數。

其次,初始種群建模。每個粒子對應一個該問題的可行解,粒子群便是由多個這樣的粒子組成的,若以矩陣形式表示粒子群,則矩陣的每一行由一個粒子向量組成,矩陣的總行數便是粒子群的規模大小M。種群大小對算法的運行效率會產生一定影響,若M太大,會降低算法尋優速度,但若M太小會降低種群多樣性,使結果過早收斂,故種群規模大小的取值范圍一般在30到60之間[11]。

初始種群的選取通常是隨機的,這樣既簡單又保證了種群的多樣性,只要在算法執行前確定種群規模、資源數量和任務數量以及資源限制便可以得到一個隨機的初始種群,進而進行下一步迭代。

2.2.2 目標函數模型

為完成多傳感器任務分配,需選擇一個適應度函數作為優化的目標函數。本文以最大探測概率為目標函數進行任務分配,探測概率模型[12]以信噪比作為主要輸入參數,將虛警率視為消耗因子:

(7)

(8)

本文以粒子所代表分配方案的平均探測概率作為尋優的適應度函數,也即多傳感器任務分配的目標函數:

(9)

2.3 算法步驟

根據前述改進粒子群算法和機載多傳感器任務分配建模的方法,得到改進粒子群算法的流程圖如圖1所示。

圖1 改進粒子群算法流程圖

3 仿真算例

利用改進粒子群算法對本文所研究的機載多傳感器任務分配問題進行求解,以驗證改進算法的性能優劣。仿真算例設置如下:在空間區域為20 km*20 km*15 km的空戰場中存在m=10的資源和n=15的目標任務,資源與目標位置隨機生成,每個資源可處理最多2個任務,慣性權重w設為1,加速常數sp設為1.5,sg設為1.2,速度上限為2,虛警率為0.2,每次仿真進行300次迭代,進行2次仿真,得到改進粒子群算法的適應度變化曲線如圖2和圖3所示。

圖2 改進粒子群算法適應度曲線(1)

圖3 改進粒子群算法適應度曲線(2)

由于粒子初始位置和轉移過程具有隨機性,加上每次仿真時資源與目標位置也是隨機生成的,使得每次仿真結果會存在一定差異,但通過觀察圖2、圖3的適應度,發現適應度均會在迭代初始便達到0.3左右,且隨著進化次數增加逐漸升高,最終呈收斂狀態,說明在不同戰場態勢環境下改進粒子群算法具有良好的尋優收斂效果。通過觀察發現圖中曲線發生多次跳變,這說明改進粒子群算法能夠成功跳出局部收斂尋找到更優解。

通過上述分析可知改進粒子群算法可以有效進行可行解尋優,為了驗證改進粒子群算法的優勢,在上述仿真算例基礎上,設計對比算例實驗,設置傳感器與任務目標三維坐標如表1、表2所示。

表1 任務目標初始位置坐標

表2 傳感器初始位置坐標

將本文所采用的IMPSO方法與同為遠離最劣解的LMPSO方法[9]進行比較,LMPSO方法在粒子群算法基礎上增加了遠離個體最劣解的方法,但并未對加速系數作出調整。同時使用IMPSO和LMPSO進行500次迭代尋優,得到結果如圖4所示。

圖4 算法改進后適應度對比圖

由圖4可以看出,針對機載多傳感器任務分配問題,2種粒子群算法均能使結果收斂,但IMPSO能夠先于LWPSO算法發現更優解,在有限次迭代內收斂效果更優,大大提高了算法效率。由于本文所涉及的問題為整數規劃問題,粒子速度只能以整數形式體現,相比LWPSO算法而言,IMPSO算法具有更松弛的速度調整機制,能夠防止高速變化導致的最優解失蹤情況,因此能夠更快找到個體最優解并有效防止局部收斂。在上述算例下,算法可在當前搜索范圍內獲得已搜索空間內的機載多傳感器任務分配的最優解,如表3所示。

表3 最優解分配結果

通過觀察表3中的分配結果可以發現規劃結果符合每個資源最多指派2個任務的限制條件，2號、6號、7號、8號、9號資源得到了重復利用。

4 結 論

本文提出了一種以最大探測概率為目標函數的機載多傳感器任務分配問題的解決方法，建立了機載多傳感器任務分配模型，針對傳統粒子群算法過早進入局部收斂的不足，設計了改進粒子群算法及多傳感器任務分配模型求解達到最大探測能力的分配方案，從仿真案例的尋優結果可以看出本文提出的方法針對機載多傳感器任務分配問題具有較好的尋優效果，從適應度變化情況可以看出，算法能夠有效跳出當前局部收斂狀態，尋找到更優解，相對于同類粒子群優化方法，提高了求解效率。