基于并行遗传算法的网络最优弥补研究

Research of Minimum-cost Network Hardening Based on Parallel Genetic Algorithm

将攻击图与并行遗传算法相结合,提出了一种基于并行遗传算法的网络最优弥补模型PGA-ONHM(optimal network hardening model based on parallel genetic algorithm),该模型能得到目标网络系统的近似解。为了验证该模型的可行性、有效性和可扩展性,本文从不同的分析角度进行仿真验证,实验结果表明:并行遗传算法的CPU消耗时间随着初始属性节点数量的增加呈多项式增加,随着子群体数量的增加呈减小趋势;无论是平均迭代次数还是单次迭代的平均计算时间,并行遗传算法比经典遗传算法都要优越;并行遗传算法可以得到较好的加速比;能够克服局部最优解的问题,可以适用于大规模复杂的网络系统。

This paper combines attack graph and parallel genetic algorithm and proposes a new minimum-cost network hardening PGA-ONHM based on the parallel genetic algorithm, which can be used to obtain the approximate solution of the target network system. In order to verify the feasibility, effectiveness and scalability of the proposed model, the results show that the CPU consumption time of the parallel genetic algorithm increases with the increase of the number of the initial nodes. The parallel genetic algorithm is superior to the classical genetic algorithm, and can overcome the problem of local optimal solution.