基于遗传算法的网络脆弱性计算方法  

Computing Vulnerability of Network Based on Genetic Algorithm

作　　者：王玥[1] 蔡皖东[1] 段琪[1] 

机构地区：[1]西北工业大学计算机学院,西安710072

出　　处：《系统仿真学报》2009年第6期1628-1632,共5页Journal of System Simulation

基　　金：教育部博士点基金(200806990030)

摘　　要：韧性度是衡量网络结构脆弱性的重要指标,它描述了网络在节点失效或遭遇外来攻击时被破坏的难易程度、网络损毁后持续通信能力的强弱及修复受损子网的难易程度。韧性度的计算是NP问题,目前尚无多项式时间内的实用算法。针对穷举搜索算法时间复杂度过高的缺陷,提出一种基于遗传算法的韧性度计算方法,利用随机优化技术对韧性度的参数空间进行高效搜索。仿真试验表明,该算法能快速、有效地收敛于最优解,为基于韧性度的网络脆弱性评估提供了一种可行、有效的方法。Tenacity is an important indication of network vulnerability.It indicates the difficulty of destroying the network when nodes were invalidated or network was attacked.Tenacity also indicates the communication capability of subnet and the difficulty of network restoration after parts of network were damaged.At present,no algorithm can compute the tenacity in polynomial time because the computation of tenacity is an NP problem.Over against the exhaustive scheme which has high time complexity,an algorithm based on genetic algorithm was proposed to compute the tenacity of network,stochastic optimization technique was used to search optimum solution efficiently in parametric space of tenacity.The results of simulation suggest that the algorithm always converges at optimum solution efficiently.This algorithm provides a feasible and valid method to measure the vulnerability of networks.

关 键 词：脆弱性 韧性度 遗传算法 初始种群 

分 类 号：TP393.02[自动化与计算机技术—计算机应用技术]