作為一名非數(shù)學(xué)、非計(jì)算機(jī)專業(yè)的野生研究僧程序員，在學(xué)習(xí)和實(shí)踐多目標(biāo)優(yōu)化時(shí)，遇到了各種困難，加之相關(guān)方向的交流資源有限，也使得整個(gè)過程顯得緩慢。在此，非常感謝西電曉風(fēng)（https://blog.csdn.net/qq_40434430/article/details/82876572）及其他各路貢獻(xiàn)知識(shí)的大神給予的啟發(fā)、交流，他的嚴(yán)謹(jǐn)、謙虛、熱情讓我能不拋棄不放棄，入了門。

為何要專門講解NSGA2非支配排序函數(shù)

多目標(biāo)優(yōu)化中的經(jīng)典是NSGA2，NSGA2的經(jīng)典是non-dominated sort。非支配排序做好了，才能談后面的一切（這句話的領(lǐng)悟，非生而知之，而是在各種試錯(cuò)、奔潰的過程中領(lǐng)略到的）。掌握了NSGA2才能談后面的其他各類算法，如：NSGA3，ε-NSGA2，MOEA，MOEA/D（這里的提法也并非完全正確，他們直接部分并沒有強(qiáng)耦合關(guān)系，僅為個(gè)人一己之見）。

非支配排序函數(shù)的基本原理

首先看一下數(shù)學(xué)定義：

需要說明幾點(diǎn)潛在內(nèi)涵：

• 都是求最小化問題（一個(gè)約定俗成的規(guī)則）；
• 所有的 $f_i(X_a)$ 小于或者等于$f_i(X_b)$ ，且至少存在一個(gè) $f_i(X_a)$ 完全小于$f_i(X_b)$
• $f_i(X_a)$ 完全等于$f_i(X_b)$時(shí)，$X_a$和$X_b$不存在支配關(guān)系（劃重點(diǎn)：這個(gè)在實(shí)際的進(jìn)化過程中，會(huì)出現(xiàn)很多，目前網(wǎng)上很多的代碼忽略了這一點(diǎn)，會(huì)導(dǎo)致在已有Deb大神原始NSGA2測(cè)試問題上運(yùn)行沒問題，但是轉(zhuǎn)換到現(xiàn)實(shí)問題中會(huì)出現(xiàn)很多的問題，如：不收斂、不穩(wěn)定等。為什么會(huì)出現(xiàn)這樣的問題呢？因?yàn)镈eb大神采用的是標(biāo)準(zhǔn)遺傳算子中的一種，即：實(shí)數(shù)編碼和多項(xiàng)式交叉，且論文中定義的PC很大，世代之間出現(xiàn)完全復(fù)制的可能性小。然而，現(xiàn)實(shí)中應(yīng)用改造問題，很多時(shí)候需要改造掉遺傳算子，即：非標(biāo)遺傳算子，從而就會(huì)展現(xiàn)出各種奇葩問題。之所以在這里強(qiáng)調(diào)這問題，是因?yàn)槲易约涸谶@里耗費(fèi)了很多的精力，各種調(diào)試，找不出原因，最終發(fā)現(xiàn)是因?yàn)橐粋€(gè)等于號(hào)坑了我。也特別感謝課題組Jing Huang給予的耐心調(diào)試和討論。）

如何測(cè)試非支配排序函數(shù)

我們需要構(gòu)建專門針對(duì)非支配排序函數(shù)的測(cè)試類，從而驗(yàn)證函數(shù)的正確性，構(gòu)建測(cè)試類的關(guān)鍵是在于輸入的測(cè)試評(píng)價(jià)值A(chǔ)rray的有效性。我通過大量的實(shí)驗(yàn)，提煉出基礎(chǔ)的、正確的、報(bào)錯(cuò)的三個(gè)測(cè)試評(píng)價(jià)值A(chǔ)rray。

• 基礎(chǔ)的測(cè)試評(píng)價(jià)值A(chǔ)rray，大家可以用來(lái)自行推演，該值參考至鄭金華老師的書（主觀評(píng)價(jià)：鄭老師的書是目前國(guó)內(nèi)對(duì)此塊做了系統(tǒng)介紹的書，他的治學(xué)風(fēng)格嚴(yán)謹(jǐn)、務(wù)實(shí)，而非論文的直接堆砌，建議入門學(xué)生可以從這本書開始，論文堆砌的書可以到高階階段再學(xué)習(xí)）
• 正確的測(cè)試評(píng)價(jià)值A(chǔ)rray，跑ZDT3的時(shí)候從內(nèi)存中Debug Copy的。
• 報(bào)錯(cuò)的測(cè)試評(píng)價(jià)值A(chǔ)rray，跑ZDT6的時(shí)候從內(nèi)存中Debug Copy的。以下給出的代碼中test_fast_non_dominated_sort_error函數(shù)會(huì)顯示出他錯(cuò)在哪。

import random import numpy as np from matplotlib.ticker import MultipleLocator import matplotlib.pyplot as pltclass Test_class():def __init__(self,f_num):self.f_num=f_num# 測(cè)試代碼Y1 = [9, 7, 5, 4, 3, 2, 1, 10, 8, 7, 5, 4, 3, 10, 9, 8, 7, 10, 9, 8]Y2 = [1, 2, 4, 5, 6, 7, 9, 1, 5, 6, 7, 8, 9, 5, 6, 7, 9, 6, 7, 9]self.objectives_fitness_zjh=np.array([Y1,Y2]).Tself.objectives_fitness_8 = np.array([[0.6373723585181119, 9.089424920752537],[0.6307563745957109, 9.484134522661321],[0.6307726564027054, 9.370453232401315],[0.9214017573731662, 8.974173267351892],[0.8106208092655269, 9.00814519794432],[0.6308299859236132, 9.381311843663337],[0.9996933421004693, 8.998732212375378],[0.8106208092655269, 9.087298161567794],[0.9968206553777186, 9.020037858133483],[0.9503113437004427, 9.04519027298749],[0.9214017573731662, 8.974173267351892],[0.9214017573731662, 9.00187266065025],[0.6307563745957109, 9.493829448943414],[0.999999999999489, 9.180616877016963],[0.8150090640161689, 9.041622216379706],[0.9990805452551389, 8.980910429010232],[0.9979468094812165, 9.04561922020985],[0.7527617476769539, 9.136335451211739],[0.6364241984468356, 9.20992553291975],[0.8106208092655269, 9.083868693443087]])self.objectives_fitness_20 = np.array([[0.01783689,1.02469787],[0.04471213,0.93037726],[0.0236877,0.96322404],[0.04938809,0.92641409],[0.07031985,0.83355839],[0.05199109,0.88398541],[0.05006115,0.91107188],[0.,1.18579768],[0.05358649,0.85849188],[0.01657041,1.0721905,],[0.10409921,0.84829613],[0.06643826,0.84941993],[0.05358649,0.89876683],[0.01740193,1.09732744],[0.04938809,0.94687415],[0.05199109,0.93536007],[0.02400905,1.11603965],[0.05358649,0.89107165],[0.,1.23996387],[0.01783689,1.11625582]])def test_fast_non_dominated_sort_1(self, objectives_fitness):#對(duì)華電小扎扎寫的非支配排序的修改和調(diào)整# https: // blog.csdn.net / qq_36449201 / article / details / 81046586fronts = [] # Pareto前沿面fronts.append([])set_sp = []npp = np.zeros(2*10)rank = np.zeros(2*10)for i in range(2 * 10):temp = []for j in range(2 * 10):if j != i:if (objectives_fitness[j][0] >= objectives_fitness[i][0] and objectives_fitness[j][1] > objectives_fitness[i][1]) or \(objectives_fitness[j][0] > objectives_fitness[i][0] and objectives_fitness[j][1] >= objectives_fitness[i][1]) or \(objectives_fitness[j][0] >= objectives_fitness[i][0] and objectives_fitness[j][1] >= objectives_fitness[i][1]):temp.append(j)elif (objectives_fitness[i][0] >= objectives_fitness[j][0] and objectives_fitness[i][1] > objectives_fitness[j][1]) or \(objectives_fitness[i][0] > objectives_fitness[j][0] and objectives_fitness[i][1] >= objectives_fitness[j][1]) or \(objectives_fitness[j][0] > objectives_fitness[i][0] and objectives_fitness[j][1] > objectives_fitness[i][1]):npp[i] += 1 # j支配 i，np+1set_sp.append(temp) # i支配 j，將 j 加入 i 的支配解集里if npp[i] == 0:fronts[0].append(i) # 個(gè)體序號(hào)rank[i] = 1 # Pareto前沿面 第一層級(jí)i = 0while len(fronts[i]) > 0:temp = []for j in range(len(fronts[i])):a = 0while a < len(set_sp[fronts[i][j]]):npp[set_sp[fronts[i][j]][a]] -= 1if npp[set_sp[fronts[i][j]][a]] == 0:rank[set_sp[fronts[i][j]][a]] = i + 2 # 第二層級(jí)temp.append(set_sp[fronts[i][j]][a])a = a + 1i = i + 1fronts.append(temp)del fronts[len(fronts) - 1]self.output_fronts(fronts)def output_fronts(self, fronts):# test codesum_coun = 0for kk in range(len(fronts)):sum_coun += len(fronts[kk])print(sum_coun)print(fronts)def test_fast_non_dominated_sort_error(self, objectives_fitness):#對(duì)華電小扎扎寫的非支配排序的修改和調(diào)整# https: // blog.csdn.net / qq_36449201 / article / details / 81046586fronts = [] # Pareto前沿面fronts.append([])set_sp = []npp = np.zeros(2*10)rank = np.zeros(2*10)for i in range(2 * 10):temp = []for j in range(2 * 10):if j != i:if (objectives_fitness[j][0] >= objectives_fitness[i][0] and objectives_fitness[j][1] >= objectives_fitness[i][1]) :temp.append(j)elif (objectives_fitness[i][0] > objectives_fitness[j][0] and objectives_fitness[i][1] > objectives_fitness[j][1]):npp[i] += 1 # j支配 i，np+1set_sp.append(temp) # i支配 j，將 j 加入 i 的支配解集里if npp[i] == 0:fronts[0].append(i) # 個(gè)體序號(hào)rank[i] = 1 # Pareto前沿面 第一層級(jí)i = 0while len(fronts[i]) > 0:temp = []for j in range(len(fronts[i])):a = 0while a < len(set_sp[fronts[i][j]]):npp[set_sp[fronts[i][j]][a]] -= 1if npp[set_sp[fronts[i][j]][a]] == 0:rank[set_sp[fronts[i][j]][a]] = i + 2 # 第二層級(jí)temp.append(set_sp[fronts[i][j]][a])a = a + 1i = i + 1fronts.append(temp)del fronts[len(fronts) - 1]self.output_fronts(fronts)def output_fronts(self, fronts):# test codesum_coun = 0for kk in range(len(fronts)):sum_coun += len(fronts[kk])print(sum_coun)print(fronts)def test_fast_non_dominated_sort_2(self, objectives_fitness):#對(duì)Github Haris Ali Khan寫的NSGA2的非支配排序函數(shù)的調(diào)整# coding:utf-8# Program Name: NSGA-II.py# Description: This is a python implementation of Prof. Kalyanmoy Deb's popular NSGA-II algorithm# Author: Haris Ali Khan# Supervisor: Prof. Manoj Kumar Tiwariset_sp=[[] for i in range(0, np.shape(objectives_fitness)[0])]fronts = [[]]npp=[0 for i in range(0, np.shape(objectives_fitness)[0])]rank = [0 for i in range(0, np.shape(objectives_fitness)[0])]for i in range(0, np.shape(objectives_fitness)[0]):set_sp[i]=[]# npp[i]=0for j in range(0, np.shape(objectives_fitness)[0]):if i != j:if (objectives_fitness[j][0] >= objectives_fitness[i][0] and objectives_fitness[j][1] > objectives_fitness[i][1]) or \(objectives_fitness[j][0] > objectives_fitness[i][0] and objectives_fitness[j][1] >= objectives_fitness[i][1]) or \(objectives_fitness[j][0] >= objectives_fitness[i][0] and objectives_fitness[j][1] >= objectives_fitness[i][1]):# 個(gè)體p的支配集合Sp計(jì)算set_sp[i].append(j)elif (objectives_fitness[i][0] >= objectives_fitness[j][0] and objectives_fitness[i][1] > objectives_fitness[j][1]) or \(objectives_fitness[i][0] > objectives_fitness[j][0] and objectives_fitness[i][1] >= objectives_fitness[j][1]) or \(objectives_fitness[j][0] > objectives_fitness[i][0] and objectives_fitness[j][1] > objectives_fitness[i][1]):# 被支配度Np計(jì)算# Np越大，則說明i個(gè)體越差npp[i] += 1 # j支配 i，np+1if npp[i]==0:rank[i] = 0if i not in fronts[0]:fronts[0].append(i)i = 0while(fronts[i] != []):Q=[]for p in fronts[i]:for q in set_sp[p]:npp[q] =npp[q] - 1if( npp[q]==0):rank[q]=i+1if q not in Q:Q.append(q)i = i+1fronts.append(Q)del fronts[len(fronts)-1]self.output_fronts(fronts)def test_fast_non_dominated_sort_3(self, objectives_fitness):# 參考MoeaPlat的非支配排序# https://blog.csdn.net/qq_40434430/article/details/82876572fronts = [] # Pareto前沿面fronts.append([])set_sp = []npp = np.zeros(2 * 10)rank = np.zeros(2 * 10)for i in range(2 * 10):temp = []for j in range(2 * 10):if j != i:less = 0 # y'的目標(biāo)函數(shù)值小于個(gè)體的目標(biāo)函數(shù)值數(shù)目equal = 0 # y'的目標(biāo)函數(shù)值等于個(gè)體的目標(biāo)函數(shù)值數(shù)目greater = 0 # y'的目標(biāo)函數(shù)值大于個(gè)體的目標(biāo)函數(shù)值數(shù)目for k in range(self.f_num):if (objectives_fitness[i][k] < objectives_fitness[j][k]):less = less + 1elif (objectives_fitness[i][k] == objectives_fitness[j][k]):equal = equal + 1else:greater = greater + 1if (less == 0 and equal != self.f_num):npp[i] += 1 # j支配 i，np+1elif (greater == 0 and equal != self.f_num):temp.append(j)set_sp.append(temp) # i支配 j，將 j 加入 i 的支配解集里if npp[i] == 0:fronts[0].append(i) # 個(gè)體序號(hào)rank[i] = 1 # Pareto前沿面 第一層級(jí)i = 0while len(fronts[i]) > 0:temp = []for j in range(len(fronts[i])):a = 0while a < len(set_sp[fronts[i][j]]):npp[set_sp[fronts[i][j]][a]] -= 1if npp[set_sp[fronts[i][j]][a]] == 0:rank[set_sp[fronts[i][j]][a]] = i + 2 # 第二層級(jí)temp.append(set_sp[fronts[i][j]][a])a = a + 1i = i + 1fronts.append(temp)del fronts[len(fronts) - 1]self.output_fronts(fronts)if __name__ == '__main__':test_class=Test_class(f_num=2)# test zjh 普通print("測(cè)試1：普通")test_class.test_fast_non_dominated_sort_1(test_class.objectives_fitness_zjh)test_class.test_fast_non_dominated_sort_2(test_class.objectives_fitness_zjh)test_class.test_fast_non_dominated_sort_3(test_class.objectives_fitness_zjh)test_class.test_fast_non_dominated_sort_error(test_class.objectives_fitness_zjh)# test ZDT3 正確print("測(cè)試2：正確，重點(diǎn)看錯(cuò)誤的函數(shù)test_fast_non_dominated_sort_error")test_class.test_fast_non_dominated_sort_1(test_class.objectives_fitness_20)test_class.test_fast_non_dominated_sort_2(test_class.objectives_fitness_20)test_class.test_fast_non_dominated_sort_3(test_class.objectives_fitness_20)test_class.test_fast_non_dominated_sort_error(test_class.objectives_fitness_20)# test ZDT6 錯(cuò)誤print("測(cè)試3：ZDT6 錯(cuò)誤，重點(diǎn)看錯(cuò)誤的函數(shù)test_fast_non_dominated_sort_error")test_class.test_fast_non_dominated_sort_1(test_class.objectives_fitness_8)test_class.test_fast_non_dominated_sort_2(test_class.objectives_fitness_8)test_class.test_fast_non_dominated_sort_3(test_class.objectives_fitness_8)test_class.test_fast_non_dominated_sort_error(test_class.objectives_fitness_8)

總結(jié)

這里寫的測(cè)試函數(shù)，客觀來(lái)說還是不夠好的，因?yàn)槭遣捎酶F舉的方式來(lái)驗(yàn)證小于、等于、大于的關(guān)系，兩個(gè)目標(biāo)函數(shù)的時(shí)候，這樣寫還是可以湊合的，但是如果是5個(gè)目標(biāo)，這個(gè)顯然就不可以了。所以增加了test_fast_non_dominated_sort_3()函數(shù)，正確的做法應(yīng)該是參考mooplatm中，排除的寫法，可以適用于多個(gè)目標(biāo)，而不僅僅局限于兩個(gè)目標(biāo)。

總結(jié)

以上是生活随笔為你收集整理的多目标优化系列1---NSGA2的非支配排序函数的讲解的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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