论文投稿_医学论文投稿_核心期刊,职称论文投稿发表_论文部落

　　3、多目标优化网络社区的形式描述

　　性质1与性质2说明了采用多目标优化方法解决网络社区发现问题的必要性,为了更好地理解与描述多目标优化网络社区的问题,本节从Pareto最优的角度对此问题进行形式化描述.

　　4、MOCD-PSO算法

　　由性质1与性质2可知,设计基于优化多种社区质量评判指标的社区挖掘算法可以较好地克服以单一评判指标为优化目标的网络社区发现算法所具有的不足,因此,本节尝试设计一种基于多目标离散粒子群优化的网络社区发现算法MOCD-PSO,该算法是在多目标演化优化的NSGA-II算法框架下,采用基于PSO的繁殖策略,选取3种代表性的评判指标(Q,MinMaxCut与GS)进行网络社区结构优化.值得指出的是,该算法的设计思想具有很好的推广性,可以对算法框架、选择更新策略、繁殖策略、个体编码策略与社区质量评判指标进行合理组合,从而形成一个基于多目标优化的网络社区发现算法家族,MOCD-PSO是此家族的一分子而已.当前,代表性的算法框架主要包括NSGA-II、MOEA/D、基于偏好的MOEAs、基于指示器(indicator)的MOEAs、HybridMOEAs与MemeticMOEAs;选择更新策略主要有基于个体指标排序的方法(轮盘赌选择法、随机遍历抽样法、锦标赛选择法等)与基于群体指标的方法;个体繁殖策略主要有基于差分进化的方法、基于免疫的方法、基于PSO的方法、基于概率模型的方法与基于模拟退火的方法;个体编码方法有二进制编码、整数编码与实数编码.

　　4.1粒子编码

　　粒子编码采用CDPSO中的基于节点邻居有序表的编码方法,其基本思想是:首先对图中所有节点进行编号,然后对每个节点的邻居根据其编号进行排序形成邻居有序表,在初始化或粒子位置更新阶段生成新粒子时,确保该个体的合法性.以网络为例,首先建立各节点的邻居有序根据此表可以对网络社区结构进行个体编码,结果所示.该编码过程比较简单,下面的节点1为例加以说明:对于节点1,其与节点2相连接,由中的中心节点1的邻居有序表可知,节点2是该有序表中的第1个元素,故在中,粒子的第Dim(Dim=1)维的值为1;类似地,可以得到粒子其他Dim所对应的值.

　　该编码方式有如下3个优势:

　　1)避免非法粒子的产生,能减少多目标优化问题中的约束限制条件数;2)自动确定社区数;3)避免基于二值编码的迭代二划分策略所遭遇的容易陷入局部最优划分的处境.

　　4.2粒子更新策略

　　粒子群算法的提出,主要受启发于这样的生物学研究结果:鸟群在进行觅食时会记忆并共享自己所发现的最优觅食路径,通过这种共享信息,鸟群能够更快地找到更优质的食物.该算法在求解最优化问题时,将每个优化问题的解都对应着搜索空间中的一只鸟,或称为粒子,所有的粒子都可以由被优化的函数计算出其适应值;同时,每个粒子还具有相应的速度决定其飞翔的方向和距离.也就是说,整个优化过程是通过对粒子的位置与速度不断更新来实现的.

　　粒子的速度更新方法有很多,基本上可以概括为如下公式(6):Vi(t+1)=wVi(t)+c1.rand(.).(Pi.Xi(t))+c2.rand(.).(Pg.Xi(t))(6)其中,Xi=(xi1,xi2,…,xid)与Vi=(vi1,vi2,…,vid)分别是粒子i的位置与速度,t为进化代数,w为惯性系数,c1与c2为学习因子,rand(.)为均匀分布在[0,1]之间的随机数,Pi=(pi1,pi2,…,pid)是粒子i的历史最优位置,Pg=(pg1,pg2,…,pgd)是粒子i当前所处邻域中的最优粒子位置.公式(6)的作用是对在问题解空间中飞行的粒子Pi的速度进行调整,即通过记忆自身迄今为止搜索到的最优位置Pi=(pi1,pi2,…,pid)来实现粒子的自学习和通过感知整个粒子群迄今为止搜索到的最优位置Pg=(pg1,pg2,…,pgd)来实现群体信息共享.由于Pg是粒子群中具有最佳适应度的粒子,亦称为leader,即Pleader,其主要作用是引导粒子群向包含潜在最优解的解区域方向飞行.粒子邻域拓扑结构决定Pleader的身份.例如:当粒子邻域拓扑结构为环形时,Pleader=Plbest;当粒子邻域拓扑结构为全连接时,Pleader=Pgbest;当粒子邻域拓扑结构为星形时,Pleader=Pfocal.MOCD-PSO采用全连接的粒子邻域拓扑结构.

　　4.3Leader选择策略

　　作为多目标离散PSO算法,MOCD-PSO会在迭代优化的过程中形成多个非支配解(nondominated),即相互之间不满足Pareto支配关系的网络社区划分方案集合NonSet,这提出了一个如何在粒子更新时进行leader选择的问题.MOCD-PSO运用基于核密度估计leader选择机制进行leader选择(如图4所示).为简化说明,令|objectives|=2,|NonSet|=10,即,优化目标数为2,算法当前迭代过程中共有10种相互之间不满足Pareto支配关系的网络社区划分方案,分布在由目标1与目标2构成的平面上.对于NonSet中的每一个点x,都存在一个以该点为中心的r邻域Neighbor(x,r),计算该中心点到在其邻域内其他点的距离dist的平均值,选择具有最大平均值的中心点作为leaders.若存在多个这样的leader,则从中选取具有最多r邻居者为leaders;若此leaders含有多个leader,则从中随机选取一个.该过程可以形式化为算法leaderSelection.若令粒子的r邻域邻居数.Nb,则有该算法的时间复杂度为O(N.b.|NonSet|).

　　4.4Pareto最优社区结构集更新策略

　　研究表明,一个好的多目标优化算法应该能产生尽可能多且分布尽可能均匀平滑的高精确极优解.现有大多数多目标优化算法是借助外部存档(externalarchive,简写EA)存储Pareto最优解,基本思想是:通过对算法当前迭代过程中产生的最优解与EA中的元素进行Pareto关系的比较来实现Pareto最优解的更新,即:当EA中的元素数目达到其最大容量MAXP时,直接将新生的非被支配解插入;而当EA已满时,随机决定是否用新生的非被支配解代替EA中的某个随机元素.显然,这样无法很好地达成一个优质多目标优化算法的期望:使极优解的分布尽可能均匀.在EA已达其最大容量且当前迭代过程产生的网络社区划分方案CurBestP满足如公式(10)所示条件时,会面临这样一个问题:如何从(|CurBestP|+MAXP)候选Pareto最优社区结构集合中选择出MAXP个具有最大均匀分布特性的Pareto最优社区结构.一种朴素的策略就是遍历候选Pareto最优社区结构集合的所有大小为MAXP的组合情况,令EA.为其中一种组合情况,再利用KL散度的组合数使得这种朴素策略在计算上是prohibitive的.

　　值得说明是,由于在多目标优化算法中每个网络社区结构都对应到网络社区结构质量评判指标空间中的一个点,我们希望MOCD-PSO算法在寻优过程中找到最优网络社区结构集合所对应的点集合分布更加均匀,因为这样可以加强算法的寻优能力.而在信息论中,KL散度通常被用来度量两个不同分布之间的差异,故我们采用KL散度来度量EA中的点分布均匀性.

　　基于上述分析,我们提出一种启发式策略来实现Pareto最优社区结构集更新,给EA中粒子赋以年龄属性,用以标识其从进入EA到当前迭代所经历的代数.若简单地实现给EA中的每个粒子配置一个年龄跟踪器,这一方面会增加空间开销,同时还会加大计算复杂度.由于我们只对粒子的年龄大小顺序感兴趣,而无需知道粒子的精确年龄,因此在具体实现中,我们巧妙地将EA表示成队列QPS,这既节省空间又提高了计算效率.该策略可形式化为算法UpdatePS.

　　4.5算法描述与分析

　　MOCD-PSO算法的具体步骤描述如下:

　　Step1:设置粒子群规模、粒子位置和速度的范围与维度、粒子群惯性因子、邻域半径以及外部存档最大容量;

　　Step2:建立网络各节点的邻居节点编号表;

　　Step3:采用基于节点邻居有序表的编码方法初始化粒子群;Step4:计算粒子适应度向量F(P);

　　Step5:进行粒子的Pareto支配关系比较;

　　Step6:调用UpdatePS算法更新Pareto最优社区结构集;Step7:调用leaderSelection算法选择粒子飞行的leader;Step8:根据公式(6)、公式(8)与公式(9)对粒子的位置和速度进行更新;Step9:重复Step4~Step7,直至算法迭代次数达到用户指定的最大迭代次数值,输出全部Pareto最优解集元素所对应的网络社区结构.MOCD-PSO算法步骤可划分为两大块:第1块是Step1~Step3,主要负责初始化算法执行所需要的相关参数与数据结构;第2块是Step4~Step9,主要通过粒子群在解空间中协作飞行来实现多个目标函数的寻优,若迭代寻优的结束条件满足,则输出Pareto最优解对应的网络社区,算法结束.

　　假定原网络的节点数为n,由用户指定的最大迭代次数为t,由用户指定的粒子数为k,则算法的复杂度可以估计如下: