本文關鍵詞：網(wǎng)絡關鍵鏈路集算法的研究與應用

  更多相關文章： 關鍵鏈路集 遺傳算法 云計算 網(wǎng)絡 魯棒性

【摘要】：網(wǎng)絡的生存性,表征了網(wǎng)絡在遭受自然或者蓄意破壞后,能維持網(wǎng)絡性能的能力大小,因此研究網(wǎng)絡的生存性具有重要意義。研究網(wǎng)絡的生存性的一個重要切入口就是關鍵鏈路集問題。簡單說來,關鍵鏈路集是指蓄意攻擊者在破壞能力有限的情況下,想要對相關網(wǎng)絡實行最大程度的破壞,所選擇攻擊的一個有限的鏈路集合�！捌茐摹焙汀坝邢蕖贝嬖诙喾N不同的定義,本文主要研究了基于連通性點對測度和基于剩余交互流測度的關鍵鏈路集問題。本課題的最終目的是希望設計一類能夠求解大規(guī)模網(wǎng)絡的關鍵鏈路集的最優(yōu)化算法,并將算法應用到網(wǎng)絡的魯棒性(生存性的一種)的評估中。文章的主要研究工作和創(chuàng)新點如下:1.從分析最小化連通性點對目標函數(shù)下的破壞模型的理論性質(zhì)著手,獲得了關鍵鏈路集問題的近似難度理論結果。該理論結果提供了關鍵鏈路集問題近似算法解的質(zhì)量的一個不可能的界,能供作者本人及其他研究者參考來設計關鍵鏈路集問題可行的近似算法。2.提出了對中小規(guī)模網(wǎng)絡有效的整數(shù)規(guī)劃模型求解算法,而在更大規(guī)模的網(wǎng)絡上提出了基于多輪次刪除的線性規(guī)劃近似算法。此線性規(guī)劃算法能較快捷地求解出問題的近似解,且經(jīng)過比較,算法比前人提出的算法更優(yōu),與精確解的近似程度更高。3.提出了一個能成批次優(yōu)化帶參數(shù)問題的遺傳算法新框架,并基于此框架設計了關鍵鏈路集問題的遺傳算法。經(jīng)過研究發(fā)現(xiàn),關鍵鏈路集問題可以劃分到一類帶參數(shù)的優(yōu)化問題中。由于參數(shù)取不同值時的子問題之間存在著一定的聯(lián)系,因此可以據(jù)此設計新型的遺傳算法框架。所提出的遺傳算法新框架,能為研究者解決別的帶參數(shù)優(yōu)化問題提供了一個有力工具。4.借助亞馬遜所提供的云計算環(huán)境AWS,將算法應用到了網(wǎng)絡的魯棒性的評估測量中,并取得了良好的結果。大量實驗數(shù)據(jù)表明,網(wǎng)絡的魯棒性能夠通過網(wǎng)絡的結構分布、流的分布以及兩者的耦合情況進行快速估計。此處的工作使評估大規(guī)模網(wǎng)絡的魯棒性成為可能。
【關鍵詞】：關鍵鏈路集 遺傳算法 云計算 網(wǎng)絡 魯棒性
【學位授予單位】：國防科學技術大學
【學位級別】：碩士
【學位授予年份】：2015
【分類號】：O221;TP18
【目錄】：

• 摘要9-10
• ABSTRACT10-12
• 符號使用說明12-13
• 第一章 緒論13-18
• 1.1 研究背景與研究意義13-14
• 1.2 研究內(nèi)容14-17
• 1.2.1 研究問題14-15
• 1.2.2 研究思路15-16
• 1.2.3 研究成果16-17
• 1.3 論文結構介紹17-18
• 第二章 相關概念與相關研究工作18-24
• 2.1 相關概念18-20
• 2.1.1 計算復雜性18-19
• 2.1.2 數(shù)學規(guī)劃19-20
• 2.1.3 元啟發(fā)式算法20
• 2.2 關鍵鏈路集問題的相關研究工作20-22
• 2.3 網(wǎng)絡魯棒性的相關研究工作22-24
• 第三章 基于數(shù)學規(guī)劃的近似算法24-36
• 3.1 關鍵鏈路集問題的理論難度24-27
• 3.2 關鍵鏈路集問題的整數(shù)規(guī)劃模型27-30
• 3.3 基于線性規(guī)劃的近似算法30-33
• 3.3.1 預處理階段31-32
• 3.3.2 多輪次線性規(guī)劃階段32-33
• 3.3.3 局部優(yōu)化階段33
• 3.4 實驗結果33-36
• 第四章 基于新遺傳算法框架的近似算法36-53
• 4.1 傳統(tǒng)遺傳算法框架36
• 4.2 帶參數(shù)的優(yōu)化問題36-39
• 4.3 異構種群的遺傳算法新框架39-45
• 4.3.1 新框架的偽代碼及說明39-42
• 4.3.2 新框架的交叉算子的設計42-45
• 4.3.3 新框架的變異及其它算子的設計45
• 4.4 關鍵鏈路集問題的試驗結果45-49
• 4.5 新框架下更多的實驗和討論49-53
• 4.5.1 p-中值問題49-50
• 4.5.2 最小頂點覆蓋問題50-52
• 4.5.3 進一步討論和比較52-53
• 第五章 關鍵鏈路集算法在網(wǎng)絡魯棒性評估中的應用53-67
• 5.1 網(wǎng)絡魯棒性模型的建立53-56
• 5.2 實驗數(shù)據(jù)的大量生成56-57
• 5.3 云環(huán)境計算實驗數(shù)據(jù)57-61
• 5.4 實驗結果分析及評價61-67
• 第六章 總結與未來工作67-70
• 致謝70-72
• 參考文獻72-76
• 作者在學期間取得的學術成果76

【相似文獻】

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

1 郭慶軍;李慧民;賽云秀;;多項目關鍵鏈進度優(yōu)化算法分析[J];工業(yè)工程與管理;2008年06期

2 張靜文;胡信布;王茉琴;;關鍵鏈項目計劃調(diào)度方法研究[J];科技管理研究;2008年03期

3 王明明;徐磊;賀雅麗;;科技研發(fā)項目關鍵鏈管理應用研究[J];科學學研究;2008年04期

4 林晶晶;周國華;;基于優(yōu)先級的關鍵鏈多項目管理研究[J];科技管理研究;2009年08期

5 殷莎莎;;關鍵鏈技術研究動態(tài)評述[J];科技管理研究;2011年08期

6 趙道致,廖華;對關鍵鏈法的幾個認識誤區(qū)[J];工業(yè)工程;2005年02期

7 田文迪;崔南方;;關鍵鏈項目管理中關鍵鏈和非關鍵鏈的識別[J];工業(yè)工程與管理;2009年02期

8 李雙辰;王艷春;;基于灰色關聯(lián)的關鍵鏈緩沖設置方法研究[J];科技管理研究;2013年17期

9 張敏;陳榮秋;唐偉勤;;不確定收益下關鍵鏈項目緩沖前置分配模型[J];工業(yè)工程與管理;2009年04期

10 彭武良;金敏力;徐皓;;基于差分進化的關鍵鏈項目調(diào)度方法[J];系統(tǒng)管理學報;2013年06期

中國重要會議論文全文數(shù)據(jù)庫 前4條

1 蔣國萍;陳英武;;基于關鍵鏈的項目進度問題研究[A];中國運籌學會第七屆學術交流會論文集（中卷）[C];2004年

2 徐陽;;試用關鍵鏈理論組織預測市場需求[A];上海市煙草專賣局2007年度獲獎論文集（經(jīng)濟管理類）[C];2007年

3 周正龍;董雄報;左園;;MIS開發(fā)項目進度管理的關鍵鏈識別研究[A];第八屆（2013）中國管理學年會——管理與決策科學分會場論文集[C];2013年

4 萬偉;蔡晨;;在兩資源約束項目環(huán)境中的關鍵鏈管理[A];2003年中國管理科學學術會議論文集[C];2003年

中國重要報紙全文數(shù)據(jù)庫 前1條

1 路長全;速度領先導致資源匯聚[N];中國證券報;2007年

中國博士學位論文全文數(shù)據(jù)庫 前7條

1 林晶晶;考慮資源可替代性的關鍵鏈識別與緩沖設置方法研究[D];西南交通大學;2011年

2 郭方銘;基于粒子群優(yōu)化和關鍵鏈的多項目計劃管理問題研究[D];華中科技大學;2010年

3 別黎;關鍵鏈項目管理中緩沖估計與監(jiān)控方法研究[D];華中科技大學;2012年

4 金敏力;基于關鍵鏈的項目優(yōu)化調(diào)度問題研究[D];哈爾濱工業(yè)大學;2013年

5 田文迪;隨機DTRTP環(huán)境下項目調(diào)度策略的比較研究[D];華中科技大學;2011年

6 劉英杰;大型水利工程費用/進度集成控制研究[D];天津大學;2012年

7 趙雁;時間緩沖設置與魯棒性項目調(diào)度[D];華中科技大學;2014年

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

1 唐藝軒;基于關鍵鏈的工程進度與成本集成管理研究[D];山東建筑大學;2015年

2 劉博;基于多項目優(yōu)先級的關鍵鏈識別和緩沖區(qū)設置研究[D];河北工程大學;2015年

3 李力真;空間受限大型復雜項目的關鍵鏈管理研究[D];蘭州大學;2015年

4 殷蕊;基于關鍵鏈技術的多資源多項目進度控制研究與應用[D];沈陽大學;2015年

5 任格葉;關鍵鏈的隨機性及其應用研究[D];西安建筑科技大學;2015年

6 韓家寧;基于關鍵鏈的船舶機艙系泊計劃進度研究[D];上海交通大學;2015年

7 李恩成;基于關鍵鏈技術的工程建筑項目進度管理方法研究[D];華北電力大學;2015年

8 崔爽;基于關鍵鏈技術資源約束下項目調(diào)度應用研究[D];華北電力大學;2015年

9 玉樹偉;基于關鍵鏈法的超高層項目施工進度管理研究[D];廣西大學;2015年

10 蒙唐媛怡;基于灰色關鍵鏈的項目進度管理研究[D];北京化工大學;2015年

，

本文編號：540276