快速非支配排序算法流程
輸入：父代子代個體構成的種群P PP
FOR each p ∈ P p\in Pp∈P
\quad S p = ? S_p=\varnothingS?
p?=?
\quad n p = 0 n_p=0n?
p?=0
\quad FOR each q ∈ P q\in Pq∈P
\qquad IF p ? q p\prec qp?q
\quad\qquad S p = S p ? { q } S_p=S_p\bigcup \{q\}S?
p?=S?p?{q}
\qquad ELSEIF q ? p q\prec pq?p
\quad \qquad n p = n p + 1 n_p=n_p+1n?p?=n?
p+1
\qquad ENDIF
\quad ENDFOR
\quad IF n p = = 0 n_p==0n?
p
?==0
\qquad p r a n k = 1 p_{rank}=1p?
rank
?
?=1
\qquad F 1 = F 1 ? { p } F_1=F_1\bigcup \{p\}F?
1
?
?=F?
1
?
??{p}
\quad ENDIF
ENDFOR
i = 1 i=1i=1
WHILE F i ≠ ? F_i\neq \varnothingF?
i
?
??

?
?=?
\quad Q = ? Q=\varnothingQ=?
\quad FOR each p ∈ F i p\in F_ip∈F?
i
?
?
\qquad FOR each q ∈ S p q\in S_pq∈S?
p
?
?
\quad \qquad n q = n q ? 1 n_q=n_q-1n?
q
?
?=n?
q
?
??1
\quad \qquad IF n q = = 0 nq==0nq==0
\qquad \qquad q r a n k = i + 1 q_{rank}=i+1q?
rank
?
?=i+1
\qquad \qquad Q = Q ? { q } Q=Q\bigcup \{q\}Q=Q?{q}
\quad \qquad ENDIF
\qquad ENDFOR
\quad ENDFOR
\quad i = i + 1 i=i+1i=i+1
\quad F i = Q F_i=QF?
i
?
?=Q
ENDWHILE
輸出：F 1 , F 2 , . . . , F i F_1,F_2,...,F_iF?
1
?
?,F?
2
?
?,...,F?
i
?
?

再就是把每層相加直到超過種群個體，也即滿足l = a r g m i n l ∑ i = 1 l > N l=argmin_l{\sum_{i=1}^{l}}>Nl=argmin?
l
?
?∑?
i=1
l
?
?>N 并且有 ∑ i = 1 l ? 1 < N \sum_{i=1}^{l-1}<N∑?
i=1
l?1
?
?<N， 再在第l ll層基于擁擠距離來選擇解，擁擠距離偽代碼如下：

擁擠距離計算方法
輸入：第i ii層的解R t = F l Rt=F_lRt=F?
l
?
?
r = ∣ R t ∣ r=|Rt|r=∣Rt∣
for each j jj,set R t [ j ] d i s t a n c e = 0 Rt[j]_{distance}=0Rt[j]?
distance
?
?=0
FOR each objective m mm
\quad R t = s o r t ( R t , m ) Rt=sort(Rt,m)Rt=sort(Rt,m)
\quad R t [ 1 ] d i s t a n c e = R t [ r ] d i s t a n c e = ∞ Rt[1]_{distance}=Rt[r]_{distance}=\inftyRt[1]?
distance
?
?=Rt[r]?
distance
?
?=∞
\quad FOR j = 2 : ( r ? 1 ) j=2:(r-1)j=2:(r?1)
\qquad R t [ j ] d i s t a n c e = R t [ j ] d i s t a n c e + ( R t [ j + 1 ] . m ? R t [ j ? 1 ] . m ) / ( f m m a x ? f m m i n ) Rt[j]_{distance}=Rt[j]_{distance}+(Rt[j+1].m-Rt[j-1].m)/(f_m^{max}-f_m^{min})Rt[j]?
distance
?
?=Rt[j]?
distance
?
?+(Rt[j+1].m?Rt[j?1].m)/(f?
m
max
?
??f?
m
min
?
?)
\quad ENDFOR
ENDFOR

具體來說，NSGA-II使用快速非支配排序來保證收斂性，并且利用擁擠距離來保證分布性。特別說下，在迭代后期，大多數解都是非支配的，也即大多數解都在第一層。
當然，隨著NSGA-II的提出，很多基于此的算法如雨后春筍般大量涌現，特別是在處理高維多目標優化問題時這種想法得到很多的應用，如VaEA，RVEA，NSGA-III等。
同時，SPEA2也是基于Pareto支配關系的一種較為流行的算法(SPEA2: Improving the Strength Pareto Evolutionary Algorithm)，該算法使用一個外部保存集來保存較為優秀的解，同時，對每一個解，利用其支配的解的數量和基于KNN的鄰近解的距離來給每一個解打分，得分越小的解更優。
————————————————
原文鏈接：https://blog.csdn.net/qithon/article/details/72885053

總結

以上是生活随笔為你收集整理的快速非支配排序算法流程的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。