本文關(guān)鍵詞：基于遺傳算法的度約束最小生成樹問題的研究，由筆耕文化傳播整理發(fā)布。

【摘要】：度約束最小生成樹(Degree Constrained Minimum Spanning Tree, DCMST)問題是網(wǎng)絡(luò)優(yōu)化中一個常見的問題。近年來,度約束最小生成樹在計算機網(wǎng)絡(luò)、通信網(wǎng)絡(luò)和運輸網(wǎng)絡(luò)設(shè)計等領(lǐng)域得到了廣泛的應(yīng)用,許多網(wǎng)絡(luò)設(shè)計問題都和度約束最小生成樹問題有關(guān)。比如,在構(gòu)建通訊網(wǎng)絡(luò)時,網(wǎng)絡(luò)布局就是尋找連通圖的生成樹,建網(wǎng)費用最少就是尋找最小生成樹,每個結(jié)點負(fù)載不能太多就是對結(jié)點的度約束。然而,度約束的最小生成樹的求解被證明是一個NP難問題,因此對大規(guī)模DCMST問題,目前還沒有有效的算法。本文介紹了求解DCMST問題的古典算法、啟發(fā)式算法以及現(xiàn)代優(yōu)化算法。設(shè)計了一種在非完全圖下求解度約束最小生成樹問題的遺傳算法,為此構(gòu)造了新的編碼方法、適應(yīng)度函數(shù)、初始化方法、遺傳算子。為了加快優(yōu)化進(jìn)度,設(shè)計了尋優(yōu)算子,取得了較好的效果。
【關(guān)鍵詞】：度約束 最小生成樹 DCMST 非完全圖 遺傳算法
【學(xué)位授予單位】：內(nèi)蒙古大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2015
【分類號】：O157.5;TP18
【目錄】：

• 摘要4-5
• Abstract5-9
• 第一章 緒論9-12
• 1.1 度約束最小生成樹問題簡介9-10
• 1.1.1 度約束最小生成樹的提出背景及研究意義9-10
• 1.1.2 度約束最小生成樹的研究現(xiàn)狀10
• 1.2 本文的主要內(nèi)容及結(jié)構(gòu)10-11
• 1.3 本文創(chuàng)新工作11-12
• 第二章 DCMST問題綜述12-20
• 2.1 基本概念及有關(guān)結(jié)論12-14
• 2.2 基本符號說明14-15
• 2.3 DCMST問題的數(shù)學(xué)模型15
• 2.4 求解DCMST算法綜述15-20
• 2.4.1 求解DCMST問題的精確算法16
• 2.4.2 求解DCMST問題的啟發(fā)式算法16-18
• 2.4.3 求解DCMST問題的現(xiàn)代優(yōu)化算法18-20
• 第三章 求解度約束最小生成樹的遺傳算法20-49
• 3.1 求解DCMST問題的遞歸算法20-23
• 3.1.1 給出連通圖全部生成樹的方法簡介20
• 3.1.2 度約束最小生成樹的遞歸算法20-23
• 3.2 求解DCMST問題的新快速算法QDC23-27
• 3.2.1 定義邊的可用度值23-24
• 3.2.2 修改邊的可用度值的DET算法24
• 3.2.3 求解度約束生成樹的快速算法QDC24-25
• 3.2.4 快速算法QDC有時會找不到生成樹25-27
• 3.3 求解DCMST問題算法的討論27-32
• 3.3.1 d-prim算法和d-kruska算法的進(jìn)一步討論27-29
• 3.3.2 采用Prufer編碼方式遺傳算法的進(jìn)一步討論29-30
• 3.3.3 構(gòu)造新算法的基本思路30-32
• 3.4 求解DCMST問題的遺傳算法流程32-33
• 3.5 編碼和解碼33-36
• 3.6 適應(yīng)度函數(shù)36-37
• 3.7 初始化種群37-38
• 3.8 選擇算子38-39
• 3.9 遺傳算子39-46
• 3.9.1 交叉算子39-44
• 3.9.2 變異算子44-46
• 3.10 尋優(yōu)算子46-48
• 3.11 算法終止條件48-49
• 第四章 結(jié)論49-50
• 參考文獻(xiàn)50-52
• 致謝52

【參考文獻(xiàn)】

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

1 朱曉虹;;量子遺傳算法求解度約束最小生成樹[J];巢湖學(xué)院學(xué)報;2010年06期

2 董軍,關(guān)鳳巖,呂宗寶;基于遺傳算法度約束的最小生成樹問題的研究[J];淮北煤炭師范學(xué)院學(xué)報(自然科學(xué)版);2005年01期

3 趙玲;劉三陽;;基于螞蟻搜索度約束最小生成樹的改進(jìn)算法[J];計算機仿真;2006年10期

4 熊小華;寧愛兵;馬良;;基于降階的最小生成樹快速算法[J];計算機應(yīng)用研究;2010年06期

5 胡茂林,藺勇;全部生成樹的組合生成法[J];陜西科技大學(xué)學(xué)報;2004年01期

6 馬良,蔣馥;度限制最小樹的螞蟻算法[J];系統(tǒng)工程學(xué)報;1999年03期

7 宋海洲;;求解度約束最小生成樹的快速近似算法[J];系統(tǒng)工程學(xué)報;2006年03期

8 王勵成,孫麟平;求解度限制最小生成樹問題的啟發(fā)式遺傳搜索算法[J];系統(tǒng)工程理論與實踐;2003年05期

9 宋海洲;求解度約束最小生成樹的單親遺傳算法[J];系統(tǒng)工程理論與實踐;2005年04期

10 唐立軍;羅日成;肖紅光;鄧敏;粟娟;;基于改進(jìn)Wang-代數(shù)生成連通圖全部樹的方法研究[J];湘潭大學(xué)自然科學(xué)學(xué)報;2005年04期

中國碩士學(xué)位論文全文數(shù)據(jù)庫 前4條

1 韓麗霞;解兩類組合優(yōu)化問題的遺傳算法[D];西安電子科技大學(xué);2005年

2 焦森林;度約束最小生成樹算法[D];西安電子科技大學(xué);2008年

3 尉春杰;度約束最小生成樹WCJ遺傳算法[D];東北大學(xué);2008年

4 郭仁杰;基于單親遺傳算法的度約束最小生成樹問題研究[D];內(nèi)蒙古大學(xué);2014年

  本文關(guān)鍵詞：基于遺傳算法的度約束最小生成樹問題的研究，由筆耕文化傳播整理發(fā)布。

，

本文編號：495250