快速的非支配排序
在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的伪代码
|
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 |
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++实现：
|
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 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
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代码：
|
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 28 29 30 |
%-------非支配排序 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具体算法实现还在编写中。
想问一下，你用matlab写的NSGA-II里面的改进演绎排序的出处在哪里呀，我想在我论文里引用一下你这里面的排序方法，不知道怎么引用，可以回复我下吗，谢谢啦。
Deb et al., “A Fast and Elitist Multiobjective Genetic Algorithm.” 就直接引用原文
我是说那个非支配排序那段，matlab代码注释里面写的使用采用改进的deductive sort。想用改进的deductive sort不知道怎么引用。
您好，算法很好用，不过有个小问题：当存在多个相同的解时，该算法只保留了一个，再小补一下，就非常棒了。
您好，请问如何理解您表达的意思，如何小补呢？