快速的非支配排序
在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的伪代码
代码语言：txt复制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[i]:
Q = [ ]
for p in F[i]:
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 = 1下面是C 实现：
C
代码语言：txt复制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[i].np=0;//支配个数np
R[i].is_domied=0;//被支配的个数
len[i]=0;//初始化
}
for(i=0;i<2*popsize;i )
{
for(j=0;j<2*popsize;j )
{
if(i!=j)//自己不能支配自身
{
if(is_dominated(R[i],R[j]))
{
R[i].domi[R[i].is_domied ]=j;
//如果i支配j，把i添加到j的is_domied列表中
}
else if(is_dominated(R[j],R[i]))
R[i].np =1;
//如果i被j支配，则把np加1
}
}
if(R[i].np==0)//如果该个体的np为0，则该个体为Pareto第一级
{
len_f=1;
F[0][len[0] ]=R[i];//将R[i]归并
}
}
i=0;
while(len[i]!=0)
{
h_len=0;
for(j=0;j<len[i];j )
{
for(k=0;k<F[i][j].is_domied;k )
//对所有在is_domied集合中的个体进行排序
{
R[F[i][j].domi[k]].np--;
if( R[F[i][j].domi[k]].np==0)
//如果该个体的支配个数为0，则该个体是非支配个体
{
H[h_len ]=R[F[i][j].domi[k]];
R[F[i][j].domi[k]].rank=i 1;
}
}
}
i ;
len[i]=h_len;
if(h_len!=0)
{
len_f ;
for(j=0;j<len[i];j )
{
F[i][j]=H[j];
}
}
}
}matlab代码：
MATLAB
代码语言：txt复制%-------非支配排序
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
endNSGA2具体算法实现还在编写中。
