下载掌阅APP，畅读海量书库
立即打开
多目标遗传算法是多目标优化问题，显然具有多个目标函数，且一般地，多个目标之间是相互冲突的。一个具有 n 个决策变量， m 个目标函数的多目标优化问题的数学模型为：
其中，
为
n
维的决策向量，
X
为
n
维的决策空间，
y
=（
y
1
，
y
2
，…，
y
m
）
为
m
维的目标向量，
Y
为
m
维的目标空间。目标函数定义了
m
个由决策空间向目标空间的映射函数，定义了
q
个不等约束，定义了
p
个等式约束。
对于一个无向无符号网络 G ，可以用 G =（ V ， E ）表示，其中 V 表示节点集， E 表示网络中边的集合。对于多目标遗传算法的社区检测，其目标函数的数学模型可以表示为：
第一个目标函数NAR（NegativeRatio Association）反映了社区内节点连接的紧密程度，第二个目标函数RC（Ratio Cut）反映了社区间的分离程度。这两个目标函数是由模块密度函数
D
分离得到的。其中，
C
i
表示第
i
个社区，
表示社区
C
i
内节点的个数；
表示了社区
C
i
的内部节点度，定义为
，其中
A
为网络的邻接矩阵，当点
v
i
和点
v
j
之间有连接时，
A
ij
=1，反之为0；
表示了社区
C
i
的外部节点度，定义为
。
主要的多目标遗传算法有非支配排序遗传算法NSGA-Ⅱ、MOEA/D等。
NSGA-Ⅱ是Deb等在NSGA基础上提出的。NSGA的实质是一种基于所有元素排名的多目标优化算法。其思路是，首先确定非支配解，然后被分配一个很大的虚拟适应度值。为了保证种群的多样性，这些非支配解用它们的虚拟适应度值进行共享。暂时不考虑这些非支配解，从余下的种群中确定第二批非支配个体，并给其分配一个比前一批非支配个体共享后最小适应度值还要小的虚拟适应度值。依次向下求新的非支配个体，直到不能再划分。NSGA采用比例选择来复制出第一代。相对于NSGA而言，NSGA-Ⅱ具有以下优点：①提出了新的基于分级的快速非支配解排序方法，降低了计算复杂度；②为了标定快速非支配排序后同级中不同元素的适应度值，同时使当前Pareto前沿面中的个体能扩展到整个Pareto前沿面，并尽可能均匀分布，该算法提出了拥挤距离的概念，采用拥挤距离比较算子代替NSGA中的适值度共享方法；③引入了精英保留机制，经选择后参加繁殖的个体所产生的后代同其父代个体共同竞争，产生下一代种群，因此有利于保持优良的个体，提高种群的整体进化水平。
2007年，Zhang和Li等提出MOEA/D算法，其主要思想是通过一些分解策略把优化多个问题的模型划分为优化多个单目标子问题。其中，各个子问题是由相邻子问题的权重向量信息来同时优化的，从而保持了种群多样性。针对不同的问题，选择合适的分解策略和权重向量，就可以使子问题的局部最优解均匀地分布在Pareto前沿面。单纯形格子法是常用的权重向量的获取方法，分解策略有加权和法、切比雪夫法和基于惩罚的边界交叉法。
遗传算法用于解决社区检测问题时，常用的编码方式有两种：一种是基于标签的编码方式（string based encoding method）；另一种是基于轨迹的编码方式（local based encoding）。这两种编码方式都属于实数编码。
基于标签的编码方式是随机给定节点一个标签来编码染色体，解码方式是将拥有相同标签的节点划分为同一社区，最终通过优化目标函数，求得实现最佳划分结果的染色体。该方法的编码与译码过程如图1.33所示，网络中有9个节点，分别用1～9表示。图1.33（a）为网络连接情况，按图1.33（b）所示的方式编码，将1～5的节点赋标签1，6～9节点赋标签2，最终的解码如图1.33（c）所示，标签为1的节点均被划分到社区1中，标签为2的节点被划分到社区2中。
图1.33 基于标签的解码与译码
基于轨迹的编码规则是根据节点的连接情况，将节点 i 的编码值从与它相连接的节点中选取，包括自身节点值，所以基因位上的值属于[1， N ]， N 为节点数。具体编码方式如图1.34所示。其中图1.34（a）为原始网络图，图1.34（b）是编码后的染色体，其编码规则为：如节点2在包括自身节点值的情况下有1、2、3、4共4个相邻节点，所以可以从中随机选择一个作为编码值，此处选择节点3。再根据该染色体的编码值查看连接，将互相连接的节点划分进一个社区，如图1.34（c）所示，即实现解码。
图1.34 基于轨迹的编码与解码
在单目标中，最优解的性能相对于其他解的性能是绝对占有的，且适应度值越高结果就越优。而在多目标优化中各个目标之间可能是相互冲突的，所以一般很难找到一个类似于单目标优化的绝对占优的最优解，只能找到一组不可比较的解。这些解在目标空间的像称为Pareto前沿（Pareto Front）。由此给出以下定义。
定义1-1 Pareto占优 ：假设 x A ， x B ∈ X f 一个多目标优化的两个可行解，若 x A 相比 x B 是Pareto占优的，则满足：
记作
，也叫作
x
A
支配
x
B
。
定义1-2 Pareto最优解 ：一个解 x * ∈ X f 被称为Pareto最优解（或非支配解），当且仅当满足如下条件：
定义1-3 Pareto最优解集 ：Pareto最优解集是所有Pareto最优解的集合，定义如下：
定义1-4 Pareto前沿面 ：Pareto最优解集 P * 中的所有Pareto最优解对应的目标向量组成的曲面称为Pareto前沿面 PF * ：
