[发明专利]基于免疫克隆多目标优化的网络社区划分方法

摘要

本发明公开了一种基于免疫克隆多目标优化的网络社区划分方法，主要解决现有单目标遗传方法划分结果不稳定和准确率低的问题。其实现步骤是：(1)读入网络图，生成邻接矩阵；(2)设置初始化参数；(3)计算目标值矩阵；(4)根据目标值矩阵，选出非支配抗体群；(5)对非支配抗体群进行克隆操作；(6)对克隆后的抗体群进行交叉和变异，构成父代抗体群；(7)父代抗体群进行局部搜索，构成子代抗体群；(8)根据目标值矩阵大小，得到新的父代抗体群；(9)判断运行代数it是否达到50，若达到，则终止运行，输出目标矩阵最大的抗体中各个节点的划分结果，即社区的划分结果。本发明具有搜索能力强、划分结果稳定和准确率高的优点。

主权项

1.一种基于免疫克隆多目标优化的网络社区划分方法，包括如下步骤：(1)读入一幅实际网络图，并生成网络图对应的邻接矩阵A_ij；(2)初始化：将运行次数it初始值设为0,最大运行次数G设为50，社区类别数x设为2，抗体群规模N(it)设为450，随机产生的抗体群Al(it)表示为：Al(it)={al₁(it),al₂(it),…,al_I(it)…,al_N(it)(it)}，其中I=1,…,N(it)，al_I(it)表示第I个抗体，N(it)表示抗体群规模，it表示当前运行次数；(3)更新运行次数it，进行第it次运行：根据网络图的邻接矩阵A_ij和抗体群Al(it)，计算目标值矩阵Q(Al(it))：Q(Al(it))=([Q₁(Al(it))],[Q₂(Al(it))])，其中，Q₁(Al(it))为第1个目标的目标值，Q₂(Al(it))为第2个目标的目标值，Al(it)为抗体群，it为当前代数。(4)根据计算出的目标值矩阵，将抗体群中的抗体划分为支配抗体群和非支配抗体群，其中非支配抗体群A(it)表示如下：A(it)={a₁(it),…,a_p(it),…,a_n(it)}，其中p=1,…,n，a_p(it)表示第p个非支配抗体，n表示非支配抗体个数，it表示当前代数；(5)对非支配抗体群A(it)执行克隆操作，克隆后的抗体群A′(it)表示为：A′(it)={ap1(it),ap2(it),...apf(it)...,apq(it)},]]>其中p=1,…,n，n为非支配抗体个数，f=1,…,q，q为克隆比例，为第p个抗体的f次克隆，it表示当前代数；(6)对克隆后的抗体群A'(it)进行交叉操作和变异操作，构成父代抗体群；(7)用模拟退火法对父代抗体群中的抗体进行局部搜索，得到的新的抗体加入到父代抗体群中，构成子代抗体群；(8)根据子代抗体群中抗体的目标矩阵的大小，对子代抗体群进行由大到小排序，选择出目标值矩阵和最大的450个抗体作为新的父代抗体群；(9)判断步骤(3)中运行代数it是否达到最大运行次数50，若达到，则终止运行，输出新的父代抗体群中目标值矩阵最大的抗体，输出的抗体中对各个节点的划分就是社区的划分结果，并输出社区的划分结果；否则，将新的父代抗体群作为抗体群Al(it)，在步骤(3)继续进行第it次运行，直到达到最大运行次数。