基于改進遺傳算法的相控陣雷達任務調度方法

明 樂，周 峰

(空軍工程大學防空反導學院，陜西 西安 710051)

0 引言

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

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

上述遺傳算法在任務調度過程中容易出現收斂速度慢以及早熟的問題，針對這一問題，本文提出了一種基于改進遺傳算法的相控陣雷達任務調度方法。

1 任務調度模型

1.1 遺傳算法調度的目標函數

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

(1)

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

1.2 遺傳算法調度的約束條件

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

1) 時間資源約束

時間資源約束反映的是在一個調度間隔內能調度的事件數目，其約束條件如下所示：

(2)

式(2)中，Dj表示的是一個調度間隔中第j個雷達任務的波束駐留時間，N為調度間隔內任務總數。

2) 能量資源約束

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

(3)

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

3) 計算機資源約束

計算機資源對信號處理的速度有一定的影響，從而對雷達的任務調度也會產生一定的影響，具體表達式如下：

(4)

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

4) 硬件約束

其約束條件為：

(5)

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

2 改進的遺傳算法及其任務調度流程

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

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

ξ=α/n

(6)

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

假設個體X的代碼為1010101010，個體Y的代碼為1000011001，那么可以看出兩個個體的相同位串數量為5，此時的α=5，n=10，因此ξ=5/10=0.5。

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

(7)

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

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

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

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

第一步 在一個調度間隔內的任務根據優(yōu)先級進行排序，得到待調度任務序列Q。

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

第三步 當tzs+Δts>twm時，任務ql分配至刪除隊列；當tzs+Δts=twm時，任務ql分配至延遲隊列；當tzs+Δts

第四步 本調度間隔內的任務結束，此時Q=?；若不是，則l=l+1，返回第一步。

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

圖1 基于改進遺傳算法任務調度結構框圖Fig.1 Structure diagram of task scheduling based on improved genetic algorithm

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

3 仿真試驗及性能評估

3.1 性能評估指標

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

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

(8)

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

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

(9)

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

3.2 仿真分析

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

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

任務的參數設置如表1所示。

表1 任務參數設置

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

圖3 任務調度成功率對比Fig.3 The contrast of schedule success ratio

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

從圖3中可以看出，當目標很少時，兩種算法在調度成功率方面相差并不大，由于此時相控陣雷達資源充足，大部分任務基本都可以被成功安排。隨著目標數目的增多，兩種算法的調度成功率都有所下降，但是改進遺傳算法相較于標準的遺傳算法，其任務調度成功率更高。在目標數量160左右時，曲線已經降到很低，是由于相控陣雷達資源趨于飽和導致了兩種調度方法的成功率很低。

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

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

表2 調度性能指標統(tǒng)計結果

4 結論

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