基于改進(jìn)遺傳算法的頻率指配方法

基于改進(jìn)遺傳算法的頻率指配方法

1傳統(tǒng)優(yōu)化算法在頻率指配研究中的應(yīng)用目前，通信臺(tái)還采用了傳統(tǒng)的頻率壓縮方法，如手動(dòng)段分法、組分法和交叉分法。這些方法可以在一定程度上解決無線電頻率使用中的兼容性問題，但考慮到當(dāng)前信息水平不斷提高的現(xiàn)狀，這些傳統(tǒng)方法難以滿足當(dāng)前和高效化以及安全性的要求，難以適應(yīng)復(fù)雜的電磁環(huán)境和新的高效和智能信息。而近兩年將遺傳算法、蟻群算法、模擬退火算法等優(yōu)化算法引入到解決頻率指配問題的研究已成為熱點(diǎn),這大大提高了頻率指配的實(shí)時(shí)性和高效性,但這些傳統(tǒng)的優(yōu)化算法在進(jìn)行頻率指配時(shí)仍存在很多不足。為解決上述問題,本文根據(jù)通信電臺(tái)的用頻情況,結(jié)合通信電臺(tái)的工作特點(diǎn),采用一種應(yīng)用較為廣泛的遺傳算法對(duì)通信電臺(tái)進(jìn)行頻率指配,并對(duì)算法進(jìn)行了改進(jìn),這大大提高了算法的高效性和實(shí)時(shí)性。2臺(tái)風(fēng)的頻率組合及約束條件對(duì)同一區(qū)域內(nèi)同時(shí)工作的N個(gè)通信電臺(tái)進(jìn)行頻率指配,在這N個(gè)通信電臺(tái)同時(shí)工作時(shí)每個(gè)電臺(tái)都有各自的一段可用頻段,而頻率指配所要解決的問題是如何在每個(gè)電臺(tái)的可用頻段內(nèi),依據(jù)電磁兼容原則選取可用頻點(diǎn)分配給各個(gè)電臺(tái)使用。具體表示如下:設(shè)有N個(gè)電臺(tái),第i(i=1,2,…,N)個(gè)電臺(tái)的可用頻段為(fiLiL,fiΗiH),fiLiL為起始頻點(diǎn),fiΗiH為終止頻點(diǎn)。設(shè)電臺(tái)在頻段內(nèi)的頻率間隔為Δf。則第i個(gè)電臺(tái)在其可用頻段內(nèi)可選擇的頻點(diǎn)是(fiL,fiLiL+Δf,fiLiL+2Δf,…,fiΗiH)。這樣如果在各自頻段內(nèi)為每個(gè)電臺(tái)隨機(jī)地分配工作頻率之后就可以得到一個(gè)所有電臺(tái)的頻率組合:(f1,f2,…,fi,…,fN),其中fi∈{fiLiL,fiLiL+Δf,fiLiL+2Δf,…,fiΗiH},表示分配給電臺(tái)i的工作頻率。頻率指配的目的就是找到這樣的一系列頻率組合,使電臺(tái)按照所分配的頻率工作時(shí)相互之間能兼容工作。因此,對(duì)電臺(tái)同時(shí)工作時(shí)電磁兼容性進(jìn)行分析,通過設(shè)置約束條件來避免干擾的發(fā)生,對(duì)違反約束條件的約束數(shù)進(jìn)行統(tǒng)計(jì),建立數(shù)學(xué)模型如下:(1)電臺(tái)i和j之間違反同頻干擾條件約束判斷A(fi,fj)={1fi=fj且di,j<D0其余(i,j∈[1,Ν])(1)A(fi,fj)={1fi=fj且di,j<D0其余(i,j∈[1,N])(1)其中,D為兩電臺(tái)間不產(chǎn)生同頻干擾的最小間隔距離,di,j為兩電臺(tái)工作時(shí)實(shí)際物理距離,N為需指配的信道總數(shù)。(2)電臺(tái)i和j之間違反鄰頻干擾條件約束判斷Η(fi,fj)={1|fi-fj|≤l0|fi-fj|>l(i,j∈[1,Ν])(2)H(fi,fj)={1|fi?fj|≤l0|fi?fj|>l(i,j∈[1,N])(2)其中,l鄰頻信道最小間隔。(3)電臺(tái)i和j之間違反互調(diào)干擾條件約束判斷綜合上述三個(gè)干擾約束條件,可以得到目標(biāo)函數(shù),即總的干擾數(shù)目的表達(dá)式:E(f)=Ν∑i=1Ν∑j=1[αA(fi,fj)+βΗ(fi,fj)+γΜ(fi,fj)](4)E(f)=∑i=1N∑j=1N[αA(fi,fj)+βH(fi,fj)+γM(fi,fj)](4)其中,α、β、γ為權(quán)重系數(shù)。3算法的實(shí)現(xiàn)和改進(jìn)3.1適應(yīng)度函數(shù)前面已經(jīng)設(shè)計(jì)了系統(tǒng)的目標(biāo)函數(shù)E(f),由于適應(yīng)度函數(shù)的設(shè)計(jì)要求是使干擾數(shù)大的個(gè)體獲得較小的概率遺傳到下一代中,而干擾數(shù)較小的個(gè)體以較大概率遺傳到下一代中去,為了使干擾較小的個(gè)體獲得更大的適應(yīng)度,應(yīng)將適應(yīng)度函數(shù)F(E)與目標(biāo)函數(shù)E(f)定為反比例關(guān)系。由于個(gè)體的干擾數(shù)會(huì)出現(xiàn)0,因此還要設(shè)定一個(gè)適應(yīng)度常數(shù)C。適應(yīng)度函數(shù)與目標(biāo)函數(shù)的關(guān)系可以用式(5)表示:F(E)=1E(f)+C(5)F(E)=1E(f)+C(5)其中C為適應(yīng)度常數(shù),在文獻(xiàn)中作者經(jīng)過驗(yàn)證C的最佳取值為3.2。3.2個(gè)體編碼串遺傳算法中通常有符號(hào)編碼和二進(jìn)制編碼兩種方式。在本算法實(shí)現(xiàn)中,采用符號(hào)編碼方式。即對(duì)電臺(tái)的可用頻點(diǎn)進(jìn)行編號(hào),每個(gè)電臺(tái)分得的頻點(diǎn)就用該編號(hào)表示,這樣每組電臺(tái)都分得一個(gè)頻點(diǎn)編號(hào)之后,就得到了一個(gè)個(gè)體編碼串。如第i個(gè)電臺(tái)的可用頻段為(fiLiL,fiΗiH),頻率間隔為Δf,總共可劃分出n+1個(gè)可用頻點(diǎn),則所有可用頻點(diǎn)為(fiLiL,fiLiL+Δf,fiLiL+2Δf,…,fiLiL+n*Δf),進(jìn)行編碼后可以表示為(0,1,2,…,n)。3.3數(shù)據(jù)的初始化產(chǎn)生初始種群的方法通常有兩種,一種是完全隨機(jī)的方法產(chǎn)生的,它適合于對(duì)問題的解無任何先驗(yàn)知識(shí)的情況。某些先驗(yàn)知識(shí)可轉(zhuǎn)變?yōu)楸仨殱M足的一組要求,然后在滿足這些要求的解中再隨機(jī)地選取樣本,這樣選擇初始化種群可使遺傳算法更快地到達(dá)最優(yōu)解。本文采用加入某些先驗(yàn)知識(shí)的初始化方法,具體過程為:首先按照每個(gè)電臺(tái)的可用頻段及頻點(diǎn)之間的頻率間隔,計(jì)算出各個(gè)電臺(tái)的可用頻點(diǎn)數(shù),對(duì)電臺(tái)的各自可用頻點(diǎn)進(jìn)行編號(hào);然后依次向各電臺(tái)隨機(jī)分配該電臺(tái)可用頻點(diǎn)編號(hào)范圍內(nèi)的頻點(diǎn)編號(hào),直到所有電臺(tái)分配完畢。3.4有條件干擾實(shí)驗(yàn)群體的初始化完畢之后,就要對(duì)個(gè)體的適應(yīng)度進(jìn)行評(píng)估。評(píng)估的依據(jù)就是適應(yīng)度函數(shù)F(E),由適應(yīng)度函數(shù)與目標(biāo)函數(shù)的關(guān)系可知,對(duì)個(gè)體的評(píng)估主要依據(jù)個(gè)體對(duì)應(yīng)頻組的干擾數(shù)來定,當(dāng)搜索到干擾數(shù)為0的個(gè)體后,如解的存放區(qū)域還沒有個(gè)體,可以將其直接保存。如果解的存放區(qū)域已經(jīng)有解,就要判斷搜索到的解是否已經(jīng)存在。如果已經(jīng)存在就不保存繼續(xù)進(jìn)行評(píng)估,如果是新的解就按順序?qū)⑵浔４孢M(jìn)存放區(qū)域。4.5遺傳設(shè)計(jì)與改進(jìn)4.5.1pk/fkpk法本文在進(jìn)行遺傳操作時(shí)采用改進(jìn)的輪盤賭法選擇個(gè)體,傳統(tǒng)的輪盤賭選擇法即適應(yīng)度比例選擇法,設(shè)第k個(gè)個(gè)體的選擇概率為pk,適應(yīng)度值為Fk,則選擇概率為pk=FkΝ∑k=1Fkpk=Fk∑k=1NFk。傳統(tǒng)的選擇操作方法是對(duì)pk在(0,1)區(qū)間進(jìn)行區(qū)域劃分,然后選擇一個(gè)(0,1)區(qū)間的隨機(jī)數(shù)r,判斷r所在區(qū)間,按位置存儲(chǔ)該個(gè)體。本文引用群體平均適應(yīng)度值ˉFFˉˉˉ,首先判斷Fk與ˉFFˉˉˉ的大小,由于本文所求為目標(biāo)函數(shù)的最小值,即適應(yīng)度函數(shù)的最大值,在此只對(duì)Fk≥ˉFFk≥Fˉˉˉ的個(gè)體進(jìn)行保留,然后計(jì)算其選擇概率pk,這樣將大大提高計(jì)算效率。4.5.2自適應(yīng)交叉概率交叉操作是對(duì)種群中的兩個(gè)父代個(gè)體根據(jù)交叉概率pc進(jìn)行交叉操作,產(chǎn)生新的后代。因此交叉操作執(zhí)行前要設(shè)定交叉概率的大小,文獻(xiàn)中通過實(shí)驗(yàn)驗(yàn)證交叉概率最佳取值應(yīng)為0.91。但在進(jìn)化后期,隨著進(jìn)化次數(shù)的增加,解集群體逐漸靠近最優(yōu)解,此時(shí)如果再采用大的交叉率,則會(huì)產(chǎn)生許多發(fā)散分布在整個(gè)搜索空間的新個(gè)體,大的交叉率會(huì)導(dǎo)致破壞優(yōu)良個(gè)體所占比重,延緩收斂進(jìn)程。因此本文對(duì)交叉概率pc進(jìn)行了改進(jìn),采用隨進(jìn)化次數(shù)而改變的自適應(yīng)交叉概率,其公式為:pc=pc0-(pc0-pcmin)*dD(6)pc=pc0?(pc0?pcmin)*dD(6)其中,pc0為初始設(shè)置交叉率,pcmin為交叉概率最小取值,d為當(dāng)前進(jìn)化代數(shù),D為總的進(jìn)化代數(shù);通常pc0=0.95,pcmin=0.4。4.5.3變異概率的選取變異本身是一種局部隨機(jī)搜索,可以提供初始種群中未含有的基因,或找回選擇過程中丟失的基因,為種群提供新的內(nèi)容,使遺傳算法保持種群的多樣性。變異概率的選取非常重要,若變異概率取值較大的話,雖然能產(chǎn)生較多的新個(gè)體,但也有可能破壞很多較好的模式,使得遺傳算法的性能近似于隨機(jī)搜索算法的性能;若變異概率取值太小的話,則變異操作產(chǎn)生新個(gè)體的能力和抑制早熟的能力就會(huì)較差。一般情況下交叉概率選取為0.01到0.1之間。本文采用文獻(xiàn)中經(jīng)過實(shí)驗(yàn)驗(yàn)證后最佳變異概率0.095。5頻率指配仿真本