一、前言
????????最近在準(zhǔn)備畢業(yè)論文，研究了一下主流的多目標(biāo)算法，對(duì)于NSGA-II，網(wǎng)上大部分代碼是全部是面向過(guò)程來(lái)實(shí)現(xiàn)的，本人更喜歡采用面向?qū)ο蟮姆绞?，故采用python面向?qū)ο髮?shí)現(xiàn)了一個(gè)示例，實(shí)現(xiàn)了對(duì)于二元多目標(biāo)問(wèn)題的求解。
二、算法基本流程
三、核心思想
1、非支配排序
這個(gè)簡(jiǎn)單的例子說(shuō)明了帕累托最優(yōu)的概念。上面我們有4個(gè)成員A, B, C和D，有兩個(gè)特征:身高和工資。現(xiàn)在，如果我們同時(shí)比較他們的身高和薪水，我們會(huì)發(fā)現(xiàn)這不是很直觀，因?yàn)樗麄冇卸鄠€(gè)目標(biāo)。
既然這兩個(gè)目標(biāo)越大越好，我們可以簡(jiǎn)單地對(duì)它們進(jìn)行比較。首先，我們觀察到A和B都比C和D多，所以我們說(shuō)A和B在身高和薪水上“支配”C和D。同理，C支配D，D可被A,B,C支配。
A和B呢?A比B高，但是工資低。相反，B面臨著同樣的情況。我們稱(chēng)這種情況為“非支配”。 如果我們能找到一組解它們不互相支配，也不受其他解支配，我們稱(chēng)之為"帕累托最優(yōu)"解。在上面的例子中，A和B都在帕累托最優(yōu)前沿。
幾個(gè)概念：
非支配解：假設(shè)任何二解S1 及S2 對(duì)所有目標(biāo)而言，S1均優(yōu)于S2，則我們稱(chēng)S1 支配S2，若S1 的解沒(méi)有被其他解所支配，則S1 稱(chēng)為非支配解（不受支配解），也稱(chēng)Pareto解（帕雷托解）
支配解：若解S2的所有目標(biāo)均劣于S1，則稱(chēng)S1優(yōu)于S2，也稱(chēng)S1支配S2，S2為受支配解。
Pareto前沿面：找到所有Pareto解之后，這些解組成的平面叫做Pareto前沿面（Non-dominated front）。在目標(biāo)函數(shù)較多時(shí)，前沿面通常為超曲面。
2、擁擠度
通俗的來(lái)講，當(dāng)需要舍棄某一rank平面的部分節(jié)點(diǎn)時(shí)，由于同一平面中的所有節(jié)點(diǎn)rank相同，不能通過(guò)rank來(lái)舍棄，而是要通過(guò)擁擠度來(lái)舍棄，以上就是擁擠度的作用。
算法更傾向于稀疏的點(diǎn)，也就是讓節(jié)點(diǎn)更可能的分散，可以有效地方式早熟和過(guò)擬合現(xiàn)象
3、精英選擇策略
每次都將父類(lèi)與子類(lèi)想結(jié)合，依次采用非支配排序、計(jì)算擁擠度來(lái)選擇父代。
文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-800569.html
四、python實(shí)現(xiàn)
github:? ?源代碼地址文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-800569.html
"""
author: pym
time: 2023.10.29
ide: pycharm2
"""
from collections import defaultdict
import numpy as np
import random
import matplotlib.pyplot as plt
import math
class Individual(object):
def __init__(self):
self.solution = None # 實(shí)際為nparray類(lèi)型，方便四則運(yùn)算
self.objective = defaultdict()
self.n = 0 # 解p被幾個(gè)解支配
self.rank = 0 # 解p所在層數(shù)
self.S = [] # 解p支配解的集合
self.distance = 0 # 擁擠度距離
def bound_process(self, bound_min, bound_max):
"""
對(duì)解向量 solution 中的每個(gè)分量進(jìn)行定義域判斷；超過(guò)最大值賦為最大值
:param bound_min: 定義域下限
:param bound_max: 定義域上限
:return:
"""
for i, item in enumerate(self.solution):
if item > bound_max:
self.solution[i] = bound_max
elif item < bound_min:
self.solution[i] = bound_min
def calculate_objective(self, objective_fun):
"""
計(jì)算目標(biāo)值
:param objective_fun: 目標(biāo)函數(shù)
:return:
"""
self.objective = objective_fun(self.solution)
def __lt__(self, other):
"""
重載小于號(hào)，只有當(dāng)solution中全部小于對(duì)方，才判斷小于
:param other: 比較的個(gè)體
:return: 1：小于 0：大于
"""
v1 = list(self.objective.values())
v2 = list(other.objective.values())
for i in range(len(v1)):
if v1[i] > v2[i]:
return 0
return 1
def fast_non_dominated_sort(P):
"""
非支配排序
:param P: 種群P
:return: F：分層結(jié)果，返回值類(lèi)型為dict，鍵為層號(hào)，值為list（該層中的個(gè)體）
"""
F = defaultdict(list)
for p in P:
p.S = []
p.n = 0
for q in P:
if p < q: # p支配q
p.S.append(q)
elif q < p: # q支配p
p.n += 1
if p.n == 0:
p.rank = 1
F[1].append(p)
i = 1
while F[i]:
Q = []
for p in F[i]:
for q in p.S:
q.n -= 1
if q.n == 0:
q.rank = i + 1
Q.append(q)
i += 1
F[i] = Q
return F
def crowding_distance_assignment(L):
"""
計(jì)算擁擠度
:param L: F[i]，是個(gè)list，為第i層的節(jié)點(diǎn)集合
:return:
"""
l = len(L)
# 初始化距離
for i in range(l):
L[i].distance = 0
# 遍歷每個(gè)目標(biāo)方向（有幾個(gè)優(yōu)化目標(biāo)，就有幾個(gè)目標(biāo)方向）
for m in L[0].objective.keys():
L.sort(key=lambda x: x.objective[m]) # 使用objective值排序
L[0].distance = float('inf')
L[l - 1].distance = float('inf')
f_max = L[l - 1].objective[m]
f_min = L[0].objective[m]
# 當(dāng)某一個(gè)目標(biāo)方向上的最大值和最小值相同時(shí)，會(huì)出現(xiàn)除0錯(cuò)誤
try:
for i in range(1, l - 1):
L[i].distance = L[i].distance + (L[i + 1].objective[m] - L[i - 1].objective[m]) / (f_max - f_min)
except Exception:
print(str(m) + "目標(biāo)方向上，最大值為：" + str(f_max) + " 最小值為：" + str(f_min))
def binary_tornament(ind1, ind2):
"""
二元錦標(biāo)賽：先選非支配排序靠前的，再選擁擠度低（即距離遠(yuǎn)）；如果都不行，則隨機(jī)
:param ind1: 個(gè)體1
:param ind2: 個(gè)體1
:return: 返回較優(yōu)的個(gè)體
"""
if ind1.rank != ind2.rank:
return ind1 if ind1.rank < ind2.rank else ind2
elif ind1.distance != ind2.distance:
return ind1 if ind1.distance > ind2.distance else ind2
else:
return ind1
def crossover_mutation(parent1, parent2, eta, bound_min, bound_max, objective_fun):
"""
交叉：二進(jìn)制交叉算子（SBX），變異：多項(xiàng)式變異（PM）
:param parent1: 父代1
:param parent2: 父代2
:param eta: 變異參數(shù)，越大則后代個(gè)體越逼近父代
:return:
"""
poplength = len(parent1.solution) # 解向量維數(shù)
# 初始化兩個(gè)后代個(gè)體
offspring1 = Individual()
offspring2 = Individual()
offspring1.solution = np.empty(poplength)
offspring2.solution = np.empty(poplength)
# 二進(jìn)制交叉
for i in range(poplength):
rand = random.random()
if rand < 0.5:
beta = (rand * 2) ** (1 / (eta + 1))
else:
beta = (1 / (2 * (1 - rand)))**(1 / (eta + 1))
offspring1.solution[i] = 0.5 * ((1 + beta) * parent1.solution[i] + (1 - beta) * parent2.solution[i])
offspring2.solution[i] = 0.5 * ((1 - beta) * parent1.solution[i] + (1 + beta) * parent2.solution[i])
# 多項(xiàng)式變異
for i in range(poplength):
mu = random.random()
if mu < 0.5:
delta = 2 * mu ** (1 / (eta + 1))
else:
delta = (1 - (2 * (1 - mu)) ** (1 / (eta + 1)))
# 只變異一個(gè)
offspring1.solution[i] = offspring1.solution[i] + delta
offspring1.bound_process(bound_min, bound_max)
offspring2.bound_process(bound_min, bound_max)
offspring1.calculate_objective(objective_fun)
offspring2.calculate_objective(objective_fun)
return [offspring1, offspring2]
def make_new_pop(P, eta, bound_min, bound_max, objective_fun):
"""
選擇交叉變異獲得新后代
:param P: 父代種群
:param eta: 變異參數(shù)，越大則后代個(gè)體越逼近父代
:param bound_min: 定義域下限
:param bound_max: 定義域上限
:param objective_fun: 目標(biāo)函數(shù)
:return: 子代種群
"""
popnum = len(P) # 種群個(gè)數(shù)
Q = []
# 二元錦標(biāo)賽選擇
for i in range(int(popnum / 2)):
# 從種群中隨機(jī)選擇兩個(gè)個(gè)體，進(jìn)行二元錦標(biāo)賽，選擇一個(gè)parent
i = random.randint(0, popnum - 1)
j = random.randint(0, popnum - 1)
parent1 = binary_tornament(P[i], P[j])
parent2 = parent1
while (parent1.solution == parent2.solution).all(): # 小細(xì)節(jié)all
i = random.randint(0, popnum - 1)
j = random.randint(0, popnum - 1)
parent2 = binary_tornament(P[i], P[j])
Two_offspring = crossover_mutation(parent1, parent2, eta, bound_min, bound_max, objective_fun)
Q.append(Two_offspring[0])
Q.append(Two_offspring[1])
return Q
def KUR(x):
"""
計(jì)算各個(gè)目標(biāo)方向上的目標(biāo)值
:param x: 解向量
:return: 字典：各個(gè)方向上的目標(biāo)值（key：目標(biāo)方向；value：目標(biāo)值）
"""
f = defaultdict(float)
poplength = len(x)
f[1] = 0
f[2] = 0
for i in range(poplength - 1):
f[1] = f[1] + (-10) * math.exp((-0.2) * (x[i] ** 2 + x[i + 1] ** 2) ** 0.5)
for i in range(poplength):
f[2] = f[2] + abs(x[i]) ** 0.8 + 5 * math.sin(x[i] ** 3)
return f
def plot_P(P):
"""
給種群繪圖
:param P: 種群集合
:return:
"""
X = []
Y = []
for ind in P:
X.append(ind.objective[1])
Y.append(ind.objective[2])
plt.xlabel('F1')
plt.ylabel('F2')
plt.scatter(X, Y)
def main():
# 初始化參數(shù)
generations = 250 # 迭代次數(shù)
popnum = 100 # 種群大小
eta = 1 # 變異分布參數(shù)
poplength = 3 # 單個(gè)個(gè)體解向量的維數(shù)
bound_min = -5
bound_max = 5
objective_fun = KUR
# 生成第一代種群
P = []
for i in range(popnum):
P.append(Individual())
P[i].solution = np.random.rand(poplength) * (bound_max - bound_min) + bound_min
P[i].bound_process(bound_min, bound_max) # 越界處理
P[i].calculate_objective(objective_fun) # 計(jì)算目標(biāo)值
# 快速非支配排序
fast_non_dominated_sort(P)
Q = make_new_pop(P, eta, bound_min, bound_max, objective_fun)
P_t = P # 當(dāng)前這一代的父代種群
Q_t = Q # 當(dāng)前這一代的子代種群
for gen_cur in range(generations):
R_t = P_t + Q_t
F = fast_non_dominated_sort(R_t)
P_n = [] # 即為P_t+1，表示下一代的父代
i = 1
# 依次將最高級(jí)別的支配平面中的節(jié)點(diǎn)放入到P_n中，之后更新非支配，直到達(dá)到要求的規(guī)模
while len(P_n) + len(F[i]) < popnum:
crowding_distance_assignment(F[i])
P_n += F[i]
i += 1
# 按照支配排序選完之后，再按照擁擠度來(lái)選擇
F[i].sort(key=lambda x: x.distance)
P_n = P_n + F[i][:popnum - len(P_n)]
Q_n = make_new_pop(P_n, eta, bound_min, bound_max, objective_fun)
# 將下一屆的父代和子代成為當(dāng)前的父代和子代
P_t = P_n
Q_t = Q_n
# 可視化
plt.clf()
plt.title("current generation: " + str(gen_cur + 1))
plot_P(P_t)
plt.pause(0.1)
plt.show()
return 0
if __name__ == "__main__":
main()
到了這里，關(guān)于NSGA-II 遺傳多目標(biāo)算法（python示例）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
