一種基于遺傳算法的戰場頻率分配方法

于 江,張 磊,沈劉平,秦愛祥,王春嶺

(1.解放軍73691部隊,南京 210014;2.解放軍理工大學 通信工程學院,南京 210007;3.解放軍73681部隊,南京 210042)

1 引 言

未來高科技條件下的局部戰爭,將向著“陸、海、空、天、電”五維一體的空間立體式方向發展,而與之相配套的電子信息技術的不斷更新及其在軍事領域中的廣泛應用,使得大量電子裝備被投入到戰場中,遍及指揮通信、情報偵察、武器制導、預警探測、導航定位等多種領域[1],涉及地面、海上、空中和特種作戰力量及各種武器系統。

在這紛繁的戰場環境下,眾多用頻裝備對有限的頻譜資源展開了激烈的爭奪,導致戰場電磁環境異常復雜。因此,對于作戰部隊來說,怎樣才能掌控好所配備的用頻裝備,進一步提高頻率資源的使用效率,就成為亟待解決的問題。基于此,本文提出了一種以遺傳算法為核心的啟發式戰場頻率分配方法,并對具體的頻率分配過程進行模擬仿真,然后采用3種選取策略對生成的頻率分配結果進行質量評估,以便向作戰用頻單位提供比較優化的頻率分配方案。

2 遺傳算法的原理及其應用

2.1 遺傳算法的基本原理

遺傳算法(Genetic Algorithm,GA)的操作對象是群體,群體由若干個體組成,個體的具體特征又是由組成個體的一條基因鏈決定。群體經過多次選擇、交叉、變異操作后,可以得到質量越來越高的個體[2]。遺傳算法的基本運作流程如圖1所示。

圖1 遺傳算法的基本流程Fig.1 The basic flow of Genetic Algorithm

遺傳算法是一種不依賴于具體問題的直接搜索方法,其主要目的是借助生物進化中的“適者生存”規律來說明自然和人工系統的自適應過程,適合數值求解那些帶有多參數、多變量、多目標和多區域,但連通性較差的NP-Hard優化問題[3]。目前,遺傳算法在模式識別、神經網絡、圖像處理、機器學習、工業優化控制等方面都得到了廣泛應用,在頻率分配技術領域中,也有很多成功的應用案例,這為遺傳算法在戰場頻率分配中的應用鋪平了道路。

2.2 遺傳算法在戰場頻率分配領域中的應用

在戰場電磁環境下的頻率分配算法中,任何一個頻點(信道)就是一個基因,所有頻點按照一定順序排列成一條基因鏈就組成了一個個體,每個個體都反映出戰場上按地理環境劃分的某一個小區域的頻率分配情況,若干個體再組成一個群體,這就是所研究的整個戰場電磁環境(在后期算法的描述中把它定義為“研究空間”)。初始群體是隨機產生的,它是一個以頻率分配方案為參考對象的基因組庫(在后期算法的描述中把它定義為“樣本空間”),后代的群體則是由這個基因組庫中擇優選取的父體和母體通過交叉、變異產生的[4]。算法終止的評判標準有3種:一是得到了所求解;二是遺傳到了一定的代數;三是經過若干代后,適應度一直沒有變化。算法輸出的結果是一個最優頻率分配方案。

3 啟發式戰場頻率分配算法

將遺傳算法應用到戰場頻率資源分配領域,并形成符合戰場電磁環境具體特點和實際需求的啟發式頻率分配算法,需要考慮如下幾個方面的問題。

3.1 戰場頻率分配算法的約束條件

通常,軍用通信系統的頻率分配問題可以表述為:對于給定的一組無線發射機,找到一種受干擾最小的頻率配置方案,滿足所有的頻率約束關系。這些約束一般分為兩類:操作約束和電磁約束。前者隨著具體問題不同而不同,而后者可以用有用信號的最低信噪比或最大允許的干擾噪聲比來衡量。根據實際系統要求,這類約束又可以細分為同信道約束、鄰道約束和共址約束[5]3種情況。

(1)同信道約束

同信道約束(Co-channel Constraint,CCC)是指為了避免同頻干擾,分別處于不同位置的一對發射機不能分配相同的頻率,除非它們相隔足夠遠的距離。設fi和fj是分配給發射機i和j的頻率,則同信道約束要求滿足如下條件:fi≠fj。

(2)鄰道約束

鄰頻干擾是指一對發射機即使工作頻率相隔幾個信道,仍然可能造成相互之間干擾的情形。鄰道約束(Adjacent-channel Constraint,ACC)就是為了避免鄰頻干擾,發射機之間至少要間隔m個頻道,即滿足如下條件:︱fi-fj︱>m。

(3)共址約束

共址約束(Co-site Constraint,CSC)是指同一個小區分配的信道之間必須有一個最小的頻率間隔。具體地說,就是處于相同位置的發射機為了保證能夠正常工作,必須間隔 m個信道的頻率,即滿足如下條件:︱fi-fj︱≥m。

3.2 戰場頻率分配算法的數學模型

(1)頻率分配方案矩陣F[6]

頻率分配方案矩陣F采用二進制的編碼方式,F矩陣由n×m個元素組成,其中n是待規劃的小區數目,m則是可以使用的頻點個數。

F矩陣中每一個元素fik的取值由式(1)決定:

當確定了頻率分配方案矩陣F以后,位于戰場環境下的各個小區就可以按照該矩陣中各行劃分的特定信道來部署所在地域的作戰用頻裝備。

(2)電磁兼容矩陣 C

結合3.1節涉及到的3個干擾約束條件,這里引入電磁兼容(EMC)矩陣C。假設某一戰場環境的電磁空間被劃分成了n個小區,一般可用一個n×n的對稱矩陣C來描述EMC,表現形式如下:

C矩陣中的每個元素cij表示了i小區和j小區所分配的頻點集合間最小的頻率間隔[7]。由此可以看出,在 C矩陣中,對角線上的元素cii代表同一小區所分配頻點的最小頻率間隔,即CSC約束;同理,cij=1表示CCC約束,即小區i中的頻率fi和小區j中的頻率fj是不可以相等的,它們之間的頻率間隔至少為1;而cij=2則表示ACC約束,即小區i中的頻率fi和小區j中的頻率fj不可以相鄰,它們之間的頻率間隔至少為2。對于可以復用同一頻率的兩個小區,cij=0,即小區 i中的頻率fi和小區j中的頻率fj可以相等。

另外,還涉及到頻點(信道)需求數組

數組中的元素a1,a2,…,an分別對應第1,2,…,n個小區實際需要的頻點個數。

3.3 戰場頻率分配算法的具體構造

戰場頻率分配算法的實現主要通過對遺傳算法加以改進來實現,也就是說該算法中同樣會涉及到適應度函數生成、選擇操作、交叉操作以及變異操作等基本步驟。下面對算法的設計進行詳細說明。

(1)戰場頻率分配算法的適應度函數

結合頻率分配算法的具體特點,可以設置出如下的適應度函數,分別拿需求數組needarray[n]中的每個元素值(即某一小區實際需要的頻點數)與樣本空間(即前面提到的頻率分配方案基因庫)中的各個個體中1的個數進行比對,若兩者在數值上越接近,即它們的差值越小,則認為該個體的適應度越高。因此,適應度函數的具體形式為

式中,fitness(j)為樣本空間中第j個個體的適應度值,ind-length為樣本空間中各個個體的總長度,needarray[i]為第 i個小區實際需要的頻點數,value(j)為樣本空間中第j個個體中1的個數。

(2)戰場頻率分配算法的選擇操作

戰場電磁環境下的頻率分配算法采用適應度比例選擇方式來進行個體的選擇,在該方法中,每個個體的選擇概率與其適應度成正比。

設種群規模為N,種群中第i(i=1,2,…,N)個個體的適應度為fi,則第i個個體的選擇概率pi如式(3)所示:

(3)戰場頻率分配算法的交叉操作

由于頻率分配算法操作的對象和輸出的結果是一個個頻率分配方案,即每個個體中1的個數等于所分配的頻點數,所以在交叉過程中如果改變了原有個體的結構而使個體中1的個數變多或變少,將導致算法給出的頻率分配方案出現信道閑置或無法滿足用頻需求,這顯然不是期望看到的結果。

為確保交叉操作后每行個體中l的個數固定不變,算法提出一種調整措施對遺傳算法的基本交叉操作加以改進。具體步驟如下:假設A和B是兩個待交叉父體,并且有一個后進先出的堆棧,As、Bs代表兩個父體染色體的第s位上的數值,若As、Bs兩位相異,則暫時先不互換這兩位,而是把它們放到堆棧中存儲起來,然后繼續搜索A和B的后續位,若發現還存在 Ai、Bi這對相異位,且 As和Ai也是相異的,則同時交換 As、Bs和Ai、Bi兩組基因位,這樣就可以確保A和B兩個個體在交叉操作以后仍能保證個體中l的個數固定不變。

(4)戰場頻率分配算法的變異操作

同樣,這里也不希望遺傳算法的變異操作破壞原有頻率分配方案個體在信道容量上的穩定性,為確保變異操作后每個個體中1的個數固定不變,就必須采用特殊的變異方法。具體步驟如下:根據給定的變異概率決定一行個體基因序列的某一位s是否發生變異,如果是,則在同一行選取另外一個隨機位i,假設這兩位也是相異的,就將s和i直接交換,否則不交換,從而達到變異的效果。這與傳統遺傳算法0、1互換的變異模式有所不同。

3.4 戰場頻率分配算法分配結果的代價評估[8]

經3.2節定義,F矩陣代表一組頻率分配方案。第i行元素的和,即代表小區i所分配到的信道總數,設di為i小區實際需要的頻點數,那么如果這種頻率分配方案違背了該設計,則會造成以下代價:

式中,q為小區i的待分配頻點。

其次,用F矩陣來對照給定的C矩陣可得到以下結論:對于CSC,假設以待分配頻點q與被分配給了小區i的已有頻點p為研究對象,如果p與q之間的間隔小于cii,即,那么根據CSC約束,頻點q就不能被分配給i小區,否則就會造成如式(5)的代價:

注意這里的頻點 p、q僅用來標識實際分配到小區i中的兩個頻點(應有其具體的數值)在F矩陣中的位置,通過查找 F矩陣,可以知道這兩個頻點的頻率間隔是否滿足上面所述的約束條件。

同理,對于CCC和ACC,假設頻點p已經分配給了i小區,頻點q等待分配給j小區,如果根據 C矩陣,cij>0(i≠j),那么一旦p與q之間的間隔小于cij,即,根據CCC或者ACC,頻點q就不能分配給小區 i,否則就會造成以下代價:

綜上所述,對于某個頻率分配方案,都能產生一個F矩陣,衡量這個 F矩陣優劣的標準可以綜合考慮上述各種代價,得到函數

式中,α、β、γ分別為第i個小區的同信道/鄰道約束(CCC&ACC)、共址約束(CSC)和需求差異因素的權重。對于不同的戰場環境,這三個方面的因素對代價函數所造成的影響各不相同,因此,需要根據實際情況對α、β、γ進行合理配置。

4 案例仿真與方案效能評估

假設圍繞某作戰地域,頻管部門根據己方用頻裝備的部署情況將戰場劃分為4個面積相等的小區域,如圖2所示。與此同時,分別處在4個小區中的作戰部隊向頻管部門提出用頻需求,且所有的用頻申請都集中在頻率范圍為Fmin～Fmax的有限頻段內,根據當前頻段的無線電業務類型,現將頻段Fmin～Fmax分成若干個等間隔的小信道,假定劃分為10個信道。在經過戰場電磁環境測試的輔助決策以后,頻管部門就可以生成頻率需求數組needarray[4]={8,3,9,4}(為簡化算法實現的復雜性,needarray[4]中的4個元素值為隨機產生的數值)。

圖2 戰場環境下的小區劃分示意圖Fig.2 The sketch map of cell partition in battlefield environment

此時,通過對戰場監測分隊上報的重點頻段(Fmin～Fmax)監測數據進行數學分析和計算,并結合己方用頻部隊上報的干擾申訴情況,可以生成電磁兼容矩陣 C。在本課題中,算法隨機生成一個4×4的矩陣,用來反映各小區間的干擾情況。

另外,還有存儲頻率分配方案的樣本空間群體,算法中也是隨機生成一個10×10的二進制矩陣,作為頻率分配方案的初始化提取庫。這里需要注意,由于樣本空間的群體規模比較小,為了能夠快速搜索到最優分配方案,算法在進行遺傳代數循環時,每一代都會重新生成隨機樣本空間群體,這與傳統遺傳算法只對選擇、交叉、變異操作進行遺傳代數循環有所差異。

有了頻率需求數組needarray[4]、電磁兼容矩陣C以及初始化樣本空間群體,再結合戰場頻率分配算法,就可以迅速給出比較理想的頻率分配方案矩陣F。算法的實現采用C++語言,通過n代循環,可以得出n個不同的頻率分配方案,再借助代價函數C(F)對這些頻率分配方案進行質量評估,選擇其中代價最小的那個方案作為最終分配方案下發給頻率使用單位。本課題將通過3個實驗對不同選擇策略的頻率分配方案進行性能比較。

4.1 代價函數權值完全相同的分配方案選取策略

利用頻率分配算法產生200個頻率分配方案矩陣F,再選取3.4節中定義的代價函數 C(F)對這200個頻率分配方案進行代價評估,顯然當權值 α、β、γ選擇不同的數值時,C(F)所反映的頻率分配方案的代價信息是不同的。首先令 α、β、γ均為1,來看一下這些頻率分配方案的代價分別為多少,并給出頻率分配方案在算法遺傳了100代和遺傳了200代以后的代價分布情況,如圖3和圖4所示。

圖3 算法執行100代后得出的代價最小頻率分配方案(α=β=γ=1)Fig.3 The smallest cost of frequency assignment project after the algorithm has been executed for 100 generations(α=β=γ=1)

圖4 算法執行200代后得出的代價最小頻率分配方案(α=β=γ=1)Fig.4 The smallest cost of frequency assignment project after the algorithm has been executed for 200generations(α=β=γ=1)

對照圖3和圖4不難得出以下結論:

(1)隨著遺傳代數的增加,該分配算法可以產生代價更小的頻率分配方案,如圖中顯示在算法執行了100代以后產生的最優頻率分配方案代價為68,200代以后產生的最優頻率分配方案代價為51,后者的代價比前者更小。

其中,第134代結果為最優頻率分配方案:

該矩陣需求約束的代價為13,CSC的代價為10,CCC和ACC的代價為28,總代價 C(F)值為51。

(2)矩陣F134各行中1的個數反映了該頻率分配算法分配給每個小區的信道數,比如第1區分得2個頻點(2<8)、第2區分得3個頻點、第3區分得3個頻點(3<9)、第4區分得3個頻點,這與頻率需求數組needarray[4]={8,3,9,4}顯示的各小區實際需求的頻點數有巨大差異。

也就是說,采用 α、β、γ均為1的代價評估策略得到的最優頻率分配方案是以降低頻點使用量為代價來減少干擾影響的。顯然,這違背了信息化條件下的現代戰場上電子裝備的使用密度越來越大的總趨勢,因此,必須加大對需求約束的代價權重。

4.2 增強型需求約束代價的分配方案選取策略

為避免出現前一節中選擇的頻率分配方案給出的各小區頻點容量過低的問題,本次試驗中將代價函數的權值分別設置為 α=1、β=1、γ=100,以提高需求約束對方案選取的影響效果,這樣就得出了如圖5所示的代價分布結果。

圖5 算法執行200代后得出的代價最小頻率分配方案(α=β=1,γ=100)Fig.5 The smallest cost of frequency assignment project after the algorithm has been executed for 200 generations(α=β=1,γ=100)

其中,第191代結果為最優頻率分配方案:

該矩陣需求約束的代價為3,CSC的代價為72,CCC和ACC的代價為180,總代價值 C(F)為552。

在矩陣F191各行中1的個數(第1區分得8個頻點、第2區分得4個頻點、第3區分得8個頻點、第4區分得 5個頻點)基本與頻率需求數組needarray[4]={8,3,9,4}中的對應數值相當,所以在需求約束方面,該頻率分配方案取得的效果是不錯的(3<13)。但是由于提高了各小區的頻點供應量,使得小區間干擾陡然增高,比如矩陣F191的CSC代價為72,遠高于前一節中的10;CCC和ACC的代價為180,遠高于前一節中的28。因此,對于權值 α、β、γ的處理,應該科學設置以便均衡這三方面代價對頻率分配方案選擇的影響。

4.3 均衡型代價的分配方案選取策略

基于權值的均衡性考慮,本次試驗做如下處理:

(1)確定頻率分配算法在執行了200代以后,給出的200個頻率分配方案的相應需求約束、CSC,以及CCC和ACC的代價數值;

(2)確定這三者之間的比例關系(1∶a1∶b1,1∶a2∶b2,…,1∶a200∶b200);

(3)對需求約束與CSC的代價比例值做一個均方根得到值a,對需求約束與CCC/ACC的代價比例值也做一個均方根得到值b,如式(8)所示,這樣就產生了一個最終的均方根比例值1∶a∶b[10];

(4)最后對得到的均方根比例1∶a∶b取最小公倍數,從而確定 α、β、γ的最終分配關系(α=1×a,β=1×b,γ=a×b)。

經過上述處理以后,得到均方根比例1∶a∶b=1∶6.80∶16.06,則實際代價函數的權值就設置為 α=6.8、β=16.06、γ=109.208,這樣就得出如圖6所示的代價分布結果。

圖6 算法執行200代后得出的代價最小頻率分配方案(α=6.8,β=16.06,γ=109.208)Fig.6 The smallest cost of frequency assignment project after the algorithm has executed for 200 generations(α=6.8,β=16.06,γ=109.208)

為了驗證本策略的均衡性所在,這里首先列出其中的最優頻率分配方案矩陣:

該矩陣需求約束的代價為7,CSC的代價為28,CCC和ACC的代價為76,總代價值為1730.94。

現將該策略(策略3)所付出的這3個代價值分別與4.1節中的策略(策略1)、4.2節中的策略(策略2)產生的最佳頻率分配方案所付出代價的對應值進行比較,可以得出如表1所示的比較結果。

表1 3種策略之間的代價對比情況Table 1 Cost contrast of three strategies

從表1可以看到,策略3的需求約束代價介于策略1和策略2之間,比策略1小,比策略2稍大;而策略3的CSC約束代價以及CCC和ACC約束代價也介于策略1和策略2之間,比策略2小,比策略1稍大。實驗得到預期結果,可將F189作為最終分配方案下發給作戰用頻單位。

5 結 語

戰場頻譜資源科學分配是現代戰爭中作戰決策部門必須考慮的重要環節,而戰場頻譜分配效率的高低將直接影響作戰方案中各個進程的有效實施,對最后戰爭的成敗意義深遠。本文以傳統的遺傳算法為基礎,結合戰場電磁環境的具體特點,對其進行改進優化,最后生成啟發式戰場頻率分配算法,并對采用不同策略得出的頻率分配結果進行代價評估。仿真結果表明,采用均衡型權重配置的評估策略選擇出來的頻率分配方案相對比較理想,但仍需結合實際戰場電磁環境所反映的不同特性,進一步研究頻率分配算法的優化問題,以及分配方案選取的科學性問題。

[1] 李楠,張雪飛.戰場復雜電磁環境構成分析[J].裝備環境工程,2008,5(1):16-19.LI Nan,ZHANG Xue-fei.Constitution Analysis of Complicated Electromagnetic Environment in Battlefield[J].Equipment Environmental Engineering,2008,5(1):16-19.(in Chinese)

[2] Karen I Aardal.Models and solution techniques for frequency assignment problems[EB/OL].Maastricht:Maastricht research school of Economics of Technology andOrganization in its series,2003[2010-07-23].http://ideas.repec.org/p/dgr/umamet/2002002.html.

[3] 司小江.數據鏈規劃技術的研究[D].南京:解放軍理工大學,2003:12.SI Xiao-jiang.The Research of Tactical Data Link Planning Technique[D].Nanjing:PLA University of Science and Technology,2003:12.(in Chinese)

[4] 古邦倫.電磁頻譜管理中的頻率分配技術研究[D].長沙:國防科學技術大學,2006:5.GU Bang-lun.The Research of Frequency Assignment in Frequency Spectrum Management System[D].Changsha:National University of Defense Technology,2006:5.(in Chinese)

[5] 賀志強,牛凱,林雪紅,等.頻率分配與管理算法研究[C]//2007年通信理論與信號處理學術年會論文集.北京:電子工業出版社,2007:427-433.HE Zhi-qiang,NIU Kai,LIN Xue-hong,et al.The Study of Algorithms for Frequency Assignment and Management[C]//Proceedings of 2007 Annual Conference on Communication Theory and Signal Processing.Beijing:Publishing House of Electronics Industry,2007:427-433.(in Chinese)

[6] 章春芳,陳陵,陳娟.求解頻率分配問題的自適應的多種群蟻群算法[J].小型微型計算機系統,2006,27(5):837-841.ZHANG Chun-fang,CHEN Ling,CHEN Juan.Solving Frequency Assignment Problem Using an Adaptive Multi Colony Ant Algorithm[J].Mini-Micro Computer Systems,2006,27(5):837-841.(in Chinese)

[7] 薛學猛.一種面向工程應用的啟發式頻率分配算法研究與應用[D].北京:北京郵電大學,2008:2.XUE Xue-meng.Research and Application of An Engineering-Oriented Heuristic Algorithm for Frequency Assignment[D].Beijing:Beijing University of Posts and Telecommunications,2008:2.(in Chinese)

[8] 謝珊.遺傳算法在無線頻率規劃的應用[D].廣州:中山大學,2007:9.XIE Shan.The Genetic Algorithm Application of The Wireless Frequency Plan[D].Guangzhou:SUN Yat-sen University,2007:9.(in Chinese)