复杂网络的经典定义, 是将具有自组织、自相似、吸引子、小世界、无标度中部分或全部性质的网络称为复杂网络^[1]. 在现实生活中, 通信网络, 电力网络, 生物网络, 社会网络和经济网络等实际网络, 都可以称之为复杂网络, 它们都具有上述复杂网络的5种特性中的一种或多种. 这些网络系统中的成员可以表示为节点, 成员之间的交互关系可以表示为连接复杂网络因其节点, 连边, 以及其连接关系的复杂性而与现实中大量的物理系统相匹配. 例如, 神经系统可以看作大量神经细胞通过神经纤维相互连接形成的网络^[2], 计算机网络可以看作是自主工作的计算机通过通信介质如光缆、双绞线、同轴电缆等相互连接形成的网络^[2]. 复杂网络领域的研究关注于看上去互不相同的复杂网络之间的共性和处理它们的普适方法, 着眼于复杂网络的定量和定性特征的分析, 其中包含了统计力学、博弈论、动力系统等分支的概念、理论与方法, 常用的分析方法和工具包括图论、组合数学、矩阵理论、概率论、随机过程、优化理论等. 研究内容主要体现在网络结构复杂性, 节点复杂性, 结构与节点之间的相互影响以及网络之间的相互影响这4个方面^[3].

(1) 网络结构复杂性可以理解为网络处于一个演化过程, 网络连接和网络拓扑结构会随着时间发生变化.

(2) 节点复杂性一方面可以理解为在一个网络中节点也存在复杂的时间演化行为; 另一方面, 在一个同质网络中相同类型的节点存在不同的重要程度和不同的类别; 再者, 在异质网络中, 类似于知识图谱, 则存在不同类型的节点.

(3) 结构与节点之间的相互影响意为网络结构会影响节点的行为, 同样, 节点的行为也会影响网络的结构.

(4) 网络之间的相互影响则表示在一个网络化社会中不同网络之间的相互联系. 如电网故障不仅会影响电力网络的稳定性, 也可能造成供水网络的故障, 金融机构的关闭等.

目前, 复杂网络领域的研究方向包括但不局限于复杂网络模型、网络性质、网络博弈、网络传播、网络同步与控制等.

为了理解网络结构与网络行为之间的关系使网络指导现实系统的规划和建设, 首先我们需要对网络的拓扑和特征结构有一定了解, 其关键在于对网络拓扑结构进行建模, 进而辅助更加深入的研究. 20世纪50年代末由Erdös和Rényi建立的随机图理论(random graph theory)被公认为是在数学上开创了复杂网络拓扑结构的系统性研究^[4]. 随机图理论中的核心是随机图模型(ER随机图模型), 其建立在任意两点之间产生连边概率相同的前提下, 是第1个以概率描述复杂网络系统的模型. 1998年, Watts及其导师Strongatz针对实际网络中具有的小世界(small world, SW)数值特性^[2]和聚类特征构建了WS小世界网络模型(SWWS)^[2], 通过在规则初始环结构上对连边进行随机重连得到. 1999年, Newman和Watts提出的NW小世界网络模型(SWNW)则是在规则环结构的基础上通过随机添加连边得到的^[5]. 同年, Barabási和Albert针对实际网络的幂律度分布特性(或无标度性)提出了BA无标度网络模型^[6]. 无标度(scale free, SF)网络具有严重的异质性, 其各节点之间的连接状况(度数)具有严重的不均匀分布性: 网络中少数称之为Hub点的节点拥有极其多的连边, 而大多数节点只有很少量的连边. 少数Hub点对无标度网络的运行起着主导的作用, 该特性与大量的现实系统高度相似, 如互联网^{[7, 8]}、蛋白质分子网络、科研合作网络等, 其度分布可用适当的幂律形式来描述. 而前述ER随机图和小世界模型其网络的度分布则可近似用泊松分布来表示.

网络性质的研究目前已经十分完善, 如无标度性^[6]、小世界性^[2]、社团性^[9]. 这些研究不仅用于网络模型的构建, 也应用于实际网络中, 反映了社会现象, 如社交网络的小世界特性^[2].

通过复杂网络建模, 模拟进化博弈, 可以将复杂网络应用于模拟人类社会中的竞争合作现象, 演化竞争与合作关系. 为了表达经济学和社会学中的利他主义和利己主义^{[10, 11]}, 研究人员提出的经典的进化博弈场景有: 囚徒困境、雪堆博弈、鹰鸽博弈、猎鹿博弈等. 以往的研究中发现不同结构的网络保持合作的能力不同, 如在博弈双方收益关系符合囚徒困境时, 正则三角形网格网络倾向于保持合作. 这些研究为某些社会现象提供了一定的解释.

复杂网络传播理论的研究涉及基本的流行病(生物病毒、计算机病毒、信息等)的传播模型的构建、网络传播动力学方程和传播临界值的构建与计算^[12]、研究不同网络结构对于传播临界值的影响和本质原因等. 网络传播理论的研究有助于人们设计免疫策略, 鉴别超级传播节点, 预防并阻断流行病的传播等.

同步现象分为两种, 一种是大自然中存在的同步现象, 称为耦合作用形成的同步; 另一种是添加了控制之后形成的同步现象. 网络同步是网络科学中一个受到较多关注的研究领域^[13-15]. 对复杂网络中同步现象的研究基于复杂动力网络模型. 复杂动力网络是刻画多个个体耦合的复杂系统模型, 每个个体均是一个动力系统, 并且个体之间存在特定的耦合关系. 因此, 模型有两个主要部分, 一是节点动力学, 二是网络结构. 控制复杂系统是人们对复杂系统模型结构及相关动力学进行研究的最终目标, 反映人们对复杂系统的认识能力^[16]. 因此, 对于复杂网络的控制研究在近年来越来越受关注^[16-21]. 宏观上讲, 控制表示指导和调节一个系统达到预期目标的功能或力量, 复杂网络的控制理论和方法源于经典控制理论与复杂系统研究的结合, 由于自身的复杂性特点使其又不同于经典控制论^[22]. 网络控制技术和计算、通信技术的融合共同助力大型互联系统的形成.

在现有的研究中, 启发式算法被广泛用于解决复杂网络优化问题中, 如社团检测, 鲁棒性优化等. 且其依然有广大的研究与应用前景.

进化算法(evolutionary algorithm, EA)是一类模拟生物自然选择与自然进化的随机搜索算法, 因其适用于求解高度复杂的非线性问题而得到了非常广泛的应用, 同时它又具有较好的通用性. 在解决单个目标的复杂系统优化问题时, 进化算法的优势得以充分展现.

进化算法的研究可以追溯到20世纪60年代, 早期的研究旨在解决黑盒问题, 如设计自适应系统^[23]、模式识别任务^[24]和功能优化^[25]. 这些问题没有明确答案甚至没有明确的定义. 1975年, De Jong等人对进化算法的概念进行了总结^{[26, 27]}. 自此, 进化算法被广泛应用, 包括机器学习^[28]、计算智能^[29]和并行系统^[30]等工程领域.

经典的优化算法中, 最普通的优化策略为穷举, 但计算成本十分昂贵. 爬山算法是一种基于贪心策略的算法, 简单但易陷入局部最优解中. 随机搜索算法中, 如模拟退火算法和禁忌搜索算法, 能避免陷入局部最优, 但是不能利用进化种群提供的信息实现并行搜索.

进化算法依赖于一组候选解. 这些候选解之间经过多代进化, 通过信息交换产生新的适应度更高的候选解. 进化算法的基本要素是: (1)变量编码; (2)初始种群集合; (3)适应度函数的设计; (4)遗传算子的设计; (5)控制参数的设置, 包括种群规模、进行遗传算子的概率等.

进化算法中的候选解称为个体, 一组个体称为一个种群. 算法循环执行以下步骤: (1)对种群中所有个体进行适应度评估; (2)从种群中选择进行繁殖的父代个体; (3)父代个体间进行信息交换, 生成子代个体; (4)通过幸存者选择机制(survivor selection mechanism)确定保留到下一代的个体. 如果此时满足终止条件, 则终止循环, 否则继续. 该过程类似于生物进化论中的“物竞天择, 适者生存”, 能够保留更适合解决方案的个体, 而淘汰哪些不具有竞争力的个体. 上述信息交换通过遗传算子执行, 包括选择、交叉和变异算子. 这些算子有助于搜索过程的收敛性, 并引导个体靠近最优解. 上述进化算法基本要素和遗传算子的具体内容如下^[31].

(1) 编码: 经典的进化算法通过编码将需要优化的变量转换成可操作的表示形式. 如遗传算法中常用二进制编码, 可以加快处理速度. 但是, 大多数进化算法的实现并不依赖于这一特性. 其他编码方案包括使用实数和字符串. 一些实现要求编码字符串(也称为染色体)的长度是固定的, 而另一些实现允许可变长度的编码.

(2) 初始化: 初始种群通常是通过随机初始化创建的. 这样能减少初始种群中的偏差, 使候选解具备多样性. 由于种群的大小的有限的, 初始化偏差随着种群大小的减小而增大. 工程人员会针对具体问题具体分析, 使用领域知识设计更好的初始化方法.

(3) 适应度评估: 适应度通常被称为个体相对于整体的表现. 优化问题包括一个或多个目标函数, 这些目标函数用于测量单个个体的性能. 以不同的方式计算适应度, 来评估候选解相对于种群中其他个体的质量.

(4) 选择算子: 选择的目的是择优, 受达尔文进化论的启发, 通过选择更优秀的个体作为双亲, 使它们通过交叉算子得到的子代个体具有更高的适应度值. 经典的选择策略有适应度占比选择(fitness proportional selection)、排序选择(ranking selection)、轮盘赌(roulette wheel)和锦标赛选择(tournament selection). 最简单的实现方法是适应度占比选择, 首先计算种群中所有适应度值的总和 $\left(\displaystyle\sum f\right)$ , 每个个体被选择的概率取决于它对这个总和的贡献程度 $\left(\dfrac{{{f_i}}}{{\displaystyle\sum f}}\right)$ . 该方法虽然简单但是存在许多缺点, 其他选择策略都相对于该策略有所改进.

(5) 交叉算子: 交叉的概念可以被理解为信息的交换, 通常需要一对个体(双亲), 这对个体通过交换信息生成子代个体(类似于“基因重组”). 在经典的进化算法中, 交叉起着重要作用.

(6) 变异算子: 变异算子的实质是向个体注入新信息. 但是, 要确保引入新信息的来源, 以避免个体陷入局部最优状态. 以二进制编码为例, 随机选择个体的一位执行变异算子, 即改变该位的值(二进制编码中, 0变为1或1变为0), 生成一个新的个体.

(7) 幸存者选择: 通常根据个体的适应度值决定哪些个体可以进入下一代. 由于进化算法执行过程中, 种群大小一般固定不变, 所以, 常见的策略分为两种: 第1种策略直接从生成的子代个体中进行选择, 第2种策略则是从父代和子代中共同决定.

上述操作组成经典进化算法的基本成分. 单目标无约束优化问题的简单实现即为: 随机初始化种群; 对单个个体进行适应度评估; 通过选择算子选出一对双亲个体; 每一对双亲个体执行交叉算子生成子代个体; 子代个体执行变异算子; 评估子代个体的适应度值, 然后执行幸存者选择, 确定下一代的个体并重复上述步骤.

本文第1节为相关基础知识, 第2节针对不同任务详述其相关优化目标及实例, 第3节为多目标进化算法的性能评价指标, 第4节为实验, 第5节为总结与展望.

1 复杂网络和进化算法基本概述 1.1 复杂网络

目前, 许多系统可以被抽象出来用复杂网络表示. 这既包含自然系统, 如蛋白质分子网络, 也包括人工系统, 如互联网、引文网络等. 在进行复杂网络建模时, 通常使用图论的知识来描述一个网络, 一个网络(或者一个图)由边集合和节点集合构成. 一般, 用符号 $G$ 表示一个网络, 对于无权网络 $G = \left( {V, E} \right)$ . 其中 $V = \left\{ {1, 2, \cdots, N} \right\}$ 和 $E = \{ \left( {i, j} \right)|i, j \in V, i \ne j\} $ 分别代表节点和连边的集合. $G$ 的邻接矩阵 $A$ 用于描述节点之间的相邻关系, 矩阵中元素 ${a_{ij}}$ 的定义如下:

$ \begin{array}{c}\begin{array}{rr} {a}_{ij}& = \left\{ \begin{array}{ll}1, & \text{if}存在连边{(i, j)} \\ 0, & \text{otherwise} \end{array}\right.\end{array}\end{array} $

(1)

有权网络通过三元组 $G = \left( {V, E, W} \right)$ 进行标识. $W$ 表示权重矩阵, 与邻接矩阵的大小、维度相同, 矩阵中元素 ${w_{ij}}$ 表示节点 $i$ 和节点 $j$ 之间连边的权值.

符号网络属于特殊的有权网络, 在符号网络中, 用+和–标记连边的两种相反的类型, 如社交网络中, 这两种连边被赋予“朋友”和“敌人”的含义.

1.2 经典单目标进化算法

近年来, 在进化算法领域中, 一个流行的分支是模因算法(memetic algorithms, MA). “模因”的概念来自于Dawkins等人提出的“meme”, 它代表一个文化进化的单位, 可以表现出局部的精细化^{[32, 33]}. 在进化算法中, 模因通常被认为是一个能够进行局部细化的个体学习过程. 因此, 进化算法成功地将全局搜索和局部搜索结合起来, 在许多问题上都比传统的进化算法更加高效和有效^{[34, 35]}. 相比较进化算法, 模因算法增加了局部搜索算子. 一个简单的模因算法的流程如算法1所示.

算法1. 模因算法

输入: 初始个体

输出: 最佳候选解

初始化: 生成初始种群;

适应度评估: 对初始种群中每个个体进行适应度评估;

REPEAT

　选择算子: 选择双亲个体;

　交叉算子: 双亲个体进行信息交换;

　局部搜索算子: 优化子代个体;

　适应度评估: 评估新生成个体的适应度值;

　幸存者选择: 选择保留到下一代的个体;

UNTIL (满足终止条件)

在进化算法中, 另一个常用的算法为粒子群优化算法(particle swarm optimization, PSO), 属于群体智能(swarm intelligence, SI)领域, 是一种启发式的全局优化算法. 粒子群算法通过一群粒子来搜索解空间. 这些粒子通过迭代更新它们的位置. 在每次迭代中, 粒子的移动方向由之前已知的最佳位置( $pbest$ )和全局最佳位置( $gbest$ )指导^[36]. $pbest$ 和 $gbest$ 的定义如式(2):

$\left\{ { \begin{split} & {pbest(i,t) = \mathop {\rm argmin}\limits_{k = 1,2, \cdots ,t} f({P_i}(k)),i \in [1,2, \cdots ,{N_p}]}\\ & {gbest = \mathop {{\rm{argmin}}}\limits_{\begin{array}{*{20}{c}} {k = 1,2, \cdots ,t\atop i = 1,2, \cdots ,{N_p}} \end{array}} f({P_i}(k))} \end{split} } \right.$

(2)

其中, ${N_p}$ 为种群中粒子数, $i$ 表示每个粒子的索引, $t$ 为当前迭代数, $f$ 为最小化目标, ${P_i}\left( k \right)$ 为第 $i$ 个粒子在第 $k$ 轮迭代时的位置. 粒子更新位置的方式如下:

$\left\{ { \begin{split} & {V_i}(t + 1) =\omega {V_i}(t) + {c_1}{r_1}(pbest(i, t) - {P_i}(t)) \\ &\qquad\qquad\;\; { + {c_2}{r_2}(gbest(i, t) - {P_i}(t))} \\ & {{P_i}(t + 1) = {P_i}(t) + {V_i}(t + 1)} \end{split} } \right.$

(3)

其中, $V$ 表示粒子的速度, $\omega $ 是惯性权重因子, 用来平衡局部和全局搜索方向, ${r_1}$ 和 ${r_2}$ 是两个符合均匀分布的随机数, 介于 $[0, 1]$ 之间, ${c_1}$ 和 ${c_2}$ 是加速度系数. PSO的伪代码如算法2所示.

算法2. PSO算法

输入: 最小化目标函数 $\scriptstyle f\left( X \right):{R^N} \to R$ ; 搜索空间 $\scriptstyle {D_x} = \{ X|{l_1} \leqslant {x_i} \leqslant {u_i}\} $

输出: 全局最优值 $\scriptstyle {X^*}$

FOR 每个粒子 $\scriptstyle i = \{ 1, 2, \cdots , {N_p}\} $ DO

　用 $\scriptstyle {D_x}$ 中均匀分布的向量初始化 $\scriptstyle {P_i}$ ;

　　 $\scriptstyle pbes{t_i}: = {P_i}$ ;

　用 $\scriptstyle {D_V} = \{ V|{l_i} - {u_i} \leqslant {v_i} \leqslant {u_i} - {l_i}\} $ 中均匀分布的向量初始化 $\scriptstyle {V_i}$ ;

END FOR

$\scriptstyle gbest: = {\rm argmin}{\text{ }}f({P_i})$ ;

$\scriptstyle t = 1$ ;

REPEAT

　FOR 每个粒子 $\scriptstyle i = \{ 1, 2, \cdots , {N_p}\} $ DO

　在 $\scriptstyle [0, 1]$ 之间选择两个随机数作为 $\scriptstyle {r_1}$ 和 $\scriptstyle {r_2}$ ;

　 $\scriptstyle {V_i}{{: = \omega }}{V_i} + {c_1}{r_1}\left( {pbes{t_i} - {P_i}} \right) + {c_2}{r_2}\left( {gbest - {P_i}} \right)$ ;

　 $\scriptstyle {P_i}: = {P_i} + {V_i}$ ;

IF $\scriptstyle f\left({P}_{i}\right) < f\left(pbes{t}_{i}\right) $ THEN

　　 $\scriptstyle pbes{t_i}: = {P_i}$ ;

　IF $\scriptstyle f\left({P}_{i}\right) < f\left(gbest\right) $ THEN

　　　 $\scriptstyle gbest: = {P_i}$ ;

　　END IF

　END IF

UNTIL (满足终止条件)

1.3 经典多目标进化算法

通常, 现实中的优化问题往往是多目标的, 且多个目标之间是相互作用且相互冲突的, 需要对相互冲突的子目标进行折衷(tradeoffs). 由此, 出现了多目标进化算法(multi-objective evolutionary algorithm, MOEA). 在不同的文献中, 将MOEA亦称为多目标遗传算法(multi-objective genetic algorithm, MOGA)以及进化多目标优化(evolutionary multi-objective optimization, EMOO)等^[37].

多目标优化问题定义如下:

$ \begin{array}{*{20}{c}} {\mathop {\min }\limits_{x \in \omega } F(x) = } \end{array}\mathop {\min }\limits_{x \in \omega } ({f_1}(x), {f_2}(x), \cdots , {f_m}(x)) $

(4)

其中, $F\left( x \right):\omega \to {R^m}$ 由 $m$ 个需要被最小化的实值连续函数组成, $x$ 为决策向量, $\omega $ 为决策空间中的可行域. 多目标优化问题中, 在目标空间给定两个向量 $w = \left( {{w_1}, {w_2}, \ldots , {w_m}} \right)$ 和 $\;\mu = \left( {{\mu _1}, {\mu _2}, \cdots , {\mu _m}} \right)$ , $\;\mu $ 支配 $w$ 当且仅当 $\;{\mu _i} \leqslant {w_i}, i = 1, 2, \cdots , m$ 并且 $\;\mu \ne w$ , 记为 $\;\mu \prec w$ . 当不存在任何一个向量 $x \in \omega $ 支配决策向量 ${x}{{'}}$ 时, ${x}{{'}}$ 被认为是Pareto最优解(Pareto-optimal). 所有Pareto最优解构成的集合, 称为Pareto最优解集(Pareto-optimal set, PS), 公式定义如下:

$ \begin{array}{c}PS=\left\{{x'}\in \omega \text{|}\nexists x\in \omega , 且F(x)\prec F({x'})\right\}\end{array} $

(5)

同时, Pareto最优解集的映射称为Pareto最优前沿(Pareto-optimal front, PF), $PF = F\left( x \right)|x \in PS$ . 多目标优化的目标是求解一组均匀分布的Pareto最优解. 如图1所示, 以两个目0标的优化问题为例, $x$ 轴和 $y$ 轴分别代表相互冲突的两个优化目标, 曲线表示Pareto前沿. 由于这是一个最小化问题, 因此, 可行域中候选解的两个目标的值越小, 该解更优. 图中, 点 $A$ 支配点 $B$ 和其所在的阴影区域, 点 $A$ 和点 $C$ 互不支配, 点 $D$ 所属的Pareto前沿以下的不可达区域.

按进化机制的不同, MOEA可分为3类: 基于分解的MOEA (decomposition-based MOEA)、基于支配关系的MOEA (domination-based MOEA)和基于指标的MOEA (indicator-based MOEA)^[37].

基于分解的MOEA: 其思想是将多目标问题通过组合函数(combine)或聚集函数(aggregate)转换为单目标问题. 聚集函数可以是线性的也可以是非线性的. 但聚集函数是线性的时候会出现很难找到非凸解的问题. 代表的算法有向量评价遗传算法(VEGA)^[38]、MOEA/D^[39]、MOEA/D-ACO^[40].

基于支配关系的MOEA: 利用基于Pareto的适应度的分配策略, 从当前进化群体中找出所有的非支配个体, 该方法由Goldberg等人^[41]提出. 代表进化算法有NSGA^[42]、NSGA-II^[43]、NSGA-III^[44]、SPEA^[45]、SPEA2^[46]、MOGA^[47]、NPGA^[48]、PAES^[49]、PESA^[50]等.

基于指标的MOEA: 使用性能评价指标来引导搜索过程和对解的选择过程. 如Zitzler等人提出的IBEA^[51], 使用一个任意的指标来评价并比较一对候选解的性能, 以及Bader和Zitzler提出的针对高维优化的一个快速计算的基于超体积指标的算法^[52].

在上述算法中, MOEA/D得到了广泛的应用和改进, 其核心思想是将多目标优化问题分解为一组单目标子问题或多个多目标子问题, 利用子问题之间的邻域关系, 通过协作的方式同时优化所有子问题, 从而找到整个Pareto前沿的逼近. 一般, 子问题( $K$ 个)的定义由权重向量( $K$ 个)确定, 每个子问题关联一个权重向量, 子问题之间的邻域关系(每个子问题有 $T$ 个最近邻)通过计算权重向量之间的欧氏距离确定. 由于MOEA/D强调从邻域中选择父代执行交叉算子产生新的子代个体, 并在邻域内按照一定规则更新种群, 所以, MOEA/D的搜索效率得到提升, 同时也区别于简单的 $K$ 个独立并行搜索. 基于切比雪夫方法的MOEA/D的伪代码如算法3所示^[39].

算法3. MOEA/D算法

输入: 初始个体

输出: 最优非支配解集

初始化精英种群 $\scriptstyle EP = \emptyset $ ;

为权重向量集合 $\scriptstyle \left\{ {{\lambda ^1}, \cdots, {\lambda ^K}} \right\}$ 中每个权重 $\scriptstyle {\lambda ^i}$ 确定 $\scriptstyle T$ 个相邻权重向量 $\scriptstyle \left\{ {{\lambda ^{i1}}, \cdots, {\lambda ^{iT}}} \right\}$ ,

并标记其邻域为 $\scriptstyle N{S_i} = \left\{ {{i_1},\cdots, {i_T}} \right\}$ ;

初始化种群 $\scriptstyle P = \left\{ {{x^1}, \cdots, {x^K}} \right\}$ ;

初始化参考点 $\scriptstyle {{\textit{z}}_j} = \mathop {{\text{min}}}\limits_{i \in \left\{ {1, \cdots, K} \right\}} {f_j}\left( {{x^i}} \right)$ ;

REPEAT

　FOR每个 $\scriptstyle i \in \left\{ {1, \cdots, K} \right\}$ DO

　交叉算子: 从邻域 $\scriptstyle N{S_i} = \left\{ {{i_1}, \cdots, {i_T}} \right\}$ 中随机选取两个个体, 通过交叉算子产生新的个体 $\scriptstyle x$ ;

　根据约束修正解 $\scriptstyle x$ 产生 $\scriptstyle x'$ ; 更新参考点 $\scriptstyle{\textit{z}}$ ;

　FOR每个 $\scriptstyle j \in N{S_i}$ DO

　　IF $\scriptstyle {g^{te}}\left( {x'|{\lambda ^j}} \right) \leqslant {g^{te}}\left( {{y^j}|{\lambda ^j}} \right)$ THEN

　　　　 $\scriptstyle {y^j} = x'$ ;

　　　　更新邻域中的个体;

　　　END IF

　　END FOR

　　更新 $\scriptstyle EP$ ;

　END FOR

UNTIL (满足终止条件)

算法3中, ${g^{te}}\left( {x|\lambda } \right) = \mathop {{\text{max}}}\limits_{i = 1, 2, \cdots, N} \left\{ {{\lambda ^i}{f_i}\left( x \right) - {\textit{z}}_i^{\text{*}}} \right\}$ 是切比雪夫函数(Chebyshev scalarizing function).

目前, 多目标进化优化的研究方向主要包括方法研究, 理论研究和应用研究. 方法研究的内容包括但不限于高维MOP, 基于偏好的MOP, 动态MOP. MOEA的理论研究的内容有如收敛性分析, Pareto最优解集的构造方法, MOEA性能评价方法, MOEA测试及测试函数的构造方法等. MOEA应用研究则是将MOEA应用到不同的领域. 已有的研究成果中, MOEA已经应用到了机器学习、优化控制、数据挖掘、通信与网络优化等领域中^[37].

2 进化算法在复杂网络中的应用

进化算法常用于复杂网络中的3类任务: 社团检测、鲁棒性优化以及其他任务. 本节将根据不同任务进行详述.

2.1 社团检测任务及其相关优化目标

在网络科学研究中, 如果某个网络中的节点可以轻易地被划分为若干个内部紧密连接的节点集(集合间可能重合), 那么就可以说这个网络具有社团结构^[8]. 社团结构存在于各种不同的网络中, 如社交网络、生物网络、信息网络等. 网络中社团结构的检测问题称为社团检测问题(community detection problems, CDPs). 社团结构分为两类: 分离社团结构(separated community structure)和重叠社团结构(overlapped community structure). 其中分离社团结构中每个节点只会被划分到一个社团中, 而重叠社团结构中每个节点允许被划分到多个社团中.

社团检测是一个常用的分析策略, 复杂网络中的社团检测可以帮助人们更好地了解网络的组织结构. 其实际应用场景有如商品推荐^[53], 疾病的预测和预防^[54], 为高维数据集降维^[55], 以及流行病的传播和控制^{[56, 57]}. 通常, 社团检测问题被建模为优化问题. 由于优化问题一般为NP难问题. 因此, 出现了许多元启发式算法, 如遗传算法、模拟退火算法和协同进化算法.

通常的社团检测任务针对无向无权网络, 对于有向网络通常选择忽略连边方向, 但与此同时也丢失了有向边提供的额外信息. 在有权网络中, 连边权重被认为是两个节点之间关系强弱的度量, 因此社团检测任务可以轻松地适应有权网络.

社团检测任务的常见优化目标如下.

(1)标准化互信息(normalized mutual information, $NMI$ ): 社团结构的优化应该保证优化前后社团划分的相似性. 简单的边重连策略会扰乱甚至破坏网络内部社团结构, 因此优化过程应该保留社团内部的连接信息. 文献[58]提出的 $NMI$ 根据混淆矩阵判断社团划分后信息保留的完整程度. 其公式定义如下所示:

$ NMI\left( {X, Y} \right) = \dfrac{{ - 2\displaystyle\mathop \sum \nolimits_{i = 1}^{cX} \displaystyle\mathop \sum \nolimits_{j = 1}^{cY} {N_{ij}}\log\left( {\dfrac{{{N_{ij}}N}}{{{N_{i.}}{N_{.j}}}}} \right)}}{{\displaystyle\mathop \sum \nolimits_{i = 1}^{cX} {N_{i.}}\log\left( {\dfrac{{{N_{i.}}}}{N}} \right) + \displaystyle\mathop \sum \nolimits_{j = 1}^{cY} {N_{.j}}\log\left( {\dfrac{{{N_{.j}}}}{N}} \right)}} $

(6)

其中, $X$ 表示真实社团划分结果, $Y$ 表示通过社团检测得到的社团划分结果, $cX\;(cY)$ 则表示划分结果 $X\;(Y)$ 中的社团数, ${N_{ij}}$ 则表示社团 $i$ 中节点被划分到社团 $j$ 的数量, ${N_{i.}}\;({N_{.j}}$ )表示社团 $i\;(j)$ 的节点数. $NMI$ 只适用于分离社团结构, Lancichinetti等人提出的广义 $NMI$ ^[59]适用于重叠社团结构.

(2)模块化值(modularity, $Q$ ): Newman提出的模块化值^[60]用于评价社团结构的质量. 其原理基于随机图不存在社团结构, 因此随机图和原始网络社团密度的差异可以反映社团结构的质量. 模块化值的公式定义如下:

$ \begin{array}{c}Q=\dfrac{1}{2M} \end{array}{\displaystyle \sum }_{i, j}({A}_{ij}-{P}_{ij})\delta ({C}_{i}, {C}_{j}) $

(7)

其中, $M$ 为图中总边数, $A$ 为邻接矩阵, ${P_{ij}}$ 代表随机图中节点 $i$ 和节点 $j$ 之间连边数的期望, 其值取决于对零模型的选择. 通常选择和原始网络度分布相同的零模型, 此时节点 $i$ 和节点 $j$ 之间连边数的期望为 $ \dfrac{{{k_i}{k_j}}}{{4{M^2}}} $ . ${C_i}\;({C_j})$ 表示节点 $i$ (节点 $j$ )属于的社团, 当节点 $i$ 和节点 $j$ 同属一个社团时, $\delta = 1$ , 否则为 $0$ . 模块化值越大, 表示社团结构质量越好.

有向网络的社团结构模块化值^[61]定义如下:

$ \begin{array}{c}{Q}_{D}=\dfrac{1}{2M} \end{array}{\displaystyle \sum }_{i, j}\left({A}_{ij}-\frac{{k}_{i}^{\rm out}{k}_{j}^{\rm in}}{M}\right)\delta ({C}_{i}, {C}_{j}) $

(8)

其中, $k_i^{{\rm{out}}}$ 指节点 $i$ 的出边数, $k_j^{{\rm{in}}}$ 为节点 $j$ 的入边数.

对于有权的无符号网络, 使用权重和代替度数, 公式定义如下:

$ \begin{array}{c}{Q}_{W}=\dfrac{1}{2M} \end{array}{\displaystyle \sum }_{i, j}\left({w}_{ij}-\frac{{w}_{i}{w}_{j}}{2w}\right)\delta ({C}_{i}, {C}_{j}) $

(9)

其中, ${w_{ij}}$ 表示节点 $i$ 和节点 $j$ 之间的权重, ${w_i}\;({w_j})$ 表示和节点 $i$ (节点 $j$ )相连的连边的权重和, $w$ 则表示网络中所有连边的权重和.

对于符号网络, 文献[62]中提出如下公式, 其正边和负边需要分别计算.

$ {Q}_{S}=\frac{1}{2{w}^++2{w}^-} {\displaystyle \sum }_{i, j}\left({w}_{ij}-\left(\frac{{w}_{i}^+{w}_{j}^+}{2{w}^+}-\frac{{w}_{i}^-{w}_{j}^-}{2{w}^-}\right)\right)\delta ({C}_{i}, {C}_{j}) $

(10)

其中, $w_i^ + \;(w_j^ + )$ 代表和节点 $i$ (节点 $j$ )相连的正边的权重和, $w_i^ - \;(w_j^ - )$ 代表和节点 $i$ (节点 $j$ )相连的负边的权重和, ${w^ + }\;({w^ - })$ 则分别代表整个网络中的正边和负边的权重和.

文献[63]将模块化值的概念扩展到了重叠社团结构中, 公式定义如下:

$ \begin{array}{c}{Q}_{O}=\dfrac{1}{2M} \end{array}{\displaystyle \sum }_{C}{\displaystyle \sum }_{i, j\in C}\frac{1}{{O}_{i}{O}_{j}}\left({A}_{ij}-\frac{{k}_{i}{k}_{j}}{2M}\right) $

(11)

其中, ${O_i}\;({O_j})$ 表示节点 $i$ (节点 $j$ )属于多少个的社团数目.

此外, 文献[64]提出了适用于具有重叠社团结构的符号网络的模块化值, 定义如下:

$\begin{split} & {Q}_{S}O=\\ &\dfrac{1}{2{w}^++2{w}^-}{\displaystyle \sum }_{C}{\displaystyle \sum }_{i, j\in C}\frac{1}{{O}_{i}{O}_{j}}\left({w}_{ij}-\left(\frac{{w}_{i}^+{w}_{j}^+}{2{w}^+}-\frac{{w}_{i}^-{w}_{j}^-}{2{w}^-}\right)\right) \end{split} $

(12)

但是模块化值被文献[65]证实具有局限性, 当模块化值无法识别小于一定规模的社团结构, 而该规模的大小取决于网络自身的大小和社团结构之间的互连程度.

(3) Ratio association ( $RA$ )和ratio cut ( $RC$ ): $RA$ 与 $RC$ 的公式定义如下所示. 给定图的划分 $ S = \left( {{V_1}, {V_2}, \cdots, {V_m}} \right) $ , $ {V_i} $ 是图 $G$ 的子图. $RA$ 与 $RC$ 分别代表子图 ${V_i}$ 内部度与子图大小之比和外部度与子图大小之比.

$\left\{ { \begin{split} & RA = \mathop \sum \limits_{i = 1}^m \frac{{L\left( {{V_i}, {V_i}} \right)}}{{\left| {{V_i}} \right|}} \\ & RC = \mathop \sum \limits_{i = 1}^m \left( {\frac{{L\left( {{V_i}, \overline {{V_i}} } \right)}}{{\left| {{V_i}} \right|}}} \right) \end{split} } \right.$

(13)

(4)核K均值(kernel K-means, $KKM$ ): 文献[66]中指出 $KKM$ 是关于社团数量递减的函数, 而 $RC$ 与之相反, 即二者是相互冲突的目标. 因此, 有许多文章用 $KKM$ 与 $RC$ 作为两个优化目标. $KKM$ 的定义如下:

$ \begin{array}{*{20}{c}} {KKM = 2\left( {N - m} \right) - \displaystyle\mathop \sum \limits_{i = 1}^m \left( {\dfrac{{L\left( {{V_i}, {V_i}} \right)}}{{\left| {{V_i}} \right|}}} \right)} \end{array} $

(14)

(5)模块化密度(modularity density, D): 针对模块化值没有考虑到社团中节点的数量的问题, Li等人提出了一种新的评价网络社团划分的量化指标, 称为模块化密度^[67]. 其公式定义如下:

$ D = \mathop \sum \limits_{i = 1}^m \frac{{L\left( {{V_i}, {V_i}} \right) - L\left( {{V_i}, \overline {{V_i}} } \right)}}{{\left| {{V_i}} \right|}} = RA - RC $

(15)

最大化 $RA$ 趋于将网络划分为内部紧密连接的小社团结构, 而最小化 $RC$ 趋于将网络划分为外部稀疏连接的大社团结构, 模块化密度则是这两个目标之间的权衡. 此外, 文献[67]证明了D与 $KKM$ 的等价性.

(6)紧密度(tightness, $T$ ): Huang等人基于结构相似性提出度量社团结构质量的新方法^[68], 称为紧密度. 公式定义如下:

$ \begin{array}{c}T\left(C\right)=\dfrac{{S}_{C}^{{\rm{in}}}}{{S}_{C}^{{\rm{in}}}+{S}_{C}^{{\rm{out}}}} \end{array} $

(16)

其中,

$\left\{ { \begin{array}{*{20}{l}} {S_C^{{\rm{in}}} = \displaystyle\mathop \sum \limits_{u \in C, v \in C, u, v \in E} s\left( {u, v} \right)} \\ {S_C^{{\rm{out}}} = \displaystyle\mathop \sum \limits_{u \in C, v \in \overline C , u, v \in E} s\left( {u, v} \right)} \\ {s\left( {u, v} \right) = \dfrac{{\displaystyle\mathop \sum \nolimits_{x \in \Gamma \left( u \right) \cap \Gamma \left( v \right)} {w_{ux}} \times {w_{vx}}}}{{\sqrt {\displaystyle\mathop \sum \nolimits_{x \in \Gamma \left( u \right)} w_{ux}^2} \sqrt {\displaystyle\mathop \sum \nolimits_{x \in \Gamma \left( v \right)} w_{vx}^2} }}} \end{array} } \right.$

其中, $S_C^{{\rm{in}}}$ 表示在社团 $C$ 内部所有相邻节点间相似度的和, $S_C^{{\rm{out}}}$ 表示社团 $C$ 内外两个节点间相似度之和, $v \in \overline C $ 表示节点 $v$ 属于社团 $C$ 之外的节点. $s\left( {u, v} \right)$ 则表示节点 $u$ 和节点 $v$ 间的相似度值的度量, $\Gamma \left( x \right)$ 表示节点 $x$ 及其邻居构成的节点集合, ${w_{ux}}\;({w_{vx}})$ 则表示节点 $u$ (节点 $v$ )和节点 $x$ 连边的权重, 若两个节点共享的邻居越多, 那两者的相似度值越高.

文献[64]基于社会平衡理论^[69]将紧密度扩展到符号网络中, 公式定义如下:

$ \begin{array}{c}{T}_{S}\left(C\right)=\dfrac{{S}_{C}^{{\rm{in}}+}-{S}_{C}^{{\rm{in}}-}}{{S}_{C}^{{\rm{in}}+}-{S}_{C}^{{\rm{in}}-}+{S}_{C}^{{\rm{out}}+}} \end{array} $

(17)

其中,

$\left\{ { \begin{array}{ll} {S}_{C}^{{\rm{in}}+} ={\displaystyle \sum }_{u, v\in C, \left(u, v\right)\in E}\max\left({s}_{{\rm{signed}}}\left(u, v\right), 0\right)\\ {S}_{C}^{{\rm{out}}+} ={\displaystyle \sum }_{u\in C, v\in \overline{C}, \left(u, v\right)\in E}\max\left({s}_{{\rm{signed}}}\left(u, v\right), 0\right)\\ {S}_{C}^{{\rm{in}}-} ={\displaystyle \sum }_{u, v\in C, \left(u, v\right)\in E}\min\left({s}_{{\rm{signed}}}\left(u, v\right), 0\right)\\ {s}_{{\rm{signed}}}(u, v) =\frac{{{\displaystyle \sum }}_{x\in \Gamma \left(u\right)\cap \Gamma \left(v\right)}\psi \left(x\right)}{\sqrt{{{\displaystyle \sum }}_{x\in \Gamma \left(u\right)}{w}_{ux}^{2}}\sqrt{{{\displaystyle \sum }}_{x\in \Gamma \left(v\right)}{w}_{vx}^{2}}}\\ \psi (x) =\left\{ {\begin{array}{ll}0, & \text{if }{w}_{ux}\leqslant 0, {w}_{vx}\leqslant 0 \\ {w}_{ux}\times {w}_{vx}, & \text{otherwise} \end{array}} \right.\end{array}} \right. $

其中, $S_C^{{\rm{in}} + }$ 表示社团 $C$ 内部所有正边相连节点间相似度的和, $S_C^{{\rm{out}} + }$ 表示社团 $C$ 内外所有正边相连节点间相似度的和, $S_C^{{\rm{in}} - }$ 表示社团 $C$ 内部所有负边相连节点间相似度的和, ${s_{{\rm{signed}}}}\left( {u, v} \right)$ 则表示符号网络中, 节点 $u$ 和节点 $v$ 间的相似度值的度量.

单目标优化方法是现有研究中解决社团检测问题的一个关键思路. 如, Pizzuti^[70]提出了一种基于遗传算法的方法, 称为GA-Net, 用于社交网络中的社团检测. Gong等人提出了一种社团检测方法, 称为Meme-Net, 通过模因算法来优化网络模块化密度^[71]. Cai等人^{[72, 73]}设计了用于社团检测的离散粒子群优化(discrete particle swarm optimization)算法. 为提高遗传算法的空间搜索能力, Bui等人提出了一种基于模式预处理阶段的图划分遗传算法^[74]. Talbi等人针对图划分问题提出了一种并行遗传算法, 该算法具有超线性加速^[75]的特性. Tasgin等人使用一种基于模块化值的遗传算法来检测社团^[76]. Gog等人提出了一种基于种群中个体间信息共享极值的新型协作进化算法^[77].

为了避免单目标优化算法陷入局部最优的缺点, 许多多目标社团检测方法被提出. 如Pizzuti提出的多目标遗传算法(MOGA-Net)通过两个目标函数分别最大化社团内部连接和最小化社团间的连接来发现社团结构^[78]. Shi等人提出了一个两阶段的多目标社团检测的框架(MOCD), 并基于此框架提出一种多目标进化算法寻找有效解^[79]. Shi等人同样分析了11种与社团检测任务相关的目标函数间的相关性, 并指出对一对负相关的目标进行多目标优化的结果要优于对任意一个原始目标进行单目标优化的结果^[80]. Gong等人使用基于分解的多目标进化算法, 提出了用于社团检测的方法(MOEA/D-Net), 将 $RA$ 与 $RC$ 作为优化目标, 寻找最大化社团内部连接和最小化社团间连接的权衡^[81]. 之后, Gong等人提出了一种用于社团结构检测的多目标离散粒子群优化(MODPSO)算法, 并将 $KKM$ 和 $RC$ 作为优化目标^[82]. Zhou等人提出的基于局部搜索的多目标优化算法(MOLS-Net)同样使用 $KKM$ 和 $RC$ 作为优化目标完成社团检测任务^[83]. Li等人^[84]提出了一种新的基于离散粒子群算法的多目标方法(QDM-PSO), 该方法采用量子机制同时优化 $KKM$ 和 $RC$ . 虽然基于算法的量子机制可以并行工作, 但搜索空间太大, 导致算法效率很低, 所以该方法仅在小规模的网络上有较好的表现. 鉴于此, 文献[85]将 $KKM$ 和 $RC$ 的变体作为两个优化目标, 采用了一种基于奇异值分解(SVD)框架的网络嵌入方法——任意阶近似保留嵌入(AROPE)^[86]. 将网络嵌入方法和多目标优化算法结合, 不仅能避免单目标优化算法易陷入局部最优的缺点, 同时能减少多目标优化算法的搜索空间, 使算法适用于大规模网络. 此外, Ghaffaripour等人提出了一种针对有权网络中社团检测问题的多目标优化算法^[87]. Liu等人提出了一种多目标进化算法用于同时检测分离社团结构和重叠社团结构^[88].

2.2 鲁棒性优化任务相关目标

本节的鲁棒性优化任务中, 鲁棒性分为连通性鲁棒性和能控性鲁棒性两种, 二者对于复杂网络的不同应用场景均有重要意义. 复杂网络通过演化动力学研究网络的鲁棒性, 鲁棒性是指发生蓄意攻击或内部错误时, 系统保持其原有功能的能力. 鲁棒性的研究对于系统设计而言具有指导意义, 能够有效抵抗未知错误和攻击的健壮系统已经成为迫切的需要. 近年来, 人们已经从不同的角度提出了评估网络的鲁棒性的方法. 1994年, Merris提出了基于拉普拉斯矩阵^[89]特征值的方法; 2000年, Albert等人^[90]从图论的角度提出了鲁棒性度量方法, 利用网络解体(network disintegration)过程中最大联通分支的数值表现来评价网络在去除部分顶点或连边后的性能. 此外, 针对不同攻击方式, 也提出了相应的评级指标. 如, 在随机攻击中, 每次以等概率删除一个节点或一条连边^[90]; 在蓄意攻击中, 节点或连边按照某种性质进行排序, 然后删除最重要的节点或连边, 最后根据实际情况判断删除后是否需要重新计算重要度^[91].

鲁棒性优化任务相关的目标具体如下.

(1)连通性鲁棒性(connectivity robustness, $R$ ): 2011年, Schneider等人提出了一种新的度量方法 $R$ (为区别于其他鲁棒性评价方法, 称其为连通性鲁棒性)^[92], 利用对网络进行攻击后, 网络中剩余最大连通子图的大小进行度量. 计算如式(18)所示, 其中, $N$ 为网络中的节点数; $Q$ 为被移除的节点数; $s\left( Q \right)$ 为移除 $Q$ 个节点后, 最大连通分量所占的比例; 归一化因子 $1/N$ 确保具有不同节点数量的网络具有可比性.

$ \begin{array}{c}\begin{array}{rr} R =\dfrac{1}{N}{\displaystyle \sum }_{Q=1}^{N}s\left(Q\right)\end{array} \end{array} $

(18)

现有的研究中, 针对网络鲁棒性的优化通常在某种结构约束(如保持节点度分布不变)下, 通过拓扑重连来提高网络的鲁棒性. 常用的算法包括贪心算法^[92]、模拟退火算法^[93]和进化算法^[94].

(2)能控性(controllability): 复杂网络能控性的概念由Kalman在1960年首先提出^{[95, 96]}, 目前已成为复杂网络研究的一个核心问题. 能控性的概念是指在有限时间内, 通过适当的控制输入, 控制网络从任意初始状态到达一个目标状态的能力^[22]. 对于一个复杂网络系统或线性时不变(linear time-invariant, LTI)系统, 满足 $\dot x = Ax + Bu$ . 其中 $A$ 和 $B$ 分别为 $N \times N$ 和 $N \times {N_D}$ 的常系数矩阵, $x$ 为状态向量, $u$ 为控制输入, $N$ 为系统中节点数, ${N_D}$ 是系统所需控制节点的总和. 卡尔曼准则(Kalman criterion)提出该系统能控的充分必要条件是系统的能控性矩阵 $ C=\left[B AB {A}^{2}B\cdots{A}^{N-1}B\right] $ 满足行满秩^[96], 该能控性被称为复杂网络的状态能控性(state controllable). 结构能控性的概念是状态能控性的泛化, 对于常参数系数矩阵 $A$ 和 $B$ , 如果存在一组非零参数值可以确保系统是状态能控的, 那么则称该系统是结构能控的. 一个能控系统, 其状态向量 $x$ 可以通过适当的控制输入 $u$ 从任意初始状态驱动至任意目标状态.

控制节点数( ${N_D}$ )的计算方式通常有两种, 分别依据结构能控性^[16]和精确能控性^[97]. 在文献[16]中, Liu等人提出了最大匹配来识别控制节点的最小集, 从而引导整个网络进入任意期望的最终状态. 依据最小输入理论(minimum inputs throrem), 控制节点数为: ${N_D} = \max \left\{ {1, N - \left| {{E^{\text{*}}}} \right|} \right\}$ . 其中 $\left| {{E^{\text{*}}}} \right|$ 为最大匹配 ${E^{\text{*}}}$ 中的节点数; Yuan等人根据卡尔曼准则的等价条件(Popov-Belevitch-Hautus)秩提出精确能控性^[97], 将控制节点的计算从有向图扩展到无向图中, 其表达式为: ${N_D} = \max\left\{ {1, N - rank\left( A \right)} \right\}$ , $rank\left( A \right)$ 表示邻接矩阵 $A$ 的秩.

复杂网络能控性一般可以通过控制节点的密度 $\left({n_D} = \dfrac{{{N_D}}}{N}, \in \left[ {\dfrac{1}{N}, 1} \right]\right)$ 来量化. 当 ${n_D} = \dfrac{1}{N}$ 时, 网络中控制节点数为1, 此时网络能控性最好, 当 ${n_D} = 1$ 时, 网络中所有节点为孤立结点, 此时能控性最差^[98].

(3)能控性鲁棒性(controllability robustness, ${R_c}$ ): 复杂网络的能控性理论为研究神经网络结构和功能之间的联系提供了分析工具, 而能控性鲁棒性则为进一步研究提供量化分析基础^[98]. 文献[99-101]将鲁棒性和能控性的定义结合在一起, 发现网络结构对这两种性质都有影响. 复杂网络在攻击下维持能控性的能力称为能控性鲁棒性, 能控性鲁棒性好的网络系统具有好的抵御攻击的能力, 同时也能为攻击后的补救争取时间, 延迟系统的整体瘫痪.

通常, 能控性鲁棒性计算基于能控性曲线, 它由一组能控性值的序列组成, 通过计算系统遭受节点或连边攻击后, 剩余网络的能控性得到. 由于伴随攻击过程, 网络能控性是动态变化的. 因此, 网络整体的能控性鲁棒性为控制节点密度( $n_D^N\left( i \right) = \dfrac{{{N_D}\left( i \right)}}{{N - i}}, i = 0, 1, \cdots, N - 1$ )的平均值. 以节点攻击下的能控性鲁棒性为例, 其计算公式如下所示:

$ \begin{array}{c}\begin{array}{r} {R}_{c}=\dfrac{1}{N}{\displaystyle \sum }_{i=0}^{N-1}{n}_{D}^{N}\left(i\right)\end{array} \end{array} $

(19)

网络拥有较小的 ${R_c}$ 表示其能控性鲁棒性较好.

(4)可控的鲁棒性(controllable robustness, $CR$ ): 文献[92]中指出, 网络中最大连通分支的存在是在故障发生时保持系统功能的关键. 而有向网络的动态过程主要依赖于有向传播路径, 因此, 对于有向网络, 仅关注连通分支是很局限的. 于是, Wang等人将连通性与能控性的概念结合, 提出可控的鲁棒性( $CR$ )^[99], 其公式定义如下:

$ \begin{array}{c}\begin{array}{rr} CR =\dfrac{1}{N}{\displaystyle \sum }_{q=1}^{N}\dfrac{s\left(q\right)}{{N}_{D}\left(q\right)}\end{array} \end{array} $

(20)

其中, $s\left( q \right)$ 表示删除 $q$ 个节点后, 最大连通分支大小; ${N_D}\left( q \right)$ 表示删除 $q$ 个节点后, 网络控制节点的数量. 同样, 采用拓扑重连策略优化 $CR$ .

(5)社团鲁棒性(community robustness, ${R_{\rm com}}$ ): 社团鲁棒性关注的是攻击发生时社团的完整性. Ma等人基于文献[92]中的鲁棒性评价方法, 提出社团的鲁棒性的度量方法^[102], 公式定义如下所示:

$ \begin{array}{c}\begin{array}{rr} {R}_{{\rm{com}}} =\dfrac{1}{N}{\displaystyle \sum }_{q=1}^{N}\left[\dfrac{1}{k}{\displaystyle \sum }_{p=1}^{k}\dfrac{{S}_{pq}}{{S}_{p}}\right]\end{array} \end{array} $

(21)

其中, $k$ 为社团数目, ${S_p}$ 为社团 $p$ 中节点数, ${S_{pq}}$ 为第 $q$ 个节点被攻击后, 社团 $p$ 中剩余节点数. $1/N$ 和 $1/k$ 是归一化因子, 保证不同规模和社团规模的网络具有可比性. ${R_{{\rm{com}}}}$ 值较大的网络在故障下具有较好的社团鲁棒性.

(6)互依网络中的社团鲁棒性( $R_{{\rm{com}}}^{{\rm{inter}}}$ ): 文献[103]将社团鲁棒性的概念扩展到互依网络^[104-107]中, 公式计算如下:

$ R_{{\rm{com}}}^{{\rm{inter}}} = \frac{1}{{{L_{\max}}}}\mathop \sum \limits_{l = 1}^{{L_{\max}}} {f_{{\rm{com}}}}\left( {{G_l}} \right) = \frac{1}{{{L_{\max}}}}\mathop \sum \limits_{l = 1}^{{L_{\max}}} \mathop \sum \limits_{q = 1}^{{N_l}} \frac{1}{{{N_l}}}\left[ {\frac{1}{{{k_l}}}\mathop \sum \limits_{p = 1}^{{k_l}} \frac{{{S_{pq}}}}{{{S_p}}}} \right] $

(22)

其中, ${f_{{\rm{com}}}}\left( {{G_l}} \right)$ 是互依网络中 ${G_l}$ 层的社团完整性, ${L_{\max}}$ 为互依系统中的网络的总层数.

(7)针对连边攻击的社团鲁棒性( ${R}_{NMI}^{l}$ ): 此前的衡量指标基本上有两种: 第1种通过记录失去连边后, 网络中社团结构的 $NMI$ 的变化判断社团鲁棒性, 第2种是文献[108]中提出的通过最大连通分量的大小计算连边攻击下的连通性鲁棒性. 公式定义如下:

$ \begin{array}{c}\begin{array}{r} {R}_{l}=\dfrac{1}{M}{\displaystyle \sum }_{l=1}^{M}s\left(l\right)\end{array} \end{array} $

(23)

其中, $M$ 为网络中总的连边数, $1/M$ 是归一化因子, $s\left( l \right)$ 表示失去l条连边后, 剩余的最大连通分支的大小. 文献[109]扩展了两种计算方法, 定义了 $R_{NMI}^l$ , 公式如下所示:

$ \begin{array}{c}{R}_{NMI}^{l}=\dfrac{1}{M}{\displaystyle \sum }_{l=1}^{M} \end{array}NMI({C}_{l}, {C}_{{\rm{ori}}}) $

(24)

其中, ${C_l}$ 是在删除 $l$ 条连边后的社团检测结果, ${C_{{\rm{ori}}}}$ 是原始的社团划分结果. 与 ${R_l}$ 的衡量方式不同, 该公式通过衡量遭到连边攻击后社团结构前后变化情况来反映社团的稳定性.

(8)节点抵御级联故障的能力: 文献[110]根据节点度提出节点的负载 ${L_i}$ . ${{{C}}_i}$ 为节点 $i$ 抵御级联故障的能力, 和节点的负荷成正比. 公式定义如下:

$ \left\{ {\begin{gathered} {C_i} = \beta {L_i} \\ {L_i} = k_i^\alpha \\ \end{gathered} } \right.$

(25)

其中, 参数 $\;\beta \geqslant 1$ , ${k_i}$ 为节点 $i$ 的度, $\alpha $ 为初始负荷的权重.

(9)网络抵抗级联故障的能力: 在以往的研究中, 为了提高网络抗级联故障的鲁棒性, 一种方法是区分系统中最脆弱的节点并保护它们不受故障影响. 另一种方法则是拓扑重连, 在文献[111]中通过进化算法得到对级联故障具有更好抵御能力的网络. 文献[112]中设计了一种模因算法(memetic algorithm), 并发现以高概率连接负载相似的节点有助于增强网络对级联故障的鲁棒性. 文献[109]中扩展了网络抵抗级联失效模型的衡量指标, 定义如下:

$ \begin{array}{c}{R}_{cf}=\dfrac{1}{N}{\displaystyle \sum }_{t=1}^{T}{s}^{t} \end{array} $

(26)

其中, $T$ 是完全瓦解网络所需的总轮数. 对于不同的网络, $T$ 可能是不同的. ${s_t}$ 为第 $t$ 轮攻击后, 网络中最大连通分量的大小, $1/N$ 为归一化因子, 以保证能够比较不同规模网络的鲁棒性值.

(10)结构平衡的网络的鲁棒性: 文献[113]提出了基于社会心理学领域的结构平衡理论, 文献[114]将其扩展为广义的图论版本, 指出当一个网络可以被划分为几个簇(cluster), 簇内节点之间是正的连接关系, 簇间节点之间是负的连接关系时, 这个网络被认为是平衡的. 通常基于符号网络来研究网络的结构平衡, 平衡网络中的有效连边同时被分为两类: 簇间负关系连边和簇内正关系连边. 文献[115]中通过攻击网络中簇间有效连边后, 最大连通分量的大小来衡量结构平衡的网络簇间鲁棒性, 公式定义如下:

$ {R_{{\rm{inter}}}} = \frac{1}{M}\mathop \sum \limits_{e \in {E_{{\rm{nega}}}}} s(e) $

(27)

同样, 文献[115]中通过攻击网络中簇内有效连边后, 最大连通分量的大小来衡量结构平衡的网络簇内鲁棒性, 公式定义如下:

$ {R_{{\rm{intra}}}} = \frac{1}{M}\mathop \sum \limits_{e \in {E_{{\rm{posi}}}}} s(e) $

(28)

其中, ${E_{{\rm{nega}}}}$ 表示簇间有效连边, 即负关系连边集合, ${E_{{\rm{posi}}}}$ 表示簇内有效连边, 即正关系连边集合.

针对鲁棒性优化任务, 有许多单目标优化的文章. 如, 文献[116]使用代理模型辅助完成网络连通性鲁棒性的优化, 目的是减少网络鲁棒性优化过程的计算成本, 提出了GE-SU-EA_net. 首先, 通过图嵌入方法训练网络的数值化表示, 同时, 使用3种代理模型完成网络的性能预测过程, 得到网络适应度估计器. 在模型管理策略的帮助下, 分别对网络的初始化, 变异, 决策(局部搜索)过程进行管控. 结合图嵌入信息和鲁棒性评价指标, 利用代理模型对鲁棒性进行预测, 既考虑了真实评估因子, 也考虑了代理模型来引导整个优化过程. 在互依网络中, 由于存在多层结构, 不同层之间存在连接, 导致某层遭到蓄意攻击时, 会造成整个互依网络上的级联故障. 针对互依网络面临的蓄意攻击, 文献[117]提出了一种模因算法通过优化网络内部连接增强互依网络的连通性鲁棒性. 对于互依网络中的社团鲁棒性优化问题, 文献[103]设计了一个鲁棒性评测方法, 即 $R_{{\rm{com}}}^{{\rm{inter}}}$ , 将普通的单一网络中社团鲁棒性评测指标扩展到社团鲁棒性中. 提出算法MA-CR_inter, 采用模因算法对互依网络的鲁棒性进行优化. 和单一网络的区别在于, 交叉算子和变异算子都发生在社团内部. 同时, 对于一些网络系统不易重构的问题, 文献[103]还提出并改进了解耦(de-coupling)和信息干扰(information disturbance)两种非重连优化策略, 以提高相互依网络的社团鲁棒性. 此外, 文献[118]针对网络面临的连边攻击设计了一种社团鲁棒性的衡量指标, 即 $R_{NMI}^l$ . 提出算法MA-R_com, 优化过程采用模因算法, 每次生成子代种群时, 采用精英策略确保种群的多样性, 并以一定概率执行局部搜索算子. 为保护社团内部的特性, 拓扑重连等操作大部分发生在社团内部, 只有变异算子中存在随机重连, 该操作不局限于社团内部.

同时, 也有许多文章对网络的鲁棒性进行多目标优化. 文献[109]综合考虑了系统可能遇到的蓄意攻击和级联故障, 提出MAGA-Net_R算法. 优化过程在一个网格网络(lattice)中实现. 优化目标中, 网络抵抗蓄意攻击的能力通过 $R$ 进行衡量, 抵御级联故障的能力用 ${R_{cf}}$ 衡量. 文献[119]设计了一个多目标进化算法SP-RV-MOEA_Net, 同时优化在节点攻击下和连边攻击下的网络的连通性鲁棒性. 创新处在于解决了两个鲁棒性评价指标之间存在延迟的问题, 并且通过3种代理模型降低了通过仿真攻击计算网络真实鲁棒性时昂贵的成本. 文中也指出, 3种代理模型虽然能提供不确定信息, 但是只使用一个代理模型同样能得到很好的预测结果. 针对复杂网络中网络结构平衡的问题, 以往的研究中通过减少不平衡的分支来实现, 但并不关心平衡网络抵御攻击和容错的能力. 文献[115]基于MOEA/D设计了多目标进化算法MOEA/D-RSB, 同时优化结构平衡网络的簇内鲁棒性( ${R_{{\rm{intra}}}}$ )和簇间鲁棒性( ${R_{{\rm{inter}}}}$ ). 并发现在簇内保证一定的竞争关系, 即簇内节点间负的连边关系, 和簇间的合作关系, 即簇间节点间正的连边关系, 能增强结构平衡的网络抵御攻击和容错的能力.

2.3 其他优化任务相关目标

本节介绍了两种复杂网络中的优化任务, 其一是博弈论中的合作能力, 其二是寻找网络中最具传播影响力的节点集合. 以下为二者的详述.

(1)合作: 合作是指人类社会在进化博弈过程中的合作现象. 合作性就是指在网络博弈演化趋于稳定时, 网络保存合作者的能力. 合作强调了个体行为, 其广泛存在于社会困境和经济活动中. 保持合作者和叛逃者之间的平衡不仅对系统的稳定和和谐很重要, 对于决策者来说也是必要的. 如在经济学上, 不同的公司可以选择相互合作或竞争. 合作过多可能会导致缺乏创新, 导致行业在海外市场中的竞争力下降, 对金融动荡的抵抗力下降, 而合作过少可能会形成恶性竞争, 也不利于行业的健康发展^[120]. 因此, 对于行业监管机构来说, 合作和竞争之间达到平衡是相当重要的. 此前的研究将进化博弈与复杂网络理论结合在一起^[121-124], 通过仿真模拟博弈演化过程, 并发现不同结构的网络具有不同的能力来保存合作者.

(2)节点的影响力: 为了模拟网络中节点的影响力传播过程, 许多研究提出了影响力传播模型, 如IC (independent cascade)模型^[125]、WC (weighted cascade)模型^[126]以及LT (linear threshold)模型^[127]. 针对社交网络中的影响力最大化问题(influence maximization problem), 文献[128]基于IC模型设计了一种算法, 通过寻找k-种子集(k-seed set), 最大化社交网络中的影响力. 即在给定参数 $k$ 的情况下, 寻找最具影响力的 $k$ 个节点的集合.

由于复杂网络中的鲁棒性和合作性在现实应用和理论分析中都具有重要意义. 然而, 已有研究表明, 在网络结构上, 鲁棒性和合作性是相互冲突的. 因此, 在演化博弈模型的基础上, 许多文章对合作能力与鲁棒性进行共同优化. 对于鲁棒性而言, 同配的网络结构或异质性低的网络结构对于攻击和错误有更高的抵御能力^[92,129], 但这种结构限制了合作者的出现^{[122, 123]}. 为了构建鲁棒且能保证合作能力的网络系统, 文献[130]对 $CR$ 与合作性进行多目标优化, 得到了一系列具有不同鲁棒性和合作水平的网络. 其中进化博弈模拟的是囚徒困境模型, 其回报策略满足: $T > R > P > S$ ( $R$ : 博弈双方相互合作的收益; $P$ : 博弈双方相互背叛的收益; 博弈双方做出不同的选择时, 合作者得到收益 $S$ , 而叛逃者得到收益 $T$ ). 文献[131]在文献[130]的基础上将鲁棒性和合作性的多目标优化扩展到有向图中, 对于实际应用有更多的现实参考意义. 针对有向图的多目标优化, 在不改变节点的入度和出度的前提下, 采用拓扑重连策略调整网络结构.

关于寻找最具影响力的节点集合任务, 文献[132]在文献[125]的基础上, 将模拟影响力传播过程的模型扩展到复用网络(multiplex networks)中, 利用模因算法寻找复用网络中影响力最大的节点集合. 该实验有助于在复用网络中识别潜在的传播者, 为深入了解和分析网络提供了思路.

2.4 优化目标替代指标

在复杂网络中, 除了上述优化目标外, 还有其他性能评价指标, 有时也可以作为优化目标的替代指标.

(1)谱分析方法(spectral measures): 基于网络拉普拉斯矩阵或邻接矩阵特征值的谱分析方法是一种经典的鲁棒性评价方法. 本文将详细介绍谱半径(spectral radius, $SR$ )、谱隙(spectral gap, $SG$ )、代数连通度(algebraic connectivity, $ACo$ )、自然连通度(natural connectivity, $NCo$ )、有效电阻(effective resistance, $ERe$ )和生成树计数(spanning tree count, $STC$ ).

${\textit{SR}}$ : 网络邻接矩阵的最大特征值, 用于衡量图的鲁棒性^[133].

$ \begin{array}{c}{\textit{SR}}={\lambda }_{1} \end{array} $

(29)

${\textit{SG}}$ : 网络邻接矩阵最大特征值与第二大特征值之差, 其与图的扩展性质(expansion property)有关^[134], 同样作为图的鲁棒性衡量指标^[135].

$ \begin{array}{c}\begin{array}{r} {\textit{SG}}={\lambda }_{1}-{\lambda }_{2}\end{array} \end{array} $

(30)

$ACo$ : 拉普拉斯矩阵中第二小的特征值(或第一个非零特征值), Fiedler证明了代数连通度的大小反映了整个图的连通性. 网络的 $ACo$ 越大, 其鲁棒性也就越强^[136].

$ \begin{array}{c}\begin{array}{r} ACo={\mu }_{2},\; {\mu }_{1}\leqslant {\mu }_{2}\leqslant \dots \leqslant {\mu }_{N}\end{array} \end{array} $

(31)

其中, $\;{\mu _i}, i = 1, 2, \cdots, N$ 为拉普拉斯矩阵的特征值.

$NCo$ : $NCo$ 由Wu等人提出, 可以被理解为网络的“平均特征值”^[137]. $NCo$ 的提出在一定程度上解决了 $ACo$ 难以捕捉复杂网络的结构鲁棒性的重要特征这一弱点.

$ \begin{array}{c}\begin{array}{r} NCo=\ln\left(\dfrac{1}{N}{\displaystyle \sum }_{i=1}^{N}{\rm e}^{{\lambda }_{i}}\right)\end{array} \end{array} $

(32)

在给定节点数的情况下, 孤立图(没有连边)的自然连通度最小, 完全图的 $NCo$ 最大, 所以 $NCo$ 越大, 表示该网络越鲁棒.

$ERe$ : $ERe$ 的计算基于将图视作电阻网络这一前提, 整个网络的 $ERe$ 为所有节点对之间 $ERe$ 之和^[138], 数值上与拉普拉斯矩阵的非零特征值之和^[139].

$ \begin{array}{*{20}{c}} {\begin{array}{*{20}{r}} {ERe = \dfrac{1}{2}\displaystyle\mathop \sum \limits_{i, j}^N ER{e_{ij}} = N\displaystyle\mathop \sum \limits_{i = 2}^N \dfrac{1}{{{\mu _i}}}} \end{array}} \end{array} $

(33)

${\textit{STC}}$ : 依据基尔霍夫矩阵树定理, 非同构生成树的数量可以写成拉普拉斯特征值的函数^[140], 之后Baras等人将 $STC$ 作为网络的鲁棒性指标^[141].

$ \begin{array}{c}{\textit{STC}}=\dfrac{1}{N}{\displaystyle \prod }_{i=2}^{N}{\mu }_{i} \end{array} $

(34)

(2)同配性(assortativity, $r$ ): Herrmann等人指出, 具有洋葱状结构的网络在抵御蓄意攻击方面往往表现得更好^[129]. 具有较高 $r$ 值^{[142, 143]}的网络往往呈现出洋葱状结构, 对持续攻击具有较高的抵抗力.

$ \begin{split} & r = \\ &\dfrac{{{{\left| E \right|}^{ - 1}}\displaystyle\mathop \sum \nolimits_{\forall \left\langle {i, j} \right\rangle \in E} {k_i}{k_j} - {{\left[ {{{\left| E \right|}^{ - 1}}\displaystyle\mathop \sum \nolimits_{\forall \left\langle {i, j} \right\rangle \in E} \dfrac{1}{2}\left( {{k_i} + {k_j}} \right)} \right]}^2}}}{{{{\left| E \right|}^{ - 1}}\displaystyle\mathop \sum \nolimits_{\forall \left\langle {i, j} \right\rangle \in E} \dfrac{1}{2}\left( {k_i^2 + k_j^2} \right) - {{\left[ {{{\left| E \right|}^{ - 1}}\displaystyle\mathop \sum \nolimits_{\forall \left\langle {i, j} \right\rangle \in E} \dfrac{1}{2}\left( {{k_i} + {k_j}} \right)} \right]}^2}}} \end{split} $

(35)

(3)异质性(heterogeneity, $H$ ): Ma等人指出, 网络的度分布也会影响其鲁棒性, 同质的网络对蓄意节点攻击的容忍度更高^[144]. 在度分布方面, $H$ 描述了网络中节点度之间的不平等程度^[145], $H$ 越小, 网络的度分布越均匀, 鲁棒性越好. 文献[130]中, 作者用 $H$ 和 $r$ 作为性能代替指标, 调整其值获得不同连通性鲁棒性水平和合作能力的网络.

$ \begin{array}{c}H=\dfrac{{{\displaystyle \sum }}_{i=1}^{N}{{\displaystyle \sum }}_{j=1}^{N}\left|{k}_{i}-{k}_{j}\right|}{2{N}^{2}\langle k\rangle } \end{array} $

(36)

2.5 复杂网络的表示方式

在对复杂网络进行进化优化时, 不同网络在不同情境下的表示方式有所不同.

(1)普通的无权网络通常用邻接矩阵 $A$ 进行表示.

(2)有权网络中则用权重矩阵 $W$ 表示.

(3)社团检测任务中通常采用直接表示方式, 每个社团由 $N$ 维的二进制向量构成, 记第 $k$ 个社团为 ${X_k}$ , 当 ${X_k}$ 的第 $i$ 个元素为1时, 表示第 $i$ 个节点属于第 $k$ 个社团. 直接表示方式将社团结构表示为一个 $N$ 维向量( $X$ ), ${X_i}$ 表示第 $i$ 个节点所属社团. 执行交叉算子时, 两个个体直接交换向量 $X$ 中的部分片段, 执行变异算子时, 可改变向量 $X$ 上的一个或多个值. 直接表示方式的缺点在于社团的数量未知时, 最大社团数为 $N$ , 此时可行解的数量为 ${N^N}$ , 由于搜索空间太大, 远大于贝尔数 ${B_N}$ ( ${B_N}$ 为 $N$ 个节点的网络在理论上划分方式的种数^[146]), 会带来冗余和低效的结果, 且直接表示方式不适用于重叠社团结构. 针对直接表示方式的缺点, Park等人提出的基于位置的表示方式(locus-based representation)较直接表示方式高效, 可行解的数量也相对减少^[147]. 此外, Liu等人提出的排列表示方式(permutation representation)可应用于重叠社团结构中^[88].

(4)使用图嵌入方法获取图中节点的特征表示时, 通常可以得到节点特征的降维表示, 将输出结果喂入下游学习任务可以大大减少参数量. 文献[148]中提出, 网络表示学习方法从算法的角度可以归纳为5类: 基于矩阵分解的算法, 如HOPE^[149], LANE^[150]; 基于游走启发的算法, 如DeepWalk^[151], node2vec^[152]; 基于连边建模的方法, 如LINE^[153]算法, 直接从顶点与顶点的连边中学习顶点表示; 基于深度学习的算法, 如SDNE^[154], 为了提取复杂结构的特称, 学习高度非线性的定点表示; 最后一种是混合方法, 混合使用上述方法来学习顶点表示, 如HARP^[155]利用了基于随机游走的方法(DeepWalk和node2vec)和基于连边建模的方法(LINE)学习从小样本网络到原始网络的顶点表示.

3 MOEA性能评价指标

通常评价一个多目标进化算法的性能从两个方面: 算法的效果与算法的效率. 算法的效果通过其所求Pareto最优解集的质量进行判断, 主要看算法的收敛性和分布; 算法效率是指其求解多目标优化问题的时间复杂度和空间复杂度. 此外, 多目标优化算法的鲁棒性、泛化能力等也是衡量其性能的重要指标. 同样, 评价MOEA的性能有两类方法: 理论分析和实验分析. 理论分析可以解决算法的运行效率和收敛性; 实验分析可以对算法的性能进行测试和比较. 实践中, 两种方法可以结合使用来评价一个MOEA的性能^[37].

目前, 研究者归纳出来的MOEA性能评价方法或工具主要分为3类: 第1类用于评价所求解集和真正Pareto最优面的趋近程度, 即评价MOEA的收敛性; 第2类用于评价解集的分布性; 第3类综合考虑解集的收敛性和分布性, 作为综合评价指标. 表1为MOEA性能评价指标分类表.

3.1 收敛性评价指标

收敛性评价方法主要通过 $P{F_{{\rm{known}}}}$ (一致的Pareto面)和 $P{F_{{\rm{true}}}}$ (真正的Pareto面)这两个重要参数进行Pareto最优面的趋近度评价.

(1)错误率(error ratio, $ER$ ): 运行一个MOEA后, 得到 $P{F_{{\rm{known}}}}$ , 但可能存在某些解向量不在 $P{F_{{\rm{true}}}}$ 中. 若存在这样的向量, 称这些向量是没有被覆盖的. $ER$ 的定义即为没有被覆盖的解向量与群体规模的比例^[156].

$ \begin{array}{c}ER=\dfrac{{{\displaystyle \sum }}_{i=1}^{n}{e}_{i}}{n} \end{array} $

(37)

其中, $n$ 是 $P{F_{{\rm{known}}}}$ 中向量数目, $P{F_{{\rm{known}}}} = \{ {X_1}, {X_2}, \cdots, {X_n}\}$ , ${e_i}$ 定义如下:

$ \begin{array}{*{20}{r}} {{e_i}}{ = \left\{ {\begin{array}{*{20}{l}} 0,&{{\rm{if}}向量{X_i} \in P{F_{{\rm{true}}}}\left( {i \in \left\{ {1,2,\cdots,n} \right\}} \right)}\\ 1,&{{\rm{otherwise}}} \end{array}} \right.} \end{array} $

(2)覆盖率(coverage, $C$ ): Zitzler提出的两个解集相对覆盖率的比较方法^[157], 用于比较不同解集之间的支配关系, 并非衡量解集与 $P{F_{{\rm{true}}}}$ 之间的关系. 假设 ${P^{\left( 1 \right)}} \subset P{F_{{\rm{known}}}}$ , ${P^{\left( 2 \right)}} \subset P{F_{{\rm{known}}}}$ 为目标空间中的两个解集, 将 $\left( {{P^{\left( 1 \right)}}, {P^{\left( 2 \right)}}} \right)$ 映射到 $\left[ {0, 1} \right]$ 之间, 得到 ${P^{\left( 1 \right)}}$ 和 ${P^{\left( 2 \right)}}$ 之间的覆盖率, 公式如下:

$ \begin{array}{c}C\end{array}({P}^{(1)}, {P}^{(2)})=\frac{\left|\{{a}^{(2)}\in {P}^{(2)}\}|\exists {a}^{(1)}\in {P}^{(1)}, {a}^{(1)}\prec {a}^{(2)}\right|}{\left|{P}^{(2)}\right|} $

(38)

若 ${P^{\left( 1 \right)}}$ 中所有点都支配 ${P^{\left( 2 \right)}}$ 中的点, 此时 $C = 1$ , 相反, $C = 0$ . 由于 ${P^{\left( 1 \right)}} \cap {P^{\left( 2 \right)}} \ne \emptyset $ , 因此, 需要同时考虑 $C\left( {{P^{\left( 1 \right)}}, {P^{\left( 2 \right)}}} \right)$ 和 $C\left( {{P^{\left( 2 \right)}}, {P^{\left( 1 \right)}}} \right)$ .

(3)世代距离(generational distance, $GD$ ): $GD$ 由Van Veldhuizen等人提出, 用于衡量 $P{F_{{\rm{known}}}}$ 偏离 $P{F_{{\rm{true}}}}$ 的程度^[158], 公式定义如下:

$ \begin{array}{c}GD=\dfrac{{\left({{\displaystyle \sum }}_{i=1}^{n}{d}_{i}^{p}\right)}^{\frac{1}{p}}}{n} \end{array} $

(39)

其中, $n$ 为 $P{F_{{\rm{known}}}}$ 中的向量数, $p = 2$ , ${d_i}$ 为目标空间上每一维向量与 $P{F_{{\rm{true}}}}$ 中最近向量之间的欧几里得距离. $GD = 0$ 时, 表示 $P{F_{{\rm{true}}}} = P{F_{{\rm{known}}}}$ .

(4)高维空间及其比率(hyperarea, $HA$ 和hyperarea ratio, $HAR$ ): 由Zitzler等人^[157]提出, Van Veldhuizen等人将其命名的 $HA$ 是指目标空间中被 $P{F_{{\rm{known}}}}$ 所覆盖的空间(即曲线下的空间)^[159]. 其定义如下所示:

$ \begin{array}{*{20}{c}} {HA = \left\{ {\mathop \cup \limits_i {a_i}{\text{|}}{v_i} \in P{F_{{\rm{known}}}}} \right\}} \end{array} $

(40)

其中, ${v_i}$ 为 $P{F_{{\rm{known}}}}$ 中的非支配向量, ${a_i}$ 为原点及 ${v_i}$ 所形成的高维空间. 同时, Van Veldhuizen等人针对目标空间中每一维取值范围不同的问题对高维空间进行了改进, 提出 $HAR$ ^[159], 其定义如下:

$ \begin{array}{c}HAR=\dfrac{{H}_{1}}{{H}_{2}} \end{array} $

(41)

其中, ${H_1}$ 和 ${H_2}$ 分别为 $P{F_{{\rm{known}}}}$ 与 $P{F_{{\rm{true}}}}$ 的高维空间, $HA$ 和 $HAR$ 的取值越小, 表示解集的收敛性越好.

3.2 多样性评价指标

多样性评价指标衡量解集的分布性和延展性. 当解集分布均匀时, 称其具有良好的分布性; 若解集在Pareto前沿分布过于稀疏, 称其具有较差的延展性.

(1)空间评价方法(spacing metric, $\Delta $ ): Deb等人提出的 $\Delta $ 用于评价近似解集中个体在目标空间的分布情况^[160], 公式定义如下:

$ \begin{array}{c}\Delta ={\displaystyle \sum\limits }_{i=1}^{\left|PF\right|}\dfrac{{d}_{i}-\overline{d}}{\left|PF\right|} \end{array} $

(42)

其中, $PF$ 表示Pareto最优面, ${d_i}$ 指解集中非支配边界上两个连续解之间的欧氏距离, $\overline d $ 则为这些距离的平均值. 此前, Schott也提出了一种分布性计算方法^[163], 定义如下:

$ \begin{array}{c}{\Delta }^{\prime }=\sqrt{\dfrac{1}{n-1}{\displaystyle \sum }_{i=1}^{n}{\left(\overline{d}-{d}_{i}\right)}^{2}} \end{array} $

(43)

其中, ${d_i}$ 计算的并非两个解之间的欧氏距离, 而是曼哈顿距离. 式(42)和式(43)均只对分布性进行衡量, 其中, $\Delta $ 更适用于衡量二维目标空间的分布性, $\Delta '$ 则适用于更高维的空间, 但是具有较高的计算复杂度.

(2)分布广度指标(spread indicator, ${\textit{SI}}$ ): ${\textit{SI}}$ 由李密青等人提出^[161], 利用边界解集对非支配集的分布范围进行评价, 对非支配解集中边界解的特点进行分析, 根据边界解技术区别不同边界解对分布范围的影响, 进而利用低维空间超立方体进行分布范围的估计.

3.3 综合评价指标

综合评价指标能同时反应MOEA的收敛性和多样性, 最为广泛应用的综合评价指标为超体积评价指标(hypervolume, $HV$ )和反转世代距离评价指标(inverted generational distance, $IGD$ ).

(1) $HV$ : $HV$ 衡量个体所支配的空间, 通过计算非支配解集与参考点围成空间的超体积的值实现对MOEA的综合性能评价^[45]. 其计算公式为:

$ \begin{array}{*{20}{c}} {HV = \lambda \left( {\mathop {\mathop \cup \limits^{\left| {PF} \right|} }\limits_{i = 1} {v_i}} \right)} \end{array} $

(44)

其中, $\lambda $ 表示勒贝格测度, ${v_i}$ 表示参考点与非支配个体 ${p_i}$ 构成的超体积, $\left| {PF} \right|$ 表示非支配解集. $HV$ 的值越大, 说明算法得到的 $P{F_{{\rm{known}}}}$ 越接近 $P{F_{{\rm{true}}}}$ , 解集的综合性越好.

(2) $IGD$ : 世代距离指MOEA算法求得的非支配解集 $P{F_{{\rm{known}}}}$ 中所有个体到Pareto最优解集 $P{F_{{\rm{true}}}}$ 的平均距离. 而 $IGD$ 则是世代距离的逆向映射, 通过 $P{F_{{\rm{true}}}}$ 中个体到 $P{F_{{\rm{known}}}}$ 的平均距离表示^[162], 其公式如下:

$ \begin{array}{c}IGD=\dfrac{{{\displaystyle \sum }}_{\bar{j}\in PF}{d}_{\bar{j}}{{'}}}{n}\end{array} $

(45)

其中, $d_{\bar j }{{'}}$ 为Pareto前沿上点 $\bar j $ 到最终解集 $\bar i $ 的最小欧几里得距离, $IGD$ 的值越小, 算法性能越好.

4 实验

实验部分由3部分组成: 多目标优化实验、单目标优化与多目标优化对比实验以及部分鲁棒性相关目标的皮尔森相关性实验. 具体内容详述如下.

4.1 多目标优化实验

多目标优化实验在Wang等人提出的SP-RV-MOEA_Net^[119]的基础上完成. 实验将网络在节点度攻击下的连通性鲁棒性( ${R^{{{ndeg}}}}$ )和连边介数攻击下的连通性鲁棒性( ${R^{{{lbet}}}}$ )作为两个优化目标, MOEA/D算法作为进化算法, 对是否加入代理模型以及加入不同数量的代理模型的效果进行对比. 具体实验设计内容如表2所示.

SP-RV-MOEA_Net利用图自编码器(SDNE^[154])获得网络的数值化表示, 通过代理模型对网络的性能进行评价, 获得鲁棒性预测值, 利用3个代理模型(RBF^[164], LS^[165], IDW^[166])提供的不确定信息选择更优的解. MOEA/D₀模型则是仅使用MOEA/D多目标进化算法, 不使用任何代理模型. MOEA/D_RBF, MOEA/D_LS和MOEA/D_IDW则是仅使用一种代理模型. 上述5个模型分别对节点数为200, 平均度为5的SF网络和SW网络进行优化, 最终得到的Pareto前沿如图2所示, $HV$ 值的变化如图3所示, 实验运行时间如表3所示.

结果表明: 在使用代理模型之后, 目标优化过程所需要的运行时间大大缩短, 而且最终得到的非支配解集比不使用代理模型得到的结果更优MOEA/D_RBF, MOEA/D_LS和MOEA/D_IDW虽然仅使用一个代理模型, 不能提供不确定信息, 但是结果表现并不逊色于使用了3个代理模型的SP-RV-MOEA_Net.

4.2 单目标优化与多目标优化对比实验

实验以BA模型构建的SF网络为例, 同样将 ${R^{ndeg}}$ 和 ${R^{lbet}}$ 作为两个优化目标, 在都使用3个代理模型(RBF^[164], LS^[165] , IDW^[166])的条件下, 进行单目标优化和多目标优化的实验对比. 实验参数如表4所示.

分别对 ${R^{ndeg}}$ 和 ${R^{lbet}}$ 进行单目标优化得到的鲁棒性值变化如图4所示.

图5将多目标优化 ${R^{ndeg}}$ 和 ${R^{lbet}}$ 得到的Pareto前沿、原始网络和单目标优化后的网络进行对比, 图中空心五角星点构成Pareto前沿面, 六边形代表原始网络两个目标对应值所在位置, 实心五角星代表单目标优化得到的最优 ${R^{ndeg}}$ 的网络所在位置, 三角形代表单目标优化得到的最优 ${R^{lbet}}$ 的网络所在位置. 实验结果显示, 单目标优化只能给决策者提供一个单一的角度, 并不能考虑到多个目标之间的权衡.

4.3 皮尔森相关性实验

在复杂网络的目标优化的研究中, 文献[130, 131]将优化目标之间的皮尔森相关性为强负相关作为多目标优化的依据. 据此, 本实验分别对以BA模型构建的SF网络、ER网络以及WS模型构建的SW网络进行优化目标之间的皮尔森相关性系数的研究. 选用的优化目标及其符号说明如表5所示, 实验结果如图6所示. 结果显示, 这些优化目标之间并不存在完全的正相关关系, 但是也没有强负相关的关系, 大部分目标间的皮尔森相关性都小于0.4. 然而从单目标优化与多目标优化对比实验结果中, 可以看出多目标优化可以在一对相关性不那么强的目标中找到它们的权衡解. 因此, 于研究人员而言可以对任意一对目标进行多目标优化, 均能得到Pareto前沿, 且能为决策者带来更多选择, 但其是否具有现实意义, 要求研究人员从实际出发, 具体情况具体分析.

5 总结与展望

本文阐述了复杂网络领域的前沿发展以及进化算法在复杂网络优化领域的应用. 具体来说包括复杂网络与进化算法的概述、常用的算法框架及其进展、针对不同任务的单目标优化和多目标优化的应用、多目标算法的性能评价指标. 实验部分则是进一步让读者对进化算法在复杂网络中的应用有更加深入的了解, 3个实验循序渐进, 希望能够对读者带来一定的思考和启发. 本文对进化算法在复杂网络中的应用有以下几点的展望.

(1)应用场景: 目前, 优化算法在复杂网络中已经有了很多的应用, 但是当前研究的方向大多着眼于网络社团检测, 网络合作与传播能力优化和网络结构鲁棒性优化, 并没有拓展到更多具有现实意义的目标中. 因此, 结合现实的复杂系统需求, 寻找更多具有现实意义的网络结构依然有很大的研究空间.

(2)优化目标: 本文中复杂网络优化目标间皮尔森相关性实验探究了以连通性鲁棒性和能控性鲁棒性为主的多种目标之间的数值相关性, 可以发现不同拓扑结构的复杂网络的各目标间都有不同的相关性表现, 使得设计满足不同现实需求. 实验结果中尽管没有强负相关的两个目标, 但是通过多目标优化, 仍能找到Pareto前沿, 这保证了优化工作的可行性.

(3)代理模型: 由于优化过程需要大量计算, 时耗很高, 因此有许多研究通过代理模型来减少大量的计算. 在今后的研究中, 也可以尝试通过深度学习来加速优化过程. 在文献[167]中, Lou等人首次设计了一个卷积神经网络结构(convolutional neural network, CNN), 称为PCR, 以用于复杂网络能控性鲁棒性的计算, 该方法保证了极低计算误差的同时, 将能控性鲁棒性的计算速度提高了近一百倍. 同时文献[167]也验证了深度学习方法论在复杂网络能控性鲁棒性研究中的可行性. 后续Lou等人在实验中发现复杂网络的能控性鲁棒性表现和其拓扑结构相对独立. 但不同的高阶网络模型表现了不同的鲁棒性. 因此提出iPCR^[168], 设计了一个由多个CNN结构组成的鲁棒性预测器, 在PCR的基础上应用更多的网络的先验知识, 进一步提高了鲁棒性预测的精度. 后续, 深度学习方法也被应用到了连通性鲁棒性的预测等方面^[169], 取得了不错的成果. 然而鉴于深度神经网络对输入大小固定的局限, 以上方法难以用于处理具有不同大小的网络. 因此Lou等人改进了Patchy-SAN算法^[170], 提出了LFR-CNN^[171], 通过对关键节点的采样, 邻域构建等步骤对网络建立特征图以进行鲁棒性预测, 在不同输入大小的网络上依然保证了较高的准确度. 基于此, 可以将上述工作作为代理模型来加速优化过程中涉及的大量计算的任务.

在之后的研究中, 不仅可以对优化目标进行扩展以优化现有复杂网络的拓扑结构, 同样可以对启发式进化算法框架进行设计, 也可以使用不同的策略来加速目标的优化过程, 如加入代理模型以降低大量重复的高计算消耗过程, 以及优化前进行图嵌入降低数据处理维度等. 当前进化算法已有了一个比较普遍的框架, 但其中各部分步骤依然存在优化的潜力, 在MOEA系算法中各类优化向我们展示了进化算法的研究空间和领域的活力. 基于多目标进化算法的复杂网络优化问题的研究已经建立起一定的理论基础, 但同时仍有更多的研究方向可供探索.