当前位置:   article > 正文

多目标进化算法——NSGA-II(python实现)_nsga2算法python

nsga2算法python

一、多目标优化的基本流程

        ·初始化N个个体(也就是N个解)

        ·计算适应值(也就是函数值,多目标也就是有多个函数值\适应值)

        ·利用旧的个体产生新的个体

                --各种策略:遗传算法、粒子群、模拟退火等等,只是这里是遗传算法GA

        ·通过对比选择得到新一轮的个体

                --Rank,非支配排序,得到一层一层的非支配解

                --对于同一个Rank内的排序,通过拥挤度来排序,拥挤度越大越好

        ·循环到你希望它循环的那个次数

二、代码实现

·Individual,定义了一个individual类,表示一个个体,包含了一些基本的属性和方法,用于表示解向量、目标函数、支配关系等

·fast_non_dominated_sort(P),对于种群P进行快速非支配排序

·crowding_distance_assignment(L),为一层Rank中的个体计算拥挤度距离

·KUP(x),目标函数

  1. """
  2. 多目标进化算法——NSGA-II(python实现)
  3. --解决的是多目标的数学函数,有两个不同的输出结果
  4. """
  5. from collections import defaultdict
  6. import numpy as np
  7. import random
  8. import matplotlib.pyplot as plt
  9. import math
  10. #note:定义了一个individual类,表示一个个体,包含了一些基本的属性和方法,用于表示解向量、目标函数、支配关系等
  11. class Individual(object):
  12. def __init__(self):
  13. # 初始化一个个体的实例,有下面几个属性:
  14. self.solution = None # 实际赋值中是一个 nparray 类型,方便进行四则运算,用于存储解向量
  15. self.objective = defaultdict() # 属性用于存储目标函数值 在多目标优化问题中
  16. # 通常有多个目标函数需要优化self.objective 就是一个包含多个目标函数值的字典
  17. self.n = 0 # 解p被几个解所支配,是一个数值(左下部分点的个数)
  18. self.rank = 0 # 解所在第几层
  19. self.S = [] # 解p支配哪些解,是一个解集合(右上部分点的内容)
  20. self.distance = 0 # 拥挤度距离
  21. def bound_process(self, bound_min, bound_max):
  22. """
  23. 对解向量 solution 中的每个分量进行定义域判断,超过最大值,将其赋值为最大值;小于最小值,赋值为最小值
  24. :param bound_min: 定义域下限
  25. :param bound_max:定义域上限
  26. :return:
  27. """
  28. for i, item in enumerate(self.solution):
  29. if item > bound_max:
  30. self.solution[i] = bound_max
  31. elif item < bound_min:
  32. self.solution[i] = bound_min
  33. def calculate_objective(self, objective_fun):
  34. # 这个方法的目的是将解向量转化为目标函数的值 objective_fun 可能是一个返回多个目标函数值的函数。
  35. # 调用 calculate_objective(objective_fun) 计算个体的目标函数值,并将结果存储在 self.objective 中,以便进一步使用。
  36. self.objective = objective_fun(self.solution)
  37. # 重载小于号“<”,支配关系比较
  38. def __lt__(self, other):
  39. # 获取两个个体的目标函数值,分别存储在 v1 和 v2 中
  40. v1 = list(self.objective.values())
  41. v2 = list(other.objective.values())
  42. # 逐个比较对应位置的值
  43. for i in range(len(v1)):
  44. if v1[i] > v2[i]:
  45. return 0 # 但凡有一个位置是 v1大于v2的 直接返回0,如果相等的话比较下一个目标值
  46. return 1
  47. # 如果目标函数是3个及以上呢 --目标函数是几个并没有什么影响
  48. # 如果比较的支配方向不是越小越好呢? --可以加入一个变量 larger_is_better,用于表示目标函数越大越好的情况。在重载中分类讨论
  49. def main():
  50. # 初始化/参数设置
  51. generations = 500 # 迭代次数
  52. popnum = 100 # 种群大小
  53. eta = 1 # 变异分布参数,该值越大则产生的后代个体逼近父代的概率越大。Deb建议设为 1
  54. # 问题定义
  55. # poplength = 30 # 单个个体解向量的维数
  56. # bound_min = 0 # 定义域
  57. # bound_max = 1
  58. # objective_fun = ZDT1
  59. poplength = 3 # 单个个体解向量的维数
  60. bound_min = -5 # 定义域
  61. bound_max = 5
  62. objective_fun = KUR # 目标函数
  63. # 生成第一代种群
  64. P = [] # 创建一个空列表 P,用于存储个体对象
  65. for i in range(popnum):
  66. # 通过循环生成 popnum 个个体,并将它们添加到列表 P 中。
  67. P.append(Individual())
  68. P[i].solution = np.random.rand(poplength) * (bound_max - bound_min) + bound_min # 随机生成个体可行解
  69. P[i].bound_process(bound_min, bound_max) # 定义域越界处理
  70. P[i].calculate_objective(objective_fun) # 计算目标函数值
  71. # 输入初始父代种群P -> 非支配排序
  72. fast_non_dominated_sort(P)
  73. # 生成子代种群Q
  74. Q = make_new_pop(P, eta, bound_min, bound_max, objective_fun)
  75. P_t = P # 当前这一届的父代种群
  76. Q_t = Q # 当前这一届的子代种群
  77. # note:循环迭代gen_cur次,每次都合并新旧种群-->排序后得到对应数量popnum新的父种群P_n-->通过交叉变异产生新的子代种群Q_n
  78. # -->将新旧种群信息更新到变量中,准备下一次循环的迭代合并-->绘制这一次此时的父种群P_n在图上的位置
  79. for gen_cur in range(generations):
  80. R_t = P_t + Q_t # 将当前父代种群和子代种群合并成一个总种群
  81. F = fast_non_dominated_sort(R_t) # 对合并后的总种群进行快速非支配排序,得到不同层的个体集合。
  82. P_n = [] # 即为P_t+1,表示下一届的父代
  83. i = 1
  84. while len(P_n) + len(F[i]) < popnum: # until the parent population is filled
  85. crowding_distance_assignment(F[i]) # calculate crowding-distance in F_i
  86. P_n = P_n + F[i] # 将第 i 层的个体加入下一代父代种群。
  87. i = i + 1 # 切换到下一层
  88. F[i].sort(key=lambda x: x.distance) # 数量将要达到popnum时,对下一层的个体按照拥挤度距离排序
  89. P_n = P_n + F[i][:popnum - len(P_n)] # 将排序后的个体加入下一代父代种群,以保证种群大小不超过 popnum
  90. Q_n = make_new_pop(P_n, eta, bound_min, bound_max,
  91. objective_fun) # 使用选择、交叉和变异操作创建新的子代种群 Q_n。
  92. # 求得下一届的父代和子代成为当前届的父代和子代,,进入下一次迭代 《=》 t = t + 1
  93. P_t = P_n
  94. Q_t = Q_n
  95. # 绘图
  96. plt.clf()
  97. plt.title('current generation_P_t:' + str(gen_cur + 1)) # 绘制当前循环选出来的父代的图
  98. plot_P(P_t)
  99. plt.pause(0.1)
  100. # plt.title('current generation_Q_t:' + str(gen_cur + 1)) # 绘制当前循环生成的子代的图
  101. # plot_P(Q_t)
  102. # plt.pause(0.1)
  103. plt.show()
  104. return 0
  105. #note 对种群p进行快速非支配排序
  106. def fast_non_dominated_sort(P):
  107. """
  108. 非支配排序
  109. :param P: 种群 P
  110. :return F: F=(F_1, F_2, ...) 将种群 P 分为了不同的层, 返回值类型是dict,键为层号,值为 List 类型,存放着该层的个体
  111. """
  112. F = defaultdict(list) # F 一个字典,键为非支配层的层号rank,值为一个列表--存储该层的个体
  113. for p in P:
  114. p.S = [] # 支配的集合
  115. p.n = 0 # 被支配的个数
  116. # 对于每个个体 p,遍历种群中的其他个体 q,根据 p 与 q 的支配关系,更新 p 的支配集合 S 和被支配计数器 n。
  117. for q in P:
  118. if p < q: # if p dominate q
  119. p.S.append(q) # Add q to the set of solutions dominated by p
  120. elif q < p:
  121. p.n += 1 # Increment the domination counter of p
  122. # 如果 n 为零,则表示 p 不被任何个体支配,将其分配到第一层 F[1] 中
  123. if p.n == 0:
  124. p.rank = 1
  125. F[1].append(p)
  126. # 接下来,对于每一层 F[i],更新被当前层个体支配的个体被支配计数器,并将新的非支配个体添加到下一层 F[i+1]。
  127. i = 1
  128. while F[i]:
  129. Q = []
  130. for p in F[i]:
  131. for q in p.S:
  132. q.n = q.n - 1
  133. if q.n == 0:
  134. q.rank = i + 1
  135. Q.append(q)
  136. i = i + 1
  137. F[i] = Q
  138. return F
  139. # todo 真想把 eta, bound_min, bound_max, objective_fun 设为全局变量-->走到哪带到那,一直往下传
  140. # note 输入一个P種群,和四个主函数中的初始化参数,得到子代种群Q
  141. def make_new_pop(P, eta, bound_min, bound_max, objective_fun):
  142. """
  143. use select,crossover and mutation to create a new population Q
  144. :param P: 父代种群
  145. :param eta: 变异分布参数,该值越大则产生的后代个体逼近父代的概率越大。Deb建议设为 1
  146. :param bound_min: 定义域下限
  147. :param bound_max: 定义域上限
  148. :param objective_fun: 目标函数
  149. :return Q : 子代种群
  150. """
  151. popnum = len(P)
  152. Q = []
  153. # binary tournament selection 二元锦标赛选择父代
  154. for i in range(int(popnum / 2)): # 让父代种群个数为双数 能避免不必要的麻烦
  155. # 从种群中随机选择两个个体,进行二元锦标赛,选择出一个 parent1
  156. i = random.randint(0, popnum - 1)
  157. j = random.randint(0, popnum - 1)
  158. parent1 = binary_tournament(P[i], P[j])
  159. # 从种群中随机选择两个个体,进行二元锦标赛,选择出一个 parent2
  160. i = random.randint(0, popnum - 1)
  161. j = random.randint(0, popnum - 1)
  162. parent2 = binary_tournament(P[i], P[j])
  163. while (parent1.solution == parent2.solution).all(): # 如果选择到的两个父代完全一样,则重选另一个
  164. # 上面的.all可能导致警告,因为如果 parent1.solution不是数组,而是单个布尔值,就不应该使用 .all() 方法
  165. # 但是我们知道解向量是单个布尔值,所以可以安全地忽略这个警告。
  166. i = random.randint(0, popnum - 1)
  167. j = random.randint(0, popnum - 1)
  168. parent2 = binary_tournament(P[i], P[j])
  169. # parent1 和 parent1 进行交叉,变异 产生 2 个子代
  170. Two_offspring = crossover_mutation(parent1, parent2, eta, bound_min, bound_max, objective_fun)
  171. # 产生的子代进入子代种群
  172. Q.append(Two_offspring[0])
  173. Q.append(Two_offspring[1])
  174. return Q
  175. #note:为一层中的个体计算拥挤度距离
  176. def crowding_distance_assignment(L):
  177. """ 传进来的参数应该是L = F(i),类型是List,传进来的一层rank的一个list集合"""
  178. l = len(L) # number of solution in F F层共有多少个个体
  179. for i in range(l):
  180. L[i].distance = 0 # initialize distance 初始化所有个体的拥挤度为0
  181. for m in L[0].objective.keys(): # 对每个目标距离进行拥挤度距离计算
  182. L.sort(key=lambda x: x.objective[m]) # sort using each objective value根据当前目标方向值对个体进行排序。
  183. # 将第一个和最后一个个体的拥挤度距离设为无穷大,确保它们总是被选择。
  184. L[0].distance = float('inf')
  185. L[l - 1].distance = float('inf') # so that boundary points are always selected
  186. # 排序是由小到大的,所以最大值和最小值分别是 L[l-1] 和 L[0]
  187. f_max = L[l - 1].objective[m]
  188. f_min = L[0].objective[m]
  189. # 当某一个目标方向上的最大值和最小值相同时,此时会发生除零错,这里采用异常处理机制来解决
  190. try:
  191. for i in range(1, l - 1): # for all other points
  192. L[i].distance = L[i].distance + (L[i + 1].objective[m] - L[i - 1].objective[m]) / (f_max - f_min)
  193. except Exception:
  194. print(str(m) + "目标方向上,最大值为" + str(f_max) + "最小值为" + str(f_min))
  195. # note 二元锦标赛选择函数--选择出输入的两个个体中较优的个体
  196. def binary_tournament(ind1, ind2):
  197. """
  198. 二元锦标赛
  199. :param ind1:个体1号
  200. :param ind2: 个体2号
  201. :return:返回较优的个体
  202. """
  203. if ind1.rank != ind2.rank: # 如果两个个体有支配关系,即在两个不同的rank中,选择rank小的
  204. return ind1 if ind1.rank < ind2.rank else ind2
  205. elif ind1.distance != ind2.distance: # 如果两个个体rank相同,比较拥挤度距离,选择拥挤读距离大的
  206. # 如果是初代父种群P生成第一子代时,此时的每一个解决方案个体还没有distance的赋值,默认都是0
  207. return ind1 if ind1.distance > ind2.distance else ind2
  208. else: # 如果rank和拥挤度都相同,返回任意一个都可以
  209. return ind1
  210. # note:两个父代个体进行交叉-变异 返回两个子代个体
  211. def crossover_mutation(parent1, parent2, eta, bound_min, bound_max, objective_fun):
  212. """
  213. 交叉方式使用二进制交叉算子(SBX),变异方式采用多项式变异(PM)
  214. :param parent1: 父代1
  215. :param parent2: 父代2
  216. :param eta: 变异分布参数,该值越大则产生的后代个体逼近父代的概率越大。Deb建议设为 1
  217. :param bound_min: 定义域下限
  218. :param bound_max: 定义域上限
  219. :param objective_fun: 目标函数
  220. :return: 2 个子代
  221. """
  222. poplength = len(parent1.solution) # 获得解向量的维度或者分量个数,表示解向量的维度
  223. offspring1 = Individual()
  224. offspring2 = Individual()
  225. # 创建一个指定长度的一维数组,该数组的元素值是未初始化的,即它们可能包含任意值。这个数组将被用来存储新生成的子代个体的解向量。
  226. # np.empty 仅仅分配了内存空间而不初始化数组元素的值
  227. offspring1.solution = np.empty(poplength)
  228. offspring2.solution = np.empty(poplength)
  229. # 二进制交叉
  230. for i in range(poplength):
  231. rand = random.random() # 生成一个在 [0, 1) 范围内的随机数
  232. # beta的计算采用了 SBX 的公式,其中 eta 是变异分布参数,用于调整交叉的程度。
  233. beta = (rand * 2) ** (1 / (eta + 1)) if rand < 0.5 else (1 / (2 * (1 - rand))) ** (1.0 / (eta + 1))
  234. offspring1.solution[i] = 0.5 * ((1 + beta) * parent1.solution[i] + (1 - beta) * parent2.solution[i])
  235. offspring2.solution[i] = 0.5 * ((1 - beta) * parent1.solution[i] + (1 + beta) * parent2.solution[i])
  236. # 多项式变异
  237. # TODO 变异的时候只变异一个,不要两个都变,不然要么出现早熟现象,要么收敛速度巨慢 why?
  238. # 通过只变异一个个体,可以确保种群中的每个个体都有机会经历一些变化,而不会太快地趋向于某个方向。这有助于维持多样性,促使算法更好地探索搜索空间。
  239. # 另一方面,如果每次都同时变异两个个体,可能导致整个种群在搜索空间中以较大的步伐移动,这可能使得算法更容易陷入局部最优解,而不太容易跳出这些局部最优解。
  240. for i in range(poplength):
  241. mu = random.random() # 生成一个在 [0, 1) 范围内的随机数
  242. # delta 的计算采用了 PM 的公式,其中 eta 是变异分布参数,用于调整变异的程度。
  243. delta = 2 * mu ** (1 / (eta + 1)) if mu < 0.5 else (1 - (2 * (1 - mu)) ** (1 / (eta + 1)))
  244. offspring1.solution[i] = offspring1.solution[i] + delta
  245. # 定义域越界处理
  246. offspring1.bound_process(bound_min, bound_max)
  247. offspring2.bound_process(bound_min, bound_max)
  248. # 计算目标函数值
  249. offspring1.calculate_objective(objective_fun)
  250. offspring2.calculate_objective(objective_fun)
  251. return [offspring1, offspring2]
  252. #note 测试目标函数
  253. def ZDT1(x):
  254. """
  255. 测试函数——ZDT1
  256. :parameter
  257. :param x: 为 m 维向量,表示个体的具体解向量
  258. :return f: 为两个目标方向上的函数值
  259. """
  260. poplength = len(x)
  261. f = defaultdict(float)
  262. g = 1 + 9 * sum(x[1:poplength]) / (poplength - 1)
  263. f[1] = x[0]
  264. f[2] = g * (1 - pow(x[0] / g, 0.5))
  265. return f
  266. #note 测试目标函数
  267. def ZDT2(x):
  268. poplength = len(x)
  269. f = defaultdict(float)
  270. g = 1 + 9 * sum(x[1:poplength]) / (poplength - 1)
  271. f[1] = x[0]
  272. f[2] = g * (1 - (x[0] / g) ** 2)
  273. return f
  274. #note:目标函数KUR,接受一个解向量x作为输入,计算并且返回一个包含两个目标函数值的字典f。
  275. def KUR(x):
  276. f = defaultdict(float) # 定义这个字典f,存放后续的两个目标函数值
  277. poplength = len(x)
  278. f[1] = 0
  279. f[2] = 0
  280. # 第一个目标函数 f[1] 是一个累加项,涉及解向量中相邻两个变量的平方和的指数衰减。
  281. for i in range(poplength - 1):
  282. f[1] = f[1] + (-10) * math.exp((-0.2) * (x[i] ** 2 + x[i+1] ** 2) ** 0.5)
  283. # 第二个目标函数 f[2] 是一个累加项,包含每个变量的绝对值的指数和一个正弦函数。
  284. for i in range(poplength):
  285. f[2] = f[2] + abs(x[i]) ** 0.8 + 5 * math.sin(x[i] ** 3)
  286. return f
  287. def plot_P(P):
  288. """
  289. 假设目标就俩,给个种群绘图
  290. :param P:
  291. :return:
  292. """
  293. X = []
  294. Y = []
  295. for ind in P:
  296. X.append(ind.objective[1])
  297. Y.append(ind.objective[2])
  298. plt.xlabel('F1')
  299. plt.ylabel('F2')
  300. plt.scatter(X, Y)
  301. # 程序入口
  302. if __name__ == '__main__':
  303. main()

三、参考资料

多目标进化算法——NSGA-II(python实现)_nsga python-CSDN博客

通俗易懂讲算法-多目标优化-NSGA-II(附代码讲解)哔哩哔哩bilibili

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/Monodyee/article/detail/459771
推荐阅读
相关标签
  

闽ICP备14008679号