本文關(guān)鍵詞：基于圖染色的頻率分配問(wèn)題的研究

  更多相關(guān)文章： 頻率分配 圖染色算法 禁忌搜索算法 雙領(lǐng)域交替搜索

【摘要】：頻率分配問(wèn)題是一種完全多項(xiàng)式非確定性問(wèn)題,屬于多目標(biāo)組合最優(yōu)化問(wèn)題。通常,頻率分配的算法包括確定性算法、啟發(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ù)頻率分配算法在收斂性、均衡性等方面存在的不足,結(jié)合圖論圖染色的特性,本文主要研究了圖頂點(diǎn)染色算法和廣義圖染色算法在頻率分配問(wèn)題上的應(yīng)用。論文圍繞頻率分配的關(guān)鍵技術(shù),從以下幾個(gè)方面展開(kāi)了研究:(1)針對(duì)傳統(tǒng)頻率分配算法收斂性差、時(shí)間復(fù)雜度高、局部搜索能力不強(qiáng)等缺點(diǎn),提出了一種基于圖頂點(diǎn)染色的混合優(yōu)化算法。該算法首先通過(guò)遺傳算法產(chǎn)生后代解對(duì)問(wèn)題進(jìn)行初始化,然后根據(jù)圖節(jié)點(diǎn)度的大小,將圖中頂點(diǎn)進(jìn)行排序染色,在相同的空間復(fù)雜度的情況下降低了編碼執(zhí)行的隨機(jī)性,提高了整個(gè)系統(tǒng)的公平性;同時(shí),利用禁忌搜索算法對(duì)搜索空間進(jìn)行雙領(lǐng)域交替搜索,減少算法陷入局部最優(yōu)而產(chǎn)生的迂回,大大提高了算法的收斂速度。(2)針對(duì)頻率分配問(wèn)題中產(chǎn)生的鄰頻干擾,提出了一種新的基于廣義圖染色(T-Colorings)的優(yōu)化算法。該算法以圖頂點(diǎn)染色的混合優(yōu)化算法為基礎(chǔ),把網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)視為是獨(dú)立、同步運(yùn)行的,通過(guò)分布式并行執(zhí)行,有效地提高了算法運(yùn)行速度。在網(wǎng)絡(luò)拓?fù)浒l(fā)生變化時(shí),廣義圖染色優(yōu)化算法只需在對(duì)比原來(lái)信息和現(xiàn)在信息之后,對(duì)局部做出少量修改補(bǔ)償來(lái)完成新的頻譜分配,而不需要重新生成分配方案,顯著降低了系統(tǒng)開(kāi)銷(xiāo)。(3)本文通過(guò)圖染色基準(zhǔn)問(wèn)題在Microsoft Visual Studio.NET 2013平臺(tái)上進(jìn)行測(cè)試。實(shí)驗(yàn)結(jié)果表明基于圖頂點(diǎn)染色的混合優(yōu)化算法在考慮到對(duì)用戶(hù)的公平性的基礎(chǔ)上,有較好的尋優(yōu)能力和更快的收斂速度,能準(zhǔn)確地得出滿足全局最優(yōu)的目標(biāo)解。通過(guò)費(fèi)城實(shí)例進(jìn)行仿真實(shí)驗(yàn)測(cè)試,實(shí)證了廣義圖染色優(yōu)化算法在一定程度上提高了信號(hào)間的抗干擾能力,實(shí)現(xiàn)了頻率資源的最大化。
【關(guān)鍵詞】：頻率分配 圖染色算法 禁忌搜索算法 雙領(lǐng)域交替搜索
【學(xué)位授予單位】：江西理工大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類(lèi)號(hào)】：TN925
【目錄】：

• 摘要4-5
• Abstract5-10
• 第一章 緒論10-15
• 1.1 研究背景和意義10
• 1.2 國(guó)內(nèi)外研究10-12
• 1.2.1 國(guó)內(nèi)外研究現(xiàn)狀10-12
• 1.2.2 頻率分配問(wèn)題的發(fā)展方向12
• 1.3 頻率分配與圖染色的主要研究?jī)?nèi)容12-13
• 1.4 論文的主要內(nèi)容及組織結(jié)構(gòu)13-15
• 第二章 頻率分配問(wèn)題15-24
• 2.1 頻率分配概述16-18
• 2.1.1 頻率分配的概念與發(fā)展16-17
• 2.1.2 頻率分配的作用17
• 2.1.3 頻率分配的分類(lèi)17-18
• 2.1.4 頻率分配策略的比較18
• 2.2 頻率分配方案18-21
• 2.2.1 頻率分配中的約束條件19
• 2.2.2 頻率分配模型19-20
• 2.2.3 頻率分配的主要性能指標(biāo)20-21
• 2.3 頻率分配的特性21
• 2.4 頻率分配方案的算法與分析21-23
• 2.4.1 頻率分配的常用算法21
• 2.4.2 頻率分配的常用算法分析21-23
• 2.5 本章小結(jié)23-24
• 第三章 圖染色問(wèn)題24-33
• 3.1 圖染色問(wèn)題的概述24-27
• 3.1.1 預(yù)備知識(shí)24
• 3.1.2 圖染色問(wèn)題的起源24-25
• 3.1.3 圖染色的相關(guān)概念25-26
• 3.1.4 圖染色問(wèn)題的相互轉(zhuǎn)化26-27
• 3.2 圖染色問(wèn)題的模型27-29
• 3.3 圖染色問(wèn)題的算法分析29
• 3.4 圖染色問(wèn)題與頻率分配的關(guān)系29-32
• 3.4.1 圖染色問(wèn)題與頻率分配問(wèn)題的相互轉(zhuǎn)化30
• 3.4.2 圖染色問(wèn)題與頻率分配問(wèn)題的異同30-32
• 3.5 本章小結(jié)32-33
• 第四章 基于圖頂點(diǎn)染色的混合優(yōu)化算法33-43
• 4.1 問(wèn)題的提出33
• 4.2 基于圖染色的混合優(yōu)化算法相關(guān)概念33-36
• 4.3 圖頂點(diǎn)染色的混合優(yōu)化算法36-42
• 4.3.1 算法思想36
• 4.3.2 初始解的生成36-37
• 4.3.3 雙領(lǐng)域交替搜索37-38
• 4.3.4 算法執(zhí)行38-40
• 4.3.5 實(shí)驗(yàn)結(jié)果與分析40-41
• 4.3.6 算法復(fù)雜度分析41-42
• 4.4 本章小結(jié)42-43
• 第五章 廣義圖染色優(yōu)化算法在頻率分配中的應(yīng)用43-52
• 5.1 問(wèn)題的提出43
• 5.2 基于廣義圖染色的優(yōu)化算法相關(guān)理論知識(shí)43-46
• 5.2.1 基于廣義圖染色優(yōu)化算法的主要參數(shù)43-44
• 5.2.2 費(fèi)城實(shí)例44-46
• 5.3 基于廣義圖染色優(yōu)化算法46-50
• 5.3.1 廣義圖染色優(yōu)化算法的主要思想46
• 5.3.2 初始解的生成46-48
• 5.3.3 廣義圖染色優(yōu)化算法的執(zhí)行48-50
• 5.4 基于廣義圖染色的優(yōu)化算法的實(shí)驗(yàn)與結(jié)果分析50-51
• 5.4.1 費(fèi)城實(shí)例的實(shí)驗(yàn)結(jié)果50
• 5.4.2 算法復(fù)雜度分析50-51
• 5.5 本章小結(jié)51-52
• 第六章 總結(jié)與展望52-54
• 6.1 工作總結(jié)52-53
• 6.2 研究展望53-54
• 參考文獻(xiàn)54-57
• 致謝57-58
• 攻讀學(xué)位期間的研究成果58-59

【參考文獻(xiàn)】

中國(guó)期刊全文數(shù)據(jù)庫(kù) 前2條

1 張遠(yuǎn)平;張永生;;一種求解頻率分配問(wèn)題的分布式算法[J];科學(xué)技術(shù)與工程;2006年20期

2 秦嶺松,喬秦寶,宋光愛(ài),陳澤宗;圖著色問(wèn)題的細(xì)胞神經(jīng)網(wǎng)絡(luò)算法研究[J];武漢水利電力大學(xué)學(xué)報(bào);1999年02期

，

本文編號(hào)：1115546