NSGA-II(非支配排序遗传算法II)详解与实现

devtools/2025/1/6 12:54:17/

NSGA-II(非支配排序遗传算法II)详解与实现

1. 算法简介

NSGA-II(Non-dominated Sorting Genetic Algorithm II)是一种高效的多目标优化算法，由Deb等人在2002年提出。它主要解决多个目标之间相互冲突的优化问题。

1.1 核心特点

  1. 快速非支配排序

    • 时间复杂度：O(MN²)
    • M为目标数量，N为种群大小
    • 比NSGA的O(MN³)更高效

  2. 拥挤度距离

    • 保持种群多样性
    • 不需要用户定义分享参数
    • 避免使用小生境技术

  3. 精英策略

    • 保留父代和子代中的优秀个体
    • 确保最优解不会丢失
    • 加快收敛速度

1.2 基本概念

  1. 帕累托支配关系

    对于最小化问题，解x支配解y，需满足：

    • ∀ i : f i ( x ) ≤ f i ( y ) \forall i: f_i(x) \leq f_i(y) ∀i:fi​(x)≤fi​(y)
    • ∃ j : f j ( x ) < f j ( y ) \exists j: f_j(x) < f_j(y) ∃j:fj​(x)<fj​(y)

  2. 帕累托前沿

    • 由非支配解构成
    • 表示目标之间的最优折中
    • 为决策者提供选择空间

2. 算法流程

2.1 主要步骤

  1. 初始化种群P(t)
  2. 生成子代Q(t)
  3. 合并R(t) = P(t) ∪ Q(t)
  4. 对R(t)进行非支配排序
  5. 根据排序和拥挤度选择新种群P(t+1)
  6. 重复步骤2-5直到满足终止条件

2.2 关键组件

  1. 快速非支配排序
def fast_non_dominated_sort(population, objectives):"""快速非支配排序返回：各个等级的解集合"""n = len(population)domination_count = np.zeros(n)  # 被支配次数dominated_solutions = [[] for _ in range(n)]  # 支配的解fronts = [[]]  # 非支配等级# 计算支配关系for i in range(n):for j in range(i + 1, n):if dominates(objectives[i], objectives[j]):dominated_solutions[i].append(j)domination_count[j] += 1elif dominates(objectives[j], objectives[i]):dominated_solutions[j].append(i)domination_count[i] += 1# 找出第一个非支配前沿for i in range(n):if domination_count[i] == 0:fronts[0].append(i)# 生成其他等级的前沿i = 0while fronts[i]:next_front = []for j in fronts[i]:for k in dominated_solutions[j]:domination_count[k] -= 1if domination_count[k] == 0:next_front.append(k)i += 1fronts.append(next_front)return fronts[:-1]  # 去掉最后一个空集
  1. 拥挤度距离计算
def crowding_distance(objectives, front):"""计算一个前沿中各个解的拥挤度距离"""n = len(front)if n <= 2:return [float('inf')] * ndistances = [0] * nm = objectives.shape[1]  # 目标数量for i in range(m):# 对每个目标进行排序sorted_idx = sorted(range(n), key=lambda k: objectives[front[k], i])# 端点设为无穷大distances[sorted_idx[0]] = float('inf')distances[sorted_idx[-1]] = float('inf')# 计算中间点的距离obj_range = objectives[front[sorted_idx[-1]], i] - objectives[front[sorted_idx[0]], i]if obj_range == 0:continuefor j in range(1, n-1):distances[sorted_idx[j]] += (objectives[front[sorted_idx[j+1]], i] - objectives[front[sorted_idx[j-1]], i]) / obj_rangereturn distances

3. 完整实现

import numpy as np
from typing import List, Tuple, Unionclass NSGA2:def __init__(self,pop_size: int = 100,n_generations: int = 100,n_objectives: int = 2,n_variables: int = 30,mutation_rate: float = 0.01,crossover_rate: float = 0.9,variable_bounds: Union[List[Tuple[float, float]], None] = None):self.pop_size = pop_sizeself.n_generations = n_generationsself.n_objectives = n_objectivesself.n_variables = n_variablesself.mutation_rate = mutation_rateself.crossover_rate = crossover_rate# 如果没有指定变量范围，默认为[0,1]if variable_bounds is None:self.variable_bounds = [(0, 1)] * n_variableselse:self.variable_bounds = variable_boundsdef create_offspring(self, population: np.ndarray) -> np.ndarray:"""生成子代"""offspring = np.zeros_like(population)for i in range(0, self.pop_size, 2):# 选择父代parent1_idx = self.tournament_selection(population)parent2_idx = self.tournament_selection(population)# 交叉if np.random.random() < self.crossover_rate:child1, child2 = self.simulated_binary_crossover(population[parent1_idx],population[parent2_idx])else:child1 = population[parent1_idx].copy()child2 = population[parent2_idx].copy()# 变异child1 = self.polynomial_mutation(child1)child2 = self.polynomial_mutation(child2)offspring[i] = child1offspring[i+1] = child2return offspringdef tournament_selection(self, population: np.ndarray, tournament_size: int = 2) -> int:"""锦标赛选择"""idx = np.random.randint(0, self.pop_size, tournament_size)return idx[0]  # 简化版本，实际应该比较个体的非支配等级和拥挤度def simulated_binary_crossover(self, parent1: np.ndarray, parent2: np.ndarray,eta: float = 20) -> Tuple[np.ndarray, np.ndarray]:"""模拟二进制交叉"""child1 = np.zeros_like(parent1)child2 = np.zeros_like(parent2)for i in range(self.n_variables):if np.random.random() < 0.5:child1[i] = parent1[i]child2[i] = parent2[i]continue# 模拟二进制交叉beta = self._get_beta(eta)child1[i] = 0.5 * ((1 + beta) * parent1[i] + (1 - beta) * parent2[i])child2[i] = 0.5 * ((1 - beta) * parent1[i] + (1 + beta) * parent2[i])# 边界处理lower, upper = self.variable_bounds[i]child1[i] = np.clip(child1[i], lower, upper)child2[i] = np.clip(child2[i], lower, upper)return child1, child2def _get_beta(self, eta: float) -> float:"""获取交叉参数beta"""u = np.random.random()if u <= 0.5:return (2 * u) ** (1 / (eta + 1))return (1 / (2 * (1 - u))) ** (1 / (eta + 1))def polynomial_mutation(self, individual: np.ndarray, eta: float = 20) -> np.ndarray:"""多项式变异"""child = individual.copy()for i in range(self.n_variables):if np.random.random() > self.mutation_rate:continuelower, upper = self.variable_bounds[i]delta = upper - lower# 多项式变异r = np.random.random()if r < 0.5:delta_l = (2 * r) ** (1 / (eta + 1)) - 1else:delta_l = 1 - (2 * (1 - r)) ** (1 / (eta + 1))child[i] += delta_l * deltachild[i] = np.clip(child[i], lower, upper)return childdef calculate_objectives(self, population: np.ndarray) -> np.ndarray:"""计算目标函数值"""return np.array([zdt1(x) for x in population])def select_by_crowding(self, front: List[int], crowding_dist: List[float],n_select: int) -> List[int]:"""根据拥挤度距离选择个体"""sorted_idx = sorted(range(len(front)),key=lambda k: crowding_dist[k],reverse=True)return [front[i] for i in sorted_idx[:n_select]]def evolve(self, initial_population: np.ndarray) -> np.ndarray:"""执行进化过程"""population = initial_populationfor gen in range(self.n_generations):# 生成子代offspring = self.create_offspring(population)# 合并父代和子代combined_pop = np.vstack([population, offspring])# 计算目标值objectives = self.calculate_objectives(combined_pop)# 非支配排序fronts = fast_non_dominated_sort(combined_pop, objectives)# 选择新种群new_population = []for front in fronts:if len(new_population) + len(front) <= self.pop_size:new_population.extend(front)else:# 计算拥挤度距离crowding_dist = crowding_distance(objectives, front)# 根据拥挤度选择剩余个体remaining = self.pop_size - len(new_population)selected = self.select_by_crowding(front, crowding_dist, remaining)new_population.extend(selected)breakpopulation = combined_pop[new_population]if gen % 10 == 0:print(f"Generation {gen}: Population size = {len(population)}")return populationdef dominates(obj1: np.ndarray, obj2: np.ndarray) -> bool:"""判断obj1是否支配obj2"""return np.all(obj1 <= obj2) and np.any(obj1 < obj2)def fast_non_dominated_sort(population: np.ndarray, objectives: np.ndarray) -> List[List[int]]:"""快速非支配排序"""n = len(population)domination_count = np.zeros(n)dominated_solutions = [[] for _ in range(n)]fronts = [[]]for i in range(n):for j in range(i + 1, n):if dominates(objectives[i], objectives[j]):dominated_solutions[i].append(j)domination_count[j] += 1elif dominates(objectives[j], objectives[i]):dominated_solutions[j].append(i)domination_count[i] += 1for i in range(n):if domination_count[i] == 0:fronts[0].append(i)i = 0while fronts[i]:next_front = []for j in fronts[i]:for k in dominated_solutions[j]:domination_count[k] -= 1if domination_count[k] == 0:next_front.append(k)i += 1fronts.append(next_front)return fronts[:-1]def crowding_distance(objectives: np.ndarray, front: List[int]) -> List[float]:"""计算拥挤度距离"""n = len(front)if n <= 2:return [float('inf')] * ndistances = [0] * nm = objectives.shape[1]for i in range(m):sorted_idx = sorted(range(n), key=lambda k: objectives[front[k], i])distances[sorted_idx[0]] = float('inf')distances[sorted_idx[-1]] = float('inf')obj_range = objectives[front[sorted_idx[-1]], i] - objectives[front[sorted_idx[0]], i]if obj_range == 0:continuefor j in range(1, n-1):distances[sorted_idx[j]] += (objectives[front[sorted_idx[j+1]], i] - objectives[front[sorted_idx[j-1]], i]) / obj_rangereturn distances

4. 应用示例

让我们以一个经典的多目标优化问题ZDT1为例：

def zdt1(x: np.ndarray) -> np.ndarray:"""ZDT1测试函数"""f1 = x[0]g = 1 + 9 * np.mean(x[1:])f2 = g * (1 - np.sqrt(f1/g))return np.array([f1, f2])# 运行示例
if __name__ == "__main__":nsga2 = NSGA2(pop_size=100, n_generations=100, n_variables=30)initial_pop = np.random.random((100, 30))final_pop = nsga2.evolve(initial_pop)# 计算最终种群的目标值final_objectives = nsga2.calculate_objectives(final_pop)# 绘制帕累托前沿import matplotlib.pyplot as pltplt.figure(figsize=(10, 6))plt.scatter(final_objectives[:, 0], final_objectives[:, 1])plt.xlabel('f1')plt.ylabel('f2')plt.title('Pareto Front')plt.grid(True)plt.show()

5. 完整实现与解析

让我们逐块解析NSGA-II的完整实现，理解每个部分的作用和原理。

5.1 类的初始化

def __init__(self,pop_size: int = 100,n_generations: int = 100,n_objectives: int = 2,n_variables: int = 30,mutation_rate: float = 0.01,crossover_rate: float = 0.9,variable_bounds: Union[List[Tuple[float, float]], None] = None
):

这部分就像是在准备一场比赛：

  • pop_size：决定有多少选手参加（种群大小）
  • n_generations：比赛要进行多少轮（迭代次数）
  • n_objectives：评判标准有几个（目标函数数量）
  • n_variables：每个选手有多少个可调整的参数
  • mutation_rate：选手自我调整的概率
  • crossover_rate：选手互相学习的概率
  • variable_bounds：每个参数的取值范围

5.2 生成子代

def create_offspring(self, population: np.ndarray) -> np.ndarray:"""生成子代"""offspring = np.zeros_like(population)for i in range(0, self.pop_size, 2):# 选择父代parent1_idx = self.tournament_selection(population)parent2_idx = self.tournament_selection(population)# 交叉和变异if np.random.random() < self.crossover_rate:child1, child2 = self.simulated_binary_crossover(population[parent1_idx],population[parent2_idx])else:child1 = population[parent1_idx].copy()child2 = population[parent2_idx].copy()

这就像是在进行一场配对比赛：

  1. 每次选两个选手（父代）
  2. 让他们互相学习（交叉）
  3. 产生两个新选手（子代）
  4. 新选手可能会有一些自己的创新（变异）

5.3 模拟二进制交叉

def simulated_binary_crossover(self, parent1: np.ndarray, parent2: np.ndarray,eta: float = 20) -> Tuple[np.ndarray, np.ndarray]:

这就像两个选手互相学习的过程：

  1. eta参数控制学习程度：
    • 值越大，子代越像父代
    • 值越小，变化越大
  2. 每个参数都有机会被交换或混合
  3. 确保新的参数不会超出范围

举个例子：

  • 父代1的某个参数是0.3
  • 父代2的某个参数是0.7
  • 交叉后可能得到0.4和0.6两个新值

5.4 多项式变异

def polynomial_mutation(self, individual: np.ndarray, eta: float = 20) -> np.ndarray:

这就像选手在尝试新东西：

  1. 每个参数都有小概率发生改变
  2. 改变的幅度由eta控制：
    • 值越大，改变越小
    • 值越小，改变越大
  3. 确保改变后的值仍在允许范围内

比如：

  • 原来的参数值是0.5
  • 变异后可能变成0.48或0.52

5.5 非支配排序

def fast_non_dominated_sort(population: np.ndarray, objectives: np.ndarray):

这就像对选手进行分级：

  1. 第一级：没有人比他们更好的选手
  2. 第二级：除去第一级后，没有人比他们更好的选手
  3. 以此类推…

举例：

  • A选手：速度快，耐力好 → 第一级
  • B选手：速度快，耐力一般 → 第二级
  • C选手：速度一般，耐力好 → 第二级
  • D选手：速度慢，耐力差 → 第三级

5.6 拥挤度距离

def crowding_distance(objectives: np.ndarray, front: List[int]):

这就像测量选手之间的独特性：

  1. 在同一级别中
  2. 看看每个选手与周围选手的不同程度
  3. 不同程度越大，得分越高

比如在第一级中：

  • A选手：与其他人很不同 → 高分
  • B选手：与C选手很相似 → 低分
  • C选手：与B选手很相似 → 低分

5.7 进化主循环

def evolve(self, initial_population: np.ndarray):

整个过程就像一个循环的比赛：

  1. 现有选手比赛
  2. 产生新选手
  3. 所有选手一起评级
  4. 选出最好的一批进入下一轮
  5. 重复这个过程

每一代都会：

  • 保留最优秀的选手
  • 淘汰表现差的选手
  • 产生新的选手

5.8 测试函数

def zdt1(x: np.ndarray) -> np.ndarray:

这是一个测试案例，就像是给选手设置的考试：

  1. 有两个目标：
    • 第一个目标：x[0]越小越好
    • 第二个目标：一个复杂的计算结果越小越好
  2. 这两个目标是相互冲突的
  3. 需要找到多个平衡的解

6. 结果分析

6.1 帕累托前沿

在这里插入图片描述

从上图的帕累托前沿我们可以观察到以下特点：

  1. 前沿形状

    • 呈现出平滑的凹形曲线
    • f1从0到1分布
    • f2从约1.4到3.8分布
    • 这是典型的ZDT1测试问题的理论前沿形状

  2. 解的分布

    • 点的分布较为均匀
    • 覆盖了整个决策空间
    • 没有明显的间隙
    • 在两端的解密度略低

  3. 权衡关系

    • 清晰展示了f1和f2之间的此消彼长关系
    • 当f1接近0时，f2达到最大值(约3.8)
    • 当f1接近1时，f2达到最小值(约1.4)
    • 中间区域展示了两个目标的平衡点

  4. 算法性能表现

    • 收敛性：

      • 解都落在一条光滑曲线上
      • 没有明显的离群点
      • 说明算法收敛性良好

    • 多样性：

      • 解在整个前沿上分布均匀
      • 端点解被很好地保留
      • 说明拥挤度距离机制效果良好

    • 前沿完整性：

      • 覆盖了整个帕累托前沿
      • 没有明显的空缺区域
      • 说明算法的搜索能力强

6.2 实际应用意义

这个结果在实际应用中意味着：

  1. 决策支持

    • 为决策者提供了一系列可选的折中方案
    • 每个点代表一个不同的权衡方案
    • 决策者可以根据实际需求选择合适的解

  2. 方案选择

    • 如果更重视f1（第一个目标），可以选择右侧的解
    • 如果更重视f2（第二个目标），可以选择左侧的解
    • 如果需要平衡，可以选择中间区域的解

  3. 解的特点

    • 左上角的解：f1较小，f2较大
    • 右下角的解：f1较大，f2较小
    • 中间的解：两个目标都处于中等水平

总结

NSGA-II算法通过其高效的非支配排序和新颖的拥挤度计算机制，成功解决了多目标优化问题中的三个关键问题：

  1. 如何引导种群向帕累托前沿收敛
  2. 如何保持解的多样性
  3. 如何保留精英个体

这使得NSGA-II成为了多目标优化领域最受欢迎的算法之一。


http://www.ppmy.cn/devtools/147919.html

相关文章

GICv2与GICv3中断架构对比与LPI中断机制分析

GICv2与GICv3中断架构对比与LPI中断机制分析

往期内容 本文章相关专栏往期内容&#xff0c;PCI/PCIe子系统专栏&#xff1a; 嵌入式系统的内存访问和总线通信机制解析、PCI/PCIe引入 深入解析非桥PCI设备的访问和配置方法 PCI桥设备的访问方法、软件角度讲解PCIe设备的硬件结构 深入解析PCIe设备事务层与配置过程 PCIe的三…
阅读更多...
C语言-找出数组中两个数字的和为该数字的位置

C语言-找出数组中两个数字的和为该数字的位置

1.题目要求 (语言: C)给定一组整形数组和一个数字&#xff0c;找出数组中两个数字的和为该数字的位置&#xff0c;例如 数组{2, 7, 11, 15}, 数字9&#xff0c;输出为1&#xff0c;2函数原型为&#xff1a; int *twoSum(int numbers[], int n, int target) //函数中定义一个动…
阅读更多...
Synopsys软件基本使用方法

Synopsys软件基本使用方法

Synopsys软件基本使用方法 1 文件说明2 编译流程3 查看波形4 联合仿真 本文主要介绍Synopsys软件vcs、verdi的基本使用方法&#xff0c;相关文件可从 GitHub下载。 1 文件说明 创建verilog源文件add.v、mult.v、top.vmodule add (input signed [31:0] dina,input signed [3…
阅读更多...
期权懂|期权交易中如何避免情绪化交易？

期权懂|期权交易中如何避免情绪化交易？

锦鲤三三每日分享期权知识&#xff0c;帮助期权新手及时有效地掌握即市趋势与新资讯&#xff01; 期权交易中如何避免情绪化交易&#xff1f; 一、制定明确的交易计划 在进入市场之前&#xff0c;投资者应制定详细的交易计划&#xff0c;包括交易目标、预期收益、可接受的风…
阅读更多...
从零开始自搭SpringBoot项目 -- Qingluopay项目工程介绍

从零开始自搭SpringBoot项目 -- Qingluopay项目工程介绍

从零开始自搭项目 – QingLuoPay 一&#xff0c;为什么要从零开始自搭项目 首先在介绍这个项目之前先介绍一下我为什么要选择从零自搭项目&#xff0c;而不是跟着网上哪些视频等做项目。 之前的很长一段时间我也都是在网上找一些做项目的视频就包含黑马的&#xff08;神领物…
阅读更多...
如何实现el-select多选下拉框中嵌套复选框并加校验不为空功能呢？

如何实现el-select多选下拉框中嵌套复选框并加校验不为空功能呢？

如何实现el-select多选下拉框中嵌套复选框并加校验不为空功能呢&#xff1f; 要实现的效果图选择部分品牌但不选选项效果问题概述实现方案el-select组件与el-checkbox组件无缝衔接给form表单加自定义校验规则 要实现的效果图 选择部分品牌但不选选项效果 问题概述 相信大家看到…
阅读更多...
xilinx的高速接口构成原理和连接结构及ibert工具的使用-以k7 GTX为例

xilinx的高速接口构成原理和连接结构及ibert工具的使用-以k7 GTX为例

一、相关简介 Xilinx的高速接口称之为transceivers(高速收发器&#xff09;&#xff0c;这部分的电路是专用电路&#xff0c;供电等都是独立的&#xff0c;根据速率可以分为GTP/GTX/GTH/GTY/GTM等。 Xilinx的高速接口是QUAD为单位的&#xff0c;没一个QUAD由一个时钟COMMON资…
阅读更多...
可由 （5V） 单片机直接驱动的模块

可由 （5V） 单片机直接驱动的模块

可由 &#xff08;5V&#xff09; 单片机 直接驱动的模块 1. 传感器类 元器件描述温度传感器DS18B20&#xff08;数字温度传感器&#xff09;光强传感器光敏电阻&#xff08;通过 ADC 读取&#xff09;红外传感器红外接收模块&#xff08;如 VS1838&#xff09;超声波传感器HC…
阅读更多...
最新文章

Copyright @ 2022~2023