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

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

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

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

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

遺傳算法用于頻率分配3．1算法的基本流程采用遺傳算法的FAP基本流程3．2遺傳算子的選擇3．2．1選擇算子選擇算子在父代群體中選出父體和母體。生物界中，父母親素質(zhì)比較高的其后代素質(zhì)高的概率也大。模擬這種現(xiàn)象，在FAP中選擇算子采用輪賭算法實現(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)生下一代個體的雛形，起全局搜索的作用。交叉算子通常有單點交叉、雙點交叉、多點交叉等等。在頻率自動分配的算法中，為了不破壞基因段內(nèi)部頻點間的關(guān)系，采用單點交叉和雙點交叉比較合適。此外，在生物界中并不是兩個個體相遇了就一定會結(jié)合，模擬此現(xiàn)象，引入交叉因子pc。其基本流程如下：

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

crossover1(mother，father);

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

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

while(allfrequentpoint)

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

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