1、一種啟發式頻率分派算法摘要:遺傳算法是依照生物學上的染色體基因因子組成機制而產生的一種啟發式算法。該算法以群體中的所有個體為對象，通過選擇、交叉、變異和重排序等類似生物遺傳的操作算子，取得知足必然群體適應度的新種群。遺傳算法為頻率分派問題提供了解決途徑。關鍵字：頻率分派遺傳算法GECP組合優化1 .通信網頻率分派問題的背景無線通信設備之間通過彼此發射電磁波達到信息溝通。彼此通信的設備之間利用特定的頻率（信道）組成無線通信鏈路。由于電磁波的自然特性，無線通信設備發射的電磁波可能對位于周圍、知足必然功率和頻率條件的其它設備形成干擾。頻率分派（FAP）的目的確實是給工作在必然地域內的無線通信設備指定

2、利用的工作頻率（或信道），使所有設備都以盡可能小的概率被干擾，從而使整個網絡的可用性取得優化。FAP能夠描述為：對N個給定的待分派工作頻率的鏈路，設G=S1,S2,Sn為所有狀態組成的解空間，C（si）為狀態si對應的目標函數值，尋覓最優解s*,使任意si£G,C（s*）=minC（si）。因此FAP是一種組合優化問題。具體設備頻率分派方式盡管會隨著設備的工作方式（單工、雙工）、工作頻段、天線類型、信號的調制解調方式的不同而有所區別，可是大部份頻率分派算法都能夠轉換為等價的圖的邊著色問題。從圖論算法理論上講，圖的廣義邊著色問題是NPC問題7,也確實是說無法在多項式時刻內求得問題的最優

3、解。例如關于存在n條邊的無向圖，利用c種顏色對其著色，在沒有其它約束條件下，其解空間是cn。即便在不考慮顏色重復利用（c>n）的情形下，其解空間也達到n!。這二者都是超越數，在c和n的值較大的情形下想利用窮舉搜索的方式求得問題的最優解在時刻上是不可行的。在工程實踐中許多NPC問題利用一些利用的近似算法取得問題的可行解。這些方式包括:只對問題的特殊實例求解；動態計劃（DP）或分支界限算法（BC）；概率算法；求近似解；啟發式算法（HeufisticAlgorithms）等。這些方式的和核心是分割問題的解空間，依照特定規那么搜索典型解作為次最優解。關于FAP問題國內外許多學者進行了深切

4、的研究，提出許多解決問題的方式。文獻4在對FAP進行理論分析的基礎上給出了幾種經常使用算法的框架，這些算法包括：最小-最后順序查找算法，貪婪T著色算法、模擬退火算法（SA）、列表尋優算法（TS）、遺傳算法（GA）、神經網絡（NN）多面體算法等，并指出各類算法有各自的適用范圍；文獻提出了利用啟發式的螞蟻算法，并對解決CELAR、GRAPH>PHILADELPHIA上的幾類問題同TS和SA算法進行了比較；文獻1比較了SA、TS>GA、YDS（variable-depthsearch）>BC等算法的性能。文獻7利用GECP理論對存在禁用頻率的異頻雙工設備的頻率分派給出工程上的有效算

5、法；文獻9那么采納了BC方式頻率分派的全排列算法進行了優化。本文將探討如何遺傳算法解決FAP問題。2 .遺傳算法在頻率分派問題中的適用性2.1遺傳算法的原理遺傳算法(GeneticAlgorithmsGA)是依照生物學上的染色體基因因子組成機制而產生的。1975年Holland教授第一次提出了GA的思想，從而吸引了大量的研究者，迅速推行到優化、搜索、機械學習等方面。遺傳算法是一種全局優化算法，其僅以目標函數值為搜索依據，通過群體優化搜索和隨機執行大體遺傳運算，實現遺傳群體的不斷進化，適合解決組合優化問題和復雜非線性問題6。利用遺傳算法解最優化問題，第一應付可行域中的點進行編碼(一樣采納二進制編

6、碼)，然后在可行域中隨機挑選一些編碼組成作為進化起點的第一代編碼組，并計算每一個解的目標函數值，也確實是編碼的適應度。接著就像自然界中一樣，利用選擇機制從編碼組中隨機挑選編碼作為繁衍進程前的編碼樣本。選擇機制應保證適應度較高的解能夠保留較多的樣本；而適應度較低的解那么保留較少的樣本，乃至被淘汰。在接下去的繁衍進程中，遺傳算法提供了交叉和變異兩種算子對挑選后的樣本進行互換。交叉算子互換隨機挑選的兩個編碼的某些位，變異算子那么直接對一個編碼中的隨機挑選的某一名進行反轉。如此通過選擇和繁衍就產生了下一代編碼組。重復上述選擇和繁衍進程，直到終止條件取得知足為止。進化進程最后一代中的最優解確實是用遺傳算

7、法解最優化問題所取得的最終結果。實踐說明，遺傳算法解最優化問題的計算效率比較高、適用范圍相當廣。為了說明這一現象，Holland給出了模式定理。所謂模式，確實是某些碼位取相同值的編碼的集合。模式定理說明在進化進程的各代碼中，屬于適應度高、階數低且長度短的圖式的編碼數量將隨代數以指數形式增加6。最近的研究那么說明，上述遺傳算法經適當改良后對任意優化問題以概率1收斂于全局最優解5。2. 2遺傳算法的大體結構在遺傳算法中，將問題的求解的進程，看成一個在候選解空間尋覓知足問題要求的解或近似解的搜索進程。遺傳算法的重點在適應計劃和適應氣宇方面。遺傳算法的適應計劃用于指導算法怎么樣在空間進行搜索，一樣采納

8、遺傳算子(或稱遺傳操作)諸如交配(Crossover)和變異(Mutation)等，和模擬自然進程的選擇機制，采納計算適應值的方式來評估一個候選解的好壞。遺傳算法求解問題的大體步驟能夠描述如下：1 .第一生成一組初始的候選解群體(假設為N個候選解個體),稱為第0代；2 .計算群體中各個候選解的適應值；3 .若是有候選解知足算法終止條件，算法終止，不然繼續4；4 .依照交配概率，將候選解群體中的個體隨機兩兩配對，進行交配操作以生成新的候選解；5 .依照變異概率，對4中生成的候選解群中的每一個個體進行變異操作；6 .利用選擇機制形成新一代候選解；轉2。GA算法具有下述特點：GA是對問題參數的編碼組

9、進行，而不是直接對參數本身；GA的搜索是從問題解的編碼組開始搜索，而不是從單個解開始；GA利用目標函數值(適應度)這一信息進行搜索，而不需導數等其他信息；GA算法利用的選擇、交叉、變異這三個算子都是隨機操作，而不是確信規那么。遺傳算法通過編碼和遺傳操作，達到了處置的并行性，能夠同時處置群體中的多個個體，即同時對搜索空間內的多個解進行評估，具有較好的全局搜索性能，減少了限于局部最優解的風險。7 .遺傳算法用于頻率分派3. 1算法的大體流程采納遺傳算法的FAP大體流程3. 2遺傳算子的選擇3. 2.1選擇算子選擇算子在父代群體當選出父體和母體。生物界中，父母親素養比較高的其后代素養高的概率也大。模

10、擬這種現象，在FAP當選擇算子采納輪賭算法實現。輪賭算法流程如下：sum=O;i=0;wheelpos=rand()*sumfitness;for(sum<wheelposSamp;&i<pop-size)i+；if(i2Pop-size)sum=O;i=0wheelpos=rand()*sumfitness;)j=rand()*pop-size;sum+=fitnessj;returnj;3. 2.2交叉算子交叉算子讓父體和母體互彼此換某部份基因此產生下一代個體的雛形，起全局搜索的作用。交叉算子通常有單點交叉、雙點交叉、多點交叉等等。在頻率自動分派

11、的算法中，為了不破壞基因段內部頻點間的關系，采納單點交叉和雙點交叉比較適合。另外，在生物界中并非是兩個個體相遇了就必然會結合，模擬此現象，引入交叉因子pc。其大體流程如下：物界中，父母的染色體交叉后產生后代個體的染色體雛形，那個雛形在成長進程中會發生基因的變異，正是這種變異使得下一代的群體中會顯現各類特點的個體.另外，生物界中并非每一個基因都會變異，模擬此現象，引入變異因子pm,利用方式與交叉因子類似。其大體流程如下：while(allfrequentpoint)if(flip(pm)mutate(frequentpoint)；4.工程上需要注意的問題4. 1初始候選種群由于遺傳算法和其它啟發

12、式算法一樣，不對全數解空間進行窮舉搜索,因此初始的候選解群體的選擇會對取得最終解的速度和質量有阻礙。初始的候選解群體在解空間內散布得越均勻，它們擁有的遺傳基因就越有代表性。實踐中采納文獻7的GECP取得以各個極點為主極點的可行解作為初始候選種群。4. 2編碼方案編碼確實是用一種數字排列方案來表示問題的解的方式，利用編碼將問題的解空間映射到GA算法的編碼空間。編碼方案的選擇依托于問題的性質，并阻礙到算法內操作的設計，是阻礙算法性能的重要因素。常見的編碼方案有二進制編碼、十進制編碼、實數編碼等。頻率分派問題適合采納十進制編碼方案，每一個碼表示一條通信鏈路，碼值表示分派的信道編號。4. 3適配值函數

13、適配值函數對個體(頻率分派方案)進行評判，也是優化進程進展的依據。能夠采納如下方式來計算適應度：fitness=1000/2(priXseperate(Freq)o其中：pri是節點的加權值；函數seperate(Freq)是節點中各條鏈路發頻率同其它鏈路的收頻率距離的和；參考文獻：1 Robert,PanosM.Pardalosetc,FrequencyAssignmentProblems,Handbookofcombinatorialoptimization,KluwerAcademicPublishers,19992 VittorioM.,AntonellaC.,AnANTSHeuristicfortheFrequencyAssignmentProblem,JoeBater,PeterJeavons,DavidCohen,ArethereoptimalreusedistanceconstraintsforFAPswithrandomTxplacement?,CSD-TR-98-01,CSRoyalHollowayUni.OfLondon,19984 Aardal,Hurkens,.etc.AlgorithmsforFree