本文關(guān)鍵詞：圖的Steiner最小樹問題的算法與應(yīng)用研究

  更多相關(guān)文章： Steiner樹 遺傳算法 啟發(fā)式算法 隨機(jī)網(wǎng)絡(luò) 組播

【摘要】：圖的Steiner最小樹問題是經(jīng)典的組合優(yōu)化問題,在通信網(wǎng)絡(luò)和電路設(shè)計(jì)等領(lǐng)域有廣泛應(yīng)用。該問題是一個(gè)NP難題,雖然有一些精確算法,但是隨著網(wǎng)絡(luò)規(guī)模的增大,這些算法的運(yùn)行時(shí)間呈指數(shù)增長。為了能夠在多項(xiàng)式時(shí)間內(nèi)得到最優(yōu)解或者近似最優(yōu)解,尋找有效的啟發(fā)式算法就顯得尤為重要。本文對遺傳算法和傳統(tǒng)的啟發(fā)式算法進(jìn)行了改進(jìn),主要工作如下:1.針對基本遺傳算法采用自適應(yīng)規(guī)則,引入模擬退火思想,提出了一種解決Steiner最小樹問題的混合遺傳算法并進(jìn)行仿真實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明:與基本遺傳算法相比,改進(jìn)的混合遺傳算法能夠加快收斂速度,減少迭代次數(shù),使得到的解更穩(wěn)定。2.分析已有典型啟發(fā)式算法,提出了一種基于加權(quán)節(jié)點(diǎn)的Steiner樹啟發(fā)式算法。該算法根據(jù)正則點(diǎn)對間的最短路徑、節(jié)點(diǎn)的度數(shù)、與正則點(diǎn)連接的次數(shù)等計(jì)算出節(jié)點(diǎn)的權(quán)值,然后根據(jù)權(quán)值對最短路徑的費(fèi)用進(jìn)行修正,通過修正費(fèi)用最短路徑將正則點(diǎn)添加到多播樹中,從而實(shí)現(xiàn)更多鏈路的共享,降低整棵樹的費(fèi)用。3.為了模擬真實(shí)的通信網(wǎng)絡(luò)來測試算法的性能,本文對Waxman算法進(jìn)行改進(jìn),設(shè)計(jì)了一種逼近現(xiàn)實(shí)網(wǎng)絡(luò)特性的隨機(jī)網(wǎng)絡(luò)生成算法。用該算法生成不同規(guī)模的仿真網(wǎng)絡(luò),然后用啟發(fā)式算法對仿真網(wǎng)絡(luò)進(jìn)行求解,結(jié)果表明基于加權(quán)節(jié)點(diǎn)的啟發(fā)式算法是一個(gè)性能較好的算法。
【關(guān)鍵詞】：Steiner樹 遺傳算法 啟發(fā)式算法 隨機(jī)網(wǎng)絡(luò) 組播
【學(xué)位授予單位】：南京郵電大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類號(hào)】：O157.5
【目錄】：

• 摘要4-5
• Abstract5-8
• 第一章 緒論8-12
• 1.1 研究背景及意義8
• 1.2 課題研究現(xiàn)狀綜述8-9
• 1.3 本文主要內(nèi)容及章節(jié)安排9-12
• 1.3.1 主要?jiǎng)?chuàng)新10
• 1.3.2 章節(jié)安排10-12
• 第二章 Steiner最小樹問題及其相關(guān)算法12-20
• 2.1 Steiner最小樹問題12-13
• 2.2 問題定義與分析13-15
• 2.2.1 圖的Steiner樹的定義13-14
• 2.2.2 數(shù)學(xué)性質(zhì)分析14-15
• 2.2.3 多項(xiàng)式解法15
• 2.3 智能優(yōu)化算法簡介15-17
• 2.4 Steiner樹啟發(fā)式算法介紹17-19
• 2.5 本章小結(jié)19-20
• 第三章 Steiner最小樹問題的混合遺傳算法20-30
• 3.1 遺傳算法原理20-24
• 3.1.1 遺傳算法基本思想20
• 3.1.2 遺傳算法基本操作20-22
• 3.1.3 遺傳算法基本步驟22-23
• 3.1.4 遺傳算法存在的問題23-24
• 3.2 模擬退火與Metropolis準(zhǔn)則24
• 3.3 混合遺傳算法描述24-27
• 3.3.1 編碼方法和群體初始化24-25
• 3.3.2 適應(yīng)度計(jì)算和選擇種群25
• 3.3.3 交叉率和變異率的確定25-26
• 3.3.4 對最優(yōu)個(gè)體進(jìn)行模擬退火操作26-27
• 3.3.5 算法步驟27
• 3.4 實(shí)例測試27-29
• 3.5 本章小結(jié)29-30
• 第四章 基于加權(quán)節(jié)點(diǎn)的Steiner樹啟發(fā)式算法30-37
• 4.1 基于關(guān)鍵節(jié)點(diǎn)的啟發(fā)式算法30-31
• 4.2 基于加權(quán)節(jié)點(diǎn)的啟發(fā)式算法31-34
• 4.2.1 算法思想31
• 4.2.2 變量設(shè)置及公式31-32
• 4.2.3 算法步驟描述32-33
• 4.2.4 算法的正確性和復(fù)雜度33-34
• 4.3 實(shí)例分析34-36
• 4.4 本章小結(jié)36-37
• 第五章 網(wǎng)絡(luò)仿真與實(shí)驗(yàn)數(shù)據(jù)37-46
• 5.1 隨機(jī)網(wǎng)絡(luò)仿真模型37-41
• 5.1.1 Waxman算法37-38
• 5.1.2 Doar算法38
• 5.1.3 隨機(jī)網(wǎng)絡(luò)的產(chǎn)生38-41
• 5.2 仿真結(jié)果41-43
• 5.2.1 參數(shù)設(shè)置41
• 5.2.2 仿真結(jié)果分析41-43
• 5.3 Steiner最小樹問題的延伸43-45
• 5.3.1 靜態(tài)QoS約束的組播路由問題44
• 5.3.2 動(dòng)態(tài)無約束組播路由問題44-45
• 5.3.3 動(dòng)態(tài)QoS約束的組播路由問題45
• 5.4 本章小結(jié)45-46
• 第六章 總結(jié)與展望46-48
• 參考文獻(xiàn)48-51
• 附錄1 程序清單51-52
• 附錄2 攻讀碩士學(xué)位期間撰寫的論文52-53
• 致謝53

【參考文獻(xiàn)】

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

1 賀素良,喻壽益;基于動(dòng)態(tài)補(bǔ)償參數(shù)和改進(jìn)的自適應(yīng)遺傳算法的系統(tǒng)辨識(shí)方法[J];計(jì)算機(jī)工程與應(yīng)用;2003年19期

，

本文編號(hào)：1047305