NSGA-ii 双目标遗传算法

论文原文《A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II》,可在IEEE上搜索。

简要叙述:编码交叉变异依然不变,在在此基础上加上了

  1. 快速非支配排序
  2. 拥挤度
  3. 精英策略

非支配排序

支配简述:对于一个点a,他的f1(a), f2(a)……fn(a)都比另一个点b,他的f1(b), f2(b)……fn(b)大,那么a支配b。
非支配即a他的所有值至少有一个小于b,且至少有一个大于b,那么,那么a和b非支配。

NSGA-ii 使用快速非支配排序,具体算法可见代码,根据代码思路自己去画一画。

非支配排序会最终将很多点分成不同rank的类,根据目标所需最大最小不同后续选择对rank不同的排序。

例子代码

拥挤度计算

个人认为很多时候可以用用拥挤距离替代,每个类都分别计算拥挤度,但最终很多时候在算法中只需要计算一个rank的拥挤度。

一个rank中的所有点,其中第一个点和最后一个点的拥挤距离为∞,中间点的距离即delta_y1 + delta_y2。拥挤距离可用delta_y1 / (max(y1) – min(y1)) + delta_y2 / (max(y2) – min(y2))

精英策略

每次从n个种群交叉变异后会生成2n的种群,通过精英策略选取其中前n个进行下一次迭代。策略如下:

  1. rank大/小的优先,看具体题目
  2. 如果有个rank加上后在超过了n个个体的种群,则进行拥挤度排序,选取最大/小的直到种群为n个个体。

Github上大佬的代码

发表评论

您的电子邮箱地址不会被公开。

浙ICP备2021019730-1    浙公网安备 33010902002953号
Copyright © 2022 PanCake