多目标优化 multi-objective optimization problem（MOP）

目录： 一、什么是多目标优化问题 二、多目标问题的解 三、相关算法

---

一、multi-objective optimization problem（MOP）

Multi-objective optimization problems deals with conflicting objectives, i.e. while one objective increases the other decreases. There is no a unique global solution but a set of solutions.

Multi-objective Optimization Programming、Pareto Optimization等等都是这个问题。 通常用下面的问题来代表： 求解时有多个条件需要服从。

得到的解 满足所有constraint且变量都在上下界范围内的solution称为 feasible solution。 所有可行解构成的集合称为 feasible region，有时也称为 search space。 objective space 的定义有待补充……

MOP的目标可能是找到一组有代表性的帕累托最优解，和/或量化满足不同目标的权衡，和/或找到一个单一的解决方案，满足人类决策者的主观偏好。

---

二、MOP的解

Dominated Solution

$x^{(1)}$ dominate $x^{(2)}$需要以下条件同时成立：

对于所有目标，$x^{(1)}$都不比 $x^{(2)}$差。至少在一个目标上$x^{(1)}$比$x^{(2)}$好（严格意义上）。

Non-dominated Solution

所有不是Dominated Solution的解。也就是所谓 Pareto optimal、Pareto efficient，此时，如果在不降低其他一些目标值的情况下，所有目标函数的价值都不能得到提高。如果没有额外的主观偏好信息，所有的帕累托最优解都被认为是同样好的。

Pareto Front

Pareto解的集合。Pareto front中的所有解不受Pareto Front之外的解（以及Pareto Front 曲线以内的其它解）所支配，因此这些非支配解较其他解而言拥有最少的目标冲突，可提供决策者一个较佳的选择空间。在某个非支配解的基础上改进任何目标函数的同时，必然会削弱至少一个其他目标函数。

---

三、相关算法

EA Evolutionary Algorithm，EA的发明是因为经典的直接和基于梯度的技术在引入非线性和复杂的交互作用时有以下问题： 最优解的收敛性取决于选择的初始解。大多数算法往往会陷入次优解。 NSGA-II Non-dominated Sorting Genetic Algorithm，是一种EA算法。它有以下三个特征： 它采用精英主义原则，即人口中的精英有机会传承给下一代。使用显式的多样性保存机制(Crowding distance）。强调Non-dominated Solution。 MCACEA Multiple Coordinated Agents Coevolution Evolutionary Algorithm，使用每个agent共享其最佳解决方案的单一进化算法来协调使用合作目标的种群进化的通用框架（每个个体之间共享，最终实现群体进化）。