基于改進(jìn)象群算法的多傳感器資源調(diào)度方法

李 琦,韋道知,謝家豪

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

0 引言

在當(dāng)前信息化、智能化作戰(zhàn)背景下,空天作戰(zhàn)能力迅猛發(fā)展。面對(duì)“隱身化、無(wú)人化、多域化、集群化、智能化”等新型空天目標(biāo)威脅,單個(gè)傳感器在探測(cè)范圍、探測(cè)信息類(lèi)別、探測(cè)精度等方面能力有限,很難完成對(duì)目標(biāo)信息的整體跟蹤探測(cè),更難以適應(yīng)復(fù)雜多變的作戰(zhàn)環(huán)境和作戰(zhàn)需求。在此情況下,需要多傳感器協(xié)同進(jìn)行優(yōu)化以發(fā)揮傳感器網(wǎng)絡(luò)最大效能。對(duì)于“傳感器協(xié)同探測(cè)” 來(lái)講,其核心就是根據(jù)某種度量指標(biāo)確定傳感器之間的最佳“協(xié)同方式”,在傳感器調(diào)度過(guò)程中也被稱(chēng)為“傳感器調(diào)度方案”[1-4]。

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

上述文獻(xiàn)中,雖然調(diào)度算法在收斂性或穩(wěn)定性等某一方面得到了改善,但在多目標(biāo)、復(fù)雜和復(fù)合多傳感器調(diào)度優(yōu)化問(wèn)題中,調(diào)度模型構(gòu)建考慮因素不全面,缺少說(shuō)服力;并且在智能搜索算法運(yùn)用中,由于算法本身的隨機(jī)特征,存在控制參數(shù)設(shè)置過(guò)多、計(jì)算復(fù)雜、容易陷入局部最優(yōu)等缺陷。針對(duì)以上問(wèn)題,由于EHO算法具有全局優(yōu)化能力、控制參數(shù)數(shù)量少、實(shí)現(xiàn)策略簡(jiǎn)單等優(yōu)點(diǎn),本文選擇將EHO算法和反向?qū)W習(xí)機(jī)制(OBL)[22]及正余弦算法(SCA)[23]相結(jié)合,提出一種基于IEHO算法的多傳感器調(diào)度方法,并將其應(yīng)用到求解傳感器調(diào)度模型中。

1 傳感器調(diào)度模型建立

1.1 決策變量

(1)

(2)

(3)

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

(4)

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

1) 傳感器探測(cè)效益最大

為提高傳感器的探測(cè)跟蹤效果,在對(duì)目標(biāo)進(jìn)行探測(cè)跟蹤時(shí),應(yīng)選擇探測(cè)跟蹤效益最大的傳感器執(zhí)行任務(wù),在進(jìn)行多傳感器調(diào)度建模過(guò)程中,由于不同類(lèi)型的傳感器探測(cè)影響因素不同,接收到的目標(biāo)信息不同,本文以傳感器和目標(biāo)之間的距離以及傳感器的探測(cè)角度來(lái)研究傳感器探測(cè)效益。

傳感器對(duì)目標(biāo)的探測(cè)效益函數(shù)可定義為

(5)

(6)

2) 傳感器負(fù)載最小

當(dāng)傳感器i對(duì)目標(biāo)j探測(cè)全過(guò)程中,傳感器完成探測(cè)跟蹤任務(wù)的負(fù)載為

(7)

在傳感器調(diào)度時(shí)間區(qū)間ΔT內(nèi),各類(lèi)傳感器的總負(fù)載為

(8)

3) 傳感器交接次數(shù)最少

當(dāng)目標(biāo)的運(yùn)動(dòng)超過(guò)傳感器的探測(cè)范圍或者傳感器狀態(tài)發(fā)生改變時(shí),需要考慮在調(diào)度區(qū)間內(nèi)傳感器之間的交接。對(duì)調(diào)度區(qū)間內(nèi)的傳感器的交接次數(shù)進(jìn)行統(tǒng)計(jì)有利于判斷傳感器是否存在跟丟目標(biāo)的情況,將相鄰兩個(gè)傳感器的探測(cè)跟蹤矩陣對(duì)應(yīng)元素進(jìn)行“異或”邏輯運(yùn)算,可以計(jì)算出發(fā)生狀態(tài)改變的傳感器數(shù)目。

(9)

1.3 約束條件

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

本文建立的模型的求解是指在調(diào)度區(qū)間ΔT內(nèi)隨著傳感器與目標(biāo)的可視化情況對(duì)應(yīng)生成的傳感器對(duì)目標(biāo)探測(cè)跟蹤與否的方案,故矩陣t與s內(nèi)的對(duì)應(yīng)元素存在如下關(guān)系：

(10)

2) 傳感器觀測(cè)時(shí)間約束

傳感器在執(zhí)行探測(cè)跟蹤任務(wù)時(shí),觀測(cè)時(shí)間應(yīng)在調(diào)度區(qū)間內(nèi),即

(11)

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

不同傳感器因其自身能力與容量設(shè)計(jì)存在差異,導(dǎo)致每個(gè)傳感器的探測(cè)跟蹤目標(biāo)的數(shù)量不能超過(guò)其最大的探測(cè)跟蹤能力,即

(12)

4) 傳感器探測(cè)跟蹤目標(biāo)最大數(shù)量約束

為防止出現(xiàn)多個(gè)傳感器同時(shí)探測(cè)跟蹤一個(gè)目標(biāo),根據(jù)不同傳感器的性能要求,要在實(shí)現(xiàn)對(duì)目標(biāo)的連續(xù)探測(cè)和穩(wěn)定跟蹤的同時(shí)避免傳感器資源的浪費(fèi),應(yīng)約束傳感器資源的最大數(shù)量。即

(13)

1.4 調(diào)度模型

在前面建立的目標(biāo)函數(shù)和約束條件的基礎(chǔ)上,建立如下多傳感器調(diào)度多目標(biāo)的調(diào)度模型：

(14)

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

2 多傳感器調(diào)度算法

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

1) 部落更新操作

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

來(lái)自不同部落的大象在其女族長(zhǎng)的領(lǐng)導(dǎo)下一起生活,其他大象的位置都根據(jù)女族長(zhǎng)和自身的位置進(jìn)行更新,位置更新公式如式(15)所示。女族長(zhǎng)的位置根據(jù)部落中心的位置進(jìn)行更新,由式(16)表示。

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

(15)

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

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

(16)

式(16)中,β設(shè)置為 0 和 1 之間的隨機(jī)數(shù), 它控制著部落中心對(duì)女族長(zhǎng)位置的影響,其中部落c中心被定義為

(17)

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

2) 部落分離操作

每個(gè)部落c中適應(yīng)度最差的個(gè)體在當(dāng)它成熟時(shí)將遠(yuǎn)離部落,在空間中進(jìn)行隨機(jī)搜索以增加全局搜索性能,它們的位置更新表達(dá)式為

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

(18)

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

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

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

2.2.1正余弦算法(SCA)

正余弦算法是Seyedali于2016年提出的利用正余弦函數(shù)的數(shù)學(xué)模型使解震蕩性地趨于最優(yōu)解的一種方法[20]。針對(duì)算法分離操作步驟中適應(yīng)度最差個(gè)體的位置隨機(jī)替換,采用正余弦算法使適應(yīng)度最差個(gè)體的每個(gè)位置都采用了信息正余弦函數(shù)共享策略進(jìn)行替換,使其總是在當(dāng)前局部最優(yōu)解周?chē)挛恢?這樣能夠保證搜索不斷趨向于空間的最佳區(qū)域,獲取更優(yōu)解。

其位置更新方程為

(19)

式(19)中,γ2∈(0,2π),γ3∈(0,2),γ4∈(0,1)為均勻分布的隨機(jī)數(shù);xbest,c為當(dāng)前最優(yōu)解個(gè)體的位置;γ1為控制參數(shù),表示為

(20)

式(20)中,a為一個(gè)常數(shù),t為當(dāng)前迭代次數(shù),Tmax為最大化迭代次數(shù)。

2.2.2反向?qū)W習(xí)策略(OBL)

反向?qū)W習(xí)策略是由Tizhoosh等人提出的用于改進(jìn)元啟發(fā)式算法的收斂性,找到優(yōu)化問(wèn)題全局最優(yōu)解的一種重要方法[21]。它是通過(guò)反向?qū)W習(xí)產(chǎn)生候選解的反向位置,隨后采取貪婪策略從當(dāng)前候選解和反向候選解中尋找最優(yōu)解決方案,求解思路如下：

1) 更新當(dāng)前的搜索區(qū)域區(qū)間;

2) 設(shè)定一個(gè)反向?qū)W習(xí)跳變率P(P0∈[0,1],且為一個(gè)常數(shù)),產(chǎn)生一個(gè)隨機(jī)數(shù)rand(rand∈[0,1],且為一個(gè)常數(shù)),如果rand

3) 根據(jù)一般反向?qū)W習(xí)公式,產(chǎn)生與N個(gè)候選解對(duì)應(yīng)的N個(gè)反向候選解,其由式(21)表示：

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

(21)

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

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

本文的OBL算法具體實(shí)現(xiàn)：首先,在象群總體初始化中使用OBL,通過(guò)在整個(gè)搜索域中搜索解,提高收斂速率,避免陷入局部最優(yōu);其次,在總體解更新階段,使用OBL來(lái)檢查相反方向的更新是否優(yōu)于當(dāng)前更新。

2.2.3算法流程

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

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

3 仿真實(shí)驗(yàn)結(jié)果與分析

3.1 仿真條件

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

表1 傳感器對(duì)目標(biāo)的探測(cè)能力及能耗Tab.1 Sensor target detection capability and energy consumption

3.2 算法改進(jìn)前后傳感器調(diào)度方案求解對(duì)比分析

分別采用基本象群算法(EHO)和改進(jìn)象群算法(IEHO)對(duì)調(diào)度方案進(jìn)行求解。種群容量N=100,最大迭代次數(shù)Tmax=100,仿真結(jié)果對(duì)比如圖2所示,傳感器調(diào)度最優(yōu)方案對(duì)比如表2所示。

表2 最優(yōu)傳感器調(diào)度方案對(duì)比Tab.2 Comparison of optimal sensor scheduling schemes

圖2 改進(jìn)前后算法適應(yīng)度值對(duì)比Fig.2 Comparison of algorithm fitness values before and after algorithm improvement

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

從表2中可以看出,采用IEHO算法生成的方案中對(duì)于每個(gè)目標(biāo)的探測(cè)跟蹤過(guò)程中傳感器利用率比較高,減少了傳感器資源浪費(fèi)問(wèn)題,并且適應(yīng)度和能耗方面均優(yōu)于EHO算法。

3.3 改進(jìn)前后算法時(shí)間復(fù)雜度分析

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

3.4 使用不同優(yōu)化算法求解對(duì)比分析

為進(jìn)一步說(shuō)明IEHO算法的優(yōu)勢(shì),將本文算法與鯨魚(yú)優(yōu)化算法(WOA)、黏菌優(yōu)化算法(SMA)、基本象群算法(EHO)、粒子群優(yōu)化算法(PSO)和布谷鳥(niǎo)算法(CSA),關(guān)于求解目標(biāo)函數(shù)適應(yīng)度值、算法運(yùn)行時(shí)間以及探測(cè)精度進(jìn)行對(duì)比。各算法參數(shù)設(shè)置如表3所示。

表3 算法參數(shù)設(shè)置Tab.3 Algorithm parameter setting

圖3中給出了上述不同算法求解目標(biāo)函數(shù)的適應(yīng)度值曲線。圖4給出了不同算法的迭代次數(shù)、運(yùn)行時(shí)間和求解精度對(duì)比曲線。

圖3 不同算法適應(yīng)度值對(duì)比Fig.3 Comparison of fitness values of different algorithms

圖4 不同算法迭代次數(shù)、運(yùn)行時(shí)間和求解精度對(duì)比Fig.4 Comparison of fitness values of different algorithms

從圖3中可以看出,盡管所有的算法最終都收斂到定值,但是收斂速度和最終收斂的值存在差異。結(jié)合圖4可以看出IEHO算法比其他算法都能更快地得到更好的解,收斂速度最快,最終收斂到0.956,這說(shuō)明了IEHO算法的優(yōu)越性。EHO算法收斂速度最慢,最終收斂到0.698。主要是因?yàn)楸疚脑O(shè)計(jì)算法時(shí)將算法在每個(gè)階段存在的劣勢(shì)進(jìn)行改進(jìn),優(yōu)化了解的質(zhì)量。

從圖4中不同算法的迭代次數(shù)、運(yùn)行時(shí)間和求解精度對(duì)比結(jié)果可以注意到IEHO算法的優(yōu)勢(shì),IEHO算法的迭代次數(shù)、運(yùn)行時(shí)間和求解精度均優(yōu)于其他算法,與EHO算法相比,迭代次數(shù)減少39次,求解精度提高62%,運(yùn)行時(shí)間提高90%。主要原因是IEHO算法通過(guò)利用正弦算法在搜索階段對(duì)算法中種群的位置進(jìn)行更新,在開(kāi)發(fā)階段通過(guò)反向?qū)W習(xí)更新算法位置方程來(lái)不斷尋找新的有前景的區(qū)域。這種方法有助于防止算法陷入局部最優(yōu),改進(jìn)了EHO算法的局部搜索。

4 結(jié)論

本文提出基于改進(jìn)象群算法的多傳感器調(diào)度方法。首先建立多傳感器調(diào)度多目標(biāo)優(yōu)化模型,其次通過(guò)交替使用正余弦機(jī)制和反向?qū)W習(xí)策略對(duì)象群算法的種群多樣性、搜索開(kāi)發(fā)之間的平衡和容易陷入局部最優(yōu)的問(wèn)題進(jìn)行了改進(jìn)。通過(guò)仿真實(shí)驗(yàn),進(jìn)一步驗(yàn)證了改進(jìn)后的算法具有較強(qiáng)的全局尋優(yōu)能力和較快的收斂速度,在多傳感器調(diào)度應(yīng)用中具有較高的可行性和實(shí)效性。