当前位置: 主页 > 新闻资讯 > 殡葬知识

多目标优化(Multi-objective optimization)的基础概念

2024-06-18 21:44   作者:佚名

多目标优化需要同时优化两个或者两个以上的目标函数,且不能显式地平衡它们(不存在同时优化每个目标函数的解)。

为了引出多目标优化的定义,先介绍一个概念,一个可容纳所有可行解的解子空间叫可行解空间。下面是多目标优化的定义:

给定可行解空间 Sm 个目标函数 f_{1},f_{2},…,f_{m}, 多目标优化的目的是找到解 s^{*} 满足s^{*}=arg max_{s\\in S}f(s)=arg max_{s\\in S}(f_{1}(s),f_{2}(s),…,f_{m}(s)), f(s)=(f_{1}(s),f_{2}(s),…,f_{m}(s)) 是解 s 的目标向量。

说明:这些目标函数通常是相互矛盾的--优化其中一个目标函数会“损害”其他目标函数--因此,不可能找到对所有的目标函数都是最优解的解。所以,多目标优化的解是一组解,其中的每个解相对其他解都有其独特的优势。这种优势可以通过一些标准来衡量,一个常用的方法是帕累托最优(Pareto optimality)。

在给出帕累托最优具体定义之前先陈述一下wiki上对帕累托最优的理解:帕累托最优是指资源分配的一种理想状态。给定固有的一群人和可分配的资源,如果从一种分配状态到另一种状态的变化中,在没有使任何人情况变坏的前提下,使得至少一个人变得更好,这就是帕累托改善。帕累托最优的状态就是不可能再有更多的帕累托改善的状态。

帕累托最优是通过“占优战略”(dominant strategy)来定义的,首先定义一下“占优战略”:

给定可行解空间 S 和目标空间 R^{m} ,f=(f_{1},f_{2},…,f_{m}),S \\rightarrow R^{m}是目标向量。对于两组解 s, s^{'}\\in S :

1)s 相对于 s^{'} 弱占优(或者说s^{'} 弱劣于 s),记作 s^{'}\\preceq s ,如果 if  \\forall i ∈[m]: f_{i}(s) \\geq f_{i}(s^{'});

2)s 相对于 s^{'} 占优,记作 s^{'}\\prec s (或者说s^{'} 劣于 s),如果 if  s^{'}\\preceq s ,and \\exists i ∈[m]: f_{i}(s) > f_{i}(s^{'});

下面给出帕累托最优的定义:

给定可行解空间 S 和目标空间 R^{m} ,f=(f_{1},f_{2},…,f_{m}),S \\rightarrow R^{m}是目标向量。 s \\in S 是帕累托最优若不存在 s^{'}\\in S, s \\prec s^{'} 。帕累托最优解的目标向量的集合称为Pareto front(或者Pareto boundary)。

下图比较容易理解:

图中黑色的方块和圆点分别代表解和目标向量。可行解空间有8组解。很明显 s_{2}\\succ s_{5} 因为 f_{1}(s_{2}) > f_{1}(s_{5}) , f_{2}(s_{2}) > f_{2}(s_{5}) .在这8组解中, s_{1},s_{2},s_{3},s_{4}是帕累托最优解。目标向量 f(s_{1}), f(s_{2}), f(s_{3}), f(s_{4}) 组成 Pareto front.

如果没有额外的主观偏好信息,所有帕累托最优解都被认为是同样好的。

因此,多目标优化的目标是最终目标是找到Pareto front.但是对于许多问题,找到Pareto front 是不可能的。因此,多目标优化的一种实用方法是找到一组尽可能代表帕累托最优的解。


参考文献:1. Evolutionary Learning: Advances in Theories and Algorithms. Zhi-Hua Zhou 等

2. Multi-objective optimization using genetic algorithms: A tutorial

3. 博弈论与信息经济学.张维迎

4. 帕累托最优

5.wiki

同类文章推荐
网络用语BY什么意思?
深度学习笔记(十):SGD、Momentum、RMSprop、Adam优化算法解析
NBA实时战报|魔术主场88:98不敌开拓者
教育部等五部门关于印发《普通高等教育学科专业设置调整优化改革方案》的通知
优化数据排布,让你的程序加速 4 倍!
电竞队伍里的教练是干什么的?

咨询登记

平台注册入口