基于小生境遺傳算法的干擾資源調度研究*

雷磊，周青松，張劍云，劉春泉

(1.電子工程學院，安徽 合肥 230037； 2.北京電子設備技術研究所，北京 100191)

0 引言

在未來戰場中，作戰任務要求和環境日益復雜多樣，對作戰武器系統電子對抗能力的要求也越來越高，而對多雷達目標的干擾決策能力就是衡量電子對抗能力的一個重要指標。以我方攻擊機對敵方空域進行突防的典型戰場態勢想定為例，我方綜合運用多部干擾機實施遠距離支援干擾和伴隨干擾，但在干擾資源有限、任務時間緊迫等不利條件下，可能同時遭遇敵方多部不同類型雷達的探測，若不能及時制定有效的干擾決策、采取有效的干擾措施進行掩護，一旦被敵方地空、空空武器平臺跟蹤鎖定，后果不堪設想。因此，如何對敵方多部探測雷達實施有效的干擾、實現“隱身”突防就成為一個極富意義和挑戰的研究課題。

干擾機的資源調度是建立在雷達偵察的基礎上，綜合分析敵方布防雷達參數，實時解算探測雷達數量、探測距離、威脅等級，并結合我方干擾機的工作效能，制定干擾方案，形成干擾決策[1]。文獻[2-4]分別將基于投影梯度、0-1規劃和最大元素算法的資源分配方法運用到了類似的問題中，取得了一定的效果，但隨著雷達數M和干擾資源數N的增加，該問題涉及的解空間呈指數級增加，容易出現計算量的組合爆炸現象[5]，上述方法難以高效求解。文獻[6]在問題的求解中引入了遺傳算法，并運用基于Grefenstette等在解決TSP問題時提出的巡回路線編碼方法，解決了常規編碼方法所對應的交叉運算和變異運算會使子代群體中產生較多不滿足問題約束條件的分配方案的問題，但由于編碼方式的限制，實際上是對模型和解空間作了額外的約束，削弱了模型和算法的普遍適用性。文獻[7]在無線自組網多目標優化資源選擇模型中引入了一種基于整數編碼的改進遺傳算法，彌補了二進制編碼和實數編碼在處理此類問題時的缺陷，但仍然存在傳統遺傳算法處理此類問題時易出現的收斂穩定性差和容易早熟等問題。

文獻[8]中首先提出了基于小生境思想的改進型遺傳算法，其基本思想是：首先給出群體中各個染色體之間的距離定義，然后兩兩比較個體之間的距離。若小于預設值D，則選擇二者中適應度值較低的個體，極大地降低其適應度。經此處理，距離較近的較差個體在后續競爭中將會逐漸被淘汰，因而數代之后在距離D之內將只存在一個的較優者。這樣既維護了群體的多樣性，又使得種群中的各個個體之間保持了一定的距離，從而使個體能夠在整個約束空間中分散開來，保證了有效基因的傳遞性。

本文從干擾壓制概率公式出發，建立了雷達干擾資源調度模型。然后采用基于整數編碼的小生境遺傳算法對模型進行尋優求解，有效改善了傳統遺傳算法收斂速度慢、計算結果穩定性差以及容易早熟等問題，相較其他文獻方法，能夠進一步提升算法的整體尋優能力。

1 雷達干擾資源調度的數學模型

雷達干擾資源調度優選問題從本質上可以歸結為一個多目標規劃問題，即在一系列節點、鏈路上優化一個反映某些參數指標的資源約束函數，并據此尋找滿足目標約束條件的滿意解。下面基于多目標規劃方法，建立雷達干擾資源調度的數學模型。

由雷達原理可知，一般地，在虛警概率Pfa一定時，信噪比SNR越大，發現概率Pd越大，即雷達發現目標的概率是以信噪比為自變量的增函數[9]。這里可以按照文獻[5]中計算發現概率Pd和壓制概率Q的方法對二者進行計算。顯然，發現概率Pd越小，壓制概率Q越大，干擾機對雷達的干擾效果就越好，所以可用壓制概率Q作為干擾壓制效果的評估準則。

假設在某次突防任務中，我方可用干擾資源由N部干擾機組成，集合為J={J1,J2,…,JN}，干擾方式為壓制式干擾；需要干擾的敵方布防雷達網由M部雷達組成，集合為R={R1,R2,…,RM}。因為各部雷達的探測性能、工作方式、開機時間以及布防區域均有所差別，所以各部雷達的威脅等級也不盡相同，因此不妨設第j部雷達的威脅等級為Lj,j=1,2,…,M，并規定威脅等級越大，其對突防任務的威脅程度就越高，需要對其分配更多的干擾壓制，以保證干擾掩護的整體效果。為方便計算，對Lj進行歸一化處理，可得第j部雷達的威脅權系數為

(1)

由文獻[5]計算方法可得如下的干擾效能矩陣

(2)

式中：Qij為第i部干擾機對第j部雷達的干擾壓制概率，i=1,2,…,N,j=1,2,…,M。

為簡化模型，設定干擾策略原則為：采用干擾效益最大準則，優先分配威脅等級較大的雷達；每部干擾機在某一時刻只能集中功率干擾一部雷達；某部雷達在某一時刻可不被干擾機干擾，也可被多部干擾機同時干擾。在這里應注意2點：一是部分文獻[5-6]在設定干擾策略原則時規定“每部雷達在某一時刻中至少分配一部干擾機”，這實際上是忽略了可能存在的“某部雷達威脅等級較低時，綜合考慮整體的干擾效益，可選擇不對其分配干擾資源，而是將多余的資源分配給威脅等級較高的雷達，進行重點干擾”的實際情況，這樣雖然模型求解時的速度較快，但卻是在以降低模型和算法的普遍適用性為代價減小解空間，因此本文并未直接采用這些文獻中的模型，而是對模型的約束條件作了相應的改進；二是若N

根據上述原則，可得N部干擾機對M部雷達實施干擾的資源調度模型目標函數為

(3)

其約束條件為

式中：E為干擾資源調度的整體效益；xij=1時表示將第i部干擾機分配給第j部雷達，xij=0時則表示不分配。

由分析可知，式(3)的干擾資源調度問題為一種多參數、多約束的非線性整數規劃問題，屬于NP難問題。當干擾機數N和雷達數M增大時，干擾資源調度問題的解空間呈指數級增加[11]，常規方法難以高效地求解此類優化問題，因此，可采用小生境遺傳算法進行優化求解。

2 基于整數編碼小生境遺傳算法的干擾資源調度優化

為進一步避免算法中存在的收斂速度慢、計算結果穩定性差以及容易早熟等問題，應對基本小生境遺傳算法進行一定的改進。其具體實現步驟如下：

步驟1 編碼

編碼的目的就是把自變量在解空間中的數據表示成遺傳空間中的基因型結構數據，其基本的碼型有0-1編碼、整數編碼和實數編碼等。二進制編碼計算量大，權系數的表示精度受到限制；而對于變量離散型的問題，采用實數編碼的GA(genetic algorithm)得到的最優解必須離散化歸整處理，結果往往不再是全局最優，對于多約束的優化問題甚至會產生不可行解[7]。為此，文獻[12]提出了基于整數編碼的改進遺傳算法，兼具二進制編碼和實數編碼的優點，具有很好的全局收斂性能。因此，本文采用整數編碼，編碼得到的基因串用一個整數數列表示，順序值表示干擾機的編號，整數值表示雷達的編號，如一個染色體為[5,1,4,2,3,4]，其表示將第1部干擾機分配給第5部雷達，第2部干擾機分配給第1部雷達，第3部干擾機分配給第4部雷達，……，第6部干擾機分配給第4部雷達。這樣就可以將干擾資源調度方案轉化為一個整數編碼的基因串，并且這種對應是唯一的。

步驟2 初始群體的產生

采用隨機方法產生K個維數為N的整數向量，每個向量作為一個獨立的染色體；向量的維數N代表染色體上基因的個數，即干擾機的個數；每個基因取≥1,≤M的整數，M為雷達的數量；K個染色體作為一個種群，每個染色體表示為Xi,t，i表示染色體在種群中的序列，1≤i≤K，t表示遺傳代數，G表示最大的遺傳代數，1≤t≤G。

步驟3 構造適應度函數

遺傳算法在搜索進化過程中一般不需要其他外部信息，僅用評估函數值來評估個體或解的優劣，并作為以后遺傳操作的依據。這里根據第1部分中的目標函數式(3)來評估群體中的每個個體的適應度。

步驟4 選擇

本文將選擇分為2步，首先從得到的子代個體中預選出前K個較優個體(這里初始群體的個數為K)，讓它們成為下步遺傳操作中的備選父代。然后利用輪盤賭的方法選出實際參與交叉操作的父代個體。為了避免傳統輪盤賭方法易出現的“一枝獨秀”而使得優化問題陷于局部解的現象，對其進行如下改進：將群體中的染色體按照適應度由好到壞進行排序，即序號越小，對應的個體越優，那么其被選中的概率也就越大。其后的個體被選中的概率應逐步減小，但也不宜過小。這里可生成一個向量

P=P0,P1,P2,…,Pi,…,PK，

然后在0,PK內產生均勻分布的隨機數r，若Pi-1≤r≤Pi，就選擇第i個染色體放入交叉隊列，i=1,2,…，K。重復上述步驟，直至得到含有K個實際參與交叉操作父代個體的交叉隊列。

步驟5 交叉

為了克服收斂對于初始群體選擇的依賴，可采用4種不同的交叉操作，并在后代生成的過程中兩兩交替使用這4種操作。

在奇次代中使用單點交叉和多點交叉操作生成子代染色體：

(1) 單點交叉操作

隨機選擇一個初始基因位，便得到了從首位基因到初始基因位的一個基因段，然后再隨機選取2個染色體，將二者的上述相應基因段進行交換，得到2個新的子代個體。

(2) 多點交叉操作

與單點交叉操作類似，不同的是被交換的基因段是由隨機產生的2個初始基因位決定的。

在偶數代中使用差分進化和內插/外推操作生成子代染色體：

(1) 差分進化操作

(4)

式中：i=1,2,…；F∈0,2，用于控制差分項的幅度，在仿真中可根據具體情況進行設定。

得到新染色體后需對超出邊界和非整數的基因進行強制規整賦值：若xi,j≤1，則令xi,j=1；若xi,j≥M，則令xi,j=M；若1

(2) 內插/外推操作

(5)

式中：i=0,1,2,…；C∈0,0.5，用于控制內插/外推的幅度，在仿真中可根據具體情況進行設定。然后再對每個基因采用類似于差分進化中規整賦值的方法進行處理。

步驟6 變異

每一代的交叉操作完成后，應隨機選取少數子代個體進行變異操作，其具體操作類似于初始群體中個體的產生。通常情況下，應使變異個體數占總群體數目的1%～2%。此外，由于在遺傳操作的后幾代，染色體會相繼進入局部解，所以可以在一定代數之后稍微增大變異概率，以使其突破局部限制，收斂到全局最優解。

步驟7 評價適應度函數

與步驟3類似。

步驟8 小生境淘汰運算

步驟9 精英保留策略

如果經過步驟8得到的種群的最優值劣于父代，則需用父代種群中的最優個體代替子代中的最差個體，以使后代種群的最優值不差于前代，提高算法的收斂效率。

小生境遺傳算法的具體實現流程如圖1所示。

圖1 小生境遺傳算法流程圖Fig.1 Flow chart of niche genetic algorithm

3 仿真實驗

3.1 算法正確性驗證

為了驗證本文算法的有效性，這里給出基于整數編碼小生境遺傳算法的雷達干擾資源調度的計算機仿真結果。設作戰區域中5部干擾機對5部雷達進行干擾，5部雷達的威脅系數分別為0.80，0.76，0.84，0.86，0.90，根據干擾機和雷達各自參數性能、空間位置關系和壓制時間段的設置，利用壓制概率計算方法，可得干擾決策矩陣，如表1所示。

表1 干擾效能數據列表Table 1 Performance data of interference

設定參數，令整數編碼小生境遺傳算法的初始種群中個體數目K=20，最大進化代數G=40，差分幅度控制系數F=1，內插外推系數C=0.25，參量ε=0.5，β=0.92，α=0.098 6，變異概率取0.015，小生境個體間最小歐幾里德距離預設值D=1。

優化結果為：gbest=[1,5,3,2,4]，其所對應的適應度函數值為3.579 4，其結果與用匈牙利算法進行的優化結果一樣，說明了本文算法的正確性。其干擾資源調度方案表示為：第1部干擾機干擾第1部雷達，第2部干擾機干擾第5部雷達，依此類推。

圖2給出了目標函數的收斂特性。

圖2 目標函數的收斂曲線Fig.2 Convergence curve of objective function

從圖2中可知，本文算法目標函數的上升，分了幾個不同的階段，這是因為雷達干擾資源調度的目標函數是非線性的多峰函數，這些不同的階段正好說明了整數編碼小生境遺傳算法的正確性和有效性，能夠很好地減小搜索過程陷入到局部最優解的概率，從而提高算法的尋優能力。

3.2 算法優越性驗證

為了驗證本文算法的優越性，這里再給出本文算法與其他文獻算法的計算機仿真結果比較。在上述參數均相同的情況下，將文獻[6]算法與本文算法進行對比，二者各獨立運行500次，算法性能對比結果如表2。

表2 兩種算法的性能對比結果Table 2 Comparisons of performance obtained with two different methods

從表2可以看出，雖然2種算法多次運行后都可以最佳收斂到全局最優解，但本文算法的收斂穩定性明顯高于文獻[6]算法，且本文算法的最差收斂結果和目標函數收斂后的平均值也明顯優于文獻[6]算法。同時，以上性能的提升所付出的代價是耗時的小幅增加。

在上述參數不變的情況下，再將二者各獨立運行100次，收斂誤差對比結果如圖3所示。

a)文獻[6]算法的收斂誤差圖

b)本文算法的收斂誤差圖圖3 收斂誤差對比結果Fig.3 Comparisons of convergence error

從圖3中可知，運行100次后，本文算法的非最優收斂次數和最差收斂誤差分別為6次和0.202 6，均優于文獻[6]算法的27次和0.358 6，因此，本文算法較文獻[6]算法有明顯優勢。

4 結束語

本文提出了一種基于整數編碼小生境遺傳算法的雷達干擾資源調度方法，采用實數編碼，以最大化雷達干擾資源調度的整體效益為目標函數，在遺傳進化過程中交替使用4種交叉方式。最后，通過仿真實驗說明了該方法的正確性和優越性，相較文獻方法，本文方法在有效提升最優收斂穩定性的前提下，可進一步提升最差收斂的目標函數值和目標函數收斂后的平均值，同時有效地控制了收斂誤差，因此能夠使雷達干擾資源調度的整體效益達到最優。

參考文獻：

[1] 裴立彬，劉春生. 寬帶陣列的同時多目標干擾資源調度研究[J]. 電子對抗信息技術，2012，25(6)：46-54.

PEI Li-bin, LIU Chun-sheng. Jamming Strategy of Wide-Band Array to Multi-Target[J]. Electronic Information Warfare Technology, 2012, 25(6): 46-54.

[2] 徐振海，王雪松，肖順平，等. 雷達組網對抗中遮蓋干擾功率優化分配[J]. 系統工程與電子技術，2003，25(6)：655-657.

XU Zhen-hai, WANG Xue-song, XIAO Shun-ping, et al. Optimum Allocation of Barrage Jamming Power in Netted Radar Countermeasure[J]. Systerns Engineering and Electronics, 2003, 25(6): 655-657.

[3] 沈陽，陳永光，李修和. 基于0-1規劃的雷達干擾資源優化分配研究[J]. 兵工學報，2007，28(5)：528-532.

SHEN Yang, CHEN Yong-guang, LI Xiu-he. Research on Optimal Distribution of Radar Jamming Resource Based on Zero-One Programming[J]. Acta Armamentarii, 2007, 28(5): 528-532.

[4] 李波，高曉光. 編隊空戰中協同電子干擾的功率分配[J]. 系統工程與電子技術，2008，30(7)：1298-1300.

LI Bo，GAO Xiao-guang. Algorithm of Power Allocation for Cooperative Electronic Jamming in Air Combat of Formation [J]. Systems Engineering and Electronics, 2008, 30(7): 1298-1300.

[5] 劉以安，倪天權，張秀輝，等. 模擬退火算法在雷達干擾資源優化分配中的應用[J]. 系統工程與電子技術，2009，31(8)：1914-1917.

LIU Yi-an, NI Tian-quan, ZHANG Xiu-hui, et al. Application of Simulated Annealing Algorithm in Optimizing Allocation of Radar Jamming Resources [J]. Systems Engineering and Electronics, 2009, 31(8): 1914-1917.

[6] 高彬，呂善偉，郭慶豐，等. 遺傳算法在電子戰干擾規劃中的應用[J]. 北京航空航天大學學報，2006，32(8)：933-936.

GAO Bin, Lü Shan-wei, GUO Qing-feng, et al. Genetic Algorithm Approach to the Jammer’s Layout for EW[J]. Journal of Beijing University of Aeronautics and Astronautics, 2006, 32(8): 933-936.

[7] 劉勇，張曉紅. 遺傳算法的多目標優化資源選擇算法[J].火力與指揮控制，2009，33(2)：89-92.

LIU Yong, ZHANG Xiao-hong. Research on Resource Selection Algorithm of Multi-Objective Optimization Based on Genetic Algorithms[J]. Fire Control and Command Control, 2009, 33(2): 89-92.

[8] DEB K, GOLDBERG D E. An Investigation of Niche and Species Formation in Genetic Function Optimization[C]∥Proceedings of the Third International Conference on Genetic Algorithms, 1989:42-50.

[9] 丁鷺飛，耿富錄. 雷達原理[M]. 西安：西安電子科技大學出版社，2002.

DING Lu-fei, GENG Fu-lu. Radar Principle[M]. Xi’an: Xidian University Press, 2002.

[10] 胡運權. 運籌學教程[M]. 北京：清華大學出版社，1998.

HU Yun-quan. The Tutorial on Operational Research[M]. Beijing: Tsinghua University Press, 1998.

[11] PARSOPOULOS K E, VRAHATIS M N. Recent Approaches to Global Optimization Problems Through Particle Swam Optimization[J]. Natural Computing, 2002, 1(2-3): 235-306.

[12] 廖美英，郭荷清，張勇軍. 一種整數編碼的改進遺傳算法[J]. 計算機工程與應用，2003(1)：103-105.

LIAO Mei-ying, GUO He-qing, ZHANG Yong-jun. An Ameliorative Integer Coded Genetic Algorithm[J]. Computer Engineering and Applications, 2003(1):103-105.