多目标优化简介

We are not mathematicians. 本文只从最直观的角度对多目标优化的各类解法做一个概览，不涉及过多数学细节。但归根结底，这是一个数学优化问题。

简介

最优化（Optmization）是数学规划/运筹学/计算机科学中广泛研究的问题，许多实际应用都可以抽象为一个最优化问题求最优解的过程：寻找可行解使得目标函数最大化或最小化（比如最大化利润或最小化损失）。然而在许多情况下，决策者需要同时优化几个不同的目标函数，于是引出了多目标优化（Multi-Objective Optimization, MOO）这一课题。对这类问题稍加思考不难发现，如果多个目标的方向不一致，寻找最优解将变得非常棘手。

背景

MOO问题不同于一般的优化问题，首先要重新定义这类问题的最优解（Optimal Solution），因为一个目标函数的最优解可能是另一个目标函数的次优解（或者更差）。

$ = \sum_i q(w_i) [R_i - \sum_k R_k q(w_k)] \nabla l_i$

不失一般性，我们定义MOO问题要在定义域 $X$ 上最小化个目标函数：。Efficient/Pareto optimal，有效解/帕累托最优解：一个可行解，不存在其他解同时满足。（如果不牺牲其他目标就无法再优化了的解）Weakly efficient，弱效解：一个可行解，如果不存在其他解满足。（Weakly）Undominated point，（弱）支配解：(weakly) efficient解对应的目标域的点：。Utopia point / Ideal point (理想点)：，其中，表示目标域映射集合。（即在所有目标上都是最优，这种情况比较少见）如果定义域是凸的，则解空间对应的目标域是一个凸包（convex hull）      上图中：点B支配点A；点C支配点A；点B和点C互不支配例子一个简单的优化问题：其定义域及对应的可行解值域如下：基本解法Weight Sum Method (Scalarization)加权求和是一种最直观的求解MOO的方法 [1]，将所有目标以weight-sum的形式从多目标优化转为单目标优化：，再利用经典的单目标优化方法求解。优点：简单方便缺点：权重系数与各个目标之间优先级的对应关系并不直观，需要精心设计，且可能受到各个目标量纲差异的影响。在一些非凸情况不能够保证获得帕累托最优解，如下图图示。The -Constraint Method另一种解法是，只优化其中一个目标函数，而将其他目标函数以约束条件的形式加入到优化问题中 [2]：，其中表示的是目标所能容许的最大损失。这同样是一种将多目标转化为单目标的思路。优点：能够应用到凸函数和非凸函数场景下，如下图：缺点：优化哪个主目标函以及参数的设置需要精心挑选，如果设置不好则可能导致找不到解，如例子中的y2必须小于14且大于1。The Goal Programming Method (目标规划法)目标规划法（Goal Programming）是一种数学规划方法 [3,4]，将原多目标优化问题转化为如下的LP（线性规划）问题：设定松弛变量，最小化目标函数与某个既定指标之间的距离。可以设定为每个目标的最优解（即理想点utopia point），也可指定为其他期望值。优化过程示意图如下：Specification of the goals, , defines the goal point, . The weighting vector defines the direction of search from P to the feasible function space, . During the optimization  is varied, which changes the size of the feasible region. The constraint boundaries converge to the unique solution point  [4].其他解法Simplex Method（单纯性法）单纯形法是一种求解线性规划的方法，传统的单纯性法可以被扩展至求解多目标优化。对于双目标优化问题（Bi-Objective Simplex），单纯形法要求优化问题是线性的形式（约束也是线性方程组）；对于更多目标的问题，求解复杂度也会呈指数级提升（pivot点个数）。关于这类解法详细的介绍可参考[5]，因为求解限制比较多，且计算代价较高，这里不做详细介绍了。Game Theoretic Approach（基于博弈的多目标优化）另外一种视角是将多目标优化问题看成一个多玩家的协同博弈（co-operaytive game），每一个玩家负责优化一个目标，则“协同型博弈”指的是所有玩家在策略上达成一致（即收敛到均衡）。一种基于博弈论的MOO解法如下[6]：Step 1: 统一所有目标函数的尺度（因为Step 4中需要所有目标函数相乘），得到一组新的目标函数。这里采用的办法是先找到一个可行解，再通过一个乘子放缩到定值上。（个人猜测）如果能拿到各个目标的上下界，也可做统一放缩，比如[0,1]。Step 2: 独立的计算每个目标的最优解，这也是一组帕累托最优解，只不过每个解只“贪心”的对某一个目标负责，没有trade-off。Step 3: 对每个目标，将其他目标解中对该目标影响最差的值作为每个目标的最差解worst value：Step 4: 新的优化问题为，选择使得各个目标函数与其对应的最差解之间的距离的乘积最大化。在这一步骤中，多个目标的trade-off（协同）是以乘积的形式出现的。这一解法的文献[6]无法下载，因此尚不确定作者是否证明是纳什均衡解。后续的改进版本及非线性规划的拓展可以参考文献[7]。Multi-objective Evolutionary Algorithm（多目标进化算法，MOEA）前面的几种解法都是从目标函数的明确形式入手，直接求解或通过一些手段转化为传统的最优化问题，从而求解帕累托最优解，是只基于先验知识的方法。另一大类解法是基于进化算法求解多目标问题（MOEA），即假定所有目标为黑箱函数（black-box），并通过不断query目标函数试错来得到评估值，进而调整求解策略，是一种基于后验知识的方法。MOEA不预设多个目标的preference，核心思路是通过代与代之间维持由潜在解组成的种群来实现全局搜索，并能在一次运行中产生一组近似的帕累托最优解集。MOEA的基本原理描述如下：从一组随机生成的种群出发，通过对种群执行选择、交叉和变异等进化操作，经过多代进化，种群中个体的适应度不断提高，从而逐步逼近多目标优化问题的Pareto最优解集。目前几个主流的MOEA算法包括：NSGA-II[8]，MOEA/D[9]等。（下图为NSGA-II在优化一个MOO问题的解集演化过程）-II结果示意图前面提到的几种解法分别求解例子中的优化问题：n图1：Scalarization method with  and bi-objective simplex method图2：Scalarization method with  and goal programming method with goal 图3：Game theoretic approach图4：-contraint method with minimizing  to the additional constraint that 图5：-contraint method with minimizing  to the additional constraint that MOEA类的方法在计算资源允许的情况下理论上可逼近完整的帕累托前端。参考文献[1] Marler, R. Timothy, and Jasbir S. Arora. “The weighted sum method for multi-objective optimization: new insights.” Structural and multidisciplinary optimization 41.6 (2010): 853-862.[2] Marler, R. Timothy, and Jasbir S. Arora. “Survey of multi-objective optimization methods for engineering.” Structural and multidisciplinary optimization 26.6 (2004): 369-395.[3] Charnes, Abraham, and William Wager Cooper. “Goal programming and multiple objective optimizations: Part 1.” European journal of operational research 1.1 (1977): 39-54.[4] https://ww2.mathworks.cn/help/optim/ug/multiobjective-optimization-algorithms.html[5] https://www.lamsade.dauphine.fr/~projet_cost/ALGORITHMIC_DECISION_THEORY/pdf/Ehrgott/HanLecture2_ME.pdf[6] Rao, Singiresu S. “Game theory approach for multiobjective structural optimization.” Computers & Structures 25.1 (1987): 119-127.[7] Ghotbi, Ehsan. “Bi-and multi level game theoretic approaches in mechanical design.” (2013).[8] Deb, Kalyanmoy, et al. “A fast and elitist multiobjective genetic algorithm: NSGA-II.” IEEE transactions on evolutionary computation 6.2 (2002): 182-197.[9] Zhang, Qingfu, and Hui Li. “MOEA/D: A multiobjective evolutionary algorithm based on decomposition.” IEEE Transactions on evolutionary computation 11.6 (2007): 712-731.