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

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

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