網(wǎng)絡關鍵鏈路集算法的研究與應用.pdf

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

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

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