多目标优化是多准则决策的一个领域，它是涉及多个目标函数同时优化的数学问题。多目标优化已经应用于许多科学领域，包括工程、经济和物流，其中需要在两个或多个相互冲突的目标之间进行权衡的情况下作出最优决策。分别涉及两个和三个目标的多目标优化问题的例子有：在购买汽车时降低成本，同时使舒适性最大化；在使车辆的燃料消耗和污染物排放最小化的同时将性能最大化。在实际问题中，甚至可以有三多个目标。
对于非平凡多目标优化问题，不存在同时优化每个目标的单个解决方案。在这种情况下，目标函数被说成是冲突的，并且存在一个（可能无限）数量的帕累托最优解。如果目标函数在值上不能改进而不降低其他一些目标值，则解决方案称为非支配、Pareto最优、Pareto有效或非劣解。如果没有额外的主观偏好信息，所有Pareto最优解都被认为是同样好的（因为向量不能完全排序）。研究人员从不同的角度研究多目标优化问题，从而在设置和解决多目标优化问题时存在不同的求解哲学和目标。目标可以是找到帕累托最优解的代表性集合，and/or量化满足不同目标的折衷，and/or找到满足人类决策者decision maker(DM)的主观偏好的单一解决方案。
形式化定义
$$
\begin{array}{cl}{\min / \max } & {f_{m}(x), \quad m=1,2, \ldots, M} \\ {\text { subject to }} & {g_{j}(x) \geq 0, \quad j=1,2, \ldots, J} \\ {} & {h_{k}(x)=0, \quad k=1,2, \ldots, K} \\ {} & {x_{i}^{(Lower)} \leq x_{i} \leq x_{i}^{(Upper)}, \quad i=1,2, \ldots, n} \end{array}
$$
发展历史
| 年份 | 事件 | 相关论文 |
|---|---|---|
| 1906 | Pareto提出核心思想 | Pareto, V. (1906). Manuale di economia politica (Vol. 13). Societa Editrice. |
| 1979 | Stadler, W. 对帕累托最优进一步回顾 | Stadler, W. (1979). A survey of multicriteria optimization or the vector maximum problem, part I: 1776–1960. Journal of Optimization Theory and Applications, 29(1), 1-52. |
| 2008 | Miettinen, K.提出一种混合方法解决多目标问题 | Miettinen, K., Ruiz, F., & Wierzbicki, A. P. (2008). Introduction to multiobjective optimization: interactive approaches. In Multiobjective Optimization (pp. 27-57). Springer, Berlin, Heidelberg. |
| 2014 | Deb, K.对多目标优化进行回顾 | Deb, K. (2014). Multi-objective optimization. In Search methodologies (pp. 403-449). Springer, Boston, MA. |
| 2018 | Sener, O., & Koltun, V.提出多任务学习来作为多目标优化的策略 | Sener, O., & Koltun, V. (2018). Multi-task learning as multi-objective optimization. In Advances in Neural Information Processing Systems (pp. 524-535). |
多目标优化算法归结起来有传统优化算法和智能优化算法两大类。
- 传统优化算法包括加权法、约束法和线性规划法等，实质上就是将多目标函数转化为单目标函数，通过采用单目标优化的方法达到对多目标函数的求解。
- 智能优化算法包括进化算法（Evolutionary Algorithm, 简称EA）、粒子群算法（Particle Swarm Optimization, PSO）等。
从九十年代初开始，进化算法系列算法被统一，如遗传算法等。
多目标优化问题的解
在单目标优化问题中，通常最优解只有一个，而且能用比较简单和常用的数学方法求出其最优解。然而在多目标优化问题中，各个目标之间相互制约，可能使得一个目标性能的改善往往是以损失其它目标性能为代价，不可能存在一个使所有目标性能都达到最优的解，所以对于多目标优化问题，其解通常是一个非劣解的集合——Pareto解集。
帕累托最优（Pareto Optimal）：帕雷托最优是指资源分配的一种理想状态。给定固有的一群人和可分配的资源，如果从一种分配状态到另一种状态的变化中，在没有使任何人境况变坏的前提下，使得至少一个人变得更好，这就是帕雷托改善。帕雷托最优的状态就是不可能再有更多的帕雷托改善的状态；换句话说，不可能在不使任何其他人受损的情况下再改善某些人的境况。帕累托最优解集的边界（boundary）被称为帕累托最优前沿面（Pareto-optimal front）。
在存在多个Pareto最优解的情况下，如果没有关于问题的更多的信息，那么很难选择哪个解更可取，因此所有的Pareto最优解都可以被认为是同等重要的。由此可知，对于多目标优化问题，最重要的任务是找到尽可能多的关于该优化问题的Pareto最优解。因而，在多目标优化中主要完成以下两个任务：
- 找到一组尽可能接近Pareto最优域的解。
- 找到一组尽可能不同的解。
第一个任务是在任何优化工作中都必须的做到的，收敛不到接近真正Pareto最优解集的解是不可取的，只有当一组解收敛到接近真正Pareto最优解，才能确保该组解近似最优的这一特性。
几种常用的多目标优化问题解决方法
Weighted Sum Method
线性加权法，其中权重代表了每个目标函数的重要程度。
$$
\begin{array}{rl}{\min } & {F(x)=\sum_{m=1}^{M} w_{m} f_{m}(x)} \\ {\text { subject to }} & {g_{j}(x) \geq 0, \quad j=1,2, \ldots, J} \\ {} & {h_{k}(x)=0, \quad k=1,2, \ldots, K} \\ {} & {x_{i}^{(Lower)} \leq x_{i} \leq x_{i}^{(Upper)}, \quad i=1,2, \ldots, n}\end{array}
$$
优点：简单
缺点：很难设定一个权重向量能够去获得帕累托最优解；在一些非凸情况不能够保证获得帕累托最优解
$\varepsilon$ -constraint method
只保留一个目标函数，其他的目标函数被设定的值约束。
$$
\begin{array}{cl}{\min } & {f_{\mu}(x)} \\ {\text {subject to }} & {f_{m}(x) \leq \epsilon_{m}, \quad m=1,2, \ldots, M \text { and } m \neq \mu} \\ {} & {g_{j}(x) \geq 0, \quad j=1,2, \ldots, J} \\ {} & {h_{k}(x)=0,} \quad {k=1,2, \ldots, K} \\ {} & {x_{i}^{(Lower)} \leq x_{i} \leq x_{i}^{(Upper)},} \quad {i=1,2, \ldots, n}\end{array}
$$
优点：能够应用到凸函数和非凸函数场景下
缺点：函数需要精心选择；需要在独立目标函数的最小值或最大值之内
Weighted Metric Method
$$
\begin{array}{cl}{\min } & {l_{p}(x)=\left(\sum_{m=1}^{M} w_{m}\left|f_{m}(x)-z_{m}^{*}\right|\right)^{1 / p}} \\ {\text { subject to }} & {g_{j}(x) \geq 0, \quad j=1,2, \ldots, J} \\ {} & {h_{k}(x)=0, \quad k=1,2, \ldots, K} \\ {} & {x_{i}^{(Lower)} \leq x_{i} \leq x_{i}^{(Upper)}, \quad i=1,2, \ldots, n}\end{array}
$$
优点：weighted Techebycheff metirc能够保证获得所有帕累托最优解
缺点：需要有每个函数最大值和最小值的先验知识；需要每个目标函数的 $z^{*}$ 能够独立被找到；对于较小的p值，不一定保证所有能够获得所有帕累托最优解；随着p增加，问题会变得不可求导
Multi-Objective Genetic Algorithms
基于遗传算法的多目标优化就是利用遗传算法的原理来搜索帕累托最优前沿面。
遗传算法相比与传统算法的优点是能够得到一个最优解集，而不是单单一个最优解，这样给我们更多的选择。但计算复杂度可能稍高，而且里面涉及的一些函数需要精心设计。
详见：https://imonce.github.io/2019/11/07/启发式算法学习（三）：遗传算法/
发展分析
多目标优化算法相对成熟，在不同的问题使用不同的优化算法。NSGA-II, SPEA 或者 MOPSO都是可选项，而到底选择哪一个方法，还需要根据特定的情景选择。
尽管多目标优化算法应用于动态的制造系统，dynamic manufacturing systems，但是制造系统和很复杂的，并且是动态的，因此算法还是有一定的缺陷性。
未来发展方向：
因为多种多目标方法已经被提出，混合方法 hybrid method可以被进一步发展。
现在的动态制造系统中的多目标优化算法需要动态调度的能力
Reference:
https://www.jiqizhixin.com/graph/technologies/cf8932be-519a-4fd9-84f9-c6ffa997a554
https://blog.csdn.net/paulfeng20171114/article/details/82454310
https://hpzhao.github.io/2018/09/17/多目标优化四种方法/
https://zh.wikipedia.org/wiki/帕累托最优