柯西變異的模擬退火鯨魚雷達資源調度算法

胡濱, 朱亞輝, 周延年

1.西北工業(yè)大學 自動化學院, 陜西 西安 710072; 2.陜西學前師范學院 數(shù)學與統(tǒng)計學院, 陜西 西安 710100;3.空軍工程大學 防空反導學院, 陜西 西安 710043

雷達資源調度問題是指在雷達實際應用中，對雷達資源高效配置，其本質上是NP-hard問題。在雷達實際的應用環(huán)境中，根據(jù)雷達數(shù)據(jù)通道剩余的雷達資源與任務某些屬性的匹配程度把任務分配給最佳通道，不但能提升所獲得感知數(shù)據(jù)的質量，還能在一定程度上提高任務分配的效率。因此，李卓等[1]在滿足數(shù)據(jù)需要時，提出一種與位置相關的多任務分配算法。蔣偉進等[2]將任務所覆蓋區(qū)域劃分成若干個互不沖突的子區(qū)間，并求取各個子區(qū)間上基于地理位置的最佳用戶，最后把這些最佳用戶的并集作為最終的任務分配結果；王鑫等[3]提出基于位置的任務分配服務計算框架，最大程度地提高信息質量、減少執(zhí)行任務的預算和響應時間；仲崇權等[4]結合了生物啟發(fā)式搜索功能，提升了任務分配的性能；王從文等[5]采用工人信譽度和距離對任務進行分配；熊遠武等[6]將改進差分進化算法應用到多智能系統(tǒng)任務分配問題中；王卓昊等[7]提出根據(jù)不同任務的特點，將其分別分配給具備特定技能的用戶，降低任務分配的成本；孟迪等[8]采用壓縮感知方法對雷達任務進行調度。Komorniczak等[9]將任務優(yōu)先設定工作交給神經(jīng)網(wǎng)絡來完成，大幅減少了主觀經(jīng)驗在任務優(yōu)先級分配問題上的影響，具有一定的先進性；Vine[10]利用模糊邏輯來解決自適應任務調度器的沖突問題，通過比較任務的相對優(yōu)先級實現(xiàn)任務的自適應調度。

以上任務分配問題的關注點都集中在質量和成本兩方面。在實際應用中，相控雷達陣任務通道的時間是固定的。因此，在確保不丟失重要任務的前提下，如何將任務合理地分配給雷達，是資源調度系統(tǒng)需要解決的問題。

針對現(xiàn)有研究的不足，本文綜合考慮雷達時間資源、計算資源以及任務完成數(shù)量，從相控陣雷達數(shù)據(jù)通道與任務間的屬性匹配程度出發(fā)，對多目標的任務分配問題進行了完整建模。鯨魚優(yōu)化算法是一種群智能優(yōu)化算法，其主要特點是參數(shù)少、收斂快、易理解[11]。但該算法在全局尋優(yōu)和收斂精度方面仍有待進一步提高，本文提出了柯西變異的模擬退火鯨魚優(yōu)化算法，并將該方法應用到雷達資源調度模型中，仿真結果表明該算法在跟蹤任務調度率、平均時間偏移率和調度價值等方面都有較好的表現(xiàn)。

1 相關理論

1.1 多目標的相控陣雷達任務分配模型

假設U={u1,u2,…,um}與S={s1,s2,…,sn}分別代表雷達跟蹤通道集與任務集。其中,雷達通道ui=〈Pi,Li,Ti〉,i=1,…,m,Pi為雷達跟蹤通道號,Li為雷達通道i可分配的時間長度,Ti=〈Ki,Zi〉為雷達通道i所具備的資源信息,Ki為雷達任務種類集,Zi∈(0,1)為任務匹配程度集合;任務si={pi,di,ti,wi,ri,qi,fi,ui,Ei,ki},pi為任務的優(yōu)先級,di為波束的期望發(fā)射時間,ti為波束的發(fā)射持續(xù)時間,wi為波束在環(huán)境中的傳播時間,ri為波束的接收期持續(xù)時間,qi為任務的總駐留時間,fi為任務的執(zhí)行時間窗,ui為任務的執(zhí)行截止期,Ei為執(zhí)行該任務消耗的能量,ki為該任務對應的目標識別碼。

1.2 鯨魚優(yōu)化算法

1) 包圍獵物

當座頭鯨確定最佳位置X*(j)后,鯨魚種群向最佳位置靠近,迭代過程如下所示

式中:X(j+1)為第j+1次迭代后鯨魚種群的位置;A和C為系數(shù),計算公式如下所示

A=2a×r-a,C=2r

(3)

2) 發(fā)泡網(wǎng)攻擊

發(fā)泡網(wǎng)攻擊是鯨魚攻擊魚群的主要方式。其數(shù)學模型包括:①鯨魚縮小包圍圈,即減小(3)式中的a值,達到收縮包圍效果；②鯨魚螺旋變換位置,即

(4)

式中：l∈[-1,1],p∈[0,1]均為隨機數(shù);D′是頭鯨與當前最優(yōu)個體間的距離;b為常數(shù)。

3) 搜索捕食

鯨魚的搜索捕食過程建模如(5)～(6)式所示

式中,Xrand是一個隨機鯨魚的位置。

2 柯西變異的模擬退火鯨魚優(yōu)化算法

褚鼎立等[13]在鯨魚算法中引入自適應權重和模擬退火算法，提高了算法尋優(yōu)能力，但仍無法解決算法易陷入局部最優(yōu)問題。在文獻[14]的基礎上，本文引入柯西分布函數(shù)以提高算法局部尋優(yōu)能力，提出了柯西變異的模擬退火鯨魚優(yōu)化算法。圖1給出了算法的流程圖。

圖1 柯西變異的模擬退火鯨魚優(yōu)化算法流程圖

1) 引入非線性收斂因子

在傳統(tǒng)鯨魚算法中,公式(3)中的收斂因子a呈線性變化,導致整個算法收斂過慢。采用一種非線性收斂因子a(t),定義如(7)式所示

(7)

式中，tmax為最大迭代次數(shù)。

自適應權重ω(t)隨迭代次數(shù)動態(tài)變化如下所示

(8)

算法更新數(shù)學模型為

X(t+1)=

(9)

2) 加入柯西變異局部抖動

柯西概率密度函數(shù)與正態(tài)分布函數(shù)都可以作為擾動函數(shù),其中柯西概率密度函數(shù)具有較寬的分布范圍。故本文將柯西概率密度函數(shù)引入到鯨魚算法中,見公式(10)。

X*′(t)=X*(t)+X*(t)×Cauchy(1,0)

(10)

3) 模擬退火混合更新策略的鯨魚優(yōu)化算法

根據(jù)雷達的任務參數(shù)模型,將任務優(yōu)先級、任務期望發(fā)射時間、任務截止時間、任務執(zhí)行窗口、任務所在調度間隔的開始時間和結束時間以及任務的能量消耗這7個因素列為適應度函數(shù)的參數(shù)。經(jīng)過多次試驗,最終確定評價個體的適應度函數(shù)為

(11)

式中:pi為任務的優(yōu)先級;di為波束的期望發(fā)射時間;fi為任務的執(zhí)行時間窗;Ei為執(zhí)行該任務消耗的能量;B為任務的期望發(fā)射時間;D為任務的期望截至時間。

3 算法設計與仿真實驗分析

3.1 算法設計

針對相控陣雷達的任務調度,應用柯西變異的模擬退火鯨魚優(yōu)化算法進行相控陣雷達資源調度的設計,流程如圖2所示。

圖2 相控陣雷達資源調度流程圖

在算法的追蹤模式中,個體將進行速度和位置的更新,更新公式為

(12)

式中：L表示局部最優(yōu)值；G表示全局最優(yōu)值。

對于中近程警戒類雷達,其調度周期一般設定為120 ms,參數(shù)S=120 ms。同時考慮到在空域中進行搜索需要覆蓋一片空域,需要花費較多的搜索時間,設定系統(tǒng)仿真的時間T=60 s。對于地面防空雷達來說,雷達的輻射能量一般能夠滿足能量需求,設置其最大功率Ermax=120 kW。為了驗證算法的有效性,在單載頻脈沖的環(huán)境下進行驗證。根據(jù)相控陣雷達的任務不同,其設置參數(shù)如表1所示。

表1 防空雷達任務參數(shù)設定表

針對基于柯西變異的模擬退火鯨魚優(yōu)化算法,此處設置自適應分組率。分組率的計算公式為

式中,Mmax,Mmin分別為分組率M的最大值和最小值;I和tc分別表示最大和當前迭代次數(shù)。

為驗證算法的有效性,以跟蹤任務調度率(TSR)[14]、平均時間偏移率(ATOR)[15]、調度價值(RV)[16]為評估指標。TSR為調度成功的跟蹤任務數(shù)量與請求的跟蹤任務數(shù)量的比值,其計算公式為

式中,Ntrack,exe為調度成功的跟蹤任務數(shù)量,Ntrack,all為系統(tǒng)產(chǎn)生的跟蹤任務數(shù)量。

ATOR為已調度任務的實際執(zhí)行時間與請求執(zhí)行時間的偏移量與任務時間窗的比值,計算公式為

式中：Nexe為調度成功任務的數(shù)量;ai為任務的實際執(zhí)行時間;di為任務的期望波束發(fā)射時間;fi為任務的執(zhí)行時間窗。

RV為已調度任務的綜合優(yōu)先級之和,公式為

式中：Nexe為調度成功任務的數(shù)量;pi為任務的綜合優(yōu)先級。

3.2 仿真及結果分析

將駱駝算法(MCA)[17]、柯西變異的模擬退火鯨魚優(yōu)化算法(W-SA-WOA)和平衡優(yōu)化(EO)[18]調度算法在相同的調度環(huán)境下進行仿真。任務相關參數(shù)如表2所示。

表2 雷達任務相關參數(shù)

圖3為3種算法的雷達任務調度序列對比圖。圖中展示了不同數(shù)量的任務的時間分布情況。從圖中可以看出，EO算法在雷達資源調度過程中全局尋優(yōu)能力較弱，導致任務在分配期間出現(xiàn)了有些任務分配時間上的重合，由于雷達任務的不可分割性，這些重合的任務就會導致任務調度失敗，例如在圖3a)第900～1 000 ms之間有較多任務時間上重合。其次，也會導致某些時間上出現(xiàn)空閑，造成資源的浪費，例如在圖3a)中第400～500 ms之間出現(xiàn)了較多的空閑時間。

同理，對比發(fā)現(xiàn)MCA算法和W-SA-WOA算法都能夠執(zhí)行任務，但是MCA任務調度的執(zhí)行率不如W-SA-WOA算法。主要原因是W-SA-WOA算法在全局尋優(yōu)能力上更勝一籌，使得整個任務調度過程中，時間都可以被合理地利用。而MAC算法在雷達任務調度過程中時間軸上明顯有空閑的時間沒有被分配，例如圖3c)中的100,150,250,400 ms等時間點上明顯空閑。

圖3 3種算法的雷達任務調度序列對比圖

圖4展示了3種調度算法關于評價指標TSR、ATOR、RV的對比。

圖4 3種算法的評價指標曲線對比圖

由圖4a)可知，當目標數(shù)量增長至30時，W-SA-WOA算法的TSR接近100%，而MCA算法和EO算法開始出現(xiàn)任務丟失；隨著目標的增多，3種算法都開始出現(xiàn)任務丟棄。但在同一目標數(shù)量時，本文調度算法始終保持著最高的TSR。這表明W-SA-WOA能夠最大限度地利用時間資源，在固定的時間間隔內(nèi)調度更多的任務。

由圖4b)可知，當目標數(shù)為13時，W-SA-WOA調度得到的ATOR為12.94%，且隨著目標數(shù)量增加，始終保持最低的ATOR。當目標數(shù)量增加至120時，調度任務的ATOR為32.04%。由圖可知，相較于另外2種算方法，W-SA-WOA算法在高效地調度任務的同時，也能最大程度地減少任務的執(zhí)行時間偏移量。

由圖4c)可知，當目標數(shù)量較少(10個及以下)時，3種調度算法的RV相差較小。當目標數(shù)量增加時，W-SA-WOA算法的調度價值增長得更快，表明W-SA-WOA算法在高任務負載情況下仍有最好的任務調度能力。

綜合分析可知，W-SA-WOA算法在跟蹤任務調度率、平均時間偏移率和調度價值方面都優(yōu)于MCA和EO調度算法。事實上，仿真還記錄了不同優(yōu)先級任務的詳細執(zhí)行率，結果與上述結論一致。總的來說，與目前大多數(shù)基于MCA和EO及其衍生的算法相比，基于柯西變異的模擬退火鯨魚雷達資源調度算法在雷達任務調度問題上具有一定的優(yōu)勢。

4 結 論

雷達系統(tǒng)的任務調度一直是雷達資源調度領域的熱點問題。結合模擬退火算法對鯨魚優(yōu)化算法進行改進，并分別對搜索模式和跟蹤模式進行了優(yōu)化，最終形成了基于柯西變異的模擬退火鯨魚雷達資源調度的防空雷達任務調度算法。與比較流行的駱駝算法和平衡優(yōu)化算法相比，所提算法在跟蹤任務調度率、平均時間偏移率和調度價值等方面都有較好的表現(xiàn)，顯示了本文算法在解決雷達任務調度問題上的卓越能力。