一種基于模因演算法的頻率分配新策略

熊 健,喻 歆

(中國西南電子技術研究所, 成都610036)

1 引 言

在現代戰爭中,無線通信設備能夠保證作戰信息的有效獲取、部隊的合成指揮以及部隊之間的協同作戰。大量的敵我方無線電子設備出現在了現代戰場中,再加上民用無線通信設備,使得現代戰場中的電磁環境十分復雜[1]。

合理地管理有限的電磁頻譜資源有利于指控通信、情報偵察、預警探測、武器制導和導航定位等系統的高效運轉[2]。頻譜資源管理需要解決的關鍵問題之一是如何為用頻設備分配頻譜資源,提高頻譜的利用率。為此,本文基于一種模因演算法提出并設計了一種新穎的頻率分配策略。

同已被工程實踐廣泛檢驗過的遺傳算法類似,模因演算法不依賴于具體問題,具有一定的普適性,能夠解決具有非線性、非連續、不可導、多目標、多變量、多模態等特征的復雜問題,并且比遺傳算法具有更好的求解性能[3]。

模因演算法已被成功應用于規劃(如路由和調度)、設計(如工業制造)、模擬和識別、控制,以及分類(如機器學習和模式識別)[4-6]。而在頻率分配領域,遺傳算法已經獲得成功[7-9],這也為將模因演算法應用于求解頻率分配問題奠定了基礎。于江等人[9]以遺傳算法為基礎設計了一種戰場頻率分配算法,但是他們使用的二進制矩陣編碼方式不能夠較好體現問題本身的特征,而且相對應的遺傳算子的設計也沒有很好地反映搜索空間的結構特點,因此算法不能保證獲得完全沒有相互干擾的分配方案。本文采用正整數序列編碼方式,并且針對該編碼方式和頻率分配問題設計了更高效的搜索算子,以期能夠獲得最優的頻率分配方案。

2 模因演算法的基本原理

模因演算法(Memetic Algorithms,MAs)的靈感來自于達爾文進化論以及拉馬克進化理論的結合。達爾文進化論的基本遺傳單位是基因(Gene),其進化主要發生于生物世界,效果的顯現通常需要數代進化的累積,速度較為緩慢;而拉馬克進化理論認為生物體可將其獲得的經驗和知識直接傳遞給后代,因此顯現效果的速度相對較快[10]。拉馬克進化理論中傳遞的基本單位被E.O.Wilson 稱為“文化基因”[10],它與R.Dawkins 在The Selfish Gene[11]中提出的“Meme”相仿,類似于遺傳算法(Genetic Algorithms,GAs)中的Gene,因此,模因演算法中的基本遺傳單位就是Meme。

從算法的角度來看,模因演算法實際就是在遺傳算法中融入了局部搜索算子,它結合了遺傳算法的全局搜索能力以及局部搜索算子的局部搜索能力,使得算法能夠以更大的概率搜索到全局最優解。該算法最早由P.Moscato[3]于1989 年提出,并成功應用于求解TSP 問題[4],且驗證了其尋優能力強于遺傳算法。模因演算法的流程如圖1 所示,其中局部搜索中實際還包含了對種群的評估操作。從該流程圖可以發現,模因演算法和遺傳算法的區別在于,所有通過遺傳算子生成的新個體在被放入種群前都要進行局部搜索,從而完成個體在局部區域的學習過程。

圖1 模因演算法的運行流程Fig.1 The flowchart of MA

3 頻率分配問題

頻率分配問題是指為無線設備的每個收發信道分配頻率,并且滿足一定的約束條件和需求特性。一般來講,有兩類頻率分配問題,第一類稱為固定頻譜頻率分配問題(Fixed Spectrum Frequency Assignment Problem,FS-FAP),即在給定可用頻譜范圍的基礎上,從收發信道之間的干擾程度的角度來盡可能高效地分配頻率;第二類稱為最小跨度頻率分配問題(M inimum Span FAP,MS-FAP),它主要以最小化分配方案中使用的頻譜跨度范圍為目標(使分配方案中使用的最大與最小頻率之間的間隔最小[12])。本文考慮的是最小化干擾程度頻率分配問題(Minimum Interference FAP,MI-FAP),它屬于FS-FAP,其優化目標是在給定可用頻譜范圍的基礎上最小化收發信道之間的干擾程度。

在求解MI-FAP 時需要考慮3 類電磁兼容約束(Electromagnetic Compatibility Constraints,EMC),即同信道約束(Co-Channel Constraint,CCC)、相鄰信道約束(Adjacent-Channel Constraint,ACC)和共址約束(Co-Site Constraint,CSC)[8-9,12]。CCC 是指同一設備的不同信道不能使用相同的頻率,且不同設備的信道若不滿足設備間的同頻復用最小地理間隔距離,也不能使用相同的頻率;ACC 是指為避免干擾,兩個信道應該間隔的最小頻率距離;CSC 是指為了保證同一設備的信道正常工作,該設備的兩個信道應該間隔的最小頻率距離。

假設一共有n 個無線設備,表示為S =(s1,s2,…,sn),需求向量D =(d1, d2, …, dn),其中di表示設備si的信道數目,可用的頻點數目為m ,按照頻率大小從低到高排序,并且按序標記為1,2, …,m,則EMC 可以用規模為n×n 的非負矩陣C 表示。矩陣C 的對角線元素cii表示同一設備的任一對信道間的約束,其余元素cij(其中i ≠j)表示設備間任一對信道間的約束。

綜上,FS-FAP 由三元組(S , D, C)確定,其中S 表示無線設備,D 表示信道需求,而C 表示EMC矩陣。若用M={1,2, …,m}表示可選用的頻點, Ai為M 的子集,表示分配到設備si的頻點。求解目標則為找到一種頻率分配方案A={A1,A2, …, An},使其滿足如下條件:

其中, Ai表示集合Ai中的頻點數目。滿足上述條件的分配方案稱為可行分配方案。

MI-FAP 的優化目標是找到一種相互間干擾程度最小的可行分配方案,優化目標形式化描述如下:

式中, ε(i,k,j,l)非負,其值根據干擾程度來確定,無干擾時取值為零,且

可以看出,當不存在任何干擾時,I =0。

4 基于模因演算法的頻率分配策略

4.1 問題描述

本文要解決的頻率分配問題以上一節定義的MI-FAP 為基礎。此外,除了每個設備都有信道數目的需求外,每個信道還有工作方式(記為方式W1和方式W2)和用途(記為用途U 1和用途U2)的需求之分。如果把一個頻道對應一個頻率點或者一個頻率集合,并且對應一種工作方式和用途,那么,實際要做的工作就是為每個設備每個信道分配一個頻道,并且滿足電磁兼容約束條件。還需要注意的一個需求條件是每個設備用于U1的信道都使用相同的頻道。類似地,我們將可用的頻道編號并且依次標記為1,2, …,m。這樣,如果把這里的頻道對應到MI-FAP 中的頻點可以發現,該問題同M I-FAP 實質是相同的,只是除了需要滿足上一節提到的3 類約束以外,還需要滿足工作方式和用途的約束要求。

4.2 算法設計

4.2.1 編碼方式

一個個體用正整數序列表示,代表一種頻道分配方案,它通過順序連接分配給每個設備每個信道的頻道號獲得。在連接分配給同一設備的信道的頻道號的時候按照W1U1頻道、W2U 1頻道、W1U 2頻道和W2U2頻道的順序進行,且需要注意的是每個設備的U1頻道都相同。編碼方式如圖2 所示,其中編碼長度為。例如,如果需求向量D=(2,1,3,4),則編碼(6,10,6,6,13,8,6,16,27,20)表示頻道6、10 分給設備1,頻道6 分給設備2,頻道6、13、8 分給設備3,頻道6、16、27、20 分給設備4。其中每個設備都有頻道6,說明需求中要求每個設備都有一個U1用途的信道。

圖2 個體編碼方式Fig.2 The encoding scheme of an individual

4.2.2 初始化方法

種群中的每一個個體都通過隨機的方式生成。根據需求,一個個體的每位數值從相應的頻道號范圍內隨機選取。例如,若第一個設備需要一個W1 U2,以及一個W2U1頻道,那么該個體頭兩位數值就可以分別從W1頻道以及W2頻道中隨機選取,并且將選出的用于U1的頻道分配給該個體上對應U1信道的其他所有編碼位。若種群規模為N(為方便后面的交叉操作,設定其為偶數),則按上述方式隨機生成N 個個體。需要注意的是,我們利用先驗知識指導初始化過程,即初始化時保證每個設備分配的頻道號各不相同,并且在后面的所有操作中,都要保證滿足該要求。此外,在以后的操作中,還需要保證每個設備的U1頻道都相同。

4.2.3 適應度評估

評估一個個體適應度時,首先需要根據輸入的信道的數目、用途、工作方式需求對個體進行解碼,從而獲得相對應的分配方案,然后根據實際的信道間干擾規則計算該分配方案的干擾程度,即公式(4)中的I。在計算一對信道間干擾程度ε(i,k,j,l)的時候,我們設定其值為:ε0——無干擾、ε1——輕微干擾、ε2——一般干擾、ε3——較大干擾以及ε4——嚴重干擾,并且設置ε0=0,ε1=1,ε2=10,ε3=100,ε4=1 000。為了將該問題轉換成最大化問題,我們令個體的適應度f 為

其中,正常數G 可以避免分母為零。這樣,個體的適應度值越大,則其對應的分配方案的干擾程度就越小,最優值1/G 在無干擾I=0 時取得。

4.2.4 選擇操作

本文采用與文獻[9]中相同的輪盤賭選擇算法。為了保證算法收斂,本文還使用了精英保留策略,即在選擇操作進行之前用上一代的最優個體替換待選擇種群中的最差個體。

4.2.5 搜索算子

對于選擇出來的個體,我們依次按概率對它們進行交叉、變異和局部搜索操作。

4.2.5.1 交叉操作

對于選擇出的N 個個體,隨機配對,得到N/2 對待交叉個體。對于每一對個體,生成[0,1] 上的隨機數r,若r>pc,則直接將該兩個個體復制到生成的種群中,否則,進行交叉操作得到兩個新個體,并將它們放入生成的種群中,此處pc表示交叉概率。假設待交叉的個體分別為a 和b,則具體操作如下:

(1)復制a 獲得副本a′,依次檢查a′中的每一位(即i 從1 遍歷至個體編碼長度),如果第i 位的值a′(i)出現在了b 的第j 位并且i ≠j 時,則交換a′(i)和a′(j)對應的值,且若a′中U1信道編碼位發生變化,還需更新a′所有U1信道編碼位信息;

(2)復制b 獲得副本b′,依次檢查b′中的每一位(即i 從1 遍歷至個體編碼長度),如果第i 位的值b′(i)出現在了a 的第j 位并且i ≠j 時,則交換b′(i)和b′(j)對應的值,且若b′中U1信道編碼位發生變化,還需更新b′所有U1信道編碼位信息;

(3)按照如下方式生成第一個個體a″:對于a″的每一位a″(i),生成一個[0,1]內的隨機數r,若r>0.5,則令a″(i)=a′(i);否則,令a″(i)=b(i);最終a″中U1信道編碼位數值以該個體第一個設備的U1信道編碼位信息為準進行更新;

(4)按照如下方式生成第二個個體b″:對于b″的每一位b″(i),生成一個[0,1]內的隨機數r,若r>0.5,則令b″(i)=b′(i);否則,令b″(i)=a(i);最終b″中U1信道編碼位數值以該個體第一個設備的U1信道編碼位信息為準進行更新。

a″和b″即為所得的生成個體,按照上述方式對每一對待操作個體交叉得到N 個生成個體。

4.2.5.2 變異操作

對于交叉得到的N 個個體,我們按概率對它們采取變異操作,以期產生新的優良結構。設交叉概率為pm,對于每一個個體,生成[0,1]上的隨機數r,若r>pm,則不采取任何操作,否則,對其做如下操作:

(1)隨機選擇該個體的某一位;

(2)隨機選擇與步驟1 所選位工作方式(指W1或W2)相同的某一位;

(3)若步驟2 中不存在符合要求的位,同時若步驟1 已經執行了10 次,則變異操作結束;否則,返回步驟1;

(4)若所選兩位均為U2頻道,則交換兩位對應數值,變異操作結束;若所選一位是U1頻道,另一位是U2頻道,則交換兩位對應數值以后,還需更新該個體所有對應U1信道的編碼位上的數值,變異操作結束;若所選兩位均為U 1頻道,變異操作結束。

4.2.5.3 局部搜索

在交叉和變異以后,對得到的N 個個體中適應度排在前10%的個體進行局部搜索, 提高搜索效率,加快找到較優解的進程。具體操作為,對每一個對應的分配方案存在干擾的個體a:

(1)選擇a 對應的分配方案中干擾程度最大的一個設備;

(2)隨機選擇已分配給該設備的一個U2頻道,隨機選擇一個與該頻道工作方式相同的頻道,且該頻道與該設備已有頻道均不相同;

(3)評估若用步驟2 中后者頻道替換前者頻道后該個體的適應度,若適應度增大,則執行此替換操作,并結束對該個體的局部搜索操作;否則,若步驟2 已執行了10 次,則轉步驟4,否則,返回步驟2;

(4)隨機選擇a 對應的分配方案中存在干擾的兩個設備,若不存在滿足條件的兩個設備,則局部搜索結束;

(5)從兩個設備中分別隨機選擇一個U2信道,且選出的兩個信道具有相同的工作方式,若不存在滿足條件的兩個信道,即若步驟4 已執行了10 次,則結束局部搜索,否則,返回步驟4;

(6)評估若交換步驟5 中兩個信道對應的頻道后個體的適應度,若適應度增大,則執行此交換操作,并結束對該個體的局部搜索操作;否則,若步驟4 已執行了10 次,則結束局部搜索,否則,返回步驟4。

4.2.6 停止條件

按照圖1 所示流程,局部搜索中實際上還包含了一次種群的評估操作,這樣,完成一次選擇、交叉、變異和局部搜索稱為一次算法迭代,可以設定算法停止條件為找到了最優分配方案(無干擾)或者已經進行了規定次數的迭代。算法停止時,最后的種群中適應度最大的個體表示的分配方案則為求得的分配方案。

5 仿真分析

5.1 測試問題

測試時,設備數目分別設為10、20、30、40、50 和100,且設備的地理位置隨機分布。可分配的頻道一共有255 個,它們的工作方式包括W1和W2,已根據一定的算法在規定的頻段內生成,而且已經依次從1 至255 編號。每個設備的信道需求統一設定為1個W1U1信道、1 個W2U1信道、1 個W1U2信道以及1個W2U2信道,即每個設備4 個信道。

5.2 參數設置

算法的參數設置為,種群大小N=30,交叉概率pc=0.80,變異概率pm=0.20,適應度常數G=3.0。需要注意的是,這里的參數都是根據經驗設定的,針對不同的問題實例,存在最優的參數配置,對于參數的優化將留到后續工作中進行。對于每個問題實例,算法運行10 次,在后面的結果展示中只列出優化效果最好的那次運行得到的分配方案,若有多個方案效果相同,則隨機展示一種方案。每次運行時,算法都從不同的隨機初始種群開始運行,直到找到無干擾的最優解或者迭代次數達到500 代停止。

算法使用C++編碼實現,開發環境為Microsoft Visual Studio 2010 ver10.0.30319.1 RTMRel,平臺環境為Windows XP Professional SP 3 操作系統, Intel CoreTM2 Quad CPU Q8400 @2.66 GHz 2.66 GHz 的CPU,以及1.96 GB的內存。

5.3 有效性驗證

實驗中,我們設計的算法在所有的問題實例上的每次運行都找到了最優解,即沒有相互干擾的分配方案。以下針對每個實例只列出某一次運行得到的最終分配方案。

由于空間限制,我們只列出了50 個設備時的最終分配結果,如表1 所示,其中,表的第2、3 列分別表示分配給每個設備的W1和W2工作方式且用于U1用途信道的頻道,因此每個設備的該兩列結果相同,而后兩列則分別表示分配給每個設備的W1和W2工作方式且用于U2用途信道的頻道。

從表中的結果可以看到,算法成功找到了滿足EMC 的無相互干擾的分配方案,從而驗證了算法的有效性。若以算法迭代的次數來衡量找到最優解耗費的時間,則當設備數目分別為10、20、30、40、50 和100時,算法分別迭代了1 次、3 次、8 次、14 次、17 次和93次找到最優解,說明在可用的頻道數目一定的情況下,設備數目越多則需要越長的時間找到最優解。

圖3 給出了100 個設備時算法當前找到的最優分配方案的干擾程度的演化曲線。從圖3 可以發現,算法迭代了39 次就找到了不含嚴重干擾的分配方案。此外,還可以發現,50 次迭代以前,干擾程度隨著搜索的進行迅速降低,這實際是算法的交叉以及變異算子起主要作用的階段,該階段的目標是搜索到可能存在最優解的潛在區域。從第50 次迭代開始,干擾程度隨著搜索的進行“相對連續地”逐步減小,這是局部搜索算子在已找到的潛在區域內更細致搜索導致的結果。

圖3 100 個設備時算法找到的當前最優分配方案的干擾程度隨迭代次數的演化曲線Fig.3 The evolutionary curve of the degree of interference of the optimal assignment found so far when there are 100 devices

在表2 中,我們列出了100 個設備時算法某一次運行中,每一次迭代中每一步算子操作消耗的平均CPU 時間以及各操作所占比例。從表2 可以發現,評估每個個體的適應度消耗了最多的時間,其次是局部搜索和交叉操作。仔細分析算法流程可以發現,每個個體上的操作實際上是獨立的,而交叉時每一對個體之間的操作也是相互沒有影響的,因此,為了縮短算法運行時間,可以考慮將交叉、局部搜索以及評估這三步操作分別并行化。

表2 100 個設備時算法每一次迭代中每一步算子操作消耗的平均時間以及所占比例Table 2 The average CPU time consumed by each operator in one iteration and the time consuming proportion when there are 100 devices

6 結 語

在極其復雜的電磁環境中,如何管理、規劃好各用頻設備的頻率需求已經越發顯得重要和關鍵。本文針對頻譜管理中的關鍵問題之一即頻率分配問題展開了研究,基于模因演算法提出并設計了一種用于解決一類實際頻率分配問題的新策略。實驗結果表明,該策略能夠有效求解實際頻率分配問題,但是也存在一些地方值得改進。例如,可以通過并行化來縮短每次迭代消耗的CPU 時間,而當需求規模逐步增大時,也可以考慮使用基于合作型協同演化[13]的技術來減少算法找到最優分配方案的迭代次數。

[1] 李楠,張雪飛.戰場復雜電磁環境構成分析[ J] .裝備環境工程,2008,5(1):16-19.

LI Nan, ZHANG Xue-fei.Constitution Analysis of Comp licated Electromagnetic Environment in Battlefield[ J] .Equipment Environmental Engineering, 2008, 5(1):16 -19.(in Chinese)

[2] 古邦倫.電磁頻譜管理中的頻率分配技術研究[ 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)

[3] Moscato P.On Evolution, Search, Optimization, Genetic Algorithms and Martial Arts:Towards M emetic Algorithms[R] .Pasadena, CA:CalTech, 1989.

[4] Moscato P, Norman M.A Memetic Approach for the Travelling Salesman Problem:Implementation of a Computational Ecology for Combinatorial Optimization on Message-passing Systems[ J] .Parallel Computing and Transputer Applications,1992, 28(1):177-186.

[5] Ishibuchi H,Yoshida T, Murata T.Balance Between Genetic Search and Local Search in Memetic Algorithms for Mu ltiobjective Permutation Flowshop Schedu ling[ J] .IEEE Transactions on Evolutionary Computation, 2003, 7(2):204-223.

[6] Tang M L,Yao X.A Memetic Algorithm for VLSI Floorplan-ning[ J] .IEEE Transactions on Systems, Man, and Cybernetics, 2007,37(1):62-69.

[ 7] Allen S M, Colombo G.Problem Decomposition for Minimum Interference Frequency Assignment[ C]//Proceedings of the 2007 IEEE Congress on Evolutionary Computation.Piscataway, New Jersey,USA:IEEE,2007:3492-3499.

[ 8] Dorne R, Hao J.An Evolutionary Approach for Frequency Assignment in Cellular Radio Networks[ C]// Proceedings of the 1995 IEEE International Conference on Evolutionary Computation.Piscataway, New Jersey, USA:IEEE, 1995:539-544.

[9] 于江, 張磊, 沈劉平, 等.一種基于遺傳算法的戰場頻率分配方法[ J] .電訊技術,2011, 51(7):90-96.

YU Jiang, ZHANG Lei, SHEN Liu-ping, et al.A Battlefield Frequency Assignment Method Based on Genetic Algorithm[ J] .Telecommunication Engineering, 2011, 51(7):90-96.(in Chinese)

[ 10] Wilson E O.Sociobiology:The New Synthesis[M] .Cambridge,MA:Belknap Press of Harvard University Press,1975.

[ 11] Dawkins R.The Selfish Gene[M] .Oxford:Oxford University Press,1989.

[12] Smith D H, Taplin R K, Hurley S.Frequency Assignment with Complex Co-Site Constraints[ J] .IEEE Transactions on Electromagnetic Compatibility, 2001,43(2):210-218.

[13] 楊振宇.基于自然計算的實值優化算法與應用研究[D] .合肥:中國科學技術大學,2010:4.

YANG Zhen-yu.Nature Inspired Real-Valued Optimization and Applications[ D] .Hefei:University of Science and Technology of China, 2010:4.(in Chinese)