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

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

• 摘要4-5
• Abstract5-9
• 第一章 緒論9-12
• 1.1 度約束最小生成樹(shù)問(wèn)題簡(jiǎn)介9-10
• 1.1.1 度約束最小生成樹(shù)的提出背景及研究意義9-10
• 1.1.2 度約束最小生成樹(shù)的研究現(xiàn)狀10
• 1.2 本文的主要內(nèi)容及結(jié)構(gòu)10-11
• 1.3 本文創(chuàng)新工作11-12
• 第二章 DCMST問(wèn)題綜述12-20
• 2.1 基本概念及有關(guān)結(jié)論12-14
• 2.2 基本符號(hào)說(shuō)明14-15
• 2.3 DCMST問(wèn)題的數(shù)學(xué)模型15
• 2.4 求解DCMST算法綜述15-20
• 2.4.1 求解DCMST問(wèn)題的精確算法16
• 2.4.2 求解DCMST問(wèn)題的啟發(fā)式算法16-18
• 2.4.3 求解DCMST問(wèn)題的現(xiàn)代優(yōu)化算法18-20
• 第三章 求解度約束最小生成樹(shù)的遺傳算法20-49
• 3.1 求解DCMST問(wèn)題的遞歸算法20-23
• 3.1.1 給出連通圖全部生成樹(shù)的方法簡(jiǎn)介20
• 3.1.2 度約束最小生成樹(shù)的遞歸算法20-23
• 3.2 求解DCMST問(wèn)題的新快速算法QDC23-27
• 3.2.1 定義邊的可用度值23-24
• 3.2.2 修改邊的可用度值的DET算法24
• 3.2.3 求解度約束生成樹(shù)的快速算法QDC24-25
• 3.2.4 快速算法QDC有時(shí)會(huì)找不到生成樹(shù)25-27
• 3.3 求解DCMST問(wèn)題算法的討論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問(wèn)題的遺傳算法流程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)】

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

，

本文編號(hào)：495250