基于圖染色的頻率分配問題的研究.pdf

1、頻率分配問題是一種完全多項式非確定性問題，屬于多目標組合最優(yōu)化問題。通常，頻率分配的算法包括確定性算法、啟發(fā)式算法、計算智能方法等。確定性算法每步可以得到確定的結果，但運行時間不能確定；啟發(fā)式算法通?？梢栽诤侠淼臅r間內解出答案，但不能保證每次的效率；計算智能方法具有自學習、自組織、自適應的特征和簡單、通用、魯棒性強、適于并行化處理的優(yōu)點。本文研究的圖染色算法就是計算智能方法的一種。
　　針對大多數頻率分配算法在收斂性、均衡性等方面

2、存在的不足，結合圖論圖染色的特性，本文主要研究了圖頂點染色算法和廣義圖染色算法在頻率分配問題上的應用。論文圍繞頻率分配的關鍵技術，從以下幾個方面展開了研究：
　?。?）針對傳統(tǒng)頻率分配算法收斂性差、時間復雜度高、局部搜索能力不強等缺點，提出了一種基于圖頂點染色的混合優(yōu)化算法。該算法首先通過遺傳算法產生后代解對問題進行初始化，然后根據圖節(jié)點度的大小，將圖中頂點進行排序染色，在相同的空間復雜度的情況下降低了編碼執(zhí)行的隨機性，提高了整個

3、系統(tǒng)的公平性；同時，利用禁忌搜索算法對搜索空間進行雙領域交替搜索，減少算法陷入局部最優(yōu)而產生的迂回，大大提高了算法的收斂速度。
　?。?）針對頻率分配問題中產生的鄰頻干擾，提出了一種新的基于廣義圖染色(T-Colorings)的優(yōu)化算法。該算法以圖頂點染色的混合優(yōu)化算法為基礎，把網絡中的每個節(jié)點視為是獨立、同步運行的，通過分布式并行執(zhí)行，有效地提高了算法運行速度。在網絡拓撲發(fā)生變化時，廣義圖染色優(yōu)化算法只需在對比原來信息和現在信息

4、之后,對局部做出少量修改補償來完成新的頻譜分配，而不需要重新生成分配方案，顯著降低了系統(tǒng)開銷。
　?。?）本文通過圖染色基準問題在Microsoft Visual Studio.NET2013平臺上進行測試。實驗結果表明基于圖頂點染色的混合優(yōu)化算法在考慮到對用戶的公平性的基礎上，有較好的尋優(yōu)能力和更快的收斂速度，能準確地得出滿足全局最優(yōu)的目標解。通過費城實例進行仿真實驗測試，實證了廣義圖染色優(yōu)化算法在一定程度上提高了信號間的抗干擾