加权模型的复杂网络的多目标鲁棒性优化.pdf

现有的方法在复杂网络单目标鲁棒性优化中已取得显著成效但在现实生活中，复杂网络结构往往会同时受到多种方式的破坏，因此设计能同时抵抗多种破坏下连通鲁棒性更佳的网络结构具有重要意义多目标复杂网络鲁棒性计算成本非常大，在搜索过程中引入代理模型来评估复杂网络的连通鲁棒性，并对几个代理模型加权评估后的值作为评估值来引导进化算法搜索连通鲁棒性更佳的网络结构进行研究通过种代理模型加权组合（）方法对复杂网络连通鲁棒性进行评估，并与种单一代理模型和种代理模型求平均的评估方法进行比较在种合成复杂网络（、）上的连通鲁棒性进行实验分析，结果验证了加权代理模型评估方法能辅助进化算法得到连通鲁棒性更佳的网络结构关键词：多目标优化；代理模型；复杂网络；连通鲁棒性；进化算法中图分类号：文献标志码：文章编号：（）：复杂网络是近几十年来在网络科学界中的一个热门学科，比如互联网、交通运输网络和人际关系等研究领域常见的网络模型有随机网络（，）、小世界网络（，）、无标度网络（，）和随机三角形网络（，）文献中提到，网络的鲁棒性可以看成是一个优化问题由于网络暴露在外，会受到各种各样的攻击，比如随机攻击、蓄意攻击随机攻击是随机移除某一个节点或者某一条连边；蓄意攻击会针对重要的节点或者连边进行攻击，如介数攻击、度攻击等目前已有成熟的单目标进化算法来优化网络受到节点或者连边攻击下的鲁棒性，但是在现实社会中，网络往往会同时受到节点和连边的攻击由于复杂网络暴露在外，可能会受到自然灾害、故意攻击、机械故障和级联故障等，如年月日，中国一条高压输电线路因下雪断裂，落在另一条线路上而造成大面积停电；网络中一个节点出故障可能会引发大面积故障，甚至整个网络崩溃，如年发生的美国历史上最大的停电事故，拥塞导致的互联网崩溃这些故障都迫使研究人员找到抗击能力更好的网络在文献 中以鲁棒性作为优化目标，使用多目标进化算法增强网络的鲁棒性，以抵御种攻击拓扑重连是增强网络鲁棒性常用的策略，文献 对几种拓扑重连方式进行了比较和分析，证明了在实验过程中对网络进行重连边之后能得到更有效的鲁棒性在优化复杂网络鲁棒性过程中，对网络结构进行重连边之后能得到更多广泛的网络结构，但在重连边的过程中没有改变节点间的度分布情况；增强网络的鲁棒性还应该考虑运行的环境及受到的干扰复杂网络对不确定性、干扰和攻击都具有鲁棒性，也就是说，复杂网络在受到攻击的情况下，网络都能够正常运行，不受外界的干扰，即鲁棒性越好，对应的网络结构抗干扰力也就越强文献 中提到网络系统可能会受到各种破坏性的攻击，因此针对复杂网络的单目标鲁棒性优化算法不能很好地解决实际应用中的问题研究人员同时考虑多种攻击下的鲁棒性，但是不同鲁棒性第期聂君凤，等：加权模型的复杂网络的多目标鲁棒性优化 之间可能会存在冲突后来，大量的研究人员针对多种攻击下得到的鲁棒性进行研究，他们越来越关注同时优化多个鲁棒性来构建网络结构，具有良好抗击能力的网络有利于实际网络系统的设计和优化文献中设计了一个多目标进化算法，同时增强网络对基于节点和连边攻击下的鲁棒性与单目标算法相比，多目标算法具有更显著的特点，每个非支配解都可以看作是个目标之间加权后的结果在文献 中提到用多目标进化算法来优化网络鲁棒性的过程中计算成本太大为了解决计算成本问题，已有研究在优化过程中使用卷积神经网络来评估网络鲁棒性，但需要大量的数据集；也有大量的研究在优化过程中采用代理模型来评估复杂网络鲁棒性代理模型可以是插值函数，也可以是非插值函数，非插值模型常用的有多项式回归和支持向量机，插值模型常用的有径向基函数（，）网络、最小二乘法（，）函数、反距离加权（，）插值函数和克里金插值的函数如何为一个复杂网络选择合适的代理模型来评估复杂网络的鲁棒性，目前仍没有明确的判别准则现在大部分研究是同时选择几种代理模型，然后使用每种代理模型对网络进行评估，再对几个评估值求平均，将其作为该网络的评估值在传统的代理模型组合基础上，本文提出了一种基于加权模型的复杂网络多目标鲁棒性优化（，）方法，使用（）分别给几个代理模型分配权值，并通过不同代理模型评估方法对合成网络多目标鲁棒性的优化结果验证了该方法的有效性多目标鲁棒性优化对于一个网络拓扑图，记录个节点与条边，并保存网络间的邻接矩阵（有连边记为，反之记为）图中给出了网络结构图表示与邻接矩阵之间的关系本文研究攻击网络中节点和连边情况下网络连通鲁棒性值，也就是网络在减少节点或者连边之后，该网络能维持正常运行的能力通过攻击节点后的变化来评估网络的连通鲁棒性，记为（），（）其中，（）是攻击个节点后，网络剩余的最大连通分量的节点数所占剩余节点数的比例在这里对节点采用的攻击方式是度攻击，即每次攻击度数最大的节点 用作标准化因子，使不同规模的网络具有可比性在网络的连通鲁棒性中，值越大表明网络的鲁棒性越好图网络拓扑结构及其对应的邻接矩阵 另一种评估方式是基于连边的攻击，在这种攻击下采用的方式是介数攻击，该攻击方式是集中于攻击全局中的最短路径，网络受到攻击后的鲁棒性记为（），（）其中，（）是攻击条边后，网络剩余的最大连通分量的连边数所占剩余连边数的比例，是标准化因子，与类似，给出了网络对基于连边攻击下的鲁棒性本文将这种情况下得到的鲁棒性问题构建成一个多目标优化问题文献 设计了一种基于启发式的算法，以成功地增强由引导的网络鲁棒性同时，文献提到，单独增强不能保证也随着增强，这种目标存在冲突由于很难同时优化和，所以出现了大量的多目标进化算法来优化网络结构代理模型及评估方法代理模型辅助的进化算法（，）不管是在单目标还是多目标问题上都广泛应用代理模型的选择、参数的确定都是中的关键问题代理模型以较低的计算成本来估计网络的鲁棒性，并使用评估得到的连通鲁棒性来引导优化过程文献 为了解决数据维度高和数据稀疏的问 四川师范大学学报（自然科学版）第卷题，采用了算法来把网络节点映射到低维空间中为了使高维空间的结构数据，降维到低纬度空间，采用图嵌入方法来提升低维空间节点相似性，降低嵌入损失，使得数据易于处理此外，由于异构输入有助于提高模型训练的多样性，在原始数据下采用了多种特征提取技术作为代理模型输入的特征首先采用的是主成分分析（），它可以以较低的计算成本来提取主要信息，把数据降维到一维；还采用了聚类，此方法就是计算样本间的距离，把相近的样本放到一个集合中文献 把原始数据、降维后的数据和聚类后的数据用来训练代理模型在不同特征属性下分别采用、和等种代理模型，然后取种模型下预测结果的平均值 种代理模型的输入数据和训练过程如图所示图代理模型结构 图中是选择的代理模型，是选择模型来进行训练，是选择模型来进行训练，是选择模型来进行训练，表示降维后的一个二维向量，是输入层单元数，是网络中心参数的初始值，是隐含层第个神经元的中心向量，表示宽度向量，影响着输入信息的作用范围，是高斯函数，表示输出向量的预测值，是反距离加权方法中的权值，（）是预测的未知点从给定网络数据，首先计算网络的鲁棒性度量（，），然后利用对网络进行降维，得到网络的二维数据随后，将原始数据和种特征提取技术作为代理模型训练的异构输入下面介绍本文所使用的径向基（）网络、最小二乘法（）函数和反距离加权（）插值函数种代理模型 径向基函数（）网络该网络中的重要部分是隐藏层中采用径向基函数，该函数中的每个插值点都可以构建一个径向距离对称的基函数，并对其进行线性组合利用径向基函数可以很好地模拟真实函数的目标值代理模型定义如下：（），（）其中，表示欧几里得范数，是权值系数，是径向基函数，以输入空间的点与中心之间的欧式距离为该函数的自变量，表示得到的预测值 最小二乘法（）函数依据最小二乘法原则，利用微分学中的极值原理，建立标准方程，求解回归方程的参数它是为了找到一个与给定点（，）的距离平方和最小的曲线（），模型如下：（）（），（）其中，（）是数据中的多组样本，是假设拟合函数，（）也就是在机器学习中常说的损失函数本文的目的就是得到使损失函数最小化拟合函数的模型 反距离加权法（）插值函数通过欧氏距离来判断彼此之间的相似度，距离较近的相似度就较高因此，根据距离预测值来评判权重大小，预测值小反而权重大，预测值大反而权重小一般形式如下：（，），（）第期聂君凤，等：加权模型的复杂网络的多目标鲁棒性优化 其中，为第个待插入数据点的权重，、为第个已知点的值，为已知数据点个数，为已知点对应的权重权重计算方式如（）式所示，权重一般满足（）式（），（），（）其中，是已知点与预测点之间的欧氏距离，权重是距离的倒数的函数 度量指标目前有大量的度量指标来衡量在进化算法中方法是否有效，本文采用超体积（，简称）来计算不同代理模型下的非支配解与原点之间的体积，根据的大小来判断方法是否有效，越大，方法越好 的计算如下：（），（）其中，是测度，用来测量体积，表示非支配解的数目，表示参考点与解集中第个非支配解构成的超体积 方法 代理模型评估方法采用代理模型进行评估的方法一般单独使用一个代理模型，或者同时使用多个代理模型，然后对其结果进行求平均代理模型组合结构如图所示，先用的方法对复杂网络降维，接下来使用、和原始数据作为输入数据来训练代理模型，采用多种输入数据是为了获得更广泛的数据，使训练模型更加准确其中，是网络的个数，是网络结构，是网络节点数图代理模型组合结构 评估方法在采用代理模型进行评估时，如果使用单一的代理模型会因为代理模型的缺陷或者不足影响复杂网络的连通鲁棒性；通过选取多个代理模型的评估结果的平均值，可能会降低对复杂网络鲁棒性评估的准确性因此，本文采用加权的方法给几个代理模型分配不同的权值，该方法弥补了直接对多个代理模型的评估值求平均而导致准确率降低的缺陷本文使用理论来分配权值，它是一种不确定性推理的一般框架，由在统计推断的背景下被引入，具有处理不确定性信息的能力，在先验概率已知的情况下，利用概率论中贝叶斯条件概率来实验然而，理论不需要知道先验概率，就能被用于解决不确定的问题文中通过给不同的代理模型分配不同的权值来评估鲁棒性进行研究，代理模型在理论下的权值计算流程如图所示其中，、是本文所使用的种代理模型，（）、（）和 四川师范大学学报（自然科学版）第卷（）分别是评估值与真实值的相关系数、均方根误差和最大绝对值误差，是权值每种复杂网络分别训练种代理模型，然后通过计算评估值与真实值之间的性能得到个权值图 下的权值计算流程 根据表中的权值计算流程，用评估得到的复杂网络鲁棒性值与真实值之间的特征属性来求出每个代理模型的权重本文为了研究种加权平均的方法与单个使用、种组合求平均的效果，选用了、和网络，每种网络分别训练种代理模型，再对复杂网络进行评估用评估值与真实值之间的相关系数、均方根误差和最大绝对值误差作为个性能指标，然后使用理论的计算方式表 理论的权值计算流程 种代理模型权值的计算输入 代理模型的个数；输入种群规模；输出 每个代理模型的权值；随机初始化复杂网络，迭代器；计算这些初始化网络的真实连通鲁棒性；（）；使用种群来训练代理模型；用预测的复杂网络结构在已经训练完成的代理模型上预测该网络的连通鲁棒性；计算真实值与预测值之间的相关系数，根均方误差和最大绝对值误差；在中已经计算了几个特征属性值，在这几个特征属性值下使用理论来计算出权值；输出权值来计算每个代理模型的权值通过使用上面提及的理论来分别对、和等种代理模型赋予不同的权值，权值的计算过程如图所示，最后复杂网络的评估值是对这个代理模型加权求平均后的结果 种网络在不同代理模型的权值分配如表所示，每种网络的个权值和为图给出了加权评估复杂网络鲁棒性的结构图，图与图的区别在于是否使用了理论为每个代理模型进行加权操作，这也是本文所提出的评估分析方法表 种网络在种代理模型上的权值分配 代理模型 先用的方法对复杂网络降维，然后使用、和原始数据作为输入数据来训练代理模型，此操作是为了获得更广泛的数据，使得训练的模型更加准确对代理模型训练完成之后，用网络结构作为数据集进行评估，然后用理论计算种代理模型下得到的评估值与真实值之间的相关系数、均方根误差和最大绝对值误差作为特征属性值，然后用理论计算权值在使用多目标进化算法过程中将图中的、分别对应第期聂君凤，等：加权模型的复杂网络的多目标鲁棒性优化、进行加权操作在本文所使用的中通过理论得到权值，然后在评估时给代理模型分配权值进行评估，评估的公式如下：（）（）（）（），（）其中，、分别代表、等个代理模型，、是使用理论后的权值图 结构 实验结果分析 实验设置本文在种合成网络上进行实验，分别为随机网络（）、无标度网络（）、小世界网络（）和随机三角形网络（）网络节点数为，平均度为，也就是连边数为 此外，在多目标进化算法中交叉率为，变异率为，代理模型更新率为，种群大小为，迭代次数为 实验结果分析在使用同一种多目标进化算法框架下，单独采用代理模型、和进行实验文献 中使用同时训练种代理模型求平均（）；本文构造一种同时训练种代理模型加权求平均的方法与上述种方法得到的复杂网络非支配解以及值进行比较从图（）中可以看出，在单独使用代理模型的情况下，在优化过程中单独采用代理模型能得到更优的复杂网络的非支配解，而的非支配解不如单独使用代理模型下得到的非支配解，但是这些非支配解与的非支配解相比，后者得到的非支配解更理想从图（）中可以看出，在单独采用种代理模型下得到的非支配解中，优化过程中采用代理模型得到的非支配解更优但是下得到的非支配解与下得到的非支配解及方法下得到的非支配解相比，下的复杂网络非支配解的效果不理想，也可以看到的非支配解与的非支配解差距不明显，但是可以明显地看出方法下的这条线的非支配解更优在图（）中，方法下得到的非支配解和单独使用、的非支配解相吻合还可以看出，前期的非支配解与的非支配解更接近，后期与代理模型得到的非支配解更接近，由此说明的方法能得到更广泛准确的非支配解，但是在搜索过程中引入加权评估后能明显地看出非支配解结果更优从图（）中看出，单独使用代理模型的效果相当不理想而、和下的非支配解很接近，有段区间内几乎不能区分这几种结果，但是可以很明显地看出使用方法的非支配解始终比其他几种非支配解更优，说明此方法有效从种不同网络结构上得到的非支配解可以看出，在优化过程中使用代理模型加权评估能辅助进化算法搜索到连通鲁棒性更优的复杂网络 四川师范大学学报（自然科学版）第卷 图 种网络在单一代理模型、和下的非支配解 ，从复杂网络的非支配解中也不能完全凭借肉眼看出结果，下面给出了用来评估该方法的性能，该方法是计算所获得的非支配解集与参考点围成的目标空间中区域的体积，值越大表明方法性能越好图给出了不同复杂网络结构下种情况的值在各代理模型中的变化，分别是单独使用、代理模型下得到的值，种代理模型结合求平均得到的值（）和种代理模型结合加权求平均得到的值（）从图（）中可以看到，几个方法下的值都在不停上升，证明这些方法对优化复杂网络连通鲁棒性都有效果虽然加权的曲线的效果一开始增长得不是那么明显，但是在后期搜索过程中，优化效果明显提升从图（）中可以看出，单独使用代理模型时，得到的曲线更突出；但是曲线和曲线相比可以看出后者的曲线效果并不好，反而得到的曲线效果更加突出从图（）中可以看出，使用后的曲线前期搜索效果更快，很快就能找到最优解，在后期阶段，增长趋势很平缓，不像其他几个模型的波动情况大，证明在使用加权后能更快地搜索复杂网络连通鲁棒性从图（）中可以看出，使用后的结果相比其他几条曲线来说，效果不理想，虽然值在增加，但增加得不明显剩下条曲线从图中看出很是接近，可以看出使用方法下的值在、和曲线的上边，其优化效果更佳从个复杂网络的不同方法下得到的值都能表明在多目标优化算法中，使用代理模型加权评估方法得到的值效果更好第期聂君凤，等：加权模型的复杂网络的多目标鲁棒性优化 图 种复杂网络在单一代理模型、和下的比较 ，表给出了种复杂网络在单独采用代理模型下的优化时间，以及和的优化时间，同时也给出了在不同情况下的平均值，其中最优的值和耗时最少的加粗表示在网络中，用时最短的是代理模型，方法的耗时多一点；的耗时与相差甚小表中的平均值能反映出模型的大致变化情况，并不起决定性作用，因为有些模型在前期表现得并不是很理想，但是后期的搜索结果会超过其他几个方法，这样也会影响平均值，但是在优化网络结构中，使用加权下的平均值比其他几个结果好在网络中，用时最少的是模型的优化时间，用时最多的是加权后运行的时间，从表中可以清楚地看出单独使用一个代理模型的时间确实更短，加权操作的过程中要花费一定的时间计算理论下的权值分配，但是使用加权的方法并没比个结合求平均的方法耗时太多，反而得到的连通鲁棒性是所有方法中最好的表 种网络在不同方法上的运行时间和平均值 网络方法运行时间 值 四川师范大学学报（自然科学版）第卷 在网络中，运行时间较短的是在优化过程中采用代理模型，其次是采用，然后是采用；同样的优化时间和的时间普遍耗费更多，因为连续训练种代理模型耗时较多在网络中平均值更大的依旧是的方法在网络中，其实从这个复杂网络优化后的非支配解和值都可以看出，除了使用方法的效果不是特别理想之外，剩下几个方法的值差距特别小从运行时间看，的运行时间是其他几种方法的倍左右但是从一系列的实验依旧可以得出在网络下，方法同样有效 从表中可以看出，不同复杂网络结构所耗时不同，不同的方法耗时也不相同，而且所消耗的运行时间在可接受的范围内，与所耗时间差不多，但方法下的效果更佳前面所有的实验分析都可以证明加权下的代理模型得到的优化结果更好，也说明本文所采用的方法是可行的，其中加粗数据代表是较优的通过的方法与采用单一代理模型和方法的对比实验结果可以表明，在多目标进化算法评估过程中，对多个代理模型进行加权操作后的结果更加理想，从图中可以看出所有的非支配解中都是值在变大，值在变小，原因就是在多目标优化问题中，目标之间存在冲突关系在图中把在下的每种网络结构的非支配解分离出来单独展示，可以明确地看出、之间的变化情况 表示值，表示值图 种网络中和值的变化情况 结束语本文为了得到能同时抵抗节点度攻击和连边介数攻击下连通鲁棒性更佳的网络结构由于复杂网络多目标鲁棒性优化计算成本非常大，因此，本文在优化过程中采用代理模型来降低优化时间通过用加权代理模型的方法评估复杂网络连通鲁棒性与种单一代理模型评估方法，以及使用种代理模型组合平均的评估方法进行比较从每种方法下得到优化后的非支配解与的大小都可以表第期聂君凤，等：加权模型的复杂网络的多目标鲁棒性优化 明本文采用的方法更优，且所耗时间近似于采用种代理模型组合平均评估方法的时间通过本文的实验表明，在优化过程中使用理论为不同的复杂网络选择合适的代理模型评估方法可以得到连通鲁棒性更佳的网络结构参考文献 ，：，（）：，（）：，（）：，（）：，：，（）：，（）：，（）：，（）：，（）：，（）：，（）：，：，（）：，（）：，：，（）：，（）：，：，（）：，（）：，（）：，：，（）：（）：，：，?，（）：四川师范大学学报（自然科学版）第卷楼洋，李均利，李升，等复杂网络能控性鲁棒性研究进展自动化学报，（）：，（）：，（）：，（）：杨旭华，熊帅利用网络表征学习辨识复杂网络节点影响力小型微型计算机系统，（）：，：，：陈，杨媛媛基于聚类的代理模型构建策略计算机工程与设计，（）：，（）：，（，）：，（），（，）：；（编辑陶志宁）