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

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

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

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

【參考文獻】

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

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

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

，

本文編號：1115546