文献翻译 (3):非支配排序遗传算法 (Non-dominated Sorting Genetic Algorithm, NSGA-II)

本文主要是介绍文献翻译 (3):非支配排序遗传算法 (Non-dominated Sorting Genetic Algorithm, NSGA-II),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 1 引入
  • 2 多目标优化
  • 3 更多的定义
    • 3.1 支配
    • 3.2 非支配集
    • 3.3 全局Pareto最优集
  • 4 NSGA-II

1 引入

本文主要介绍多目标优化的基本概念以及NSGA-II。

2 多目标优化

多目标优化的优化目标之间存在一定的冲突,例如一个目标增长,导致另一个减少。因此这里的解是一组解决方案而非唯一的全局解。

通常,我们有以下数学问题:
min ⁡ / max ⁡ : f m ( x ) , m = 1 , 2 , … , M s . t . : g j ( x ) ≥ 0 , j = 1 , 2 , … , J h k ( x ) = 0 , k = 1 , 2 , … , K x i ( L ) ≤ x i ≤ x i ( U ) , i = 1 , 2 , … , n \begin{aligned} \min/\max:&f_m(\mathbf{x}),&m&=1,2,\dots,M\\ s.t.:&g_{j}(\mathbf{x})\geq0,&j&=1,2,\dots,J\\ &h_k(\mathbf{x})=0,&k&=1,2,\dots,K\\ &x_i^{(L)}\leq x_i\leq x_i^{(U)},&i&=1,2,\dots,n \end{aligned} min/max:s.t.:fm(x),gj(x)0,hk(x)=0,xi(L)xixi(U),mjki=1,2,,M=1,2,,J=1,2,,K=1,2,,n一个解是包含 n n n个变量的向量:
x = ( x 1 , x 2 , … , x n ) T \mathbf{x}=(x_1,x_2,\dots,x_n)^T x=(x1,x2,,xn)T此外,问题屈服于 J J J个不等式约束和 K K K个等式约束,每一个变量都有一个相应的上界和下界。

满足所有约束且在上下界之间的解被称为可行解。所有可行解的集合被称为可行域 (搜索空间) S S S目标空间由所有可行解对应的的 M M M个目标函数的值构成。

3 更多的定义

3.1 支配

如果条件1和2均满足,则解 x ( 1 ) \mathbf{x}^{(1)} x(1)支配解 x ( 2 ) \mathbf{x}^{(2)} x(2)

  • 条件1:对于所有的目标函数均有 x ( 1 ) \mathbf{x}^{(1)} x(1)不差于 x ( 2 ) \mathbf{x}^{(2)} x(2)
  • 条件2:在至少一个目标函数上 x ( 1 ) \mathbf{x}^{(1)} x(1)严格优于 x ( 2 ) \mathbf{x}^{(2)} x(2)

x ( 1 ) \mathbf{x}^{(1)} x(1)支配 x ( 2 ) \mathbf{x}^{(2)} x(2)的数学表达为:
x ( 1 ) ⪯ x ( 2 ) \mathbf{x}^{(1)}\preceq\mathbf{x}^{(2)} x(1)x(2)

3.2 非支配集

对于解集 P P P,其非支配集是所有不被其他解所支配的解的集合。

3.3 全局Pareto最优集

S S S的非支配集即为全局Pareto最优集。

一个例子是土木工程中的悬臂梁设计:通过改变悬臂梁长度和直径,来最小化挠度和重量。图1展示了相应的目标空间:不同长度和直径下的挠度与重量变化。

图1:挠度与重量


该曲线可以很直观地反应全局Pareto最优集中挠度和重量的权衡。

图2:左图为可行的决策变量空间,右图为可行的目标空间


图2中靠近原点的目标空间中,形成的一条曲线即为Pareto最优前沿。非可行解也能生成靠近原点的目标值。Pareto前沿表示可能的最佳权衡

4 NSGA-II

NSGA-II是一种进化算法。进化算法被开发的原因为:直接或基于梯度的技术在处理非线性和复杂交互时存在以下问题:

  • 最优解的收敛依赖于初始解的选择;
  • 大多数算法易陷入局部最优。

NSGA-II的理解需要一些前驱知识,可以参照:

  1. 遗传算法简介
  2. Matlab与遗传算法
  3. Pymoo与遗传算法

NSGA-II的特征如下:

  1. 精英准则:种群的精英将更可能传递到下一代;
  2. 拥挤距离:一种显示的多样性保持机制;
  3. 着重非支配解

算法的步骤如下:

  1. 对父代和后代种群的组合进行非支配排序,并按前沿对它们进行分类,即它们根据非支配级别的升序排序:
图3:最小化f1、f2。三种前沿级别
  1. 根据前面的排序来填充新种群;
  2. 如果一个前沿像F3一样部分采取,则执行拥挤排序,密度较小的是首选;
  3. 使用拥挤锦标赛选择 (通过前排比较,如果相等则通过拥挤距离比较)、交叉,以及变异算子从这个新种群创建后代种群。

图4:NSGA-II的语义表示

这篇关于文献翻译 (3):非支配排序遗传算法 (Non-dominated Sorting Genetic Algorithm, NSGA-II)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/280546

相关文章

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

hdu 1285(拓扑排序)

题意: 给各个队间的胜负关系,让排名次,名词相同按从小到大排。 解析: 拓扑排序是应用于有向无回路图(Direct Acyclic Graph,简称DAG)上的一种排序方式,对一个有向无回路图进行拓扑排序后,所有的顶点形成一个序列,对所有边(u,v),满足u 在v 的前面。该序列说明了顶点表示的事件或状态发生的整体顺序。比较经典的是在工程活动上,某些工程完成后,另一些工程才能继续,此时

AI基础 L9 Local Search II 局部搜索

Local Beam search 对于当前的所有k个状态,生成它们的所有可能后继状态。 检查生成的后继状态中是否有任何状态是解决方案。 如果所有后继状态都不是解决方案,则从所有后继状态中选择k个最佳状态。 当达到预设的迭代次数或满足某个终止条件时,算法停止。 — Choose k successors randomly, biased towards good ones — Close

论文翻译:arxiv-2024 Benchmark Data Contamination of Large Language Models: A Survey

Benchmark Data Contamination of Large Language Models: A Survey https://arxiv.org/abs/2406.04244 大规模语言模型的基准数据污染:一项综述 文章目录 大规模语言模型的基准数据污染:一项综述摘要1 引言 摘要 大规模语言模型(LLMs),如GPT-4、Claude-3和Gemini的快

《数据结构(C语言版)第二版》第八章-排序(8.3-交换排序、8.4-选择排序)

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多,算法平均时间性能比直接插入排序差。当初始记录无序,n较大时, 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In

从0到1,AI我来了- (7)AI应用-ComfyUI-II(进阶)

上篇comfyUI 入门 ,了解了TA是个啥,这篇,我们通过ComfyUI 及其相关Lora 模型,生成一些更惊艳的图片。这篇主要了解这些内容:         1、哪里获取模型?         2、实践如何画一个美女?         3、附录:               1)相关SD(稳定扩散模型的组成部分)               2)模型放置目录(重要)

【软考】希尔排序算法分析

目录 1. c代码2. 运行截图3. 运行解析 1. c代码 #include <stdio.h>#include <stdlib.h> void shellSort(int data[], int n){// 划分的数组,例如8个数则为[4, 2, 1]int *delta;int k;// i控制delta的轮次int i;// 临时变量,换值int temp;in

论文翻译:ICLR-2024 PROVING TEST SET CONTAMINATION IN BLACK BOX LANGUAGE MODELS

PROVING TEST SET CONTAMINATION IN BLACK BOX LANGUAGE MODELS https://openreview.net/forum?id=KS8mIvetg2 验证测试集污染在黑盒语言模型中 文章目录 验证测试集污染在黑盒语言模型中摘要1 引言 摘要 大型语言模型是在大量互联网数据上训练的,这引发了人们的担忧和猜测,即它们可能已

学习记录:js算法(二十八):删除排序链表中的重复元素、删除排序链表中的重复元素II

文章目录 删除排序链表中的重复元素我的思路解法一:循环解法二:递归 网上思路 删除排序链表中的重复元素 II我的思路网上思路 总结 删除排序链表中的重复元素 给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。 图一 图二 示例 1:(图一)输入:head = [1,1,2]输出:[1,2]示例 2:(图