网络的生存性,表征了网络在遭受自然或者蓄意破坏后,能维持网络性能的能力大小,因此研究网络的生存性具有重要意义。研究网络的生存性的一个重要切入口就是关键链路集问题。简单说来,关键链路集是指蓄意攻击者在破坏能力有限的情况下,想要对相关网络实行最大程度的破坏,所选择攻击的一个有限的链路集合。“破坏”和“有限”存在多种不同的定义,本文主要研究了基于连通性点对测度和基于剩余交互流测度的关键链路集问题。本课题的最终目的是希望设计一类能够求解大规模网络的关键链路集的最优化算法,并将算法应用到网络的鲁棒性(生存性的一种)的评估中。文章的主要研究工作和创新点如下:1.从分析最小化连通性点对目标函数下的破坏模型的理论性质着手,获得了关键链路集问题的近似难度理论结果。该理论结果提供了关键链路集问题近似算法解的质量的一个不可能的界,能供作者本人及其他研究者参考来设计关键链路集问题可行的近似算法。2.提出了对中小规模网络有效的整数规划模型求解算法,而在更大规模的网络上提出了基于多轮次删除的线性规划近似算法。此线性规划算法能较快捷地求解出问题的近似解,且经过比较,算法比前人提出的算法更优,与精确解的近似程度更高。3.提出了一个能成批次优化带参数问题的遗传算法新框架,并基于此框架设计了关键链路集问题的遗传算法。经过研究发现,关键链路集问题可以划分到一类带参数的优化问题中。由于参数取不同值时的子问题之间存在着一定的联系,因此可以据此设计新型的遗传算法框架。所提出的遗传算法新框架,能为研究者解决别的带参数优化问题提供了一个有力工具。4.借助亚马逊所提供的云计算环境AWS,将算法应用到了网络的鲁棒性的评估测量中,并取得了良好的结果。大量实验数据表明,网络的鲁棒性能够通过网络的结构分布、流的分布以及两者的耦合情况进行快速估计。此处的工作使评估大规模网络的鲁棒性成为可能。