小議通信網頻率分配思考
前言：本站為你精心整理了小議通信網頻率分配思考范文，希望能為你的創作提供參考價值，我們的客服老師可以幫助你提供個性化的參考范文，歡迎咨詢。
摘要：遺傳算法是根據生物學上的染色體基因因子構成機制而產生的一種啟發式算法。該算法以群體中的所有個體為對象，通過選擇、交叉、變異和重排序等類似生物遺傳的操作算子，得到滿足一定群體適應度的新種群。遺傳算法為頻率分配問題提供了解決途徑。
關鍵字：頻率分配遺傳算法GECP組合優化
無線通信設備之間通過相互發射電磁波達成信息溝通。相互通信的設備之間使用特定的頻率（信道）構成無線通信鏈路。由于電磁波的自然特性，無線通信設備發射的電磁波可能對位于附近、滿足一定功率和頻率條件的其它設備形成干擾。頻率分配（FAP）的目的就是給工作在一定地域內的無線通信設備指定使用的工作頻率(或信道)，使所有設備都以盡量小的概率被干擾，從而使整個網絡的可用性得到優化。FAP可以描述為：對N個給定的待分配工作頻率的鏈路，設G={S1,S2,…Sn}為所有狀態構成的解空間，C(si)為狀態si對應的目標函數值，尋找最優解s*，使任意si∈G，C(s*)=minC（si）。因此FAP是一種組合優化問題。
具體設備頻率分配方法雖然會隨著設備的工作方式（單工、雙工）、工作頻段、天線類型、信號的調制解調方式的不同而有所區別，但是大部分頻率分配算法都可以轉換為等價的圖的邊著色問題。從圖論算法理論上講，圖的廣義邊著色問題是NPC問題[7]，也就是說無法在多項式時間內求得問題的最優解。例如對于存在n條邊的無向圖，使用c種顏色對其著色，在沒有其它約束條件下，其解空間是cn。即使在不考慮顏色重復使用（c>n）的情況下，其解空間也達到n!。這兩者都是超越數，在c和n的值較大的情況下想利用窮舉搜索的方法求得問題的最優解在時間上是不可行的。
在工程實踐中許多NPC問題使用一些使用的近似算法得到問題的可行解。這些方法包括[]：只對問題的特殊實例求解；動態規劃（DP）或者分支界限算法（BC）；概率算法；求近似解；啟發式算法（HeufisticAlgorithms）等。這些方法的和核心是分割問題的解空間，按照特定規則搜索典型解作為次最優解。
對于FAP問題國內外許多學者進行了深入的研究，提出許多解決問題的方法。文獻[4]在對FAP進行理論分析的基礎上給出了幾種常用算法的框架，這些算法包括：最小-最后次序查找算法，貪心T著色算法、模擬退火算法（SA）、列表尋優算法（TS）、遺傳算法（GA）、神經網絡（NN）多面體算法等，并指出各種算法有各自的適用范圍；文獻[2]提出了利用啟發式的螞蟻算法，并對解決CELAR、GRAPH、PHILADELPHIA上的幾類問題同TS和SA算法進行了比較；文獻[1]比較了SA、TS、GA、VDS（variable–depthsearch）、BC等算法的性能。文獻[7]利用GECP理論對存在禁用頻率的異頻雙工設備的頻率分配給出工程上的實用算法；文獻[9]則采用了BC方法頻率分配的全排列算法進行了優化。本文將探討如何遺傳算法解決FAP問題。
2.遺傳算法在頻率分配問題中的適用性
2．1遺傳算法的原理
遺傳算法(GeneticAlgorithmsGA)是根據生物學上的染色體基因因子構成機制而產生的。1975年Holland教授首次提出了GA的思想，從而吸引了大批的研究者，迅速推廣到優化、搜索、機器學習等方面。遺傳算法是一種全局優化算法，其僅以目標函數值為搜索依據，通過群體優化搜索和隨機執行基本遺傳運算，實現遺傳群體的不斷進化，適合解決組合優化問題和復雜非線性問題[6]。
利用遺傳算法解最優化問題，首先應對可行域中的點進行編碼（一般采用二進制編碼），然后在可行域中隨機挑選一些編碼組成作為進化起點的第一代編碼組，并計算每個解的目標函數值，也就是編碼的適應度。接著就像自然界中一樣，利用選擇機制從編碼組中隨機挑選編碼作為繁殖過程前的編碼樣本。選擇機制應保證適應度較高的解能夠保留較多的樣本；而適應度較低的解則保留較少的樣本，甚至被淘汰。在接下去的繁殖過程中，遺傳算法提供了交叉和變異兩種算子對挑選后的樣本進行交換。交叉算子交換隨機挑選的兩個編碼的某些位，變異算子則直接對一個編碼中的隨機挑選的某一位進行反轉。這樣通過選擇和繁殖就產生了下一代編碼組。重復上述選擇和繁殖過程，直到結束條件得到滿足為止。進化過程最后一代中的最優解就是用遺傳算法解最優化問題所得到的最終結果。
實踐表明，遺傳算法解最優化問題的計算效率比較高、適用范圍相當廣。為了解釋這一現象，Holland給出了模式定理。所謂模式，就是某些碼位取相同值的編碼的集合。模式定理說明在進化過程的各代碼中，屬于適應度高、階數低且長度短的圖式的編碼數量將隨代數以指數形式增長[6]。最近的研究則表明，上述遺傳算法經適當改進后對任意優化問題以概率1收斂于全局最優解[5]。
2．2遺傳算法的基本結構
在遺傳算法中，將問題的求解的過程，看成一個在候選解空間尋找滿足問題要求的解或近似解的搜索過程。遺傳算法的重點在適應規劃和適應度量方面。遺傳算法的適應規劃用于指導算法怎么樣在空間進行搜索，一般采用遺傳算子(或稱遺傳操作)諸如交配(Crossover)和變異(Mutation)等，以及模擬自然過程的選擇機制，采用計算適應值的方法來評估一個候選解的優劣。
遺傳算法求解問題的基本步驟可以描述如下：
1.首先生成一組初始的候選解群體(假設為N個候選解個體)，稱為第0代；
2.計算群體中各個候選解的適應值；
3.如果有候選解滿足算法終止條件，算法終止，否則繼續4；
4.根據交配概率，將候選解群體中的個體隨機兩兩配對，進行交配操作以生成新的候選解；
5.根據變異概率，對4中生成的候選解群中的每個個體進行變異操作；
6.使用選擇機制形成新一代候選解；轉2。
GA算法具有下述特點：GA是對問題參數的編碼組進行，而不是直接對參數本身；GA的搜索是從問題解的編碼組開始搜索，而不是從單個解開始；GA使用目標函數值（適應度）這一信息進行搜索，而不需導數等其他信息；GA算法使用的選擇、交叉、變異這三個算子都是隨機操作，而不是確定規則。
遺傳算法通過編碼和遺傳操作，達到了處理的并行性，可以同時處理群體中的多個個體，即同時對搜索空間內的多個解進行評估，具有較好的全局搜索性能，減少了限于局部最優解的風險。
3.遺傳算法用于頻率分配
3．1算法的基本流程
采用遺傳算法的FAP基本流程
3．2遺傳算子的選擇
3．2．1選擇算子
選擇算子在父代群體中選出父體和母體。生物界中，父母親素質比較高的其后代素質高的概率也大。模擬這種現象，在FAP中選擇算子采用輪賭算法實現。
輪賭算法流程如下：
sum=0;i=0;
wheelpos=rand()*sumfitness;
for(sum<wheelpos&&i<pop-size)
｛
i++;
if(i≥pop-size)
｛
sum=0;i=0
wheelpos=rand()*sumfitness;
｝
j=rand()*pop-size;
sum+=fitness［j］;
｝
returnj;
3．2．2交叉算子
交叉算子讓父體和母體互相交換某部分基因而產生下一代個體的雛形，起全局搜索的作用。交叉算子通常有單點交叉、雙點交叉、多點交叉等等。在頻率自動分配的算法中，為了不破壞基因段內部頻點間的關系，采用單點交叉和雙點交叉比較合適。此外，在生物界中并不是兩個個體相遇了就一定會結合，模擬此現象，引入交叉因子pc。
其基本流程如下：
//flip函數中，產生一個0到1的隨機數，若小于pc，則返回1，否則返回0
if(flip(pc))
crossover1(mother,father);
elseif(flip(pc))
crossover2(mother,father);
else
copy(mother);
copy(father);
3．2．3變異算子
變異算子對后代個體的某些基因進行變異，起局部搜索的作用.生物界中，父母的染色體交叉后產生后代個體的染色體雛形，這個雛形在成長過程中會發生基因的變異，正是這種變異使得下一代的群體中會出現各種特征的個體.另外，生物界中并非每個基因都會變異，模擬此現象，引入變異因子pm，使用方法與交叉因子類似。
其基本流程如下：
while(allfrequentpoint)
{
if(flip(pm))mutate(frequentpoint)；}
4.工程上需要注意的問題
4．1初始候選種群
由于遺傳算法和其它啟發式算法一樣，不對全部解空間進行窮舉搜索，因此初始的候選解群體的選擇會對得到最終解的速度和質量有影響。初始的候選解群體在解空間內分布得越均勻，它們擁有的遺傳基因就越有代表性。實踐中采用文獻[7]的GECP得到以各個頂點為主頂點的可行解作為初始候選種群。
4．2編碼方案
編碼就是用一種數字排列方案來表示問題的解的方法，利用編碼將問題的解空間映射到GA算法的編碼空間。編碼方案的選擇依賴于問題的性質，并影響到算法內操作的設計，是影響算法性能的重要因素。常見的編碼方案有二進制編碼、十進制編碼、實數編碼等。頻率分配問題適合采用十進制編碼方案，每個碼表示一條通信鏈路，碼值表示分配的信道編號。
4．3適配值函數
適配值函數對個體（頻率分配方案）進行評價，也是優化過程發展的依據。可以采用如下方式來計算適應度：
fitness=1000/Σ(pri×seperate(Freq))。
其中：
pri是節點的加權值；
函數seperate(Freq)是節點中各條鏈路發頻率同其它鏈路的收頻率間隔的和；
參考文獻：
[1]RobertA.Murphey,PanosM.Pardalosetc,FrequencyAssignmentProblems,Handbookofcombinatorialoptimization,KluwerAcademicPublishers,1999
[2]VittorioM.,AntonellaC.,AnANTSHeuristicfortheFrequencyAssignmentProblem,www.csr.unibo.it
[3]JoeBater,PeterJeavons,DavidCohen,ArethereoptimalreusedistanceconstraintsforFAPswithrandomTxplacement?,CSD-TR-98-01,CSRoyalHollowayUni.OfLondon,1998
[4]K.IAardal,C.A.J.Hurkens,J.K.etc.AlgorithmsforFreequencyAssignmentProblems,CWIQuarterly,Vol9(1&2),1996
[5]王凌：《智能優化算法及其應用》清華大學出版社2001
[6]陳國良等：《遺傳算法及其應用》人民郵電出版社1996
[7]孫俊柏：禁用頻點、頻段下野戰通信網的頻率分配中國科學技術大學碩士學位論文1998
[8]王曉東：《計算機算法設計與分析》電子工業出版社2001
[9]高建文，李單鏑：通信網頻率分配算法設計無線電通信技術Vol25（5）199
