基于遗传算法的抗毁性网络拓扑结构优化1
需积分: 0 51 浏览量
2022-08-04
16:36:45
上传
评论 2
收藏 799KB PDF 举报
基于遗传算法的抗毁性网络拓扑结构优化
∗
廖汉龙
系统工程学院, 管理科学与工程 19060023
hans.liaoh@gmail.com
摘 要
复杂网络的抗毁性网络拓扑结构优化是重要的研究内容。本文主要以自然连通度指标来评价网络的抗毁
性，并基于此建立了优化模型。由于模型是非线性整数规划问题（NIP），属于NP难问题，因此，根据问题的
具体特点，本文设计了参数自适应的遗传算法对问题进行了求解。通过仿真实验，该方法收敛速度较快，且
能够对网络结构进行有效优化。特别地，针对不同的 攻击场景，我们对优化后的网络的抗毁性进行了具体分
析，得到了网络拓扑结构优化的一般规律。
1. 背景
广义上，网络的抗毁性是指网络中的节点或边遭受故 意攻击并失效的条件下，网络维持其正常功能的能
力[3]。而在实际应用中，这种功能的能力主要体现在如何保持拓扑结构连通。因此，复杂网络的抗毁性从一
定意义上来说，主要来源于节点之间替代途径的冗余性[2]。
复杂网络一般描述为图， 表 示为G = (V, E)，其中，点集合为V = {v
1
, v
2
, · · · , v
N
}，边集合为E =
{e
1
, e
2
, · · · , e
W
}，图的点和边的数目分别是N， M，即N = |V|, W = |E|。图在实际的处理场 景中，一般表
示为邻接矩阵A(G) = {a
ij
}。图的自然连通度表示为λ = ln(
1
N
P
N
i=1
e
λ
i
)，其中，λ
i
指的是邻接矩阵的第i个
特征根。自然连通度可以表示网络的冗 余性，且一般 认为，网络的自然连通度越高，则网络的冗余性越高，
相应地，网络具有更强的抗毁性。
2. 优化模型定义
我们从复杂网络内部结构属性出发，选取自然连通度作为网络抗毁性测度，优化复杂网络拓扑结构。为
此，对复杂网络图G作如下基本假设:
• 复杂网络图是无权图，即a
ij
=
0, (v
i
, v
i
) /∈ E
1, (v
i
, v
i
) ∈ E
；
• 复杂网络图G是无向简单图，即a
ij
=
a
ji
, i 6= j
0, i = j
；
∗
本文为国防科大系统工程学院2019-2020学期智能优化算法课程论文，任课教师：陈宇宁老师。
1
评论0