網(wǎng)絡(luò)關(guān)鍵鏈路集算法的研究與應(yīng)用.pdf

1、網(wǎng)絡(luò)的生存性，表征了網(wǎng)絡(luò)在遭受自然或者蓄意破壞后，能維持網(wǎng)絡(luò)性能的能力大小，因此研究網(wǎng)絡(luò)的生存性具有重要意義。研究網(wǎng)絡(luò)的生存性的一個(gè)重要切入口就是關(guān)鍵鏈路集問(wèn)題。簡(jiǎn)單說(shuō)來(lái)，關(guān)鍵鏈路集是指蓄意攻擊者在破壞能力有限的情況下，想要對(duì)相關(guān)網(wǎng)絡(luò)實(shí)行最大程度的破壞，所選擇攻擊的一個(gè)有限的鏈路集合?！捌茐摹焙汀坝邢蕖贝嬖诙喾N不同的定義，本文主要研究了基于連通性點(diǎn)對(duì)測(cè)度和基于剩余交互流測(cè)度的關(guān)鍵鏈路集問(wèn)題。本課題的最終目的是希望設(shè)計(jì)一類(lèi)能夠求解大規(guī)模網(wǎng)

2、絡(luò)的關(guān)鍵鏈路集的最優(yōu)化算法，并將算法應(yīng)用到網(wǎng)絡(luò)的魯棒性（生存性的一種）的評(píng)估中。
　　文章的主要研究工作和創(chuàng)新點(diǎn)如下：
　　1.從分析最小化連通性點(diǎn)對(duì)目標(biāo)函數(shù)下的破壞模型的理論性質(zhì)著手，獲得了關(guān)鍵鏈路集問(wèn)題的近似難度理論結(jié)果。該理論結(jié)果提供了關(guān)鍵鏈路集問(wèn)題近似算法解的質(zhì)量的一個(gè)不可能的界，能供作者本人及其他研究者參考來(lái)設(shè)計(jì)關(guān)鍵鏈路集問(wèn)題可行的近似算法。
　　2.提出了對(duì)中小規(guī)模網(wǎng)絡(luò)有效的整數(shù)規(guī)劃模型求解算法，而在更大規(guī)

3、模的網(wǎng)絡(luò)上提出了基于多輪次刪除的線性規(guī)劃近似算法。此線性規(guī)劃算法能較快捷地求解出問(wèn)題的近似解，且經(jīng)過(guò)比較，算法比前人提出的算法更優(yōu)，與精確解的近似程度更高。
　　3.提出了一個(gè)能成批次優(yōu)化帶參數(shù)問(wèn)題的遺傳算法新框架，并基于此框架設(shè)計(jì)了關(guān)鍵鏈路集問(wèn)題的遺傳算法。經(jīng)過(guò)研究發(fā)現(xiàn)，關(guān)鍵鏈路集問(wèn)題可以劃分到一類(lèi)帶參數(shù)的優(yōu)化問(wèn)題中。由于參數(shù)取不同值時(shí)的子問(wèn)題之間存在著一定的聯(lián)系，因此可以據(jù)此設(shè)計(jì)新型的遺傳算法框架。所提出的遺傳算法新框架，能為