背景

? ? ? ? 我自己搞多目標(biāo)的，看來一圈中文的ENS ，寫的都是啥呀，我看不懂呀，我太菜了。花了一上午搞懂原理，然后一下午寫完了python版的，當(dāng)然寫的很粗糙，可能還有很多可優(yōu)化的點，遇到問題了在debug

我理解的ENS

? ? ? ? 這東西其實挺簡單，因為很早我就會了二維的情況，本科找工作刷力扣的時候接觸的，只是當(dāng)時不知道叫這東西。力扣題目叫 游戲中弱角色的數(shù)量 ，只是力扣這題要求每個維度都嚴格小于，帕累托則是只要一個維度小于，其他的小于等于都行。對應(yīng)到代碼就是一個是< 一個是<=.

? ? ? ? ENS 整個過程很簡單

按照第一目標(biāo)函數(shù)值進行排序, 若第一目標(biāo)函數(shù)相同，則按照第二目標(biāo)函數(shù)對比，依次類推；若所有目標(biāo)函數(shù)值均相等，則任意排列。（復(fù)雜度O（nlogn），應(yīng)該是。numpy直接調(diào)庫函數(shù) lexsort 就行，已經(jīng)有人幫我們做好優(yōu)化了，其他語言應(yīng)該也差不多，能找到相應(yīng)實現(xiàn)）

排序完了，就是局部有序的，然后在沒有分配前沿等級的解中找所有非支配解（由于是局部有序的，所以屬于線性查找，復(fù)雜度是O（nm），m是目標(biāo)個數(shù)）

找完后，就曉得這一輪的非支配解對應(yīng)的前沿等級了，然后去掉找到的所有非支配解，前沿等級加一。在剩下的解中接著找下一等級的所有非支配解（說非支配解不太準(zhǔn)確，因為非支配解特指第一前沿，這是方便理解）

? ? ? ? 就沒了，剩下的基本就是coding的小技巧，怎么找所有的非支配解，怎么判斷兩個解的支配關(guān)系，怎么去掉找到的非支配解。都是coding考慮的

代碼

import numpy as npdef n_dim_sort(X): # 多維排序N = len(X[0])temp = [X[:,i] for i in range(N-1,-1,-1)] # 構(gòu)造參數(shù)idex = np.lexsort(temp) # 調(diào)庫return idex,X[idex,:] # 返回結(jié)果def isDominated(x,y): # 判斷 x是否支配了yM = len(x) # 目標(biāo)函數(shù)個數(shù)m = 1 # 從第二個目標(biāo)開始，因為排序的時候已經(jīng)處理了第一個目標(biāo)了while m< M and y[m]>=x[m]: # 比較所有目標(biāo)m +=1Dominated = m > (M-1)return Dominateddef get_all_NotDominated(X): # 獲得所有的非支配解。 X 是局部有序的temp = []temp.append(X[0]) #第一個肯定是沒有人可以支配它的，畢竟人家第一個目標(biāo)肯定是X中最小的idex = [0]for i in range(1,len(X)): # 對每個解Dominated = Falsefor item in temp: # 都判斷是不是會被現(xiàn)有的非支配解支配掉，只要一個被支配了，那就不可能是非支配解if isDominated(item,X[i]):Dominated = Truebreak # 只要被一個支配了，就沒必要接著往下了if not Dominated: # 都檢查過了，這個解沒被支配，那就是非支配解temp.append(X[i])idex.append(i)return idex # 返回所有非支配解的下標(biāo)def ENS_ss(X): # X 是排序后的N = len(X) # 解個數(shù)index = set(range(N)) # 還沒有處理的解下標(biāo)FNO = 1 # 開始處理FrontNo = [0]*N # 每個解對應(yīng)的前沿等級while len(index):tmp_List = list(index)idex = get_all_NotDominated(X[tmp_List,:])remove_index = [] # 本輪要去掉的解下標(biāo)for k in idex:FrontNo[tmp_List[k]] = FNOremove_index.append(tmp_List[k])FNO += 1 # 前言等級加1index -= set(remove_index) # 取差集，去掉已經(jīng)處理過的解，這就是為啥用set的原因，方便去掉return FrontNodef ENS(X):idex, sorted_X = n_dim_sort(X)FrontNo = ENS_ss(sorted_X) # 得到的是排序后的前沿，要恢復(fù)到最原始的順序# 恢復(fù)原來的順序N = len(X) # 解個數(shù)Last_FrontNo = [0] * Nfor i in range(N):Last_FrontNo[idex[i]] = FrontNo[i]return Last_FrontNoX = np.array([[2,2,5],[2,1,3],[1,2,3],[3,1,4],[2,1,4],[1,3,5],[1,3,3]]) # idex, sorted_X = n_dim_sort(X) # print(idex) # print(sorted_X) # print(ENS_ss(sorted_X))print(ENS(X))

后記

? ? ? ? 當(dāng)然，這個代碼只是初版，因為我自己的課題是離散的多目標(biāo)優(yōu)化，所以我的解空間其實都是離散的，有限的。因此我沒考慮擁擠距離之類的，本來解就不太夠，再刪除一些，搞不下去呀。搞連續(xù)多目標(biāo)的朋友，再獲得每個解的前沿等級的時候，后續(xù)選擇時還是需要考慮擁擠距離的

總結(jié)

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

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