柯西變異的模擬退火鯨魚雷達(dá)資源調(diào)度算法

胡濱, 朱亞輝, 周延年

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

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

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

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

1 相關(guān)理論

1.1 多目標(biāo)的相控陣?yán)走_(dá)任務(wù)分配模型

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

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

1) 包圍獵物

當(dāng)座頭鯨確定最佳位置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ù)學(xué)模型包括:①鯨魚縮小包圍圈,即減小(3)式中的a值,達(dá)到收縮包圍效果；②鯨魚螺旋變換位置,即

(4)

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

3) 搜索捕食

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

式中,Xrand是一個隨機(jī)鯨魚的位置。

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

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

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

1) 引入非線性收斂因子

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

(7)

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

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

(8)

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

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

(11)

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

3 算法設(shè)計與仿真實(shí)驗分析

3.1 算法設(shè)計

針對相控陣?yán)走_(dá)的任務(wù)調(diào)度,應(yīng)用柯西變異的模擬退火鯨魚優(yōu)化算法進(jìn)行相控陣?yán)走_(dá)資源調(diào)度的設(shè)計,流程如圖2所示。

圖2 相控陣?yán)走_(dá)資源調(diào)度流程圖

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

(12)

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

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

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

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

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

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

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

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

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

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

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

3.2 仿真及結(jié)果分析

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

表2 雷達(dá)任務(wù)相關(guān)參數(shù)

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

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

圖3 3種算法的雷達(dá)任務(wù)調(diào)度序列對比圖

圖4展示了3種調(diào)度算法關(guān)于評價指標(biāo)TSR、ATOR、RV的對比。

圖4 3種算法的評價指標(biāo)曲線對比圖

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

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

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

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

4 結(jié) 論

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