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

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

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

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

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