Tracy's Studio.

NSGA2

MOEA
字数统计: 467阅读时长: 2 min
2020/03/18 Share

NSGA2(Non-dominated sorting in genetic algorithm2)

相比较NSGA从以下三个部分进行了改善：保留了最优个体；不用设置共享参数；构造Pareto最优解集的时间复杂度有所降低。

算法的时间开销由三部分组成：

构造分类子集(Non-dominated sort) O(r(2N)^2)

计算聚集距离

构造偏序集：个体之间的偏序e6

非支配集的构造方法

为每一个个体p设置两个性质：np记录p支配个体的数目，sp记录被p支配的个体的集合。

e1

通过一个二重循环计算每个个体的np和sp，则

e2

e3

构造非支配集的过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
nondominated-sort(P)
任意Pop中的个体p，np=0,Sp为空 //初始化
for p in Pop
	for q in Pop
    	if p支配q
         	Sp = [ Sp q ];
		else if q支配p
        	np = np + 1;
       	 end if
     end for
     if np = 0
     	P1 = [P1 , np];
     end if
end for
i = 1;
while(!Pi)
	H = [];
	for p in Pi
		for q in Sp
			nq = nq - 1;
			if nq == 0
				H = [H q];
		end for
	end for
		i = i + 1;
		Pi = H;
end while

保持解群体分布性和多样性的方法

产生新群体时，通常将优秀且聚集度比较小的个体保留参与下一代进化，聚集密度小的个体聚集距离反而大。

本算法中引入了拥挤距离。

对于一个双目标的算法

e4

e5

计算个体之间的拥挤距离

1
2
3
4
5
6
7
8
9
10
crowding-distance-assignment(P)
N = |P|
for each i
	P_distance = 0
for each objective m
	P = sort(P,m);
	for i = 2 to (N-1)
		P[i]_distance = P[i]_distance + (P[i+1]_distance.m-P[i-1]_distance.m)
end for
P[0]_distance = P[N]_distance = 无穷;

NSGA2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
初始化随机产生一个初始群体 P_0
Q_0 = make_new_pop(P_0);
t = 0;
R_t = R_t + Q_t;
F = nondominated-sort(R_t);
P_t+1 = [] and i = 1;
Until(|P_t+1|+|F_i|<=N)
	P_t=1 = p_t+1 + F_i;
	i = i + 1;
end
crowding-distance-assignment(F_i);
sort(F_i,>);
P_t+1 = P_t+1 + F_i(1:N-|P_t+1|);
Q_t+1 = make_new_pop(P_t+1);
t = t + 1;

原文作者：Tracy

原文链接：http://tracywoo.cn/2020/03/18/NSGA2/

发表日期：March 18th 2020, 10:59:08 am

更新日期：March 18th 2020, 12:24:58 pm

版权声明：本文采用知识共享署名-非商业性使用4.0国际许可协议进行许可

CATALOG
  1. 1. 非支配集的构造方法
  2. 2. 保持解群体分布性和多样性的方法
Total : 20
2022
2021
2020
2019
CRL others hexo MOEA ML git node markdown 算法 写论文小技巧 PGM pgm
博客 ML MOEA