您现在的位置是：首页 > 技术教程 正文

NSGA-II:快速精英多目标遗传算法（论文+代码解读）

admin 阅读： 2024-03-22
后台-插件-广告管理-内容页头部广告（手机）

按照本文梳理的算法各个模块实现，NSGA-II完整代码见GitHub - bujibujibiuwang/NSGA-II-in-python: 《A fast and elitist multi-objective genetic algorithm: NSGA-II》

 

目录

1.介绍

2. NSGA-II

2.1 快速非支配排序

2.1.1 NSGA的传统非支配排序

2.1.2 NSGA-II的快速非支配排序

2.2 多样性保护(Diversity Preservation)

2.2.1 NSGA的共享函数方法(sharing function)

2.2.2  NSGA-II的拥挤距离方法(crowded-comparison)

2.3 NSGA-II主循环

3. 代码实现

3.1 第三方库

3.2 自定义

NSGA提出原文 Muiltiobjective Optimization Using Nondominated Sorting in Genetic Algorithms | MIT Press Journals & Magazine | IEEE Xplore

Srinivas, N., & Deb, K. (1994). Muiltiobjective Optimization Using Nondominated Sorting in Genetic Algorithms. Evolutionary Computation, 2(3), 221-248. doi:10.1162/evco.1994.2.3.221 

NSGA-II提出原文 A fast and elitist multiobjective genetic algorithm: NSGA-II

Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T. A. M. T. (2002). A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE transactions on evolutionary computation, 6(2), 182-197. 

NSGA-II作者实验室：Kalyanmoy Deb, Koenig Endowed Chair Professor 

pymoo库：实验室创建的python第三方库，实现了各种多目标优化算法pymoo: Multi-objective Optimization in Python 

geatpy2库：Geatpy是一个高性能实用型进化算法工具箱，提供许多已实现的进化算法中各项重要操作的库函数​​​​​​​，利用“定义问题类 + 调用算法模板”的模式来进行进化优化，可用于求解单目标优化、多目标优化、复杂约束优化、组合优化、混合编码进化优化等 Geatpy

1.介绍

针对多目标优化问题，可以用一些多目标进化算法(multiobjective evolutionary algorithms (MOEAs))找到多个帕累托最优解(Pareto-optimal)，比如非支配排序基因算法(nondominated sorting genetic algorithm (NSGA))。但是NSGA有以下问题

  • 非支配排序时间复杂度太高，为O(MN^{3})

    2.2 多样性保护(Diversity Preservation)

    2.2.1 NSGA的共享函数方法(sharing function)

    在NSGA中，与普通的GA相比，交叉和变异操作相同，区别在于选择操作。首先按照传统非支配排序的方法获得种群的第一非支配前沿(first nondominated front)，给第一非支配前沿中的每个个体分配一个相同的大的虚拟适应值(dummy fitness value)，也就是最初第一非支配前沿的每个个体选择的可能性相同。接下来为了保留每层前沿解的多样性，使用共享函数方法(sharing function)得到每个解的共享适应值(shared fitness value)。共享函数如下，其中d_{ij}

    2.2.2  NSGA-II的拥挤距离方法(crowded-comparison)

    共享函数方法有两个问题

    • 用共享函数维持解的分布的性能很大程度取决于参数\sigma _{share}

      从几何角度理解拥挤距离，以两个目标函数为例，下图中黑点和白点分别为两个非支配前沿，对于解i，从与i在同一非支配前沿中选择与解i最相近的两个点i-1和i+1为顶点组成一个长方形(cuboid)，拥挤距离即为长方形平均边长。

       （2）拥挤度比较算子(Crowded-Comparison Operator) 

      在计算完每个解的拥挤距离后，从一定程度上来说，某个解的拥挤距离越小，这个解被其他解拥挤的程度越高。接下来通过拥挤度比较算子来选择解实现更广的帕累托最优解分布。种群中的每个个体都有两个属性：

      • 非支配等级i_{rank}​​​​​​​ 

        综上，有三个创新点，一个快速非支配排序方法，一个快速估计拥挤距离的方法，一个简单的拥挤度比较算子，接下来描述NSGA-II的主循环。

        2.3 NSGA-II主循环

        先明确以下概念

        • elitism：精英保留策略，核心思想是把群体在进化过程中迄今出现的最好个体不进行遗传操作而直接复制到下一代中，理论上证明了具有精英保留的标准遗传算法是全局收敛的
        • tournament selection：联赛选择算法，每次从种群中取一定数量（n）的个体(放回抽样)，选择其中适应度较好的进入子代种群

        随机生成初始种群P(0)，基于非支配排序P(0)，每个解都赋予一个适应值与其前沿等级相同(1是最好的，2其次....），假设问题是要最小化。起初使用联赛选择，重组和变异获得一个子代Q(0)，NSGA-II使用了精英选择策略，因此后面迭代过程会不同。假设现在是第t代种群，下面一步步描述结合了精英选择，快速非支配排序，拥挤距离等方法的NSGA-II算法过程。

        首先生成一个基于P(t)和Q(t)得到的组合种群R(t)，R(t)大小为2N，N为种群大小。对R(t)执行快速非支配排序，属于R(t)的第一非支配前沿F1中的解是当前最好的解，因此要重点选择。如果F1长度小于N，那么选择F1添加到新一代种群P(t+1)中，同样操作在F2,F3....，直到P(t+1)剩余解数量不足以再合并一个完整的非支配前沿。假设F(i)是最后一个无法容纳的非支配前沿，按照拥挤距离给F(i)中的元素降序排列，选择排序后靠前的元素添加到P(t+1)中直到P(t+1)大小为N。对P(t+1)执行选择，交叉，变异生成新种群Q(t+1)，此处的选择虽然也是联赛选择方法，但是选择标准是基于拥挤度比较算子。这个算子需要每个解的等级和拥挤距离，因此在组成种群P(t+1)的时候就可以计算这两个属性。P(t+1)是从大小为2N的R(t)中按照前沿等级和拥挤距离生成的大小为N的种群，而R(t)包含了所有之前和现在的种群成员，确保了精英选择策略。算法流程如下图

         分析整个过程的时间复杂度如下， NSGA-II的整体时间复杂度为O(MN^{2})

         和pymmo相比，geatpy2支持自定义问题，提供模块化的算法框架，示例代码如下

        1. import geatpy as ea
        2. import numpy as np
        4. # 构建问题
        5. r = 1 # 目标函数需要用到的额外数据
        6. @ea.Problem.single
        7. def evalVars(Vars): # 定义目标函数（含约束）
        8. f = np.sum((Vars - r) ** 2) # 计算目标函数值
        9. x1 = Vars[0]
        10. x2 = Vars[1]
        11. CV = np.array([(x1 - 0.5)**2 - 0.25,
        12. (x2 - 1)**2 - 1]) # 计算违反约束程度
        13. return f, CV
        15. problem = ea.Problem(name='soea quick start demo',
        16. M=1, # 目标维数
        17. maxormins=[1], # 目标最小最大化标记列表，1：最小化该目标；-1：最大化该目标
        18. Dim=5, # 决策变量维数
        19. varTypes=[0, 0, 1, 1, 1], # 决策变量的类型列表，0：实数；1：整数
        20. lb=[-1, 1, 2, 1, 0], # 决策变量下界
        21. ub=[1, 4, 5, 2, 1], # 决策变量上界
        22. evalVars=evalVars)
        23. # 构建算法
        24. algorithm = ea.soea_SEGA_templet(problem,
        25. ea.Population(Encoding='RI', NIND=20),
        26. MAXGEN=50, # 最大进化代数。
        27. logTras=1, # 表示每隔多少代记录一次日志信息，0表示不记录。
        28. trappedValue=1e-6, # 单目标优化陷入停滞的判断阈值。
        29. maxTrappedCount=10) # 进化停滞计数器最大上限值。
        30. # 求解
        31. res = ea.optimize(algorithm, seed=1, verbose=True, drawing=1, outputMsg=True, drawLog=False, saveFlag=Tr

        关于第三方库的内容可自行查阅官方网站

        3.2 自定义

        按照前面的算法流程分别实现快速非支配排序模块和拥挤距离计算模块

        （1）快速非支配排序模块

        1. """
        2. 两个目标函数为例
        3. 输入：种群每个解的两个目标函数值
        4. 输入：所有非支配前沿
        5. """
        6. def fast_non_dominated_sort(values1, values2):
        7. size = len(values1) # 种群大小
        8. s = [[] for _ in range(size)] # 每个解的被支配集合
        9. n = [0 for _ in range(size)] # 每个解的支配数
        10. rank = [0 for _ in range(size)] # 每个解的等级
        11. fronts = [[]] # 所有非支配前沿
        13. for p in range(size): # 遍历所有解
        14. s[p] = [] # 初始化非支配集合和支配数
        15. n[p] = 0
        16. for q in range(size): # 判断p和q支配情况
        17. # 如果p支配q，增加q到p的被支配集合
        18. if values1[p] >= values1[q] and values2[p] >= values2[q] \
        19. and ((values1[q] == values1[p]) + (values2[p] == values2[q])) != 2:
        20. s[p].append(q)
        21. # 如果q支配p，p的支配数+1
        22. elif values1[q] >= values1[p] and values2[q] >= values2[p] \
        23. and ((values1[q] == values1[p]) + (values2[p] == values2[q])) != 2:
        24. n[p] += 1
        25. # n[p]=0的解等级设为0，增加到第一前沿
        26. if n[p] == 0:
        27. rank[p] = 0
        28. fronts[0].append(p)
        29. # 依次确定其它层非支配前沿
        30. i = 0
        31. while fronts[i]:
        32. Q = []
        33. for p in fronts[i]:
        34. for q in s[p]:
        35. n[q] = n[q] - 1
        36. if n[q] == 0:
        37. rank[q] = i + 1
        38. if q not in Q:
        39. Q.append(q)
        40. i = i + 1
        41. fronts.append(Q)
        43. del fronts[-1]
        44. return fronts

        （2）拥挤距离计算模块

        1. """
        2. 输入：所有解所有目标的函数值，要计算的前沿，目标数
        3. 输出：输入前沿每个解的拥挤距离
        4. """
        5. def crowed_distance_assignment(values1, values2, front):
        6. length = len(front)
        7. sorted_front1 = sorted(front, key=lambda x: values1[x])
        8. sorted_front2 = sorted(front, key=lambda x: values2[x])
        9. dis_table = {sorted_front1[0]: np.inf, sorted_front1[-1]: np.inf, sorted_front2[0]: np.inf, sorted_front2[-1]: np.inf}
        10. for i in range(1, length - 1):
        11. k = sorted_front1[i]
        12. dis_table[k] = dis_table.get(k, 0)+(values1[sorted_front1[i+1]]-values1[sorted_front1[i-1]])/(max(values1)-min(values1))
        13. for i in range(1, length - 1):
        14. k = sorted_front1[i]
        15. dis_table[k] = dis_table[k]+(values2[sorted_front2[i+1]]-values2[sorted_front2[i-1]])/(max(values2)-min(values2))
        16. distance = [dis_table[a] for a in front]
        17. return distance
标签:
声明

1.本站遵循行业规范，任何转载的稿件都会明确标注作者和来源；2.本站的原创文章，请转载时务必注明文章作者和来源，不尊重原创的行为我们将追究责任；3.作者投稿可能会经我们编辑修改或补充。

在线投稿：投稿 站长QQ：1888636

后台-插件-广告管理-内容页尾部广告（手机）
相关文章
关注我们

扫一扫关注我们，了解最新精彩内容

搜索
排行榜
最近发表
标签列表