明 樂，周 峰

(空軍工程大學(xué)防空反導(dǎo)學(xué)院，陜西 西安 710051)

0 引言

相控陣?yán)走_(dá)具有靈活、快速的波束捷變和自適應(yīng)能力，它可以同時執(zhí)行多個任務(wù)，如搜索和跟蹤[1-4]。近年來，相控陣?yán)走_(dá)資源調(diào)度方法層出不窮，而遺傳算法作為一種模擬生物進化“優(yōu)勝劣汰”的搜索方法，是一種高效、并行、全局優(yōu)化的搜索方法，可以實現(xiàn)資源的最佳調(diào)度。

文獻(xiàn)[5]將相控陣?yán)走_(dá)任務(wù)的調(diào)度過程與車間作業(yè)的調(diào)度流程進行了類比分析。算法根據(jù)雷達(dá)任務(wù)的優(yōu)先級和時間窗對調(diào)度性能的影響，定義了最優(yōu)調(diào)度的目標(biāo)函數(shù)，同時考慮了時間、能量和計算機資源約束條件。文獻(xiàn)[6]在文獻(xiàn)[5]的基礎(chǔ)上分析了雷達(dá)任務(wù)的編碼規(guī)則，詳細(xì)介紹了算法求解過程中初始種群生成、選擇、交叉和變異算子的設(shè)計，并且通過仿真驗證了基于遺傳算法的相控陣?yán)走_(dá)任務(wù)自適應(yīng)調(diào)度算法的可行性和有效性。然而，早期的遺傳算法仍然存在早熟現(xiàn)象，針對這一缺陷，文獻(xiàn)[7]提出動態(tài)的交叉和變異概率，該算法雖然在一定程度上能克服早熟現(xiàn)象，但是當(dāng)種群較大時，在后期迭代中基因改動較小，導(dǎo)致系統(tǒng)全局能力變差。

上述遺傳算法在任務(wù)調(diào)度過程中容易出現(xiàn)收斂速度慢以及早熟的問題，針對這一問題，本文提出了一種基于改進遺傳算法的相控陣?yán)走_(dá)任務(wù)調(diào)度方法。

1 任務(wù)調(diào)度模型

1.1 遺傳算法調(diào)度的目標(biāo)函數(shù)

本文采用文獻(xiàn)[8]中的方法，把任務(wù)執(zhí)行時間與期望執(zhí)行時間的偏移量的和最小及所有類型任務(wù)調(diào)度成功率加權(quán)和最大作為調(diào)度的目標(biāo)函數(shù)，具體表達(dá)式如下：

(1)

式(1)中，M、L、P和Q分別為搜索、驗證、跟蹤和失跟的子類數(shù)目，A(·)為代價函數(shù)，當(dāng)ηi=1時，δ(·)=1，否則δ(·)=0，ρi為雷達(dá)任務(wù)的加權(quán)，ni表示第i類雷達(dá)任務(wù)調(diào)度安排的個數(shù)，Ni為待調(diào)度安排的數(shù)目，F(xiàn)(·)表示執(zhí)行效益因子。

1.2 遺傳算法調(diào)度的約束條件

限制相控陣?yán)走_(dá)任務(wù)調(diào)度的重要因素有時間、計算機、能量和硬件資源[9-11]，每一個任務(wù)的執(zhí)行都需要消耗時間、能量資源，并且還會占用計算機和硬件資源，所以在研究任務(wù)調(diào)度的過程中必須充分考慮這四種約束條件。

1) 時間資源約束

時間資源約束反映的是在一個調(diào)度間隔內(nèi)能調(diào)度的事件數(shù)目，其約束條件如下所示：

(2)

式(2)中，Dj表示的是一個調(diào)度間隔中第j個雷達(dá)任務(wù)的波束駐留時間，N為調(diào)度間隔內(nèi)任務(wù)總數(shù)。

2) 能量資源約束

能量資源約束指的是發(fā)射機占空比需要滿足一定條件，遵從發(fā)射系統(tǒng)的平均功率容量。具體如下：

(3)

式(3)中，τ表示的是占空比，α為比率，Pjk為脈寬，Lj為第j個波束駐留中發(fā)射脈沖個數(shù)。

3) 計算機資源約束

計算機資源對信號處理的速度有一定的影響，從而對雷達(dá)的任務(wù)調(diào)度也會產(chǎn)生一定的影響，具體表達(dá)式如下：

(4)

式(4)中，g(·)表示事件產(chǎn)生數(shù)目，R2表示計算機總資源。

4) 硬件約束

其約束條件為：

(5)

式(5)中，h(·)表示事件對雷達(dá)硬件的需求，R3表示雷達(dá)硬件總資源。

2 改進的遺傳算法及其任務(wù)調(diào)度流程

常見的遺傳算子有交叉、變異和選擇算子，其中交叉算子是重要組成部分。所謂交叉是交換兩個染色體的局部結(jié)構(gòu)，然后重組成新的個體，經(jīng)過交叉步驟，能夠把父代的優(yōu)良基因遺傳給子代，從而確保得到全局最優(yōu)解。所以交叉是新個體產(chǎn)生的主要途徑，是全局收斂性的重要保證[12]。傳統(tǒng)的交叉操作具有一定的盲目性，父代染色體進行交叉后可能會導(dǎo)致其優(yōu)良基因被破壞，無法遺傳給下一代。因此本文提出了一種改進的交叉方案，來保證父代的優(yōu)良基因盡可能的遺傳給子代個體。

本文提出的編碼相似度指的是種群內(nèi)兩個不同個體染色體對應(yīng)位置編碼的相似程度。假設(shè)現(xiàn)有兩個父個體X和Y，我們定義其相似度為：

ξ=α/n

(6)

式(16)中，ξ表示的是編碼相似度，α表示的是兩個個體對應(yīng)位置編碼相同的數(shù)目，n表示的是個體染色體編碼的長度。

假設(shè)個體X的代碼為1010101010，個體Y的代碼為1000011001，那么可以看出兩個個體的相同位串?dāng)?shù)量為5，此時的α=5，n=10，因此ξ=5/10=0.5。

有了編碼相似度并不能決定是否進行交叉操作，需要一個參照點，在這里提出標(biāo)準(zhǔn)交叉點的概念，所謂的標(biāo)準(zhǔn)交叉點指的是當(dāng)前染色體種群進行交叉操作的門限，是一種臨界值，其具體表示方法[13]如下：

(7)

式(7)中，k為標(biāo)準(zhǔn)交叉點，G為此群體事先設(shè)置的總進化代數(shù)，g為算法到目前為止已運行的代數(shù)。因為式中g(shù)是在隨著種群進化而在不斷增大的，所以k的值是處于一種動態(tài)變化的，是隨著種群進化不斷增大的。

當(dāng)兩個染色體的相似性ξ小于或者等于動態(tài)標(biāo)準(zhǔn)交叉點k時，才可以進行個體的交叉操作，反之，則不進行交叉操作，而是克隆其本身，直接將其基因遺傳給下一代。在遺傳算法的早期階段，種群個體是隨機產(chǎn)生的，編碼相似度比較低，此時為了保留群體中的優(yōu)良個體，所以k值應(yīng)相對較小，降低其交叉幾率；在后期階段遺傳算法趨于收斂時，個體之間的差別較小，它們的相似性較高，此時應(yīng)增大k值，使得群體中的個體還能進行交叉操作，保障了群體的多樣性，防止出現(xiàn)局部最優(yōu)解以及早熟問題。

本文提出的對父代染色體標(biāo)準(zhǔn)交叉點的動態(tài)控制，從理論上分析能有效提高遺傳算法的收斂速度，保障了群體的多樣性，防止出現(xiàn)局部最優(yōu)解，提高了其全局搜索能力。為了更好地評價本文提出的改進算法，下面會對基于改進遺傳算法的相控陣?yán)走_(dá)任務(wù)調(diào)度進行研究。

假設(shè)雷達(dá)在一個調(diào)度間隔SI=[t0,t1]內(nèi)有N個任務(wù)請求[14]{q1,q2,q3，…，qn}。對于其中一個任務(wù)qi，其優(yōu)先級是pi，最早可調(diào)度時間是tzi，最晚可調(diào)度時間是twi，期望調(diào)度時間是tqi，調(diào)度的時間長度是Δti。任務(wù)調(diào)度的具體步驟如下：

第一步 在一個調(diào)度間隔內(nèi)的任務(wù)根據(jù)優(yōu)先級進行排序，得到待調(diào)度任務(wù)序列Q。

第二步 從待調(diào)度任務(wù)序列Q中取出任務(wù)ql，并將ql的期望調(diào)度時間和Q中每個任務(wù)的調(diào)度時間進行比較，得出ql前后的兩個任務(wù)，分別記作qs和qm。確定qs的最早調(diào)度時間為tzs，qm的最晚調(diào)度時間為twm。

第三步 當(dāng)tzs+Δts>twm時，任務(wù)ql分配至刪除隊列；當(dāng)tzs+Δts=twm時，任務(wù)ql分配至延遲隊列；當(dāng)tzs+Δts

第四步 本調(diào)度間隔內(nèi)的任務(wù)結(jié)束，此時Q=?；若不是，則l=l+1，返回第一步。

基于改進遺傳算法調(diào)度結(jié)構(gòu)框圖如圖1所示，其中綜合優(yōu)先級包括任務(wù)工作方式優(yōu)先級和其截止期。結(jié)構(gòu)框圖中改進的遺傳算法模塊的具體流程圖如圖2所示。

圖1 基于改進遺傳算法任務(wù)調(diào)度結(jié)構(gòu)框圖Fig.1 Structure diagram of task scheduling based on improved genetic algorithm

圖2 改進的遺傳算法模塊Fig.2 Improved genetic algorithm module

3 仿真試驗及性能評估

3.1 性能評估指標(biāo)

本文采用以下評估指標(biāo)對改進的算法進行性能評估，從而驗證其具有一定的優(yōu)勢。

1) 調(diào)度成功率[15](Schedule Sccess Ratio，SSR)：

(8)

式(8)中，Nsuc為成功調(diào)度任務(wù)總數(shù)；N為所有請求的任務(wù)總數(shù)。調(diào)度成功率用來描述調(diào)度任務(wù)的情況，調(diào)度成功率越高，性能越好。

2) 截止期錯誤率(Miss deadline Ratio，MDR)：

(9)

式(9)中，Ndef為在截止期內(nèi)調(diào)度失敗的任務(wù)數(shù)；N為所有請求的任務(wù)總數(shù)。截止期錯誤率反映的是在截止期內(nèi)任務(wù)的調(diào)度情況，截止期錯誤率越低，方法性能越佳。

3.2 仿真分析

本文為了更好地對比新算法與傳統(tǒng)算法在性能上的差異，采用了如下仿真參數(shù)對兩種算法進行仿真，通過仿真結(jié)果來檢驗新算法的性能。

仿真參數(shù)：1)調(diào)度間隔為50 ms；2)綜合優(yōu)先級的設(shè)計均衡考慮工作方式優(yōu)先級和截止期的影響；3)改進的遺傳算法中，編碼采取二進制的方式，其最大交叉概率pc=0.9，最大變異概率pm=0.1，最大進化代數(shù)1 000。

任務(wù)的參數(shù)設(shè)置如表1所示。

表1 任務(wù)參數(shù)設(shè)置

計算出兩種方法10次獨立實驗結(jié)果的平均值。圖3得到的是兩種方法的調(diào)度成功率隨目標(biāo)數(shù)量的變化曲線；圖4得到的是兩種方法的截止期錯失率隨目標(biāo)數(shù)量的變化曲線。

圖3 任務(wù)調(diào)度成功率對比Fig.3 The contrast of schedule success ratio

圖4 截止期錯失率對比Fig.4 The contrast ofmiss deadline ratio

從圖3中可以看出，當(dāng)目標(biāo)很少時，兩種算法在調(diào)度成功率方面相差并不大，由于此時相控陣?yán)走_(dá)資源充足，大部分任務(wù)基本都可以被成功安排。隨著目標(biāo)數(shù)目的增多，兩種算法的調(diào)度成功率都有所下降，但是改進遺傳算法相較于標(biāo)準(zhǔn)的遺傳算法，其任務(wù)調(diào)度成功率更高。在目標(biāo)數(shù)量160左右時，曲線已經(jīng)降到很低，是由于相控陣?yán)走_(dá)資源趨于飽和導(dǎo)致了兩種調(diào)度方法的成功率很低。

從圖4中可以看出，隨著目標(biāo)數(shù)目的增多，兩種調(diào)度算法的截止期錯誤率都會上升，但是顯然改進遺傳算法的調(diào)度方法比傳統(tǒng)的遺傳算法上升的慢，在目標(biāo)數(shù)量為200左右時，基于標(biāo)準(zhǔn)遺傳算法的調(diào)度算法的截止期錯誤率已經(jīng)達(dá)到了0.016 8，而基于改進遺傳算法的調(diào)度方法達(dá)到了0.013，改進遺傳算法的截止期錯誤率要小一些。

表2給出的是進行10次獨立試驗后，計算出的兩種方法的SSR和MDR的均值以及標(biāo)準(zhǔn)差。由表2可以更直觀地得到結(jié)論：基于改進遺傳算法的相控陣?yán)走_(dá)任務(wù)調(diào)度方法能提升任務(wù)調(diào)度的成功率，減少截止期錯誤率，并且其統(tǒng)計標(biāo)準(zhǔn)差較小，表明改進后的算法比傳統(tǒng)的算法在任務(wù)調(diào)度方面表現(xiàn)的更加穩(wěn)定。

表2 調(diào)度性能指標(biāo)統(tǒng)計結(jié)果

4 結(jié)論

本文提出了一種改進遺傳算法的相控陣?yán)走_(dá)任務(wù)調(diào)度方法。該方法在現(xiàn)有遺傳算法的基礎(chǔ)上引入編碼相似度以及動態(tài)標(biāo)準(zhǔn)交叉點的概念，通過比較兩者的大小來決定是否進行交叉操作，避免了交叉過程的盲目性，保留了種群的優(yōu)良基因，有效提升了遺傳算法的收斂性能，提高了相應(yīng)的收斂速度；通過動態(tài)控制父代染色體的標(biāo)準(zhǔn)交叉點，來維持算法推進過程中種群的多樣性，提升系統(tǒng)全局搜索能力，避免了局部最優(yōu)解的產(chǎn)生。仿真試驗結(jié)果表明，與傳統(tǒng)的遺傳算法相比較，該算法提升了任務(wù)調(diào)度成功率，降低了截止期錯失率，有效提高了相控陣?yán)走_(dá)的整體調(diào)度性能，具有一定的優(yōu)勢。