非支配快速排序算法詳解

對(duì)NSGA-II的一個(gè)學(xué)習(xí)記錄
?? ?? ??

為易于理解，只用三個(gè)點(diǎn)舉例子。

Np=3; %三個(gè)點(diǎn) current_vector = [1:1:Np]'; %當(dāng)前向量 current_pf=1; %先找F1 RANK = zeros(Np,1); %RANK初始化 all_perm = [repmat([1:1:Np]',Np',1), reshape(repmat([1:1:Np],Np,1),Np^2,1)];%生成兩列 all_perm(all_perm(:,1)==all_perm(:,2),:) = []; %每個(gè)點(diǎn)和其余比較 d=[0 1 0 0 1 1]; %假設(shè)支配關(guān)系 dominated_particles = unique(all_perm(d==1,2));%依次找到各個(gè)點(diǎn)是否受人支配，不在乎受幾個(gè)人支配，只要受人支配了，那他就不是當(dāng)前要找的等級(jí)。 non_dom_idx = ~ismember(current_vector,dominated_particles);%找到非支配的點(diǎn)的位置，這是一個(gè)邏輯值 RANK(current_vector(non_dom_idx)) = current_pf; %讓這些位置成為當(dāng)前等級(jí) all_perm(ismember(all_perm(:,1),current_vector(non_dom_idx)),:) = [];%找到以后，刪除，因?yàn)橐粋€(gè)點(diǎn)只能屬于一個(gè)等級(jí) all_perm(ismember(all_perm(:,2),current_vector(non_dom_idx)),:) = [];%找到以后，刪除，因?yàn)橐粋€(gè)點(diǎn)只能屬于一個(gè)等級(jí) current_vector(non_dom_idx) = [];%當(dāng)前向量中刪除那些非支配點(diǎn) current_pf = current_pf + 1; %等級(jí)+1，找下一個(gè)等級(jí)。

思路以及程序?qū)崿F(xiàn)過程即為上述。其實(shí)在非支配快速排序中還要判斷是否已經(jīng)把所有粒子給分好等級(jí)了。有兩個(gè)跳出循環(huán)的地方
1、判斷當(dāng)前向量中是否只有一個(gè)點(diǎn)了，要是就一個(gè)點(diǎn)了，那他就是最后一個(gè)等級(jí)了，直接跳出就好了；
2、判斷當(dāng)前向量中，是否沒有更多空間去放等級(jí)了。（沒看太明白，這塊直接跳出了，等級(jí)也沒加，可能就是一個(gè)判斷的過程。）不影響分等級(jí)。

有兩個(gè)函數(shù)，快速非支配排序和比較函數(shù)

function [RANK] = FastNonDominatedSorting_Vectorized(fitness)% InitializationNp = size(fitness,1);RANK = zeros(Np,1);current_vector = [1:1:Np]';current_pf = 1;all_perm = [repmat([1:1:Np]',Np',1), reshape(repmat([1:1:Np],Np,1),Np^2,1)];all_perm(all_perm(:,1)==all_perm(:,2),:) = []; %每個(gè)個(gè)體去和別人比。 一個(gè)個(gè)體有兩個(gè)目標(biāo)函數(shù)值% Computing each Pareto Frontwhile ~isempty(current_vector) %非空，就是我這100個(gè)個(gè)體還沒分完等級(jí)呢。% Check if there is only a single particleif length(current_vector) == 1RANK(current_vector) = current_pf;break;end% Non-dominated particles% Note: nchoosek has an exponential grow in computation time, so% it's better to take all the combinations including repetitions using a% loops (quasi-linear grow) or repmats (linear grow)%all_perm = nchoosek(current_vector,2); %all_perm = [all_perm; [all_perm(:,2) all_perm(:,1)]]; d = dominates(fitness(all_perm(:,1),:),fitness(all_perm(:,2),:));%d是一個(gè)邏輯值，他判斷了所有個(gè)體和單個(gè)個(gè)體的支配關(guān)系。第一列是2到200，第二列全是1，先判斷2到200是不是支配了1。以此類推。dominated_particles = unique(all_perm(d==1,2)); % 找到被人支配的，unique就是不管是誰支配了1，不管有幾個(gè)，我只計(jì)數(shù)一個(gè)% Check if there is no room for more Pareto Frontsif sum(~ismember(current_vector,dominated_particles)) == 0break;end% Update ranks and current_vector 更新等級(jí)non_dom_idx = ~ismember(current_vector,dominated_particles); %找出那些沒有人支配的所在的位置，然后在current_vector中挑出來，就是第一等級(jí)RANK(current_vector(non_dom_idx)) = current_pf; %把這些定為第一等級(jí)，其余位置都是0，我不在乎他是第幾等級(jí)。用邏輯值來判斷all_perm(ismember(all_perm(:,1),current_vector(non_dom_idx)),:) = [];all_perm(ismember(all_perm(:,2),current_vector(non_dom_idx)),:) = [];%判斷完的就把剔除出去current_vector(non_dom_idx) = []; %判斷完的就剔除出去了current_pf = current_pf + 1; %找下一等級(jí)的去，知道找完了才停下來。end end % Function that returns true if x dominates y and false otherwise function d = dominates(x,y)d = (all(x<=y,2) & any(x<y,2)); end

只是記錄學(xué)習(xí)，如有錯(cuò)誤，請(qǐng)及時(shí)指出，謝謝大家。

參考：mathworks NSGA-II(2019年更新的那版)

總結(jié)

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

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。