EDA365电子论坛网

标题: NSGA-II快速非支配排序算法理解 [打印本页]

作者: pulbieup 时间: 2020-10-10 17:26
标题: NSGA-II快速非支配排序算法理解

快速的非支配排序

在NSGA进行非支配排序时，规模为N的种群中的每个个体都要针对M个目标函数和种群中的N-1个个体进行比较，复杂度为O(MN)，因此种群中的N个个体都比较结束的复杂度为O(MN2)，即每进行一次Pareto分级的时间复杂度为O(MN2)。在最坏的情况下，每个Pareto级别都只含有一个个体，那么需要进行N次分级所需要的时间复杂度则会上升为O(MN3)。鉴于此，论文中提出了一种快速非支配排序法，该方法的时间复杂度为O(MN2)。

该算法需要保存两个量：

(1).支配个数np。该量是在可行解空间中可以支配个体p的所有个体的数量。

(2).被支配个体集合SP。该量是可行解空间中所有被个体p支配的个体组成的集合。

下面是fast_nondominated_sort的伪代码

def fast_nondominated_sort( P ):
F = [ ]
for p in P:
Sp = [ ]
np = 0
for q in P:
if p > q: #如果p支配q，把q添加到Sp列表中
Sp.append( q )
else if p < q: #如果p被q支配，则把np加1
np += 1
if np == 0:
p_rank = 1 #如果该个体的np为0，则该个体为Pareto第一级
F1.append( p )
F.append( F1 )
i = 0
while F:
Q = [ ]
for p in F:
for q in Sp: #对所有在Sp集合中的个体进行排序
nq -= 1
if nq == 0: #如果该个体的支配个数为0，则该个体是非支配个体
q_rank = i+2 #该个体Pareto级别为当前最高级别加1。此时i初始值为0，所以要加2
Q.append( q )
F.append( Q )
i +=14 o, n$ F) i" `6 Q& X3 b' g: R8 _

下面是C++实现：

void population::nodominata_sort()
//求pareto解（快速非支配排序）
{
int i,j,k;
indivial H[2*popsize];
int h_len=0;
for(i=0;i<2*popsize;i++)
{
R.np=0;//支配个数np
R.is_domied=0;//被支配的个数
len=0;//初始化
}
for(i=0;i<2*popsize;i++)
{
for(j=0;j<2*popsize;j++)
{
if(i!=j)//自己不能支配自身
{
if(is_dominated(R,R[j]))
{
R.domi[R.is_domied++]=j;
//如果i支配j，把i添加到j的is_domied列表中
}
else if(is_dominated(R[j],R))
R.np+=1;
//如果i被j支配，则把np加1
}
}
if(R.np==0)//如果该个体的np为0，则该个体为Pareto第一级
{
len_f=1;
F[0][len[0]++]=R;//将R归并
}
}
i=0;
while(len!=0)
{
h_len=0;
for(j=0;j<len;j++)
{
for(k=0;k<F[j].is_domied;k++)
//对所有在is_domied集合中的个体进行排序
{
R[F[j].domi[k]].np--;
if( R[F[j].domi[k]].np==0)
//如果该个体的支配个数为0，则该个体是非支配个体
{
H[h_len++]=R[F[j].domi[k]];
R[F[j].domi[k]].rank=i+1;
}
}
}
i++;
len=h_len;
if(h_len!=0)
{
len_f++;
for(j=0;j<len;j++)
{
F[j]=H[j];
}
}
}
}
I9 I7 [; [0 ]) F" T

matlab代码：

%-------非支配排序
fnum=0; %当前分配的前沿面编号
cz=false(1,size(functionvalue,1)); %记录个体是否已被分配编号
frontvalue=zeros(size(cz)); %每个个体的前沿面编号
[functionvalue_sorted,newsite]=sortrows(functionvalue); %对种群按第一维目标值大小进行排序
while ~all(cz) %开始迭代判断每个个体的前沿面,采用改进的deductive sort
fnum=fnum+1;
d=cz;
for i=1:size(functionvalue,1)
if ~d(i)
for j=i+1:size(functionvalue,1)
if ~d(j)
k=1;
for m=2:size(functionvalue,2)
if functionvalue_sorted(i,m)>functionvalue_sorted(j,m)
k=0;
break
end
end
if k
d(j)=true;
end
end
end
frontvalue(newsite(i))=fnum;
cz(i)=true;
end
end
end
* b7 Z R' w$ h2 p% z

NSGA2具体算法实现还在编写中。

作者: NNNei256 时间: 2020-10-10 18:32
NSGA-II快速非支配排序算法理解

欢迎光临 EDA365电子论坛网 (https://bbs.eda365.com/)