基于改進象群算法的多傳感器資源調度方法

李 琦,韋道知,謝家豪

(1.空軍工程大學防空反導學院,陜西 西安 710043;2. 解放軍93605部隊,北京 102100)

0 引言

在當前信息化、智能化作戰背景下,空天作戰能力迅猛發展。面對“隱身化、無人化、多域化、集群化、智能化”等新型空天目標威脅,單個傳感器在探測范圍、探測信息類別、探測精度等方面能力有限,很難完成對目標信息的整體跟蹤探測,更難以適應復雜多變的作戰環境和作戰需求。在此情況下,需要多傳感器協同進行優化以發揮傳感器網絡最大效能。對于“傳感器協同探測” 來講,其核心就是根據某種度量指標確定傳感器之間的最佳“協同方式”,在傳感器調度過程中也被稱為“傳感器調度方案”[1-4]。

在過去的十年中,大量的群智能優化算法被提出,鯨魚優化算法(WOA)[5]、黏菌優化算法(SMA)[6]、粒子群算法(PSO)[7]、布谷鳥算法(CSA)[8]和象群算法(EHO)[9]等在解決多種優化問題方面有很多成功的應用。除此之外,近幾年群智能優化算法在傳感器資源分配問題方面的研究也成為熱點[10-12]。文獻[13]在傳統的粒子群算法中引入免疫策略,較大程度提升了算法的全局搜索能力,減少了傳感器網絡的能耗。文獻[14]在多部雷達分配目標時引用螢火蟲算法,一定程度提高了目標分配的速度和效果。文獻[15]在研究傳感器分配中,通過引入粒子群算法并進行優化,提高了傳感器資源分配效率。文獻[16]提出了基于蟻群算法的多傳感器優化分配模型,通過仿真實驗證明了其可行性。文獻[17]通過精英策略對蛙跳算法進行升級,提高了傳感器網絡配置算法的收斂速度與時間滿意度,文獻[18]通過引入種群進化策略對布谷鳥算法進行改進,提高了目標分配的速度和精度。文獻[19]通過改進猴群算法對傳感器配置進行優化,尋優能力和收斂精度得到加強。文獻[20]在解決多約束條件下目標分配問題中通過研究引入多種群遺傳算法,提高了算法的搜索能力。文獻[21]在多傳感器任務調度中,通過添加方向系數和遠離因子對粒子群算法進行優化,解決了局部收斂的缺陷。

上述文獻中,雖然調度算法在收斂性或穩定性等某一方面得到了改善,但在多目標、復雜和復合多傳感器調度優化問題中,調度模型構建考慮因素不全面,缺少說服力;并且在智能搜索算法運用中,由于算法本身的隨機特征,存在控制參數設置過多、計算復雜、容易陷入局部最優等缺陷。針對以上問題,由于EHO算法具有全局優化能力、控制參數數量少、實現策略簡單等優點,本文選擇將EHO算法和反向學習機制(OBL)[22]及正余弦算法(SCA)[23]相結合,提出一種基于IEHO算法的多傳感器調度方法,并將其應用到求解傳感器調度模型中。

1 傳感器調度模型建立

1.1 決策變量

(1)

(2)

(3)

因此,傳感器調度方案可以寫成式(4)的解矩陣,該矩陣包含目標、傳感器和時間三維信息。

(4)

1.2 目標函數

1) 傳感器探測效益最大

為提高傳感器的探測跟蹤效果,在對目標進行探測跟蹤時,應選擇探測跟蹤效益最大的傳感器執行任務,在進行多傳感器調度建模過程中,由于不同類型的傳感器探測影響因素不同,接收到的目標信息不同,本文以傳感器和目標之間的距離以及傳感器的探測角度來研究傳感器探測效益。

傳感器對目標的探測效益函數可定義為

(5)

(6)

2) 傳感器負載最小

當傳感器i對目標j探測全過程中,傳感器完成探測跟蹤任務的負載為

(7)

在傳感器調度時間區間ΔT內,各類傳感器的總負載為

(8)

3) 傳感器交接次數最少

當目標的運動超過傳感器的探測范圍或者傳感器狀態發生改變時,需要考慮在調度區間內傳感器之間的交接。對調度區間內的傳感器的交接次數進行統計有利于判斷傳感器是否存在跟丟目標的情況,將相鄰兩個傳感器的探測跟蹤矩陣對應元素進行“異或”邏輯運算,可以計算出發生狀態改變的傳感器數目。

(9)

1.3 約束條件

1) 傳感器探測跟蹤可行性約束

本文建立的模型的求解是指在調度區間ΔT內隨著傳感器與目標的可視化情況對應生成的傳感器對目標探測跟蹤與否的方案,故矩陣t與s內的對應元素存在如下關系：

(10)

2) 傳感器觀測時間約束

傳感器在執行探測跟蹤任務時,觀測時間應在調度區間內,即

(11)

3) 傳感器探測跟蹤能力約束

不同傳感器因其自身能力與容量設計存在差異,導致每個傳感器的探測跟蹤目標的數量不能超過其最大的探測跟蹤能力,即

(12)

4) 傳感器探測跟蹤目標最大數量約束

為防止出現多個傳感器同時探測跟蹤一個目標,根據不同傳感器的性能要求,要在實現對目標的連續探測和穩定跟蹤的同時避免傳感器資源的浪費,應約束傳感器資源的最大數量。即

(13)

1.4 調度模型

在前面建立的目標函數和約束條件的基礎上,建立如下多傳感器調度多目標的調度模型：

(14)

式(14)中,a、b、c分別為探測效益函數、負載函數以及切換函數的權重比,a+b+c=1。

2 多傳感器調度算法

2.1 基本象群(EHO)算法原理

1) 部落更新操作

象群算法(elephant herding optimization,EHO)是通過模擬自然界大象部落放牧過程中的社會行為來求解問題的近似解或者最優解[24-25]。算法主要分為兩個過程,即部落更新操作和部落分離操作。

來自不同部落的大象在其女族長的領導下一起生活,其他大象的位置都根據女族長和自身的位置進行更新,位置更新公式如式(15)所示。女族長的位置根據部落中心的位置進行更新,由式(16)表示。

xnew,c=xc+α×(xbest,c-xc)×γ,

(15)

式(15)中,xnew,c和xc分別是大象在部落c中的新位置和舊位置;α代表部落中女族長對大象個體的影響因子,α∈[0,1];γ用來增加每一代的種群多樣性,γ∈[0,1];xbest,c定義了部落中最適合的大象個體。每個象群部落中最合適的大象位置更新可以如下實現

xbest,c=β×(xcenter,c),

(16)

式(16)中,β設置為 0 和 1 之間的隨機數, 它控制著部落中心對女族長位置的影響,其中部落c中心被定義為

(17)

式(17)中,nc是部落c中的大象數量,xc,d是大象個體xc的第d個維度,1≤d≤D,D是搜索空間的總維數。

2) 部落分離操作

每個部落c中適應度最差的個體在當它成熟時將遠離部落,在空間中進行隨機搜索以增加全局搜索性能,它們的位置更新表達式為

xworst,c=xmin+(xmax-xmin+1)×rand,

(18)

式(18)中,xmax和xmin分別表示種群中大象搜索位置的上、下限,rand∈[0,1]。

2.2 改進象群(IEHO)算法原理

雖然基本象群算法能夠較好地解決尋優問題,算法簡單,易于實現,但是由于象群優化算法的初始解都是隨機生成的,且在空間進行隨機搜索,存在收斂速度較慢和易陷入次優區域的問題,同時在部落分離操作位置更新中,采用的是隨機更換的方式,適應度最差的個體可能被移動到更差的位置,不能保證搜索獲取更優解。針對此問題,通過引入交替使用正余弦算法(SCA)和反向學習機制 (OBL)對算法性能進行改進。

2.2.1正余弦算法(SCA)

正余弦算法是Seyedali于2016年提出的利用正余弦函數的數學模型使解震蕩性地趨于最優解的一種方法[20]。針對算法分離操作步驟中適應度最差個體的位置隨機替換,采用正余弦算法使適應度最差個體的每個位置都采用了信息正余弦函數共享策略進行替換,使其總是在當前局部最優解周圍更新位置,這樣能夠保證搜索不斷趨向于空間的最佳區域,獲取更優解。

其位置更新方程為

(19)

式(19)中,γ2∈(0,2π),γ3∈(0,2),γ4∈(0,1)為均勻分布的隨機數;xbest,c為當前最優解個體的位置;γ1為控制參數,表示為

(20)

式(20)中,a為一個常數,t為當前迭代次數,Tmax為最大化迭代次數。

2.2.2反向學習策略(OBL)

反向學習策略是由Tizhoosh等人提出的用于改進元啟發式算法的收斂性,找到優化問題全局最優解的一種重要方法[21]。它是通過反向學習產生候選解的反向位置,隨后采取貪婪策略從當前候選解和反向候選解中尋找最優解決方案,求解思路如下：

1) 更新當前的搜索區域區間;

2) 設定一個反向學習跳變率P(P0∈[0,1],且為一個常數),產生一個隨機數rand(rand∈[0,1],且為一個常數),如果rand

3) 根據一般反向學習公式,產生與N個候選解對應的N個反向候選解,其由式(21)表示：

X′i=Xmax+Xmin-Xi,Xi∈[Xmax,Xmin],

(21)

式(21)中,Xi是d維空間中的一個候選解,X′i是Xi的反向候選解;

4) 從候選解∪反向候選解2N個總體中選擇最好的N個個體組成新的群體。

本文的OBL算法具體實現：首先,在象群總體初始化中使用OBL,通過在整個搜索域中搜索解,提高收斂速率,避免陷入局部最優;其次,在總體解更新階段,使用OBL來檢查相反方向的更新是否優于當前更新。

2.2.3算法流程

改進象群算法(IEHO)流程圖如圖1所示。

圖1 改進象群算法(IEHO)流程圖Fig.1 Improved elephant algorithm (IEHO) flow chart

3 仿真實驗結果與分析

3.1 仿真條件

為驗證本文算法的有效性,仿真參數如下：偵察衛星8顆,部署高度為300 km,采用2×2×2的Walker星座模型,軌道傾角為55°。X波段地基雷達1個,L波段球載雷達1個,探測距離3 000～5 000 km,空基預警機1個,探測距離700～1 000 km,探測容量均為10。假設在某時刻有8個空襲目標,則傳感器對目標探測精度及能耗歸一化后如表1所示。

表1 傳感器對目標的探測能力及能耗Tab.1 Sensor target detection capability and energy consumption

3.2 算法改進前后傳感器調度方案求解對比分析

分別采用基本象群算法(EHO)和改進象群算法(IEHO)對調度方案進行求解。種群容量N=100,最大迭代次數Tmax=100,仿真結果對比如圖2所示,傳感器調度最優方案對比如表2所示。

表2 最優傳感器調度方案對比Tab.2 Comparison of optimal sensor scheduling schemes

圖2 改進前后算法適應度值對比Fig.2 Comparison of algorithm fitness values before and after algorithm improvement

從圖2可以看出,雖然兩個算法最終都收斂到定值,但是收斂速度和最終收斂的值存在差異性, IEHO算法收斂速度較快,在第10次達到穩定,能更快地得到更好的解,最終收斂到0.981,EHO算法收斂速度較慢,在第25次達到穩定最終收斂到0.786,這說明了IEHO算法的優越性。

從表2中可以看出,采用IEHO算法生成的方案中對于每個目標的探測跟蹤過程中傳感器利用率比較高,減少了傳感器資源浪費問題,并且適應度和能耗方面均優于EHO算法。

3.3 改進前后算法時間復雜度分析

上述兩種優化算法的計算復雜度主要取決于種群容量N、最大迭代次數T和搜索空間的總維數D。EHO算法的時間復雜度為O(N×D×T),基于EHO種群初始化方法的時間復雜度為O(N×D),利用正余弦算法更新搜索階段位置的時間復雜度為O(N×D×t),假設引用OBL反向學習實現時間為t,則此時算法的時間復雜度為O(N×D×T+t)=O(N×D×T)。由此可以看出IEHO算法增加了復雜度,但兩者處于同一數量級,計算成本沒什么差別,因此可以認為,在沒有額外成本的情況下,IEHO算法比EHO算法性能更好。

3.4 使用不同優化算法求解對比分析

為進一步說明IEHO算法的優勢,將本文算法與鯨魚優化算法(WOA)、黏菌優化算法(SMA)、基本象群算法(EHO)、粒子群優化算法(PSO)和布谷鳥算法(CSA),關于求解目標函數適應度值、算法運行時間以及探測精度進行對比。各算法參數設置如表3所示。

表3 算法參數設置Tab.3 Algorithm parameter setting

圖3中給出了上述不同算法求解目標函數的適應度值曲線。圖4給出了不同算法的迭代次數、運行時間和求解精度對比曲線。

圖3 不同算法適應度值對比Fig.3 Comparison of fitness values of different algorithms

圖4 不同算法迭代次數、運行時間和求解精度對比Fig.4 Comparison of fitness values of different algorithms

從圖3中可以看出,盡管所有的算法最終都收斂到定值,但是收斂速度和最終收斂的值存在差異。結合圖4可以看出IEHO算法比其他算法都能更快地得到更好的解,收斂速度最快,最終收斂到0.956,這說明了IEHO算法的優越性。EHO算法收斂速度最慢,最終收斂到0.698。主要是因為本文設計算法時將算法在每個階段存在的劣勢進行改進,優化了解的質量。

從圖4中不同算法的迭代次數、運行時間和求解精度對比結果可以注意到IEHO算法的優勢,IEHO算法的迭代次數、運行時間和求解精度均優于其他算法,與EHO算法相比,迭代次數減少39次,求解精度提高62%,運行時間提高90%。主要原因是IEHO算法通過利用正弦算法在搜索階段對算法中種群的位置進行更新,在開發階段通過反向學習更新算法位置方程來不斷尋找新的有前景的區域。這種方法有助于防止算法陷入局部最優,改進了EHO算法的局部搜索。

4 結論

本文提出基于改進象群算法的多傳感器調度方法。首先建立多傳感器調度多目標優化模型,其次通過交替使用正余弦機制和反向學習策略對象群算法的種群多樣性、搜索開發之間的平衡和容易陷入局部最優的問題進行了改進。通過仿真實驗,進一步驗證了改進后的算法具有較強的全局尋優能力和較快的收斂速度,在多傳感器調度應用中具有較高的可行性和實效性。