基于混合自適應(yīng)遺傳算法的相控陣?yán)走_(dá)任務(wù)調(diào)度

張浩為， 謝軍偉， 張昭建， 宗彬鋒， 陳唐軍

(1.空軍工程大學(xué) 防空反導(dǎo)學(xué)院， 陜西 西安 710051；2.94710部隊(duì)， 江蘇 無錫 214000；3.94921部隊(duì)， 福建 晉江 362200)

基于混合自適應(yīng)遺傳算法的相控陣?yán)走_(dá)任務(wù)調(diào)度

張浩為1， 謝軍偉1， 張昭建1， 宗彬鋒2， 陳唐軍3

(1.空軍工程大學(xué) 防空反導(dǎo)學(xué)院， 陜西 西安 710051；2.94710部隊(duì)， 江蘇 無錫 214000；3.94921部隊(duì)， 福建 晉江 362200)

針對(duì)相控陣?yán)走_(dá)任務(wù)調(diào)度NP難題，提出一種混合自適應(yīng)遺傳算法進(jìn)行求解。在構(gòu)建相控陣?yán)走_(dá)任務(wù)調(diào)度優(yōu)化模型的基礎(chǔ)上，通過混沌理論優(yōu)化初始種群，采取精英保留和混合排名的選擇策略以及設(shè)計(jì)自適應(yīng)的交叉、變異算子來提升算法的搜索性能；在自適應(yīng)遺傳算法的框架下，提出啟發(fā)式脈沖交錯(cuò)算法，以利用雷達(dá)任務(wù)中的等待期來交錯(cuò)執(zhí)行其他任務(wù)的發(fā)射期或接收期。仿真結(jié)果表明：相比于基于遺傳算法的調(diào)度方法，改進(jìn)算法的搜索效率更高、結(jié)果更優(yōu)；相比于傳統(tǒng)啟發(fā)式算法，改進(jìn)算法的調(diào)度成功率、時(shí)間利用率和實(shí)現(xiàn)價(jià)值率均得到了提升，并有效降低了時(shí)間偏移率。

兵器科學(xué)與技術(shù)； 相控陣?yán)走_(dá)； 調(diào)度； 自適應(yīng)遺傳算法； 混沌理論； 脈沖交錯(cuò)

Abstract: A hybrid adaptive genetic algorithm is proposed for the task scheduling of phased array radar. An optimal scheduling model for phased array radar is established. The performance and efficiency of the algorithm are improved by optimizing the initial population by the chaos theory, adopting the selection strategy of elite reservation and mixed ranking, and designing the adaptive crossover and mutation operators. A heuristic pulse interleaving algorithm is presented based on the adaptive genetic algorithm. It could utilize the waiting period in a task to execute the transmitting period or receiving period of other task. The simulated results demonstrate that the proposed algorithm provides better results and search solutions more quickly than the genetic algorithm. Moreover, compared with the heuristic scheduling algorithm, the proposed algorithm improves the scheduling success ratio, time utilization ratio and high value ratio, and decreases the average time shift ratio efficiently.

Key words: ordnance science and technology； phased array radar; scheduling; adaptive genetic algorithm; chaos theory; pulse interleaving

0 引言

相控陣?yán)走_(dá)因其對(duì)時(shí)間資源的高效利用，可以實(shí)現(xiàn)微秒量級(jí)的波束捷變，進(jìn)而同時(shí)承擔(dān)搜索、跟蹤和制導(dǎo)等多種任務(wù)。因此，研究在時(shí)間資源有限[1]的前提下實(shí)現(xiàn)任務(wù)的最優(yōu)調(diào)度，對(duì)充分發(fā)揮相控陣?yán)走_(dá)的多功能潛力具有重要意義。

大量研究結(jié)果表明，相控陣?yán)走_(dá)中的任務(wù)調(diào)度問題屬于NP難題，最優(yōu)解難以獲得。目前，解決該類問題的方法可分為啟發(fā)式算法和智能算法。前者通過預(yù)先設(shè)定的優(yōu)先級(jí)規(guī)則，對(duì)滿足條件的任務(wù)優(yōu)先進(jìn)行調(diào)度。典型的有：截止期最早最優(yōu)先(EDF)算法[2-3]、價(jià)值最高最優(yōu)先算法[4-5]等。但在調(diào)度過程中，優(yōu)先級(jí)僅由任務(wù)的單個(gè)屬性來確定是不夠的。文獻(xiàn)[6-7]依據(jù)任務(wù)序列和相關(guān)參數(shù)，將請(qǐng)求任務(wù)劃分為多個(gè)隊(duì)列，在每個(gè)隊(duì)列中運(yùn)用先入先出(FIFO)原則或截止期優(yōu)先原則進(jìn)行調(diào)度。文獻(xiàn)[8-12]綜合了任務(wù)的工作方式和截止期兩種因素，以確定任務(wù)的優(yōu)先等級(jí)，分別提出了工作方式優(yōu)先級(jí)加截止期(HPEDF)算法和截止期加工作方式優(yōu)先級(jí)(EDHPF)算法。文獻(xiàn)[13-14]進(jìn)一步考慮了任務(wù)調(diào)度的及時(shí)性，提出了基于調(diào)度收益的算法。文獻(xiàn)[15-16]通過引入目標(biāo)威脅度，提出了基于動(dòng)態(tài)優(yōu)先級(jí)的調(diào)度算法。文獻(xiàn)[17-18]提出了可變駐留時(shí)間的概念，并運(yùn)用多重嵌套的啟發(fā)式算法進(jìn)行任務(wù)調(diào)度。啟發(fā)式算法計(jì)算簡(jiǎn)便、復(fù)雜度低，但當(dāng)問題的規(guī)模較大時(shí)，所求得的結(jié)果往往與最優(yōu)解相差甚遠(yuǎn)。相比較而言，智能算法可以憑借其群體搜索、迭代進(jìn)化等優(yōu)勢(shì)，求得更佳結(jié)果。文獻(xiàn)[19-25]將改進(jìn)的遺傳算法應(yīng)用于該問題中，增強(qiáng)了任務(wù)調(diào)度的穩(wěn)健性和魯棒性。雖然上述方法多樣，但尚存在如下不足：1)部分算法[1-3，5-10，15-17,21-24]沒有考慮任務(wù)的內(nèi)部結(jié)構(gòu)，限制了任務(wù)中等待期的利用；2)雖然部分文獻(xiàn)[4，11-14，18-20]運(yùn)用了交錯(cuò)調(diào)度技術(shù)，但沒有構(gòu)建任務(wù)調(diào)度的優(yōu)化模型或僅構(gòu)建了單一目標(biāo)函數(shù)，難以保證算法在多方面的調(diào)度性能；3)大部分文獻(xiàn)[1-18，21-24]僅采用單一算法進(jìn)行求解，沒有兼顧兩類算法的優(yōu)勢(shì)。

因此，本文提出一種混合自適應(yīng)遺傳算法來求解相控陣?yán)走_(dá)的任務(wù)調(diào)度問題。該算法運(yùn)用交錯(cuò)調(diào)度技術(shù)，在多方面提供良好的調(diào)度性能的同時(shí)，可有效提升收斂速度。首先，以時(shí)間和能量為約束條件，綜合任務(wù)調(diào)度的3大原則，建立相控陣?yán)走_(dá)任務(wù)調(diào)度的最優(yōu)化模型；其次，提出改進(jìn)的自適應(yīng)遺傳算法并進(jìn)行求解。在傳統(tǒng)遺傳算法的基礎(chǔ)上，引入混沌理論優(yōu)化初始種群，使種群初值具有良好的隨機(jī)性和遍歷性；采用精英保留和混合排名選擇策略，以避免算法過早收斂于局部最優(yōu)；設(shè)計(jì)了自適應(yīng)交叉算子和變異算子，以提升算法的搜索效率。在智能算法的框架下，提出了啟發(fā)式脈沖交錯(cuò)算法，以進(jìn)一步提升時(shí)間的利用率。最后通過一系列仿真實(shí)驗(yàn)證明了該算法的有效性。

1 基本理論建模

1.1 雷達(dá)任務(wù)模型

圖1 相控陣?yán)走_(dá)的任務(wù)調(diào)度框架Fig.1 Overall scheduling structure of phased array radar

圖1為相控陣?yán)走_(dá)的任務(wù)調(diào)度框架。由圖1可知，當(dāng)雷達(dá)捕獲目標(biāo)后，調(diào)度算法將根據(jù)任務(wù)的請(qǐng)求狀態(tài)以及雷達(dá)的自身資源來調(diào)度任務(wù)。調(diào)度結(jié)果可分為執(zhí)行隊(duì)列、延時(shí)隊(duì)列和刪除隊(duì)列。其中，延時(shí)隊(duì)列中的任務(wù)將被再次送往請(qǐng)求隊(duì)列，以期在后續(xù)的時(shí)間得到執(zhí)行，執(zhí)行隊(duì)列和刪除隊(duì)列中的任務(wù)將分別被執(zhí)行和刪除。雷達(dá)任務(wù)的請(qǐng)求順序一般為：搜索—確認(rèn)—跟蹤(—失跟處理—跟蹤維持)。跟蹤任務(wù)的種類可具體分為精跟、普跟和監(jiān)視3種。圖2給出了相控陣?yán)走_(dá)的任務(wù)模型，從中可知，雷達(dá)任務(wù)主要由發(fā)射期、等待期和接收期3部分構(gòu)成。第i個(gè)相控陣?yán)走_(dá)任務(wù)[26-27]可以描述為

Ti={Pi,tai,txi,twi,tri,Pti,dwi,wi,tdi,Δti}，

(1)

式中：Pi為任務(wù)優(yōu)先級(jí)；tai為任務(wù)請(qǐng)求執(zhí)行時(shí)刻；txi為任務(wù)發(fā)射期持續(xù)時(shí)間；twi為等待期，長(zhǎng)短由目標(biāo)的距離決定；tri為接收期持續(xù)時(shí)間；Pti為任務(wù)執(zhí)行完畢時(shí)消耗的功率；dwi為任務(wù)駐留時(shí)間；wi為任務(wù)時(shí)間窗；tdi為任務(wù)截止期；Δti為相鄰兩次任務(wù)之間的時(shí)間間隔。其中任務(wù)的駐留時(shí)間滿足：

dwi=txi+twi+tri，

(2)

任務(wù)的截止期滿足：

tdi=tai+wi，

(3)

相鄰兩次任務(wù)間請(qǐng)求時(shí)刻的關(guān)系為

tai=tei-1+Δti，

(4)

tei-1為上一次任務(wù)的成功執(zhí)行時(shí)刻。

圖2 相控陣?yán)走_(dá)的任務(wù)模型Fig.2 Task model of phased array radar

1.2 資源約束模型

1.2.1 時(shí)間資源約束

調(diào)度間隔(SI)是相控陣?yán)走_(dá)進(jìn)行任務(wù)調(diào)度的基本單位。在一個(gè)SI內(nèi)，雷達(dá)要處理前一個(gè)SI內(nèi)的回波，并決定下一SI內(nèi)的任務(wù)執(zhí)行序列[26-27]。在一個(gè)SI內(nèi)，成功執(zhí)行的N1個(gè)任務(wù)在滿足各自的截止期約束的同時(shí)，還需滿足：

(5)

式中：SI為SI時(shí)長(zhǎng)。由于任務(wù)在發(fā)射期和接收期內(nèi)不能被中斷，成功執(zhí)行的N1個(gè)任務(wù)還需要滿足：

(6)

(6)式表明，任務(wù)在發(fā)射期和接收期是不可搶占的，但等待期可以被有效利用。若任務(wù)不滿足執(zhí)行要求，則會(huì)被延時(shí)執(zhí)行或被刪除。

1.2.2 能量資源約束

(7)

式中：P(x)為雷達(dá)的功率函數(shù)；τ為回退參數(shù)，表示雷達(dá)的散熱性能。

1.3 目標(biāo)函數(shù)構(gòu)建

雷達(dá)在調(diào)度任務(wù)過程中，應(yīng)遵循以下幾點(diǎn)原則：1)重要性原則，高優(yōu)先級(jí)的任務(wù)應(yīng)優(yōu)先得到調(diào)度；2)緊急性原則，更加緊急的任務(wù)應(yīng)優(yōu)先得到調(diào)度；3)及時(shí)性原則，任務(wù)的實(shí)際執(zhí)行時(shí)刻應(yīng)盡可能接近其請(qǐng)求時(shí)刻[27]。因此，綜合任務(wù)調(diào)度的三原則，構(gòu)建(8)式所示的調(diào)度目標(biāo)函數(shù)：

o(P,ta,w,ts,te)=
[o1(P)+o2(ta,w,ts)]o3(te,ta,w)，

(8)

式中：o1(P)為任務(wù)的重要性函數(shù)；o2(ta,w,ts)為任務(wù)的緊迫性函數(shù)；o3(te,ta,w)為任務(wù)執(zhí)行的及時(shí)性函數(shù)；ts為SI開始時(shí)刻。(8)式構(gòu)建的目標(biāo)函數(shù)考慮了任務(wù)調(diào)度過程中的多項(xiàng)原則，從而保證了算法在多方面具有較佳的性能。

假設(shè)在一個(gè)SI內(nèi)共有N個(gè)請(qǐng)求任務(wù)，經(jīng)調(diào)度后執(zhí)行、延時(shí)和刪除隊(duì)列中的任務(wù)個(gè)數(shù)分別為N1、N2和N3，則有N=N1+N2+N3. 因此相控陣?yán)走_(dá)的任務(wù)調(diào)度優(yōu)化模型[27]可表示為

(9)

式中：te為SI結(jié)束時(shí)刻；前4個(gè)條件為執(zhí)行任務(wù)的約束，后2個(gè)條件分別對(duì)應(yīng)延時(shí)和刪除任務(wù)的約束。從中可以看出，相控陣?yán)走_(dá)調(diào)度問題是NP難題，需要采取高效的算法對(duì)問題進(jìn)行求解。

2 混沌自適應(yīng)遺傳算法

相比于其他智能算法而言，遺傳算法具有無需先驗(yàn)知識(shí)和良好的全局尋優(yōu)能力等優(yōu)勢(shì)，在非線性規(guī)劃、約束求解等方面已經(jīng)得到廣泛應(yīng)用[28]。但傳統(tǒng)遺傳算法的搜索效率低下，因此本文根據(jù)所設(shè)計(jì)的目標(biāo)函數(shù)，采用改進(jìn)的遺傳算法對(duì)相控陣?yán)走_(dá)任務(wù)調(diào)度問題進(jìn)行求解。

2.1 混沌理論初始化

遺傳算法模擬了自然界中生物的進(jìn)化特性，種群通過不斷地進(jìn)行選擇、交叉和變異操作完成優(yōu)勝劣汰，從而找到目標(biāo)函數(shù)的最優(yōu)解。在運(yùn)用遺傳算法進(jìn)行求解時(shí)，首先應(yīng)對(duì)種群進(jìn)行初始化。在傳統(tǒng)遺傳算法中，種群初始值是隨機(jī)產(chǎn)生的，在求解過程中容易陷入局部極值。而混沌序列具有良好的隨機(jī)性和遍歷性等優(yōu)點(diǎn)，可以作為避免算法在搜索過程中陷入局部極值的一種優(yōu)化機(jī)制。因此，本文采用Logistic方程對(duì)種群進(jìn)行混沌初始化：

λk+1=μλk(1-λk)，

(10)

式中：λk為混沌變量λ迭代k次后的結(jié)果，λ[0,1]；μ為混沌狀態(tài)控制參數(shù)，μ[0,4]. 當(dāng)μ=4且λ?{0.25,0.50,0.75}時(shí)，產(chǎn)生的初始序列值將具有完全混沌特性[27，29]。

2.2 選擇算子

選擇操作、交叉操作和變異操作是遺傳算法中的3個(gè)主要步驟。通過以上3個(gè)步驟，用新的優(yōu)異個(gè)體(候選調(diào)度序列)替換較差的個(gè)體，可以完成種群的更新，促使算法找到最優(yōu)解。在進(jìn)行選擇操作時(shí)，采用精英保留和混合排名相結(jié)合的策略：設(shè)算法中的種群規(guī)模為M，對(duì)種群中的個(gè)體按照適應(yīng)值(在此為(8)式)由大到小進(jìn)行排序后，選擇前m個(gè)適應(yīng)值最佳的個(gè)體直接遺傳給下一代；其余的M-m個(gè)個(gè)體中第i個(gè)個(gè)體按照下式計(jì)算適應(yīng)度：

(11)

然后，采用輪盤賭的方式確定父本。第i個(gè)個(gè)體被選擇的概率可計(jì)算為

(12)

其中，精英保留策略是遺傳算法收斂的重要條件；而采用上述混合排名選擇策略，部分適應(yīng)值較差的個(gè)體得以保留，從而保證了種群的多樣性。

2.3 自適應(yīng)交叉、變異算子

交叉和變異操作可以保證種群個(gè)體良好的遺傳性和種群的多樣性。其中：交叉操作是從兩個(gè)被選擇的父代中產(chǎn)生兩個(gè)子代；變異操作是從一個(gè)被選擇的父代中產(chǎn)生一個(gè)子代。交叉概率pc和變異概率pm在兩項(xiàng)操作中起著重要作用：當(dāng)概率較大時(shí)，算法的搜索速度較快，但容易過早收斂；當(dāng)概率較小時(shí)，搜索出全局最優(yōu)值的概率較大，但算法的搜索速度較慢。在此，本文提出一種根據(jù)適應(yīng)值動(dòng)態(tài)調(diào)整的交叉、變異概率調(diào)節(jié)公式：

(13)

(14)

式中：pc0和pc1為交叉概率的初始調(diào)節(jié)參數(shù)，決定了交叉概率的下界和上界，可以根據(jù)大量試驗(yàn)得出；f為個(gè)體適應(yīng)值；fmax為當(dāng)前種群中個(gè)體的最佳適應(yīng)值；fmin為種群中個(gè)體的最差適應(yīng)值；fa為種群中個(gè)體的平均適應(yīng)值。(14)式中的各參數(shù)與(13)式相似。從(13)式和(14)式可以看出：當(dāng)種群中個(gè)體的適應(yīng)值低于種群的平均適應(yīng)值時(shí)，個(gè)體將以較大的概率發(fā)生改變；當(dāng)個(gè)體的適應(yīng)值高于種群的平均適應(yīng)值時(shí)，個(gè)體將以較大的概率得以保留。通過(13)式、(14)式可以使得算法的交叉、變異概率得以動(dòng)態(tài)調(diào)整，從而提升算法的搜索效率。

2.4 啟發(fā)式脈沖交錯(cuò)調(diào)度算法

如前所述，脈沖交錯(cuò)技術(shù)可以有效提升系統(tǒng)的時(shí)間利用率，但也使任務(wù)的調(diào)度分析更加復(fù)雜。圖3所示為相控陣?yán)走_(dá)任務(wù)交錯(cuò)執(zhí)行的兩種方式，從中可以看出，交錯(cuò)執(zhí)行的兩個(gè)任務(wù)需要滿足(15)式所示的時(shí)間約束：

(15)

tw1≥tx2+tw2+tr2.

(16)

圖3 相控陣?yán)走_(dá)任務(wù)交錯(cuò)執(zhí)行的兩種方式Fig.3 Two ways of task interleaving of phased array radar

(15)式和(16)式分別對(duì)應(yīng)圖3(a)和圖3(b). 同時(shí)，交錯(cuò)執(zhí)行的任務(wù)還需要滿足能量資源的約束。鑒于交錯(cuò)調(diào)度的復(fù)雜性，本文提出一種啟發(fā)式任務(wù)交錯(cuò)調(diào)度分析方法如下：

在一個(gè)SI內(nèi)，初始化剩余時(shí)間軸[ts,te]和功率指針Pt0. 若在該SI內(nèi)存在N個(gè)請(qǐng)求任務(wù)，則算法中個(gè)體的基因個(gè)數(shù)為N. 其中每個(gè)基因代表了對(duì)應(yīng)任務(wù)的候選執(zhí)行時(shí)刻。對(duì)于每個(gè)個(gè)體的所有基因，按照FIFO原則排序后，分別記為任務(wù)1，2，3，…，N，對(duì)任務(wù)1的發(fā)射期進(jìn)行時(shí)間資源約束分析：

(17)

若發(fā)射期不滿足時(shí)間資源約束，則根據(jù)(9)式中的延時(shí)或刪除條件將任務(wù)送入相應(yīng)鏈表。若發(fā)射期滿足時(shí)間資源約束，則更新剩余時(shí)間軸為[ts,te1]，[te1+tx1,te]，并繼續(xù)分析任務(wù)1的接收期能否滿足剩余時(shí)間資源約束：

(18)

若接收期不滿足剩余時(shí)間資源約束，則根據(jù) (9) 式中的延時(shí)或刪除條件將任務(wù)送入相應(yīng)鏈表，并重置剩余時(shí)間軸為[ts,te]. 若接收期滿足剩余時(shí)間資源約束，則繼續(xù)分析任務(wù)1能否滿足(19)式的能量資源約束：

(19)

若任務(wù)1不能滿足能量資源約束，則根據(jù)(9)式中的延時(shí)或刪除條件將任務(wù)送入相應(yīng)鏈表，并重置剩余時(shí)間軸為[ts,te]. 若任務(wù)1能夠滿足能量資源約束，則更新剩余時(shí)間軸為[ts,te1]，[te1+tx1,te1+tx1+tw1]，[te1+tx1+tw1+tr1,te]，并更新功率指針為

Pt0=Pt0e-tx1/τ+Pt1(1-e-tx1/τ).

(20)

然后，按照如上時(shí)間資源約束分析和能量資源約束分析方式，對(duì)剩余的N-1個(gè)任務(wù)進(jìn)行可調(diào)度性分析，得到個(gè)體的執(zhí)行任務(wù)序列、延時(shí)任務(wù)序列和刪除任務(wù)序列，從而可以大大簡(jiǎn)化任務(wù)交錯(cuò)調(diào)度的復(fù)雜度、快速計(jì)算個(gè)體的適應(yīng)值。

2.5 算法步驟

混合遺傳算法的步驟可歸納如下：

步驟1參數(shù)初始化。確定初始種群的規(guī)模M，遺傳代數(shù)G，混沌參數(shù)μ，精英保留數(shù)m，自適應(yīng)交叉、變異算子的上下界pc0、pc1、pm0和pm1.

步驟2混沌初始化種群。采用實(shí)數(shù)編碼方式對(duì)個(gè)體的基因進(jìn)行編碼，產(chǎn)生基因(任務(wù)的候選執(zhí)行時(shí)刻)滿足(9)式中的約束條件1的M個(gè)個(gè)體。個(gè)體的基因數(shù)量等于請(qǐng)求任務(wù)數(shù)量N，并根據(jù)(10)式對(duì)初始種群進(jìn)行混沌優(yōu)化。

步驟3適應(yīng)值計(jì)算。通過(15)式～(20)式對(duì)個(gè)體的候選調(diào)度序列進(jìn)行交錯(cuò)調(diào)度分析，根據(jù)個(gè)體對(duì)(9)式中約束條件的滿足情況，計(jì)算個(gè)體的適應(yīng)值((8)式)，并得到個(gè)體對(duì)應(yīng)的執(zhí)行、延時(shí)和刪除隊(duì)列。

步驟4選擇操作。根據(jù)(11)式、(12)式，對(duì)種群采用精英保留和混合排名選擇策略，得到父代個(gè)體。

步驟5自適應(yīng)交叉操作。對(duì)每一個(gè)個(gè)體，產(chǎn)生一個(gè)(0,1)之間的隨機(jī)數(shù)，并根據(jù)(13)式計(jì)算個(gè)體的交叉概率pc. 然后找出所有產(chǎn)生的隨機(jī)數(shù)小于pc的個(gè)體，對(duì)第i個(gè)個(gè)體，選擇與之不同的個(gè)體j進(jìn)行交叉操作，產(chǎn)生(1,N)之間的隨機(jī)數(shù)r，互換兩個(gè)個(gè)體中位于第r個(gè)基因之后的所有基因，得到兩個(gè)子代個(gè)體。

步驟6自適應(yīng)變異操作。對(duì)于每一個(gè)個(gè)體中的所有基因，產(chǎn)生一個(gè)(0,1)之間的隨機(jī)數(shù)，并根據(jù)(14)式計(jì)算個(gè)體的變異概率pm. 若隨機(jī)數(shù)小于pm，則對(duì)該基因進(jìn)行變異，產(chǎn)生一個(gè)與之前基因不同且滿足(9)式中約束條件1的可行基因。在對(duì)所有基因進(jìn)行檢查后，得到子代個(gè)體。在經(jīng)過交叉和變異操作后，子代個(gè)體必須不同于父代個(gè)體，且適應(yīng)值需優(yōu)于父代，否則產(chǎn)生的子代個(gè)體將被父代所替換。

步驟7若迭代次數(shù)達(dá)到遺傳代數(shù)G上限，則算法結(jié)束，輸出最優(yōu)的調(diào)度序列；否則，轉(zhuǎn)步驟3.

算法流程如圖4所示。

3 仿真校驗(yàn)

3.1 評(píng)估指標(biāo)

根據(jù)調(diào)度算法的設(shè)計(jì)原則，選取以下指標(biāo)作為評(píng)判調(diào)度算法性能的標(biāo)準(zhǔn)：

圖4 算法流程圖Fig.4 Flow chart of algorithm

1)實(shí)現(xiàn)價(jià)值率(HVR)[9-13，27]，是指成功調(diào)度任務(wù)的優(yōu)先級(jí)之和與請(qǐng)求調(diào)度任務(wù)的優(yōu)先級(jí)之和的比值，用以反映算法是否滿足重要性原則，如(21)式所示：

(21)

式中：Pi為任務(wù)的優(yōu)先級(jí)，反映任務(wù)的重要程度；Ns和Ntot分別為調(diào)度成功的任務(wù)數(shù)量和請(qǐng)求任務(wù)數(shù)量。

2)調(diào)度成功率(SSR)[9-13，26-27]，是指成功調(diào)度的任務(wù)數(shù)量與請(qǐng)求調(diào)度的任務(wù)數(shù)量之比，用以反映調(diào)度算法是否滿足緊急性原則，如(22)式所示：

SSR=Ns/Ntot.

(22)

3)時(shí)間利用率(TUR)[10-13，26-27]，是指成功執(zhí)行所有任務(wù)的所用時(shí)間與可用時(shí)間Ttot的比值。在調(diào)度過程中，算法應(yīng)充分利用可用時(shí)間資源來調(diào)度任務(wù)，如(23)式所示：

(23)

4)時(shí)間偏移率(ATSR)[10-11，27]，是指成功調(diào)度的任務(wù)執(zhí)行時(shí)刻與其請(qǐng)求執(zhí)行時(shí)刻的相對(duì)偏移程度，用以反映調(diào)度算法是否滿足有效性原則，如(24)式所示：

(24)

(24)式表明，時(shí)間偏移率越低，算法的性能越佳。

3.2 參數(shù)設(shè)置

表1 雷達(dá)任務(wù)參數(shù)表

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

圖5和圖6分別為4種算法的調(diào)度成功率和實(shí)現(xiàn)價(jià)值率對(duì)比曲線。從圖5和圖6可以看出：當(dāng)目標(biāo)數(shù)量小于20時(shí)，4種算法均能成功調(diào)度所有的請(qǐng)求任務(wù)，調(diào)度成功率和實(shí)現(xiàn)價(jià)值率均為1；當(dāng)目標(biāo)數(shù)量超過20時(shí)，啟發(fā)式算法和AGA最先開始錯(cuò)失請(qǐng)求任務(wù)，調(diào)度成功率和實(shí)現(xiàn)價(jià)值率開始下降；當(dāng)目標(biāo)數(shù)量超過30時(shí)，HGA的調(diào)度成功率和實(shí)現(xiàn)價(jià)值率開始下降；當(dāng)目標(biāo)數(shù)量超過40時(shí)，本文改進(jìn)算法的調(diào)度成功率和實(shí)現(xiàn)價(jià)值率開始下降；并且在開始錯(cuò)失請(qǐng)求任務(wù)后，相對(duì)于前3種算法，本文改進(jìn)算法中的兩條曲線下降更緩慢。在啟發(fā)式算法和AGA中，雷達(dá)任務(wù)被視為非搶占式單個(gè)駐留，沒有考慮任務(wù)的內(nèi)部結(jié)構(gòu)，限制了脈沖交錯(cuò)調(diào)度的運(yùn)用，因此，啟發(fā)式算法和AGA最先開始錯(cuò)失請(qǐng)求任務(wù)。而本文改進(jìn)算法和HGA均運(yùn)用了脈沖交錯(cuò)技術(shù)，使任務(wù)中的等待期得到充分利用，但相比較而言，本文改進(jìn)算法取得的調(diào)度成功率和實(shí)現(xiàn)價(jià)值率更高。

圖5 調(diào)度成功率對(duì)比Fig.5 Comparison of scheduling success ratios

圖6 實(shí)現(xiàn)價(jià)值率對(duì)比Fig.6 Comparison of high value ratios

圖7為4種算法的時(shí)間利用率對(duì)比。從圖7中可以看出，相對(duì)于啟發(fā)式算法、AGA和HGA，本文改進(jìn)算法取得了最高的時(shí)間利用率，更能夠充分利用時(shí)間資源來調(diào)度請(qǐng)求任務(wù)。圖8為4種算法的時(shí)間偏移率對(duì)比。圖8中：本文改進(jìn)算法和HGA的時(shí)間偏移率較低，控制在20%以內(nèi)；啟發(fā)式算法的時(shí)間偏移率較高，在45%～70%之間；AGA的時(shí)間偏移率居中。這主要是因?yàn)閱l(fā)式算法通過預(yù)先設(shè)置的規(guī)則，優(yōu)先對(duì)滿足條件的任務(wù)進(jìn)行調(diào)度，時(shí)間偏移率較高；本文改進(jìn)算法和HGA利用種群優(yōu)勢(shì)可以進(jìn)行全局搜索，因此取得的時(shí)間偏移率較低。相比于HGA，本文改進(jìn)算法取得了更低的時(shí)間偏移率，表明改進(jìn)算法能夠更有效地執(zhí)行搜索、跟蹤等任務(wù)，以適應(yīng)雷達(dá)工作環(huán)境的動(dòng)態(tài)變化。雖然AGA同樣采用了智能算法，但由于將雷達(dá)任務(wù)簡(jiǎn)化為非搶占式的單個(gè)駐留，調(diào)度柔性欠佳，相比于HGA和本文改進(jìn)算法，時(shí)間偏移率略高。

圖7 時(shí)間利用率對(duì)比Fig.7 Comparison of time utilization ratios

圖8 時(shí)間偏移率對(duì)比Fig.8 Comparison of average time shift ratios

圖9(a)、圖9(b)、圖9(c)分別給出了目標(biāo)數(shù)量為30、60和90時(shí)性能更佳的兩種算法(本文改進(jìn)算法和HGA)在單個(gè)SI內(nèi)的平均收斂速度對(duì)比，以分別代表算法面臨未過載、中度過載和嚴(yán)重過載任務(wù)量時(shí)的搜索性能。圖9(a)的子圖為HGA收斂速度的局部細(xì)節(jié)圖，其橫縱坐標(biāo)與圖9(a)～圖9(c)一致。從圖9中可以看出：HGA的初始種群質(zhì)量不高、搜索效率較低，在迭代后期易產(chǎn)生階躍現(xiàn)象，算法收斂速度較慢，容易陷入局部極值點(diǎn)；而本文改進(jìn)算法的初始種群質(zhì)量較高，收斂速度更快，尋優(yōu)能力更佳。其原因可歸納為：

圖9 本文改進(jìn)算法和HGA的收斂速度對(duì)比Fig.9 Comparison of convergence rates of the improved algorithm and HGA algorithm

1) HGA采用啟發(fā)式方法產(chǎn)生初始種群，初始種群質(zhì)量較差；本文改進(jìn)算法運(yùn)用混沌理論，對(duì)初始種群進(jìn)行了優(yōu)化，使得初始種群分布遍歷于整個(gè)解空間，提升了初始種群的質(zhì)量。

2) HGA采用的適應(yīng)值函數(shù)加懲罰函數(shù)方法本質(zhì)上是最優(yōu)選擇策略，即適應(yīng)值越大的個(gè)體被選擇的概率越大，適應(yīng)值越低的個(gè)體被選擇的概率將更小，易使得算法僅對(duì)于適應(yīng)值較優(yōu)的個(gè)體鄰域進(jìn)行搜索，適應(yīng)值差的個(gè)體鄰域被忽略，算法過早陷入局部極值點(diǎn)。本文改進(jìn)算法采用精英保留和混合排名相結(jié)合的選擇策略，使得適應(yīng)值大的個(gè)體得以保留，其他個(gè)體混合選擇，適應(yīng)值小的個(gè)體也有相同的機(jī)會(huì)被選擇，保證了不同適應(yīng)值的個(gè)體鄰域均能被搜索，增強(qiáng)了算法的全局尋優(yōu)概率。

3) HGA采用交換字串雜交、移動(dòng)變異的策略，其概率均為恒定值。本文改進(jìn)算法通過設(shè)計(jì)根據(jù)適應(yīng)值動(dòng)態(tài)調(diào)整的交叉、變異概率調(diào)節(jié)公式，使得交叉、變異概率可以根據(jù)個(gè)體的適應(yīng)值進(jìn)行調(diào)整：當(dāng)種群中個(gè)體的適應(yīng)值低于種群的平均適應(yīng)值時(shí)，個(gè)體將以較大的概率發(fā)生改變；當(dāng)個(gè)體的適應(yīng)值高于種群的平均適應(yīng)值時(shí)，個(gè)體將以較大的概率得以保留，提升了算法的搜索效率。

4)雖然HGA同樣運(yùn)用了交錯(cuò)調(diào)度算法，利用雷達(dá)任務(wù)的等待期來交錯(cuò)執(zhí)行其他任務(wù)的發(fā)射期或接收期，以提升算法對(duì)于時(shí)間的利用率，但HGA考慮了能量約束，限制了交錯(cuò)執(zhí)行的任務(wù)數(shù)量，同時(shí)將交錯(cuò)調(diào)度的約束條件遷移到染色體編碼、交叉、變異操作中，使算法更加復(fù)雜。本文改進(jìn)算法通過將能量約束公式化以及設(shè)計(jì)啟發(fā)式的交錯(cuò)調(diào)度算法，在利用任務(wù)等待期的同時(shí)，無需考慮染色體進(jìn)行交叉、變異時(shí)的約束，大大降低了算法的復(fù)雜度。

綜上所述，本文改進(jìn)算法中運(yùn)用了混沌優(yōu)化、精英保留和混合排名選擇策略、自適應(yīng)交叉、變異操作以及交錯(cuò)調(diào)度算法，因此搜索到了全局最優(yōu)解；而HGA僅搜索到了次優(yōu)解。相比于HGA，本文改進(jìn)算法的收斂速度更快；相比于啟發(fā)式算法，本文改進(jìn)算法的調(diào)度成功率提升了40%，實(shí)現(xiàn)價(jià)值率提升了20%，時(shí)間利用率提升了70%，時(shí)間偏移率減少了80%.

4 結(jié)論

實(shí)現(xiàn)任務(wù)的優(yōu)化分配是充分發(fā)揮相控陣?yán)走_(dá)潛能的關(guān)鍵。本文提出了混合自適應(yīng)遺傳算法對(duì)該問題進(jìn)行求解，所做的貢獻(xiàn)和結(jié)論主要如下：

1)綜合任務(wù)調(diào)度的重要性、緊急性和及時(shí)性原則，構(gòu)建了相控陣?yán)走_(dá)任務(wù)調(diào)度的優(yōu)化模型。

2)利用混沌理論產(chǎn)生質(zhì)量較高的初始種群；采用精英保留和混合排名的選擇策略，在保證算法收斂性的同時(shí)賦予個(gè)體多樣性；設(shè)計(jì)了自適應(yīng)的交叉、變異算子，以提升算法的求解效率；提出了嵌套的啟發(fā)式交錯(cuò)算法，以充分利用任務(wù)中的等待期。

3)仿真結(jié)果表明，相對(duì)于3種傳統(tǒng)調(diào)度算法，本文提出的基于混合自適應(yīng)遺傳算法的調(diào)度算法性能更佳。相比于啟發(fā)式算法，本文改進(jìn)算法的調(diào)度成功率提升了40%，實(shí)現(xiàn)價(jià)值率提升了20%，時(shí)間利用率提升了70%，時(shí)間偏移率減少了80%.

下一步將綜合更多的約束條件，對(duì)相控陣?yán)走_(dá)的調(diào)度優(yōu)化問題開展研究。

References)

[1] Zhang B Y, Li S H, Yan W, et al. An efficient scheduling method for phased array radars with limited time resources[C]∥Proceedings of the IET International Radar Conference. Guilin, China: IET, 2009: 1-4.

[2] Butler J M. Multi-function radar tracking and control[D]. London, UK: UCL University of London, 1998.

[3] Reinoso-Rondinel R, Yu T Y, Torres S. Multifunction phased-array radar: time balance scheduler for adaptive weather sensing[J]. Journal of Atmospheric and Oceanic Technology, 2010, 27(11): 1854-1867.

[4] Orman A J, Potts C N, Shahani A K, et al. Scheduling for a multi-function phased array radar system[J]. European Journal of Operational Research, 1996,90(1): 13-25.

[5] 曾光, 胡衛(wèi)東, 盧建斌, 等. 多功能相控陣?yán)走_(dá)自適應(yīng)調(diào)度仿真[J]. 系統(tǒng)仿真學(xué)報(bào), 2004, 16(9): 2026-2029. ZENG Guang, HU Wei-dong, LU Jian-bin, et al. The simulation on adaptive scheduling for multifunction phased array radars[J]. Journal of System Simulation, 2004, 16(9): 2026-2029.(in Chinese)

[6] Bolderheij F, Absil F G J, van Genderen P. A risk-based object oriented approach to sensor management[C]∥Proceedings of the 7th International Conference on Information Fusion. Philadelphia, PA, US: IEEE, 2005: 1-8.

[7] Jimenez M I, del Val L, Villacorta J J. Design of task scheduling process for a multifunction radar[J]. IET Radar, Sonar and Navigation, 2012, 6(5): 341-347.

[8] 盧建斌, 胡衛(wèi)東, 郁文賢. 相控陣?yán)走_(dá)實(shí)時(shí)任務(wù)調(diào)度研究[J]. 電子學(xué)報(bào), 2006, 34(4): 732-736. LU Jian-bin, HU Wei-dong, YU Wen-xian. Research on real-time scheduling algorithm for multifunction phased array radar[J]. Acta Electronica Sinica, 2006, 34(4): 732-736. (in Chinese)

[9] Lu J B, Xiao H, Xi Z M, et al. Multifunction phased array radar resource management: real-time scheduling algorithm[J]. Journal of Computational Information Systems, 2011, 7(2): 385-393.

[10] Lu J B, Xiao H, Xi Z M, et al. Phased array radar resource management: task scheduling and performance evaluation[J]. Journal of Computational Information Systems, 2013, 9(3): 1131-1138.

[11] Cheng T, He Z S, Tang T. Novel radar dwell scheduling algorithm based on pulse interleaving[J]. Journal of Systems Engineering and Electronics, 2009, 20(2): 247-253.

[12] Cheng T, He Z S, Li H Y. Adaptive dwell scheduling for digital array radar based on online pulse interleaving[J]. Chinese Journal of Electronics, 2009, 18(3):574-578.

[13] Cheng T, He Z S, Tang T. Dwell scheduling algorithm for multifunction phased array radars based on the scheduling gain[J]. Journal of Systems Engineering and Electronics, 2008, 19(3):479-485.

[14] Chen J, Tian Z, Wang L, et al. Adaptive simultaneous multi-beam dwell scheduling algorithm for multifunction phased array radars[J]. Journal of Information and Computational Science, 2011, 8(14): 3051-3061.

[15] 張浩為, 謝軍偉, 師俊朋, 等. 飽和時(shí)序下防空相控陣?yán)走_(dá)動(dòng)態(tài)優(yōu)先級(jí)調(diào)度算法[J]. 北京航空航天大學(xué)學(xué)報(bào), 2016, 42(12): 2722-2729. ZHANG Hao-wei, XIE Jun-wei, SHI Jun-peng, et al. Dynamic priority scheduling algorithm for air defense phased array radar in overload situations[J]. Journal of Beijing University Aeronautics and Astronautics, 2016, 42(12): 2722-2729.(in Chinese)

[16] 張浩為, 謝軍偉, 盛川. 綜合優(yōu)先級(jí)規(guī)劃下的相控陣?yán)走_(dá)自適應(yīng)調(diào)度方法[J]. 兵工學(xué)報(bào), 2016, 37(11): 2164-2169. ZHANG Hao-wei, XIE Jun-wei, SHENG Chuan. Adaptive scheduling algorithm over comprehensive priority for phased array radar[J]. Acta Armamentarii, 2016, 37(11): 2164-2169.(in Chinese)

[17] Mir H S, Abdelaziz F B. Cyclic task Sscheduling for multifunction radar[J]. IEEE Transactions on Automation Science and Engineering, 2012, 9(3): 529-537.

[18] Mir H S, Guitouni A. Variable dwell time task scheduling for multifunction radar[J]. IEEE Transactions on Automation Science and Engineering, 2014, 11(2): 463-472.

[19] 周穎, 王雪松,汪連棟,等.基于遺傳算法的相控陣?yán)走_(dá)最優(yōu)化調(diào)度研究[J]. 系統(tǒng)工程與電子技術(shù), 2005, 27(12): 1977-1980. ZHOU Ying, WANG Xue-song, WANG Lian-dong, et al. Optimal scheduling for phased array radar based on genetic algorithm[J]. Systems Engineering and Electronics, 2005, 27(12): 1977-1980.(in Chinese)

[20] 周穎, 王國(guó)玉, 王雪松, 等. 基于啟發(fā)式混合遺傳算法的相控陣?yán)走_(dá)最優(yōu)化調(diào)度[J]. 系統(tǒng)工程與電子技術(shù), 2006, 28(7): 992-996. ZHOU Ying, WANG Guo-yu,WANG Xue-song, et al. Optimal scheduling using hybrid GA with heuristic rules for phased array radar[J]. Systems Engineering and Electronics, 2006, 28(7): 992-996.(in Chinese)

[21] Wang S J, He J, Wang B, et al. Research on adaptive scheduling algorithm based on improved genetic algorithm for multifunctional phased array radar[C]∥Proceedings of International Conference on Future Computer and Communication Engineering. Tianjin:Atlantis Press, 2014:13-20.

[22] 潘偉. 自適應(yīng)遺傳算法在相控陣?yán)走_(dá)最優(yōu)化調(diào)度中的應(yīng)用[J]. 電子信息對(duì)抗技術(shù), 2014, 29(1): 38-41. PAN Wei. Application of adaptive genetic algorithm to optimal scheduling of phased array radar[J]. Electronic Information Warfare Technology, 2014, 29(1): 38-41.(in Chinese)

[23] 王帥杰, 何俊, 王斌, 等. 改進(jìn)遺傳算法的相控陣?yán)走_(dá)自適應(yīng)調(diào)度算法及仿真[J]. 火力與指揮控制, 2015, 40(9): 88-91. WANG Shuai-jie, HE Jun, WANG Bin, et al. Adaptive scheduling algorithm based on improved genetic algorithm for multifunctional phased array radar[J]. Fire Control & Command Control, 2015, 40(9): 88-91. (in Chinese)

[24] 鄭玉軍, 田康生, 邢曉楠, 等. 基于小生境遺傳算法的相控陣?yán)走_(dá)任務(wù)調(diào)度[J]. 現(xiàn)代防御技術(shù), 2016, 44(1):168-174. ZHENG Yu-jun, TIAN Kang-sheng, XING Xiao-nan, et al. Optimal scheduling for phased array radar based on niche genetic algorithm[J]. Modern Defence Technology, 2016, 44(1):168-174. (in Chinese)

[25] Zhang H W, Xie J W, Sheng C. Scheduling method for the phased array radar over chaos adaptively genetic algorithm[C]∥Proceedings of the 6th International Conference on Information Science and Technology. Dalian: IEEE, 2016:111-116.

[26] 張浩為, 謝軍偉, 師俊朋, 等. 動(dòng)態(tài)優(yōu)先級(jí)下防空相控陣?yán)走_(dá)在線交錯(cuò)調(diào)度算法[J]. 系統(tǒng)工程與電子技術(shù), 2017, 39(3): 1-7. ZHANG Hao-wei, XIE Jun-wei, SHI Jun-peng, et al. Dynamic priority online interleaving scheduling algorithm for the air defense phased array radar[J]. Systems Engineering and Electro-nics, 2017, 39(3): 1-7. (in Chinese)

[27] 張浩為, 謝軍偉, 張昭建, 等. 基于混合遺傳- 粒子群算法的相控陣?yán)走_(dá)調(diào)度方法[J]. 系統(tǒng)工程與電子技術(shù)，2017，39(9)：1985-1991. ZHANG Hao-wei, XIE Jun-wei, ZHANG Zhao-jian, et al. Scheduling based on the hybrid genetic particle swarm algorithm for the phased array radar[J].Systems Engineering and Electronics, 2017,39(9):1985-1991. (in Chinese)

[28] 張獻(xiàn), 任耀峰, 王潤(rùn)芃. 基于自適應(yīng)遺傳算法的連續(xù)時(shí)空最優(yōu)搜索路徑規(guī)劃研究[J]. 兵工學(xué)報(bào), 2015, 36(12): 2386-2395. ZHANG Xian, REN Yao-feng, WANG Run-peng. Research on optimal search path programming in continuous time and space based on an adaptive genetic algorithm[J]. Acta Armamentarii, 2015, 36(12): 2386-2395. (in Chinese)

[29] 劉愛軍, 楊育, 李斐, 等. 混沌模擬退火粒子群優(yōu)化算法研究及應(yīng)用[J]. 浙江大學(xué)學(xué)報(bào):工學(xué)版, 2013, 47(10): 1723-1730. LIU Ai-jun, YANG Yu, LI Fei, et al. Chaotic simulated annealing particle swarm optimization algorithm research and its application[J]. Journal of Zhejiang University:Engineering Science, 2013, 47(10): 1723-1730. (in Chinese)

[30] Kuo T W, Chao Y S, Kuo C F, et al. Real-time dwell scheduling of component-oriented phased array radars[J]. IEEE Transactions on Computers, 2005, 54(1)： 47-60.

TaskSchedulingofPhasedArrayRadarBasedonHybridAdaptiveGeneticAlgorithm

ZHANG Hao-wei1, XIE Jun-wei1, ZHANG Zhao-jian1, ZONG Bin-feng2, CHEN Tang-jun3

(1.Air and Missile Defense College, Air Force Engineering University, Xi’an 710051, Shaanxi, China；2.Unit 94710 of PLA, Wuxi 214000, Jiangsu, China；3.Unit 94921 of PLA, Jinjiang 362200, Fujian, China)

TN954+.2

A

1000-1093(2017)09-1761-10

10.3969/j.issn.1000-1093.2017.09.013

2017-01-03

國(guó)家自然科學(xué)基金青年科學(xué)基金項(xiàng)目(61503408)

張浩為 (1992—), 男, 博士研究生。E-mail: zhw_xhzf@163.com

謝軍偉(1970—)，男，教授，博士生導(dǎo)師。E-mail: xjw_xjw_123@163.com