第13卷第5期 智能系统学报 Vol.13 No.5 2018年10月 CAAI Transactions on Intelligent Systems Oct.2018 D0:10.11992/tis.201706054 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.tp.20180423.1019.006.html WSB-EA进化算法的符号网络弱结构平衡分析 常新功，赵雅娟 (山西财经大学信息管理学院，山西太原030006) 摘要：由于大多数真实符号网络更满足弱结构平衡理论，并且求解符号网络的弱结构平衡问题是P难问 题，因此提出了基于进化算法的符号网络弱结构平衡计算方法一一WSB-EA算法。该方法将弱结构平衡定理 的能量函数作为适应值函数，首先利用启发式的方法初始化种群，经过锦标赛选择、单路交叉、单点变异、局部 搜索4个阶段，迭代有限次之后得到最优解。在此算法中，提出了大型符号网络的存储方法和增量计算方式。 通过大量实验，NSB-EA算法得出了4个小型符号网络和2个大型符号网络的弱不平衡度。并且与其他算法 相比，WSB-EA算法能更快收敛得到最优解，具有较高鲁棒性。 关键词：符号网络；进化算法；NP难问题；结构平衡理论；弱结构平衡理论；单路交叉；局部搜索；弱不平衡度 中图分类号：TP301.6文献标志码：A 文章编号：1673-4785(2018)05-0783-08 中文引用格式：常新功，赵雅娟.WSB-EA进化算法的符号网络弱结构平衡分析J.智能系统学报，2018,13(5)：783-790. 英文引用格式：CHANG Xingong,ZHAO Yajuan.Weak structure balance analysis of signed network based on WSB-EA evolution- ary algorithmJ.CAAI transactions on intelligent systems,2018,13(5):783-790. Weak structure balance analysis of signed network based on WSB-EA evolutionary algorithm CHANG Xingong,ZHAO Yajuan (Faculty of Information Management,Shanxi University of Finance and Economics,Taiyuan 030006,China) Abstract:The weak structural balance (WSB)theory is suitable to solve the weak structure balance problem of most signed networks,and it is an NP-hard problem.Here a WSB evolutionary algorithm(WSB-EA)is proposed,which com- putes the global unbalanced degree of signed network based on evolutionary algorithm.In this method,the energy func- tion of WSB theory is used as the fitness function.First,a heuristic method is used to initialize the population.After the tournament selection,single crossing,single point variation,and local search,the optimal solution is obtained after a fi- nite number of iterations.The algorithm involves a storage of large signed network and incremental calculation. Through several experiments,the weak unbalanced degree of four small signed networks and two large signed networks are derived from WSB-EA algorithm.Compared with other algorithms,the WSB-EA algorithm can converge to the op- timal solution faster and has a higher robustness. Keywords:signed network;evolutionary algorithm;NP-hard problem;structural balance theory;weak structural bal- ance theory;single cross;local search;weak unbalanced degree 符号网络是指具有正边或负边的网络，其络抽象为符号网络。例如，国际关系网中合作 中正边表示积极的、正面的意义，负边表示消极和敌对的关系、社交网络中朋友和敌人关系、生 的、负面的意义。在现实生活中，可以将很多网 物网络中促进和抑制作用等。1946年Heider 收稿日期：2017-06-14.网络出版日期：2018-04-24. 提出三角形关系中正关系与负关系的相互作用模 基金项目：山西省哲学社会科学“十二五“规划2015年度课题 项目；山西省自然科学基金项目(2013011016-4). 式，将符号网络带人大家的视线。随着符号网络 通信作者：赵雅娟.E-mail:707238065@qq.com. 的兴起，网络的全局平衡性引起众多学者的关
DOI: 10.11992/tis.201706054 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.tp.20180423.1019.006.html WSB-EA 进化算法的符号网络弱结构平衡分析 常新功，赵雅娟 （山西财经大学 信息管理学院，山西 太原 030006） 摘 要：由于大多数真实符号网络更满足弱结构平衡理论，并且求解符号网络的弱结构平衡问题是 NP 难问 题，因此提出了基于进化算法的符号网络弱结构平衡计算方法——WSB-EA 算法。该方法将弱结构平衡定理 的能量函数作为适应值函数，首先利用启发式的方法初始化种群，经过锦标赛选择、单路交叉、单点变异、局部 搜索 4 个阶段，迭代有限次之后得到最优解。在此算法中，提出了大型符号网络的存储方法和增量计算方式。 通过大量实验，WSB-EA 算法得出了 4 个小型符号网络和 2 个大型符号网络的弱不平衡度。并且与其他算法 相比，WSB-EA 算法能更快收敛得到最优解，具有较高鲁棒性。 关键词：符号网络；进化算法；NP 难问题；结构平衡理论；弱结构平衡理论；单路交叉；局部搜索；弱不平衡度 中图分类号：TP301.6 文献标志码：A 文章编号：1673−4785(2018)05−0783−08 中文引用格式：常新功, 赵雅娟. WSB-EA 进化算法的符号网络弱结构平衡分析[J]. 智能系统学报, 2018, 13(5): 783–790. 英文引用格式：CHANG Xingong, ZHAO Yajuan. Weak structure balance analysis of signed network based on WSB-EA evolutionary algorithm[J]. CAAI transactions on intelligent systems, 2018, 13(5): 783–790. Weak structure balance analysis of signed network based on WSB-EA evolutionary algorithm CHANG Xingong，ZHAO Yajuan (Faculty of Information Management, Shanxi University of Finance and Economics, Taiyuan 030006, China) Abstract: The weak structural balance (WSB) theory is suitable to solve the weak structure balance problem of most signed networks, and it is an NP-hard problem. Here a WSB evolutionary algorithm (WSB-EA) is proposed, which computes the global unbalanced degree of signed network based on evolutionary algorithm. In this method, the energy function of WSB theory is used as the fitness function. First, a heuristic method is used to initialize the population. After the tournament selection, single crossing, single point variation, and local search, the optimal solution is obtained after a finite number of iterations. The algorithm involves a storage of large signed network and incremental calculation. Through several experiments, the weak unbalanced degree of four small signed networks and two large signed networks are derived from WSB-EA algorithm. Compared with other algorithms, the WSB-EA algorithm can converge to the optimal solution faster and has a higher robustness. Keywords: signed network; evolutionary algorithm; NP-hard problem; structural balance theory; weak structural balance theory; single cross; local search; weak unbalanced degree 符号网络[1-2]是指具有正边或负边的网络，其 中正边表示积极的、正面的意义，负边表示消极 的、负面的意义。在现实生活中，可以将很多网 络抽象为符号网络。例如，国际关系网[3]中合作 和敌对的关系、社交网络[4]中朋友和敌人关系、生 物网络[5]中促进和抑制作用等。1946 年 Heider[6] 提出三角形关系中正关系与负关系的相互作用模 式，将符号网络带入大家的视线。随着符号网络 的兴起，网络的全局平衡性引起众多学者的关 收稿日期：2017−06−14. 网络出版日期：2018−04−24. 基金项目：山西省哲学社会科学“十二五”规划 2015 年度课题 项目；山西省自然科学基金项目 (2013011016-4). 通信作者：赵雅娟. E-mail：707238065@qq.com. 第 13 卷第 5 期 智 能 系 统 学 报 Vol.13 No.5 2018 年 10 月 CAAI Transactions on Intelligent Systems Oct. 2018
·784· 智能系统学报 第13卷 注。根据计算得到的全局平衡性可以有效地进行 为是平衡结构。因此产生了一个新的概念，K平 个性化推荐、态度预测等。一般全局平衡性用不 衡网络。这一理论认为，一个符号网络是弱平衡 平衡度来衡量，不平衡度是指一个网络从不平衡 的，当且仅当可以将这一网络中的节点分为k个 到平衡的距离，若将这些引起不平衡的边的符号 子集，子集内部都是正边，子集之间都是负边。 取反，网络就变为平衡网络。然而对于大多数符 结构平衡定理是弱结构平衡定理中k为2的特殊 号网络而言，结构平衡定理太过严苛。Leskovec等☑ 情况。K平衡网络的结构如图2所示，图中集合 也证实了弱结构平衡定理更适合真实网络。因此 内部连边都是正边，集合之间连边都是负边。 本文从弱结构平衡定理出发，来研究网络的弱不 平衡性。孙一翔提出Meme-SB算法，将结构平 衡定理的能量函数作为适应值函数，利用混合遗 传算法求得真实符号网络的不平衡度。在Meme- SB算法基础上，本文提出了WSB-EA算法，将研 (a)三边为正b)一边为正(c)两边为正(d三边为负 究范围扩展到符号网络的弱不平衡性。即将弱结 图1符号网络中4种三角形结构川 构平衡定理的能量函数当作适应值函数，利用进 Fig.1 Four triangle signed network structures 化算法原理，初始化种群，选择、交叉、变异，最终 得到网络的弱不平衡度。4个小型数据集的实验 集合 表明，WSB-EA算法比其他算法能够更快收敛得 到最优解。在实验最后部分计算得到两大符号网 络Epinions和Slashdot的弱不平衡度。 集合 集合 背景知识 -1 从20世纪40年代，Heider提出三角形关系 中正关系与负关系的相互作用模式，到Cartwright 集合 集合 等用图论语言描述这一理论将其推广到整个网 -1 络。越来越多的研究者对符号网络的结构和演化 图2弱结构平衡网络 问题感兴趣，致力于研究社会群体的派系结构和 Fig.2 Weak balance network structure 发展过程。然而，有很大一部分真实网络并不符 1.2 弱结构平衡定理能量函数 合Heider提出的结构平衡理论，由此Davis放宽 根据弱结构平衡定理，计算符号网络的弱不 结构平衡理论的约束条件，提出弱结构平衡理论。 平衡度就是寻找一种集合划分，使得集合内部之 1.1弱结构平衡定理 间的负边数和集合外部之间的正边数最少。例 符号网络用数学符号G(V,E)表示，V表示网 如，节点1和节点2之间的连边为正，如果将这两 络节点集合，E表示网络边的集合。其中任意一 个节点分到同一个集合，这两个节点就没有对弱 条边J∈E,其符号为“+”或“-”。“+”代表节点 不平衡度做出“贡献”，如果把它们分到不同的集 i与节点j之间的边是积极关系，“-”则代表消极 合，就需要计算这两个节点对弱不平衡度做的“贡 关系。Heider指出如果网络中任意一个三角形的 献”。同理，两个节点之间的边是负边时，将其分 符号乘积为正，则网络是平衡的。如图1所示， 到同一集合，也要计算这一部分的“贡献”。因此 (a)和(b)是平衡三角，(c)和(d)是不平衡三角。 计算弱不平衡度就是遍历整个符号网络，找到所 在此基础上Cartwright和Harary等提出判断符号 有对弱不平衡度做出“贡献”的节点对。由此提出 网络是否平衡的一个充要条件一一“如果一个网 弱结构平衡定理的能量函数： 络中的节点能够被分割为两个子集，每个子集内 h(s)=∑（1-n6(s,s》/2 (1) 的所有边均是正边，子集间的边均为负边，这样 的网络就是平衡的。” 在弱结构平衡定理中，一个无向符号网络被 然而对于大多数符号网络而言，结构平衡定 分为k个子集。因此，网络中每个节点都有一个 理的要求太过严苛。之后Davis放宽结构平衡理 所属的子集编号，在式中用5，来表示这一编号。 论的约束条件，提出了弱结构平衡理论。这一理 (s,S)的计算结果由S,和s决定，如果s,和s的 论将图1()三条边都是负号这样的三角结构也认 值相同则计算结果为+1，否则为-1
注。根据计算得到的全局平衡性可以有效地进行 个性化推荐、态度预测等。一般全局平衡性用不 平衡度来衡量，不平衡度是指一个网络从不平衡 到平衡的距离，若将这些引起不平衡的边的符号 取反，网络就变为平衡网络。然而对于大多数符 号网络而言，结构平衡定理太过严苛。Leskovec 等 [7] 也证实了弱结构平衡定理更适合真实网络。因此 本文从弱结构平衡定理出发，来研究网络的弱不 平衡性。孙一翔[8]提出 Meme-SB 算法，将结构平 衡定理的能量函数作为适应值函数，利用混合遗 传算法求得真实符号网络的不平衡度。在 MemeSB 算法基础上，本文提出了 WSB-EA 算法，将研 究范围扩展到符号网络的弱不平衡性。即将弱结 构平衡定理的能量函数当作适应值函数，利用进 化算法原理，初始化种群，选择、交叉、变异，最终 得到网络的弱不平衡度。4 个小型数据集的实验 表明，WSB-EA 算法比其他算法能够更快收敛得 到最优解。在实验最后部分计算得到两大符号网 络 Epinions 和 Slashdot 的弱不平衡度。 1 背景知识 从 20 世纪 40 年代，Heider 提出三角形关系 中正关系与负关系的相互作用模式，到 Cartwright 等 [9]用图论语言描述这一理论将其推广到整个网 络。越来越多的研究者对符号网络的结构和演化 问题感兴趣，致力于研究社会群体的派系结构和 发展过程。然而，有很大一部分真实网络并不符 合 Heider 提出的结构平衡理论，由此 Davis[10]放宽 结构平衡理论的约束条件，提出弱结构平衡理论。 1.1 弱结构平衡定理 Ji j ∈ E 符号网络用数学符号 G(V, E) 表示，V 表示网 络节点集合，E 表示网络边的集合。其中任意一 条边 ，其符号为“+”或“–”。“+”代表节点 i 与节点 j 之间的边是积极关系，“–”则代表消极 关系。Heider 指出如果网络中任意一个三角形的 符号乘积为正，则网络是平衡的。如图 1 所示， (a) 和 (b) 是平衡三角，(c) 和 (d) 是不平衡三角。 在此基础上 Cartwright 和 Harary 等提出判断符号 网络是否平衡的一个充要条件——“如果一个网 络中的节点能够被分割为两个子集，每个子集内 的所有边均是正边，子集间的边均为负边，这样 的网络就是平衡的。” 然而对于大多数符号网络而言，结构平衡定 理的要求太过严苛。之后 Davis 放宽结构平衡理 论的约束条件，提出了弱结构平衡理论。这一理 论将图 1(d) 三条边都是负号这样的三角结构也认 为是平衡结构。因此产生了一个新的概念，K-平 衡网络。这一理论认为，一个符号网络是弱平衡 的，当且仅当可以将这一网络中的节点分为 k 个 子集，子集内部都是正边，子集之间都是负边。 结构平衡定理是弱结构平衡定理中 k 为 2 的特殊 情况。K-平衡网络的结构如图 2 所示，图中集合 内部连边都是正边，集合之间连边都是负边。 B A C + + + (a) 三边为正 B A C + − − (b) 一边为正 B A C − + + (c) 两边为正 B A C − − − (d) 三边为负 图 1 符号网络中 4 种三角形结构[1] Fig. 1 Four triangle signed network structures[1] 集合 1 集合 3 集合 4 集合 5 集合 2 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 图 2 弱结构平衡网络 Fig. 2 Weak balance network structure 1.2 弱结构平衡定理能量函数 根据弱结构平衡定理，计算符号网络的弱不 平衡度就是寻找一种集合划分，使得集合内部之 间的负边数和集合外部之间的正边数最少。例 如，节点 1 和节点 2 之间的连边为正，如果将这两 个节点分到同一个集合，这两个节点就没有对弱 不平衡度做出“贡献”，如果把它们分到不同的集 合，就需要计算这两个节点对弱不平衡度做的“贡 献”。同理，两个节点之间的边是负边时，将其分 到同一集合，也要计算这一部分的“贡献”。因此 计算弱不平衡度就是遍历整个符号网络，找到所 有对弱不平衡度做出“贡献”的节点对。由此提出 弱结构平衡定理的能量函数： h(s) = ∑ i j ( 1− Ji jδ ( si ,sj ))/2 (1) 在弱结构平衡定理中，一个无向符号网络被 分为 k 个子集。因此，网络中每个节点都有一个 所属的子集编号，在式中用 si 来表示这一编号。 δ(si , sj ) 的计算结果由 si 和 sj 决定，如果 si 和 sj 的 值相同则计算结果为+1，否则为–1。 ·784· 智 能 系 统 学 报 第 13 卷
第5期 常新功，等：WSB-EA进化算法的符号网络弱结构平衡分析 ·785· 由此，求解符号网络的弱结构平衡问题就转 每条染色体，但这样的初始化方式效率不高。如 变为最小化能量函数的优化问题。能量函数的最 果初始化的染色体对应的适应值很低，要经过很 小值代表了导致符号网络弱不平衡的最少边的数 多次迭代才能得到最优解，收敛速度太慢。因此 目。若将这些边的符号取反，可以将此网络转变 本文使用一种简单的启发式方法，保证在初始化 为弱结构平衡网络。如果能量函数值为0，说明 时每一个节点与它的邻居节点对能量函数没有 此网络已是弱结构平衡网络。 “贡献”。即在初始化之后，随机选择一个节点 1.3进化算法 如果此节点与它的邻居节点对能量函数没有“贡 进化算法-2或称演化算法(evolutionary al-. 献”，则不改变这一节点的取值，否则将其改为它 gorithms,.EAS),是一个算法簇，它们产生的灵感 的正邻居节点所属的子集编号。这样的操作重 都来自于大自然的生物进化，但它有很多的变化， 复n次，并且保证每次选择的节点是之前没有选 有不同的遗传基因表达方式，不同的交叉和变异 择过的。 算子，特殊算子的引用，以及不同的再生和选择 2.4遗传操作 方法。与传统的基于微积分的方法和穷举法等优 本文的遗传操作过程如算法2所示。遗传过 化算法相比，进化计算是一种成熟的具有高鲁棒 程分为3步：首先将上一代种群中的优秀个体保 性和广泛适用性的全局优化方法，具有自组织、 存到新一代种群中，这个过程称为精英保留：接 自适应、自学习的特性，能够不受问题性质的限制， 下来利用锦标赛方式选取父代染色体，经过单路 有效地处理传统优化算法难以解决的复杂问题。 交叉：单点变异得到新一代种群。 2WSB-EA算法描述 算法2 evolvePopulation(individual)算法 输入原始种群Pop,最优个体individual,.锦 2.1WSB-EA算法主要流程 标赛规模tournamentSize,交叉概率uniformRate, 根据问题定义以及进化算法原理，本文将弱 变异概率mutationRate; 结构平衡定理的能量函数作为目标函数，在Meme 输出新一代种群newPopo SB算法的基础上，初始化种群，经过选择、交叉 1)newPop.saveIndividua(0,individual):// 变异得到最优解。具体框架如算法1所示。 保留 算法1WSB-EA算法 2)for(0;j<Pop.size();j+) 输入邻接矩阵J,种群规模P,迭代次数M 3)indivl=tournamentSelection(Pop,/选择父 输出最优解的适应值，即网络弱不平衡度。 本1 1)putO,存储邻接矩阵 4)indiv2 tournamentSelection(Pop); 2)Pop-Population(P,true,/初始化种群 S)newlndiv=crossover(indivI,indiv2,∥交叉算法 3)=0; 6)newPop.saveIndividua(j,newIndiv); 4)repeat 7)for(j=0;j<Pop.size();j++) S)individual=Pop.getFittest(),/计算得到 8)mutate(newPop.getIndividual(),/变异算法 种群最优个体 2.4.1选择操作 6)Pop+-evolvePopulation(Pop,individual):// 在进化算法中轮盘赌是最常用也是最简单的 群进化，选择、交叉、变异操作 选择算子。但对于本文而言，轮盘赌不利于保持 7)a=a+1: 种群多样性。为了解决这一问题，本文选用锦标 8)until a=M达到最大进化次数时停止 赛方法选取优秀个体进行繁衍。首先确定锦标赛 2.2编码 规模1，随机从种群中选择出1个个体，计算这些 本文使用的编码方式是整数编码。种群中 个体的适应值，将适应值最小的个体作为父代进 的染色体由X={x,2x,…,x,…,x}表示，其中 行繁衍。 n为符号网络的节点个数，x表示第i个节点所属 2.4.2交叉操作 的子集编号。假设符号网络中有k个子集，则x的 般在进化算法中经常使用的两点交叉算子 取值范围是0~k-1。例如第j个染色体可以表示 很有可能会破坏父代染色体中优秀的基因结构， 成X=1,2,0,…,k-1,…,1,010 因此为了保存父代染色体中的优秀基因结构，本 2.3初始化 文选择单路交叉方式作为交叉算子。首先通过 一般进化算法中的初始化方法都是随机产生 锦标赛选择算法选择两个优秀父代A、B。随机产
由此，求解符号网络的弱结构平衡问题就转 变为最小化能量函数的优化问题。能量函数的最 小值代表了导致符号网络弱不平衡的最少边的数 目。若将这些边的符号取反，可以将此网络转变 为弱结构平衡网络。如果能量函数值为 0，说明 此网络已是弱结构平衡网络。 1.3 进化算法 进化算法[11-12]或称演化算法 (evolutionary algorithms, EAS)，是一个算法簇，它们产生的灵感 都来自于大自然的生物进化，但它有很多的变化， 有不同的遗传基因表达方式，不同的交叉和变异 算子，特殊算子的引用，以及不同的再生和选择 方法。与传统的基于微积分的方法和穷举法等优 化算法相比，进化计算是一种成熟的具有高鲁棒 性和广泛适用性的全局优化方法，具有自组织、 自适应、自学习的特性，能够不受问题性质的限制， 有效地处理传统优化算法难以解决的复杂问题。 2 WSB-EA 算法描述 2.1 WSB-EA 算法主要流程 根据问题定义以及进化算法原理，本文将弱 结构平衡定理的能量函数作为目标函数，在 MemeSB 算法的基础上，初始化种群，经过选择、交叉、 变异得到最优解。具体框架如算法 1 所示。 算法 1 WSB-EA 算法 输入 邻接矩阵 J，种群规模 P，迭代次数 M； 输出 最优解的适应值，即网络弱不平衡度。 1) putJ (); //存储邻接矩阵 2) Pop←Population(P, true); //初始化种群 3) a=0; 4) repeat 5) individual = Pop.getFittest();//计算得到 种群最优个体 6) Pop←evolvePopulation(Pop, individual); //种 群进化，选择、交叉、变异操作 7) a=a+1; 8) until a=M //达到最大进化次数时停止 2.2 编码 Xj = {x1, x2, x3,··· , xi ,··· , xn} xi xi Xj = {1,2,0,··· , k−1,··· ,1,0} 本文使用的编码方式是整数编码[13]。种群中 的染色体由 表示，其 中 n 为符号网络的节点个数， 表示第 i 个节点所属 的子集编号。假设符号网络中有 k 个子集，则 的 取值范围是 0 ~ k–1。例如第 j 个染色体可以表示 成 。 2.3 初始化 一般进化算法中的初始化方法都是随机产生 每条染色体，但这样的初始化方式效率不高。如 果初始化的染色体对应的适应值很低，要经过很 多次迭代才能得到最优解，收敛速度太慢。因此 本文使用一种简单的启发式方法，保证在初始化 时每一个节点与它的邻居节点对能量函数没有 “贡献”。即在初始化之后，随机选择一个节点， 如果此节点与它的邻居节点对能量函数没有“贡 献”，则不改变这一节点的取值，否则将其改为它 的正邻居节点所属的子集编号。这样的操作重 复 n 次，并且保证每次选择的节点是之前没有选 择过的。 2.4 遗传操作 本文的遗传操作过程如算法 2 所示。遗传过 程分为 3 步：首先将上一代种群中的优秀个体保 存到新一代种群中，这个过程称为精英保留；接 下来利用锦标赛方式选取父代染色体，经过单路 交叉；单点变异得到新一代种群。 算法 2 evolvePopulation (individual) 算法 输入 原始种群 Pop，最优个体 individual，锦 标赛规模 tournamentSize，交叉概率 uniformRate， 变异概率 mutationRate； 输出 新一代种群 newPop。 1) newPop.saveIndividua(0, individual); //精英 保留 2) for( j=0; j< Pop.size(); j++) 3) indiv1 =tournamentSelection(Pop); //选择父 本 1 4) indiv2 = tournamentSelection(Pop); 5) newIndiv=crossover(indiv1, indiv2); //交叉算法 6) newPop.saveIndividua ( j, newIndiv); 7) for( j=0; j< Pop.size(); j++) 8) mutate(newPop.getIndividual( j)); //变异算法 2.4.1 选择操作 在进化算法中轮盘赌是最常用也是最简单的 选择算子。但对于本文而言，轮盘赌不利于保持 种群多样性。为了解决这一问题，本文选用锦标 赛方法选取优秀个体进行繁衍。首先确定锦标赛 规模 t，随机从种群中选择出 t 个个体，计算这些 个体的适应值，将适应值最小的个体作为父代进 行繁衍。 2.4.2 交叉操作 一般在进化算法中经常使用的两点交叉算子 很有可能会破坏父代染色体中优秀的基因结构， 因此为了保存父代染色体中的优秀基因结构，本 文选择单路交叉方式[14]作为交叉算子。首先通过 锦标赛选择算法选择两个优秀父代 A、B。随机产 第 5 期 常新功，等：WSB-EA 进化算法的符号网络弱结构平衡分析 ·785·
·786· 智能系统学报 第13卷 生一个0~k-1的整数m,记录A中所有m所在的 之后都需重新计算一次适应值，这样重复操作使 位置，然后将B对应位置的基因值改为m。例如， 得算法的时间复杂度太高。基于此，本文在定理 图3中，每一条染色体有15个基因，选择两条父 1的基础上提出一种增量计算的方式，在重新计 代染色体，随机产生一个数2，将B中对应位置的 算适应值时，只计算个体中因基因改变使得适应 取值都改为2。 值增减的部分。 1 定理1假设个体ind在位置h处变异，sh由 2 3 old变为new,则个体ind的新适应值h(ind)w为 13103 31-2 3 0 hew=hau+∑Jh(6aew,s）-dold,s》 VJEN(n) 3 0 其中N(wa)={(v,a)∈E是节点的邻居节点集合。 2 证明 h= 》J6(,s）= 1 1 2 0 2 2 ∑h8(功+∑ J6(s,5)= (2) .VJE 1 1 ViVEENi=h 3 33 3 3 ∑Jh6(,s)+ ∑6,s) !=h 2 2 2 2 由于式(2)等号右侧第2部分在变异前后不 B B 变，所以 图3单路交叉 hpew -hold Fig.3 Single cross Jn6(new,sj)- Jh6(old,s）= 2.4.3变异操作 (3) 本文的变异算子是单点变异。从父代种群中 (6(new,sj)-6(old,sj)) VEN(V) 随机选择一条染色体，然后从这一染色体中随机 选取一个基因，对其重新赋值，但要保证变异之 上述推导表明，当个体ind在h位置变异后， 后染色体的能量函数值没有增加。这样的操作要 新的适应值通过旧适应值加一个增量就可以得 循环n次，因此变异也可以看作一种局部搜索，将 到，而这个增量只需要遍历y的邻居节点就可以 染色体变异为它的邻居染色体，试图找到局部最 算出，这样计算一个个体的适应值的时间复杂度 优的染色体。 从Om)降为O(d,其中dg为平均度数。 2.5符号网络存储 基于定理1，计算新的适应值就可以简便为 符号网络在计算机中一般有3种存储方式： 计算改变子集编号的节点与其邻居节点对适应值 邻接矩阵、三元组和链表方式。邻接矩阵是普遍 的“贡献”。具体分为两种情况：1)原本对适应值 使用的一种方式。然而对于大型符号网络来说， 没有“贡献”的边，在改变基因之后对适应值有“贡 邻接矩阵达到103×10的数量级，存储这样的邻接 献”；2)原本对适应值有“贡献”的边，在改变之后 矩阵对内存要求太高。因此本文选择邻接链表 对适应值没有“贡献”。增量计算大大地降低了时 来存储网络信息。首先为每一个节点都创建一条 间复杂度，在交叉算法中的增量计算只需循环若 链表，头结点是节点本身，后面链接与这一节点 干次，而在变异算法中只需运行一次。 有联系的节点信息，包括节点编号以及边的符 算法具体操作如算法3所示。算法第1行将 号。例如，图4中，这一链表存储节点1的连边信 increaseFitness设置为0，第2行是将c赋值为被 息。节点1与节点2的连边为1，节点1与节点6 改变基因所对应的节点的链表头结点，为了找到 的连边为-1。虽然每条边都存储了两次，但相对 这个节点的所有邻居，之后遍历整个链表。算法 于邻接矩阵的存储方式，大大降低了内存占用。 第4~8行是在判断邻居为正邻居之后，再次判断 123160 如果邻居的基因与旧基因相同，但与新基因不同 图4二维链表示例 时，increaseFitness加2；如果邻居的基因与旧基因 Fig.4 Two-dimension link structure 不同，但与新基因相同时，increaseFitness减2。算 2.6增量计算 法第9~13行是在判断邻居为负邻居之后，再次 在一般的遗传算法中，每一次的交叉和变异 判断如果邻居的基因与旧基因相同，但与新基因
生一个 0 ~ k–1 的整数 m，记录 A 中所有 m 所在的 位置，然后将 B 对应位置的基因值改为 m。例如， 图 3 中，每一条染色体有 15 个基因，选择两条父 代染色体，随机产生一个数 2，将 B 中对应位置的 取值都改为 2。 1 2 1 3 1 0 3 2 1 0 2 1 3 1 2 0 A 0 1 3 1 1 2 0 2 1 2 0 1 3 3 1 2 B 1 2 1 3 1 0 3 2 1 0 2 1 3 1 2 0 A 0 2 3 1 1 2 0 2 1 2 2 1 3 3 2 2 B 图 3 单路交叉 Fig. 3 Single cross 2.4.3 变异操作 本文的变异算子是单点变异。从父代种群中 随机选择一条染色体，然后从这一染色体中随机 选取一个基因，对其重新赋值，但要保证变异之 后染色体的能量函数值没有增加。这样的操作要 循环 n 次，因此变异也可以看作一种局部搜索，将 染色体变异为它的邻居染色体，试图找到局部最 优的染色体。 2.5 符号网络存储 符号网络在计算机中一般有 3 种存储方式： 邻接矩阵、三元组和链表方式。邻接矩阵是普遍 使用的一种方式。然而对于大型符号网络来说， 邻接矩阵达到 105 ×105 的数量级，存储这样的邻接 矩阵对内存要求太高。因此本文选择邻接链表[15] 来存储网络信息。首先为每一个节点都创建一条 链表，头结点是节点本身，后面链接与这一节点 有联系的节点信息，包括节点编号以及边的符 号。例如，图 4 中，这一链表存储节点 1 的连边信 息。节点 1 与节点 2 的连边为 1，节点 1 与节点 6 的连边为–1。虽然每条边都存储了两次，但相对 于邻接矩阵的存储方式，大大降低了内存占用。 first 1 2 1 3 1 6 −1 10 −1 ^ 图 4 二维链表示例 Fig. 4 Two-dimension link structure 2.6 增量计算 在一般的遗传算法中，每一次的交叉和变异 之后都需重新计算一次适应值，这样重复操作使 得算法的时间复杂度太高。基于此，本文在定理 1 的基础上提出一种增量计算的方式，在重新计 算适应值时，只计算个体中因基因改变使得适应 值增减的部分。 定理 1 假设个体 ind 在位置 h 处变异，sh 由 old 变为 new，则个体 ind 的新适应值 h(ind)new 为 hnew = hold + ∑ vj∈N(vh ) Jh j( δ ( new,sj ) −δ ( old,sj )) N (vh) = {vk |(vk 其中 , vh) ∈ E} 是节点 vh 的邻居节点集合。 证明 h = ∑ vi,vj∈E Ji jδ ( si ,sj ) = ∑ vh,vj∈E Jh jδ ( sh,sj ) + ∑ vi,vj∈E∧i!=h Ji jδ ( si ,sj ) = ∑ vj∈N(vh) Jh jδ ( sh,sj ) + ∑ vi,vj∈E∧i!=h Ji jδ ( si ,sj ) (2) 由于式 (2) 等号右侧第 2 部分在变异前后不 变，所以 hnew −hold = ∑ vj∈N(vh ) Jh jδ ( new,sj ) − ∑ vj∈E(vh ) Jh jδ ( old,sj ) = ∑ vj∈N(vh) Jh j( δ ( new,sj ) −δ ( old,sj )) (3) 上述推导表明，当个体 ind 在 h 位置变异后， 新的适应值通过旧适应值加一个增量就可以得 到，而这个增量只需要遍历 vh 的邻居节点就可以 算出，这样计算一个个体的适应值的时间复杂度 从 O(m) 降为 O(davg)，其中 davg 为平均度数。 基于定理 1，计算新的适应值就可以简便为 计算改变子集编号的节点与其邻居节点对适应值 的“贡献”。具体分为两种情况：1) 原本对适应值 没有“贡献”的边，在改变基因之后对适应值有“贡 献”；2) 原本对适应值有“贡献”的边，在改变之后 对适应值没有“贡献”。增量计算大大地降低了时 间复杂度，在交叉算法中的增量计算只需循环若 干次，而在变异算法中只需运行一次。 算法具体操作如算法 3 所示。算法第 1 行将 increaseFitness 设置为 0，第 2 行是将 c 赋值为被 改变基因所对应的节点的链表头结点，为了找到 这个节点的所有邻居，之后遍历整个链表。算法 第 4 ~ 8 行是在判断邻居为正邻居之后，再次判断 如果邻居的基因与旧基因相同，但与新基因不同 时，increaseFitness 加 2；如果邻居的基因与旧基因 不同，但与新基因相同时，increaseFitness 减 2。算 法第 9 ~ 13 行是在判断邻居为负邻居之后，再次 判断如果邻居的基因与旧基因相同，但与新基因 ·786· 智 能 系 统 学 报 第 13 卷
第5期 常新功，等：WSB-EA进化算法的符号网络弱结构平衡分析 ·787· 不同时，increaseFitness减2；如果邻居的基因与旧 数及其取值。算法的运行环境是Intel(R)Core(TM) 基因不同，但与新基因相同时，increaseFitness i3-2330m,运行内存4GB,操作系统Windows7旗 加2。 舰版，使用的软件是eclipse44.5。 算法3 ncreaseFitness0)算法 表1参数设置 输入需要计算适应值的个体individual,基 Table 1 Parameter setting 因改变位置id,旧基因old,新基因new; 参数 含义 取值 输出增加的适应值increaseFitness。 G 迭代次数 50 1)increaseFitness=0; M 种群规模 100 2)c=Data.node[id].first; tournamentSize 锦标赛规模 5 3)遍历节点id的所有邻居节点； uniformRate 交叉概率 0.9 4)f(正邻居) 5)if(getGene(c.data)==old&&getGene(c.data)!= mutationRate 变异概率 0.1 new) 3.2小型符号网络实验结果 6)increaseFitness=increaseFitness+2: 本文使用的小型数据集有4个：斯洛文尼亚 7)else if getGene(c.data)!=old&&getGene(c.data) 政党网络(SPP)、Gahuku-Gama部落网络(GGS)、 new) 社交圈网络(SC)和yeast网络(yeast)。 8)increaseFitness=increaseFitness-2; 斯洛文尼亚政党网络：这是一个由斯洛文尼 9)else if(负邻居) 亚10个议会政党之间的关系组成的网络， 10)if(getGene(c.data)=old&&getGene(c.data) 1994年由一些研究政治的学者提出%。10个议 !=new) 会政党的英文名字缩写分别是SKD、ZLSD、SDSS、 11)increaseFitness=increaseFitness-2: LDS、ZS-ESS、ZS、DS、SLS、SPS-SNS和SNS。这 12)else if(getGene(c.data)!=old&&getGene 一网络中有10个节点，45条连边。 (c.data)=new) Gahuku-Gama部落网络1刃：这一网络中有 13)increaseFitness=increaseFitness+2; 16个节点，代表16个部落。边数为59，代表部落 2.7复杂性分析 之间的联盟和对抗。 在整个算法中，时间复杂度最高的是遗传操 社交圈网络：这一网络是根据现实生活中人 作这一部分，因此只分析这一部分的时间复杂 与人之间的关系得到的实际网络，节点有28个， 度。首先定义几个基础概念，节点个数n、边个 边数为42，代表节点之间的朋友关系或敌人关系。 数m、种群规模M、锦标赛规模1以及迭代次数 Yeast网络：这是一个酵母菌的基因调控网络图， G。选择父本的时间复杂度是O()。交叉算法所 该网络包含690个节点和1080条边。由于这一 花费的时间复杂度是O(n)。变异算子的时间复杂 网络的节点个数较多，在实验中将种群规模增加 度是O(1)。计算适应值的时间复杂度分两种情 到500。 况，若不用增量计算，计算适应值时要遍历整个 为了验证WSB-EA算法的准确性以及健壮 网络的所有边，此时的时间复杂度是O(m)。如果 性，在这4个数据集上与孙一翔提出的Meme-SB 使用增量计算的方式，在计算适应值时只需遍历 算法和没有使用增量计算的WSB-EA算法的实 网络中的若干条边。假设改变的是节点i的子集 验结果作对比分析。每一个数据集都做30次实验， 编号，而节点i的度数为d,则需遍历d,条边。在 记录求得最小适应值时的迭代次数和时间。实验 网络中每个节点的度数是不相等的，因此用平均 结果如表2所示。同时，为了验证增量计算对算 度dve来代表某一个节点的度最合理。所以此时 法的贡献，将WSB-EA算法与没有使用增量计算 的时间复杂度是O(d)。总体算法的时间复杂度 的WSB-EA算法进行时间比较，即得到迭代相同 是OMG(+m)。 的次数所用的时间。结果如表3所示。 3实验结果与分析 从表2可知，无论是只有10个节点的SPP网 络还是有690个节点的yeast网络，在求得相同适 3.1参数设置 应值的情况下，WSB-EA算法的迭代次数较少，也 表1列出了WSB-EA算法中使用到的所有参 就说明WSB-EA算法能更快收敛到最优解。这
不同时，increaseFitness 减 2；如果邻居的基因与旧 基因不同，但与新基因相同时，increaseFitness 加 2。 算法 3 ncreaseFitness() 算法 输入 需要计算适应值的个体 individual，基 因改变位置 id，旧基因 old，新基因 new； 输出 增加的适应值 increaseFitness。 1) increaseFitness=0； 2) c =Data.node[id].first; 3) 遍历节点 id 的所有邻居节点； 4) if (正邻居) 5) if(getGene(c.data)==old&&getGene(c.data)!= new) 6) increaseFitness= increaseFitness+2； 7) else if(getGene(c.data)!=old&&getGene(c.data)== new) 8) increaseFitness= increaseFitness-2； 9) else if(负邻居) 10) if(getGene(c.data)==old&&getGene (c.data) !=new) 11) increaseFitness= increaseFitness-2； 12) else if(getGene(c.data)!=old&&getGene (c.data) == new) 13) increaseFitness= increaseFitness+2； 2.7 复杂性分析 在整个算法中，时间复杂度最高的是遗传操 作这一部分，因此只分析这一部分的时间复杂 度。首先定义几个基础概念，节点个数 n、边个 数 m、种群规模 M、锦标赛规模 t 以及迭代次数 G。选择父本的时间复杂度是 O(t)。交叉算法所 花费的时间复杂度是 O(n)。变异算子的时间复杂 度是 O(1)。计算适应值的时间复杂度分两种情 况，若不用增量计算，计算适应值时要遍历整个 网络的所有边，此时的时间复杂度是 O(m)。如果 使用增量计算的方式，在计算适应值时只需遍历 网络中的若干条边。假设改变的是节点 i 的子集 编号，而节点 i 的度数为 di，则需遍历 di 条边。在 网络中每个节点的度数是不相等的，因此用平均 度 davg 来代表某一个节点的度最合理。所以此时 的时间复杂度是 O(davg)。总体算法的时间复杂度 是 O(MG(n+m))。 3 实验结果与分析 3.1 参数设置 表 1 列出了 WSB-EA 算法中使用到的所有参 数及其取值。算法的运行环境是 Intel(R)Core(TM) i3-2330m，运行内存 4 GB，操作系统 Windows7 旗 舰版，使用的软件是 eclipse4.5。 表 1 参数设置 Table 1 Parameter setting 参数 含义 取值 G 迭代次数 50 M 种群规模 100 tournamentSize 锦标赛规模 5 uniformRate 交叉概率 0.9 mutationRate 变异概率 0.1 3.2 小型符号网络实验结果 本文使用的小型数据集有 4 个：斯洛文尼亚 政党网络 (SPP)、Gahuku-Gama 部落网络 (GGS)、 社交圈网络 (SC) 和 yeast 网络 (yeast)。 斯洛文尼亚政党网络：这是一个由斯洛文尼 亚 1 0 个议会政党之间的关系组成的网络， 1994 年由一些研究政治的学者提出[16]。10 个议 会政党的英文名字缩写分别是 SKD、ZLSD、SDSS、 LDS、ZS-ESS、ZS、DS、SLS、SPS-SNS 和 SNS。这 一网络中有 10 个节点，45 条连边。 Gahuku-Gama 部落网络[ 1 7 ] ：这一网络中有 16 个节点，代表 16 个部落。边数为 59，代表部落 之间的联盟和对抗。 社交圈网络：这一网络是根据现实生活中人 与人之间的关系得到的实际网络，节点有 28 个， 边数为 42，代表节点之间的朋友关系或敌人关系。 Yeast 网络：这是一个酵母菌的基因调控网络[18] ， 该网络包含 690 个节点和 1 080 条边。由于这一 网络的节点个数较多，在实验中将种群规模增加 到 500。 为了验证 WSB-EA 算法的准确性以及健壮 性，在这 4 个数据集上与孙一翔提出的 Meme-SB 算法和没有使用增量计算的 WSB-EA 算法的实 验结果作对比分析。每一个数据集都做 30 次实验， 记录求得最小适应值时的迭代次数和时间。实验 结果如表 2 所示。同时，为了验证增量计算对算 法的贡献，将 WSB-EA 算法与没有使用增量计算 的 WSB-EA 算法进行时间比较，即得到迭代相同 的次数所用的时间。结果如表 3 所示。 从表 2 可知，无论是只有 10 个节点的 SPP 网 络还是有 690 个节点的 yeast 网络，在求得相同适 应值的情况下，WSB-EA 算法的迭代次数较少，也 就说明 WSB-EA 算法能更快收敛到最优解。这 第 5 期 常新功，等：WSB-EA 进化算法的符号网络弱结构平衡分析 ·787·