NSGA-II快速非支配排序算法理解

里克贝斯

发布于 2021-05-21 17:07:57

2.7K1

发布于 2021-05-21 17:07:57

快速的非支配排序

在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[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++

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

%-------非支配排序????????
?
????????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

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

本文参与?腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2017-04-19，如有侵权请联系 cloudcommunity@tencent.com 删除

c++