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

熊 健,喻 歆

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

1 引 言

在現(xiàn)代戰(zhàn)爭(zhēng)中,無(wú)線通信設(shè)備能夠保證作戰(zhàn)信息的有效獲取、部隊(duì)的合成指揮以及部隊(duì)之間的協(xié)同作戰(zhàn)。大量的敵我方無(wú)線電子設(shè)備出現(xiàn)在了現(xiàn)代戰(zhàn)場(chǎng)中,再加上民用無(wú)線通信設(shè)備,使得現(xiàn)代戰(zhàn)場(chǎng)中的電磁環(huán)境十分復(fù)雜[1]。

合理地管理有限的電磁頻譜資源有利于指控通信、情報(bào)偵察、預(yù)警探測(cè)、武器制導(dǎo)和導(dǎo)航定位等系統(tǒng)的高效運(yùn)轉(zhuǎn)[2]。頻譜資源管理需要解決的關(guān)鍵問(wèn)題之一是如何為用頻設(shè)備分配頻譜資源,提高頻譜的利用率。為此,本文基于一種模因演算法提出并設(shè)計(jì)了一種新穎的頻率分配策略。

同已被工程實(shí)踐廣泛檢驗(yàn)過(guò)的遺傳算法類(lèi)似,模因演算法不依賴(lài)于具體問(wèn)題,具有一定的普適性,能夠解決具有非線性、非連續(xù)、不可導(dǎo)、多目標(biāo)、多變量、多模態(tài)等特征的復(fù)雜問(wèn)題,并且比遺傳算法具有更好的求解性能[3]。

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

2 模因演算法的基本原理

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

從算法的角度來(lái)看,模因演算法實(shí)際就是在遺傳算法中融入了局部搜索算子,它結(jié)合了遺傳算法的全局搜索能力以及局部搜索算子的局部搜索能力,使得算法能夠以更大的概率搜索到全局最優(yōu)解。該算法最早由P.Moscato[3]于1989 年提出,并成功應(yīng)用于求解TSP 問(wèn)題[4],且驗(yàn)證了其尋優(yōu)能力強(qiáng)于遺傳算法。模因演算法的流程如圖1 所示,其中局部搜索中實(shí)際還包含了對(duì)種群的評(píng)估操作。從該流程圖可以發(fā)現(xiàn),模因演算法和遺傳算法的區(qū)別在于,所有通過(guò)遺傳算子生成的新個(gè)體在被放入種群前都要進(jìn)行局部搜索,從而完成個(gè)體在局部區(qū)域的學(xué)習(xí)過(guò)程。

圖1 模因演算法的運(yùn)行流程Fig.1 The flowchart of MA

3 頻率分配問(wèn)題

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

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

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

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

其中, Ai表示集合Ai中的頻點(diǎn)數(shù)目。滿足上述條件的分配方案稱(chēng)為可行分配方案。

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

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

可以看出,當(dāng)不存在任何干擾時(shí),I =0。

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

4.1 問(wèn)題描述

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

4.2 算法設(shè)計(jì)

4.2.1 編碼方式

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

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

4.2.2 初始化方法

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

4.2.3 適應(yīng)度評(píng)估

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

其中,正常數(shù)G 可以避免分母為零。這樣,個(gè)體的適應(yīng)度值越大,則其對(duì)應(yīng)的分配方案的干擾程度就越小,最優(yōu)值1/G 在無(wú)干擾I=0 時(shí)取得。

4.2.4 選擇操作

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

4.2.5 搜索算子

對(duì)于選擇出來(lái)的個(gè)體,我們依次按概率對(duì)它們進(jìn)行交叉、變異和局部搜索操作。

4.2.5.1 交叉操作

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

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

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

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

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

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

4.2.5.2 變異操作

對(duì)于交叉得到的N 個(gè)個(gè)體,我們按概率對(duì)它們采取變異操作,以期產(chǎn)生新的優(yōu)良結(jié)構(gòu)。設(shè)交叉概率為pm,對(duì)于每一個(gè)個(gè)體,生成[0,1]上的隨機(jī)數(shù)r,若r>pm,則不采取任何操作,否則,對(duì)其做如下操作:

(1)隨機(jī)選擇該個(gè)體的某一位;

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

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

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

4.2.5.3 局部搜索

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

(1)選擇a 對(duì)應(yīng)的分配方案中干擾程度最大的一個(gè)設(shè)備;

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

(3)評(píng)估若用步驟2 中后者頻道替換前者頻道后該個(gè)體的適應(yīng)度,若適應(yīng)度增大,則執(zhí)行此替換操作,并結(jié)束對(duì)該個(gè)體的局部搜索操作;否則,若步驟2 已執(zhí)行了10 次,則轉(zhuǎn)步驟4,否則,返回步驟2;

(4)隨機(jī)選擇a 對(duì)應(yīng)的分配方案中存在干擾的兩個(gè)設(shè)備,若不存在滿足條件的兩個(gè)設(shè)備,則局部搜索結(jié)束;

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

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

4.2.6 停止條件

按照?qǐng)D1 所示流程,局部搜索中實(shí)際上還包含了一次種群的評(píng)估操作,這樣,完成一次選擇、交叉、變異和局部搜索稱(chēng)為一次算法迭代,可以設(shè)定算法停止條件為找到了最優(yōu)分配方案(無(wú)干擾)或者已經(jīng)進(jìn)行了規(guī)定次數(shù)的迭代。算法停止時(shí),最后的種群中適應(yīng)度最大的個(gè)體表示的分配方案則為求得的分配方案。

5 仿真分析

5.1 測(cè)試問(wèn)題

測(cè)試時(shí),設(shè)備數(shù)目分別設(shè)為10、20、30、40、50 和100,且設(shè)備的地理位置隨機(jī)分布?？煞峙涞念l道一共有255 個(gè),它們的工作方式包括W1和W2,已根據(jù)一定的算法在規(guī)定的頻段內(nèi)生成,而且已經(jīng)依次從1 至255 編號(hào)。每個(gè)設(shè)備的信道需求統(tǒng)一設(shè)定為1個(gè)W1U1信道、1 個(gè)W2U1信道、1 個(gè)W1U2信道以及1個(gè)W2U2信道,即每個(gè)設(shè)備4 個(gè)信道。

5.2 參數(shù)設(shè)置

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

算法使用C++編碼實(shí)現(xiàn),開(kāi)發(fā)環(huán)境為Microsoft Visual Studio 2010 ver10.0.30319.1 RTMRel,平臺(tái)環(huán)境為Windows XP Professional SP 3 操作系統(tǒng), Intel CoreTM2 Quad CPU Q8400 @2.66 GHz 2.66 GHz 的CPU,以及1.96 GB的內(nèi)存。

5.3 有效性驗(yàn)證

實(shí)驗(yàn)中,我們?cè)O(shè)計(jì)的算法在所有的問(wèn)題實(shí)例上的每次運(yùn)行都找到了最優(yōu)解,即沒(méi)有相互干擾的分配方案。以下針對(duì)每個(gè)實(shí)例只列出某一次運(yùn)行得到的最終分配方案。

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

從表中的結(jié)果可以看到,算法成功找到了滿足EMC 的無(wú)相互干擾的分配方案,從而驗(yàn)證了算法的有效性。若以算法迭代的次數(shù)來(lái)衡量找到最優(yōu)解耗費(fèi)的時(shí)間,則當(dāng)設(shè)備數(shù)目分別為10、20、30、40、50 和100時(shí),算法分別迭代了1 次、3 次、8 次、14 次、17 次和93次找到最優(yōu)解,說(shuō)明在可用的頻道數(shù)目一定的情況下,設(shè)備數(shù)目越多則需要越長(zhǎng)的時(shí)間找到最優(yōu)解。

圖3 給出了100 個(gè)設(shè)備時(shí)算法當(dāng)前找到的最優(yōu)分配方案的干擾程度的演化曲線。從圖3 可以發(fā)現(xiàn),算法迭代了39 次就找到了不含嚴(yán)重干擾的分配方案。此外,還可以發(fā)現(xiàn),50 次迭代以前,干擾程度隨著搜索的進(jìn)行迅速降低,這實(shí)際是算法的交叉以及變異算子起主要作用的階段,該階段的目標(biāo)是搜索到可能存在最優(yōu)解的潛在區(qū)域。從第50 次迭代開(kāi)始,干擾程度隨著搜索的進(jìn)行“相對(duì)連續(xù)地”逐步減小,這是局部搜索算子在已找到的潛在區(qū)域內(nèi)更細(xì)致搜索導(dǎo)致的結(jié)果。

圖3 100 個(gè)設(shè)備時(shí)算法找到的當(dāng)前最優(yōu)分配方案的干擾程度隨迭代次數(shù)的演化曲線Fig.3 The evolutionary curve of the degree of interference of the optimal assignment found so far when there are 100 devices

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

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

6 結(jié) 語(yǔ)

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

[1] 李楠,張雪飛.戰(zhàn)場(chǎng)復(fù)雜電磁環(huán)境構(gòu)成分析[ J] .裝備環(huán)境工程,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] 古邦倫.電磁頻譜管理中的頻率分配技術(shù)研究[ D] .長(zhǎng)沙:國(guó)防科學(xué)技術(shù)大學(xué),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] 于江, 張磊, 沈劉平, 等.一種基于遺傳算法的戰(zhàn)場(chǎng)頻率分配方法[ J] .電訊技術(shù),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] 楊振宇.基于自然計(jì)算的實(shí)值優(yōu)化算法與應(yīng)用研究[D] .合肥:中國(guó)科學(xué)技術(shù)大學(xué),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)