一種啟發(fā)式頻率分配算法

一種啟發(fā)式頻率分配算法

摘要：遺傳算法是根據(jù)生物學(xué)上的染色體基因因子構(gòu)成機(jī)制而產(chǎn)生的一種啟發(fā)式算法。該算法以群體中的所有個(gè)體為對(duì)象，通過選擇、交叉、變異和重排序等類似生物遺傳的操作算子，得到滿足一定群體適應(yīng)度的新種群。遺傳算法為頻率分配問題提供了解決途徑。關(guān)鍵字：頻率分配遺傳算法GECP組合優(yōu)化1.

通信網(wǎng)頻率分配問題的背景無(wú)線通信設(shè)備之間通過相互發(fā)射電磁波達(dá)成信息溝通。相互通信的設(shè)備之間使用特定的頻率（信道）構(gòu)成無(wú)線通信鏈路。由于電磁波的自然特性，無(wú)線通信設(shè)備發(fā)射的電磁波可能對(duì)位于附近、滿足一定功率和頻率條件的其它設(shè)備形成干擾。頻率分配（FAP）的目的就是給工作在一定地域內(nèi)的無(wú)線通信設(shè)備指定使用的工作頻率(或信道)，使所有設(shè)備都以盡量小的概率被干擾，從而使整個(gè)網(wǎng)絡(luò)的可用性得到優(yōu)化。FAP可以描述為：對(duì)N個(gè)給定的待分配工作頻率的鏈路，設(shè)G={S1，S2，…Sn}為所有狀態(tài)構(gòu)成的解空間，C(si)為狀態(tài)si對(duì)應(yīng)的目標(biāo)函數(shù)值，尋找最優(yōu)解s*，使任意si∈G，C(s*)=minC（si）。因此FAP是一種組合優(yōu)化問題。具體設(shè)備頻率分配方法雖然會(huì)隨著設(shè)備的工作方式（單工、雙工）、工作頻段、天線類型、信號(hào)的調(diào)制解調(diào)方式的不同而有所區(qū)別，但是大部分頻率分配算法都可以轉(zhuǎn)換為等價(jià)的圖的邊著色問題。從圖論算法理論上講，圖的廣義邊著色問題是NPC問題[7]，也就是說無(wú)法在多項(xiàng)式時(shí)間內(nèi)求得問題的最優(yōu)解。例如對(duì)于存在n條邊的無(wú)向圖，使用c種顏色對(duì)其著色，在沒有其它約束條件下，其解空間是cn。即使在不考慮顏色重復(fù)使用（c>n）的情況下，其解空間也達(dá)到n!。這兩者都是超越數(shù)，在c和n的值較大的情況下想利用窮舉搜索的方法求得問題的最優(yōu)解在時(shí)間上是不可行的。在工程實(shí)踐中許多NPC問題使用一些使用的近似算法得到問題的可行解。這些方法包括[]：只對(duì)問題的特殊實(shí)例求解；動(dòng)態(tài)規(guī)劃（DP）或者分支界限算法（BC）；概率算法；求近似解；啟發(fā)式算法（HeufisticAlgorithms）等。這些方法的和核心是分割問題的解空間，按照特定規(guī)則搜索典型解作為次最優(yōu)解。對(duì)于FAP問題國(guó)內(nèi)外許多學(xué)者進(jìn)行了深入的研究，提出許多解決問題的方法。文獻(xiàn)[4]在對(duì)FAP進(jìn)行理論分析的基礎(chǔ)上給出了幾種常用算法的框架，這些算法包括：最小-最后次序查找算法，貪心T著色算法、模擬退火算法（SA）、列表尋優(yōu)算法（TS）、遺傳算法（GA）、神經(jīng)網(wǎng)絡(luò)（NN）多面體算法等，并指出各種算法有各自的適用范圍；文獻(xiàn)[2]提出了利用啟發(fā)式的螞蟻算法，并對(duì)解決CELAR、GRAPH、PHILADELPHIA上的幾類問題同TS和SA算法進(jìn)行了比較；文獻(xiàn)[1]比較了SA、TS、GA、VDS（variable–depthsearch）、BC等算法的性能。文獻(xiàn)[7]利用GECP理論對(duì)存在禁用頻率的異頻雙工設(shè)備的頻率分配給出工程上的實(shí)用算法；文獻(xiàn)[9]則采用了BC方法頻率分配的全排列算法進(jìn)行了優(yōu)化。本文將探討如何遺傳算法解決FAP問題。2.

遺傳算法在頻率分配問題中的適用性2．1遺傳算法的原理遺傳算法(GeneticAlgorithmsGA)是根據(jù)生物學(xué)上的染色體基因因子構(gòu)成機(jī)制而產(chǎn)生的。1975年Holland教授首次提出了GA的思想，從而吸引了大批的研究者，迅速推廣到優(yōu)化、搜索、機(jī)器學(xué)習(xí)等方面。遺傳算法是一種全局優(yōu)化算法，其僅以目標(biāo)函數(shù)值為搜索依據(jù)，通過群體優(yōu)化搜索和隨機(jī)執(zhí)行基本遺傳運(yùn)算，實(shí)現(xiàn)遺傳群體的不斷進(jìn)化，適合解決組合優(yōu)化問題和復(fù)雜非線性問題[6]。利用遺傳算法解最優(yōu)化問題，首先應(yīng)對(duì)可行域中的點(diǎn)進(jìn)行編碼（一般采用二進(jìn)制編碼），然后在可行域中隨機(jī)挑選一些編碼組成作為進(jìn)化起點(diǎn)的第一代編碼組，并計(jì)算每個(gè)解的目標(biāo)函數(shù)值，也就是編碼的適應(yīng)度。接著就像自然界中一樣，利用選擇機(jī)制從編碼組中隨機(jī)挑選編碼作為繁殖過程前的編碼樣本。選擇機(jī)制應(yīng)保證適應(yīng)度較高的解能夠保留較多的樣本；而適應(yīng)度較低的解則保留較少的樣本，甚至被淘汰。在接下去的繁殖過程中，遺傳算法提供了交叉和變異兩種算子對(duì)挑選后的樣本進(jìn)行交換。交叉算子交換隨機(jī)挑選的兩個(gè)編碼的某些位，變異算子則直接對(duì)一個(gè)編碼中的隨機(jī)挑選的某一位進(jìn)行反轉(zhuǎn)。這樣通過選擇和繁殖就產(chǎn)生了下一代編碼組。重復(fù)上述選擇和繁殖過程，直到結(jié)束條件得到滿足為止。進(jìn)化過程最后一代中的最優(yōu)解就是用遺傳算法解最優(yōu)化問題所得到的最終結(jié)果。實(shí)踐表明，遺傳算法解最優(yōu)化問題的計(jì)算效率比較高、適用范圍相當(dāng)廣。為了解釋這一現(xiàn)象，Holland給出了模式定理。所謂模式，就是某些碼位取相同值的編碼的集合。模式定理說明在進(jìn)化過程的各代碼中，屬于適應(yīng)度高、階數(shù)低且長(zhǎng)度短的圖式的編碼數(shù)量將隨代數(shù)以指數(shù)形式增長(zhǎng)[6]。最近的研究則表明，上述遺傳算法經(jīng)適當(dāng)改進(jìn)后對(duì)任意優(yōu)化問題以概率1收斂于全局最優(yōu)解[5]。2．2遺傳算法的基本結(jié)構(gòu)在遺傳算法中，將問題的求解的過程，看成一個(gè)在候選解空間尋找滿足問題要求的解或近似解的搜索過程。遺傳算法的重點(diǎn)在適應(yīng)規(guī)劃和適應(yīng)度量方面。遺傳算法的適應(yīng)規(guī)劃用于指導(dǎo)算法怎么樣在空間進(jìn)行搜索，一般采用遺傳算子(或稱遺傳操作)諸如交配(Crossover)和變異(Mutation)等，以及模擬自然過程的選擇機(jī)制，采用計(jì)算適應(yīng)值的方法來(lái)評(píng)估一個(gè)候選解的優(yōu)劣。遺傳算法求解問題的基本步驟可以描述如下：1.首先生成一組初始的候選解群體(假設(shè)為N個(gè)候選解個(gè)體)，稱為第0代；2.計(jì)算群體中各個(gè)候選解的適應(yīng)值；3.如果有候選解滿足算法終止條件，算法終止，否則繼續(xù)4；4.根據(jù)交配概率，將候選解群體中的個(gè)體隨機(jī)兩兩配對(duì)，進(jìn)行交配操作以生成新的候選解；5.根據(jù)變異概率，對(duì)4中生成的候選解群中的每個(gè)個(gè)體進(jìn)行變異操作；6.使用選擇機(jī)制形成新一代候選解；轉(zhuǎn)2。GA算法具有下述特點(diǎn)：GA是對(duì)問題參數(shù)的編碼組進(jìn)行，而不是直接對(duì)參數(shù)本身；GA的搜索是從問題解的編碼組開始搜索，而不是從單個(gè)解開始；GA使用目標(biāo)函數(shù)值（適應(yīng)度）這一信息進(jìn)行搜索，而不需導(dǎo)數(shù)等其他信息；GA算法使用的選擇、交叉、變異這三個(gè)算子都是隨機(jī)操作，而不是確定規(guī)則。遺傳算法通過編碼和遺傳操作，達(dá)到了處理的并行性，可以同時(shí)處理群體中的多個(gè)個(gè)體，即同時(shí)對(duì)搜索空間內(nèi)的多個(gè)解進(jìn)行評(píng)估，具有較好的全局搜索性能，減少了限于局部最優(yōu)解的風(fēng)險(xiǎn)。3.

遺傳算法用于頻率分配3．1算法的基本流程采用遺傳算法的FAP基本流程3．2遺傳算子的選擇3．2．1選擇算子選擇算子在父代群體中選出父體和母體。生物界中，父母親素質(zhì)比較高的其后代素質(zhì)高的概率也大。模擬這種現(xiàn)象，在FAP中選擇算子采用輪賭算法實(shí)現(xiàn)。輪賭算法流程如下：

sum=0;i=0;

wheelpos=rand()*sumfitness;

for(sum<wheelpos&&i<pop-size)

｛

i++;

if(i≥pop-size)｛sum=0;i=0wheelpos=rand()*sumfitness;｝

j=rand()*pop-size;

sum+=fitness［j］;

｝

returnj;3．2．2交叉算子交叉算子讓父體和母體互相交換某部分基因而產(chǎn)生下一代個(gè)體的雛形，起全局搜索的作用。交叉算子通常有單點(diǎn)交叉、雙點(diǎn)交叉、多點(diǎn)交叉等等。在頻率自動(dòng)分配的算法中，為了不破壞基因段內(nèi)部頻點(diǎn)間的關(guān)系，采用單點(diǎn)交叉和雙點(diǎn)交叉比較合適。此外，在生物界中并不是兩個(gè)個(gè)體相遇了就一定會(huì)結(jié)合，模擬此現(xiàn)象，引入交叉因子pc。其基本流程如下：

//flip函數(shù)中，產(chǎn)生一個(gè)0到1的隨機(jī)數(shù)，若小于pc，則返回1，否則返回0if(flip(pc))

crossover1(mother，father);

elseif(flip(pc))crossover2(mother，father);

elsecopy(mother);copy(father);3．2．3變異算子變異算子對(duì)后代個(gè)體的某些基因進(jìn)行變異，起局部搜索的作用.生物界中，父母的染色體交叉后產(chǎn)生后代個(gè)體的染色體雛形，這個(gè)雛形在成長(zhǎng)過程中會(huì)發(fā)生基因的變異，正是這種變異使得下一代的群體中會(huì)出現(xiàn)各種特征的個(gè)體.另外，生物界中并非每個(gè)基因都會(huì)變異，模擬此現(xiàn)象，引入變異因子pm，使用方法與交叉因子類似。其基本流程如下：

while(allfrequentpoint)

{if(flip(pm))mutate(frequentpoint)；}4.

工程上需要注意的問題4．1初始候選種群由于遺傳算法和其它啟發(fā)式算法一樣，不對(duì)全部解空間進(jìn)行窮舉搜索，因此初始的候選解群體的選擇會(huì)對(duì)得到最終解的速度和質(zhì)量有影響。初始的候選解群體在解空間內(nèi)分布得越均勻，它們擁有的遺傳基因就越有代表性。實(shí)踐中采用文獻(xiàn)[7]的GECP得到以各個(gè)頂點(diǎn)為主頂點(diǎn)的可行解作為初始候選種群。4．2編碼方案編碼就是用一種數(shù)字排列方案來(lái)表示問題的解的方法，利用編碼將問題的解空間映射到GA算法的編碼空間。編碼方案的選擇依賴于問題的性質(zhì)，并影響到算法內(nèi)操作的設(shè)計(jì)，是影響算法性能的重要因素。常見的編碼方案有二進(jìn)制編碼、十進(jìn)制編