多目标优化(进化)算法入门（一）

acecase · 发表于 2022-3-11 21:13

基于研究生阶段的学习和研究，将自己所理解到的知识进行一个记录分享。文中提及的都是个人认为核心的主线，理解清楚能拓展到其他的多目标优化算法。文中或许有些许错误，思虑不周，还望海涵。
基本概念

如果存在若干相互冲突的目标并需要同时处理，即成为多目标优化问题（Multi-objective Optimization Problems, MOPs）。对于MOPs，不可能使得所有的目标同时达到最优状态，只能得到一组均衡解，称之为Pareto最优集合。进化算法（Evolutionary algorithm，EA）是一类基于群体搜索的随机优化方法。EA运行一次可以获得一组解，而且对待复杂问题的数学性质不做严格假设，因而被广泛地应用于求解各类MOPs，并因此产生了许多经典的多目标进化算法（Multi-objective evolutionary algorithm，MOEA）。
非常重要的概念：对于所有子目标，若解xa不比解xb差，且xa至少有一个子目标比解xb好(好坏从目标空间取值来看，下文会举例说明)，则称xa支配xb，称xa为非支配解，xb为支配解。若没有解支配xa，则称xa为Pareto最优解。所有Pareto最优解组成的集合被称为Pareto最优集合(Pareto Set,PS)。Pareto最优集合在目标空间的映射称为Pareto前沿(Pareto Front,PF)。
举例说明多目标优化问题：min f1=x2，min f2=(x-1)2

还是举例能最直接清楚阐述问题。首先单独来看，目标 f1和 f2都是单目标最优化问题，最优解分别为x=0和x=1（多目标优化中一般以最小化为最优目标）。但是对于多目标优化来说，最优解并不是一个具体的数值对，而是一组Pareto(帕累托)最优解，即PS。
注：PS是决策空间，也就是变量x；PF是PS在目标空间的映射，也就是目标 f1和 f2。

图1 f1和 f2问题空间

图 2 目标空间

说明：由图1可以看出没有解可以使f1和 f2同时最小。当一个子目标达到最优时，另一个目标并不是最优。因此，当x[0,1]时，两个函数达成折衷解，称x[0,1]为PS。
那估计有家人们要问，其他x取值就不是PS了吗？
显然不是，找个反例就能解释这种情况。例如，x=2就不是Pareto最优解，因为此时的两个函数的取值都没有x=1时好。设x1，x2[0,1]，x3[0,1]；显然，x1,x2没有被其他解支配，它们互为非支配解。x1，x2支配x3，x3为支配解。图2中加粗部分为此问题的PF。
这一节主要说明了什么是多目标优化问题，以及多目标相关的基础概念。讲到这里核心的基本概念就说完了，清晰明了吧。提出问题之后就得解决问题，那如何解决问题，请看下回分解。
有问题请随时指正。

RecursiveFrog · 发表于 2022-3-11 21:17

帕累托最优解的含义是，每一步更新，各项损失函数都下降或者不变，有一项损失增加了，那就不是最优解了

mastertravels77 · 发表于 2022-3-11 21:22

Pareto解一般根据目标函数向量每一个目标的“大小的等级”来进行判断。

DungDaj · 发表于 2022-3-11 21:23

最新多目标优化算法参考代码https://zhuanlan.zhihu.com/p/479491067

		自动登录	找回密码
密码			立即注册

多目标优化(进化)算法入门（一）

本帖子中包含更多资源