本文關(guān)鍵詞：基于遺傳算法的直徑限制最小生成樹問題的研究

  更多相關(guān)文章： 直徑限制 非完全圖 最小生成樹 BDMST 樹圖

【摘要】：最小生成樹是經(jīng)典的組合優(yōu)化問題,在實(shí)際的應(yīng)用中,由于人們對(duì)傳輸速度、信號(hào)質(zhì)量以及維修的簡(jiǎn)易性等方面的要求,對(duì)最小生成樹的直徑需要加一定的限制,于是得到一類基于遺傳算法的直徑限制的最小生成樹問題。即在給定賦權(quán)無向連通圖以及一個(gè)正整數(shù)D的前提下,在圖的所有的生成樹中,尋找一個(gè)滿足直徑限制且權(quán)值最小的生成樹,并且不能包括超過直徑限制D的路徑。一般來說,當(dāng)直徑限制在[4,n-1)時(shí),直徑限制最小生成樹問題是一個(gè)NP-Hard問題。對(duì)于此類問題,當(dāng)規(guī)模比較大時(shí),大多是采用啟發(fā)式算法或遺傳算法等現(xiàn)代優(yōu)化方法求解,且基本上是以完全連通圖為前提。針對(duì)非完全連通圖,本文提出求解直徑限制最小生成樹的新的遺傳算法。數(shù)值試驗(yàn)驗(yàn)證了算法的有效性。
【關(guān)鍵詞】：直徑限制 非完全圖 最小生成樹 BDMST 樹圖
【學(xué)位授予單位】：內(nèi)蒙古大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類號(hào)】：O157.5;TP18
【目錄】：

• 摘要4-5
• ABSTRACT5-9
• 第一章 緒論9-12
• 1.1 引言9
• 1.2 BDMST的研究意義9-10
• 1.3 BDMST問題的研究現(xiàn)狀10-11
• 1.4 本文的主要工作11-12
• 1.4.1 本文的主要結(jié)構(gòu)和內(nèi)容11
• 1.4.2 本文的創(chuàng)新工作11-12
• 第二章 BDMST問題的概述12-27
• 2.1 圖的相關(guān)概念12-16
• 2.2 基本符號(hào)說明16-17
• 2.3 MST問題簡(jiǎn)介17
• 2.4 MST的數(shù)學(xué)模型17-18
• 2.5 MST的算法介紹18-20
• 2.6 BDMST問題描述20
• 2.7 BDMST的數(shù)學(xué)模型20-21
• 2.8 求解BDMST問題已有算法的綜述21-27
• 2.8.1 求解BDMST問題的啟發(fā)式算法22-25
• 2.8.2 使用序列編碼的遺傳算法求解BDMST問題25-27
• 第三章 用遺傳算法求解BDMST問題27-62
• 3.1 求解BDMST問題的遞歸算法27-30
• 3.1.1 給出連通圖全部生成樹的方法簡(jiǎn)介27-28
• 3.1.2 直徑限制最小生成樹的遞歸算法28-30
• 3.2 求解BDMST問題算法的討論30-38
• 3.2.1 OTTC算法、RGH算法的進(jìn)一步討論31-34
• 3.2.2 采用序列編碼方式遺傳算法的進(jìn)一步討論34-35
• 3.2.3 構(gòu)造新算法的基本思路35-38
• 3.3 編碼、解碼38-42
• 3.4 適應(yīng)度函數(shù)42-45
• 3.4.1 權(quán)矩陣的適應(yīng)度函數(shù)42-44
• 3.4.2 邊權(quán)向量的適應(yīng)度函數(shù)44-45
• 3.5 初始化種群45-49
• 3.5.1 從中心點(diǎn)出發(fā)的初始化方法45-48
• 3.5.2 從最小生成樹出發(fā)的初始化方法48-49
• 3.6 選擇算子49-50
• 3.7 遺傳算子50-59
• 3.7.1 交叉算子50-57
• 3.7.2 變異算子57-58
• 3.7.3 遺傳算子使用策略58-59
• 3.8 局部尋優(yōu)算子59-60
• 3.8.1 尋優(yōu)算子a59
• 3.8.2 尋優(yōu)算子b59-60
• 3.9 算法終止條件60-61
• 3.10 算法流程圖61-62
• 第四章 算法驗(yàn)證62-68
• 4.1 實(shí)驗(yàn)數(shù)據(jù)的選取62-63
• 4.2 實(shí)驗(yàn)結(jié)果63-68
• 第五章 結(jié)論68-69
• 參考文獻(xiàn)69-71
• 致謝71

【參考文獻(xiàn)】

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

1 王棟,張文彬;用遺傳算法求解dc_MST問題[J];哈爾濱理工大學(xué)學(xué)報(bào);2001年05期

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

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

4 趙青;楊倩;;遺傳算法三種編碼策略的比較研究[J];重慶文理學(xué)院學(xué)報(bào)(自然科學(xué)版);2008年02期

5 趙禮峰;王小龍;;圖的Steiner最小樹問題的混合遺傳算法[J];計(jì)算機(jī)技術(shù)與發(fā)展;2014年10期

6 阿不力米提·伊明;;樹圖及其頂點(diǎn)數(shù)的計(jì)算[J];新疆師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2007年02期

，

本文編號(hào)：1106599