多目标优化四种方法 |
您所在的位置：网站首页 › 多目标遗传算法有哪些 › 多目标优化四种方法 |
|
在现实中很多问题都能最终抽象为多目标优化问题。这是因为现实问题往往比较复杂，一般在达成目标时会权衡很多方面，也会有很多约束，这天然就是一个多目标优化问题。本文简单介绍主流的几种方法，内容主要是对参考文献的总结，作为学习笔记。 多目标优化问题（Multi-Objective Optimization,MOO）形式化定义 \begin{aligned} min/max \quad &f_m(x), \quad m=1,2,\dots,M\\ subject~to\quad &g_j(x) \geq 0, \quad j=1,2,\dots,J\\ &h_k(x)=0,\quad k=1,2,\dots,K\\ &\underset{lower\\bound}{x_i^{(L)}} \leq x_i \leq \underset{upper\\bound}{x_i^{(U)}},\quad i=1,2,\dots,n \end{aligned} 特点 包含多个可能有冲突的目标函数 希望找到能够很好平衡全部优化目标的解集 帕累托最优（Pareto Optimal）$\dagger$ 帕累托最优帕雷托最优是指资源分配的一种理想状态。给定固有的一群人和可分配的资源，如果从一种分配状态到另一种状态的变化中，在没有使任何人境况变坏的前提下，使得至少一个人变得更好，这就是帕雷托改善。帕雷托最优的状态就是不可能再有更多的帕雷托改善的状态；换句话说，不可能在不使任何其他人受损的情况下再改善某些人的境况。[wiki] $\dagger$ 支配（Dominace）当$x_1$和$x_2$满足如下条件时称$x_1$支配$x_2$： 对于所有目标函数$x_1$不比$x_2$差 至少在一个目标函数上，$x_1$严格比$x_2$要好上图中点1支配点2；点5支配点1；点1和点4互不支配 $\dagger$ 不可支配解集（Non-dominated solution set）当一个解集中任何一个解都不能被该集合中其他解支配，那么就称该解集为不可支配解集。 $\dagger$ 帕累托最优解集（Pareto-optimal set）所有可行中的不可支配解集被成为帕累托最优解集 $\dagger$ 帕累托最优前沿面（Pareto-optimal front）帕累拖最优解集的边界（boundary）被成为帕累托最优前沿面 MOO问题的目标 寻找尽可能接近帕累托最优前沿面的解集 尽可能增大找到解的多样性 多目标优化问题的经典方法Weighted Sum Method \begin{aligned} min\quad &F(x)=\sum\nolimits_{m=1}^{M} w_mf_m(x),\\ subject~to\quad &g_j(x) \geq 0, \quad j=1,2,\dots,J\\ &h_k(x)=0,\quad k=1,2,\dots,K\\ &x_i^{(L)} \leq x_i \leq x_i^{(U)},\quad i=1,2,\dots,n \end{aligned}线性加权法，其中权重代表了每个目标函数的重要程度。 优点： 简单 缺点： 很难设定一个权重向量能够去获得帕累托最优解 在一些非凸情况不能够保证获得帕累托最优解 ε-constraint method只保留一个目标函数，其他的目标函数被设定的值约束。 \begin{aligned} min\quad &f_{\mu}(x),\\ subject~to\quad &f_m(x)\leq \epsilon_m,\quad m=1,2,\dots,M~and~m \neq \mu \\&g_j(x) \geq 0, \quad j=1,2,\dots,J\\ &h_k(x)=0,\quad k=1,2,\dots,K\\ &x_i^{(L)} \leq x_i \leq x_i^{(U)},\quad i=1,2,\dots,n \end{aligned} 优点： 能够应用到凸函数和非凸函数场景下 缺点： 函数需要精心选择，需要在独立目标函数的最小值或最大值之内 Weighted Metric Method \begin{aligned} min\quad &l_p(x) = \left(\sum\nolimits_{m=1}^M w_m \lvert f_m(x)-z_m^* \rvert \right)^{1/p},\\ subject~to\quad &g_j(x) \geq 0, \quad j=1,2,\dots,J\\ &h_k(x)=0,\quad k=1,2,\dots,K\\ &x_i^{(L)} \leq x_i \leq x_i^{(U)},\quad i=1,2,\dots,n \end{aligned} 优点： weighted Techebycheff metirc能够保证获得所有帕累托最优解 缺点： 需要有每个函数最大值和最小值的先验知识 需要每个目标函数的$z^*$能够独立被找到 对于较小的p值，不一定保证所有能够获得所有帕累托最优解 随着p增加，问题会变得不可求导 Multi-Objective Genetic Algorithms基于遗传算法的多目标优化就是利用遗传算法的原理来搜索帕累托最优前沿面。其基本流程如下： 随机产生初始群体; 计算各点的目标函数值和约束函数值; 根据目标函数值对群体分级; 根据约束函数值和分级结果计算各点的约束罚项、劣解罚项及总罚项; 根据各点的总罚项计算适应度; 根据各点的适应度,进行选择、交叉和变异操作,生成新群体; 将总罚项为0的点放入非劣解集侯选表,对侯选表进行检查,保留第1级非劣点 , 删除其它点; 检查是否收敛,如没有,转到步骤2; 删除侯选表中与其它点距离太近的点; 输出侯选表中的 Pareto最优解集及对应的目标函数值; 决策人根据个人偏好从Pareto最优解集中挑选出最适合该问题的解；遗传算法相比与传统算法的优点是能够得到一个最优解集，而不是单单一个最优解，这样给我们更多的选择。但计算复杂度可能稍高，而且里面涉及的一些函数需要精心设计。 参考资料 Multi-Objective Optimization 飞机方案多目标优化的Pareto遗传算法 |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |