多目标优化的三种分解方法
多目标优化的三种分解方法
多目标优化是运筹学和机器学习领域的重要研究方向，其核心是如何在多个相互冲突的目标之间找到最优解。本文将介绍三种常见的多目标优化分解方法：加权求和法、切比雪夫法和边界交叉法。这些方法通过将多目标优化问题转化为单目标优化问题，从而简化了求解过程。
多目标进化的三种分解方法
1. 加权求和 (Weighted Sum)
加权求和法是一种将多目标优化问题转化为单目标优化问题的经典方法。其核心思想是将不同的目标函数通过线性组合的方式融合成一个单一的标量目标函数。
设λ = ( λ 1 , ⋯ , λ m ) T \lambda=(\lambda_1,\cdots,\lambda_m)^Tλ=(λ1 ,⋯,λm )T为权重向量，即对于所有i = 1 , ⋯ , m i=1,\cdots,mi=1,⋯,m和 $ \sum_{i=1}^{m}{\lambda_i=1},\lambda_i\geq0$。则以下标量优化问题的最优解为：
m a x i m i z e g w s ( x ∣ λ ) = ∑ i = 1 m λ i f i ( x ) s u b j e c t t o x ∈ Ω maximize\quad g^{ws}(x\mid\lambda)=\sum_{i=1}^{m}{\lambda_if_i(x)} \subject;to\qquad\qquad x\in\Omegamaximizegws(x∣λ)=i=1∑m λi fi (x)subjecttox∈Ω
具体步骤如下：
定义权重向量： 首先，需要为每个目标函数分配一个权重，组成一个权重向量λ = ( λ 1 , ⋯ , λ m ) T \lambda=(\lambda_1,\cdots,\lambda_m)^Tλ=(λ1 ,⋯,λm )T。权重的大小反映了各个目标在优化过程中的重要性。
构造标量目标函数： 将权重向量与目标函数相乘并求和，得到标量目标函数$ f(x) = \lambda_1 * f_1(x) + \lambda_2 * f_2(x) + … + \lambda_n * f_n(x)$。
求解单目标优化问题： 将多目标优化问题转化为求解上述标量目标函数的最小值问题。
优点：
简单易行： 加权求和法的原理简单，易于理解和实现。
控制方便： 通过调整权重向量，可以灵活地控制各个目标在优化过程中的重要性。
缺点：
难以保证解的均匀性： 当帕累托前沿非凸时，加权求和法可能无法获得所有的帕累托最优解。
目标尺度不一致问题： 如果各个目标的尺度差异较大，直接使用加权求和法可能会导致优化结果偏向于尺度较大的目标。
应用场景：
加权求和法适用于帕累托前沿凸的情况，或者目标函数数量较少，且目标尺度相对一致的多目标优化问题。
2.切比雪夫(Tchebycheff)
Tchebycheff法是另一种将多目标优化问题转化为单目标优化问题的方法，其核心思想是通过引入一个参考点，并最小化各个目标函数与参考点之间距离的最大值。
在该方法中，标量优化问题的形式为
m i n i m i z e g t e ( x ∣ λ , z ∗ ) = m a x 1 ≤ i ≤ m { λ i ∣ f i ( x ) − z i ∗ ∣ } s u b j e c t t o x ∈ Ω minimize\quad g^{te}(x|\lambda,z^)=\underset{1\leq i\leq m}{max}{\lambda_i|f_i(x)-z^_i|}\subject;to\qquad\qquad\qquad x\in\Omegaminimizegte(x∣λ,z∗)=1≤i≤mmax {λi ∣fi (x)−zi∗ ∣}subjecttox∈Ω
其中z ∗ = ( z 1 ∗ , ⋯ , z m ∗ ) z^=(z^_1,\cdots,z_m^)z∗=(z1∗ ,⋯,zm∗ )为参考点，即每个i = 1 , ⋯ , m i=1,\cdots,mi=1,⋯,m的z i ∗ = m a x { f i ( x ) ∣ x ∈ Ω } z_i^=max{f_i(x)|x\in\Omega}zi∗ =max{fi (x)∣x∈Ω}。
具体步骤如下：
定义参考点： 选择一个参考点Z = ( z 1 , z 2 , . . . , z n ) Z = (z_1, z_2, ..., z_n)Z=(z1 ,z2 ,...,zn )。
构造标量目标函数： 对于每个目标函数 fi(x)，计算其与参考点之间的距离∣ f i ( x ) − z i ∣ |f_i(x) - z_i|∣fi (x)−zi ∣，并取这些距离中的最大值作为标量目标函数f ( x ) = m a x ( ∣ f 1 ( x ) − z 1 ∣ , ∣ f 2 ( x ) − z 2 ∣ , . . . , ∣ f n ( x ) − z n ∣ ) f(x) = max(|f_1(x) - z_1|, |f_2(x) - z_2|, ..., |f_n(x) - z_n|)f(x)=max(∣f1 (x)−z1 ∣,∣f2 (x)−z2 ∣,...,∣fn (x)−zn ∣)。
求解单目标优化问题： 将多目标优化问题转化为求解上述标量目标函数的最小值问题。
优点：
能够保证解的多样性： Tchebycheff Approach 可以获得所有帕累托最优解，并且能够保证解在帕累托前沿上的均匀分布。
目标尺度不一致问题： Tchebycheff Approach 能够有效地处理目标尺度不一致的问题。
缺点：
需要确定参考点： Tchebycheff Approach 需要选择一个合适的参考点，这可能会增加算法的复杂性。
标量目标函数不光滑： 对于连续多目标优化问题，Tchebycheff Approach 构造的标量目标函数不光滑，可能会影响算法的收敛速度。
应用场景：
Tchebycheff Approach 适用于目标函数数量较少，且帕累托前沿非凸的多目标优化问题。
3.边界交叉（Boundary Intersection ，BI）
Boundary Intersection (BI) Approach是一种将多目标优化问题转化为一系列单目标优化问题的方法，其核心思想是通过求解一系列与帕累托前沿边界相交的线段的交点来近似帕累托前沿。
从几何学角度看，这些BI方法旨在找到最上边界与一组线的交点。如果这些线在某种意义上是均匀分布的，则可预期由此生成的交点能很好地逼近整个PF。在数学上，我们考虑以下标量优化子问题：
m i n i m i z e g b i ( x ∣ λ , z ∗ ) = d s u b j e c t t o z ∗ − F ( x ) = d λ , x ∈ Ω minimize\qquad g^{bi}(x|\lambda,z^)=d\ subject;to\quad z^-F(x)=d\lambda,x\in\Omegaminimizegbi(x∣λ,z∗)=dsubjecttoz∗−F(x)=dλ,x∈Ω
其中，λ \lambdaλ和z ∗ z^*z∗分别为权重向量和参考点。
如图1所示，约束z ∗ − F ( x ) = d λ z^*-F(x)=d\lambdaz∗−F(x)=dλ确保F ( x ) F(x)F(x)总是在中，即方向为λ \lambdaλ并通过z ∗ z^*z∗的直线。目标是将F ( x ) F(x)F(x)推到尽可能高的位置，使其达到可实现目标集的边界。
\qquad\qquad\qquad\qquad\qquad\qquad\qquad图1 边界交叉法说明
上述方法的缺点之一是必须处理等式约束。在我们的实现中，我们使用惩罚法来处理该约束。更确切地说，我们考虑
m i n i m i z e g b i p ( x ∣ λ , z ∗ ) = d 1 + θ d 2 s u b j e c t t o x ∈ Ω minimize\quad g^{bip}(x|\lambda,z^*)=d_1+\theta d_2\ subject;to\qquad\qquad x\in\Omegaminimizegbip(x∣λ,z∗)=d1 +θd2 subjecttox∈Ω
其中，
d i = ∥ ( z ∗ − F ( x ) ) T λ ∥ ∥ λ ∥ d_i=\frac{\lVert(z^*-F(x))^T\lambda\lVert}{\lVert\lambda\lVert}di =∥λ∥∥(z∗−F(x))Tλ∥
d 2 = ∥ F ( x ) − ( z ∗ − d 1 λ ) ∥ d_2=\lVert F(x)-(z^*-d_1\lambda)\lVertd2 =∥F(x)−(z∗−d1 λ)∥
θ > 0 \theta>0θ>0为预定义罚因子。如图2所示，d 1 d_1d1 为z ∗ z^*z∗和y yy之间的距离，d 2 d_2d2 为F ( x ) F(x)F(x)和L LL之间的距离。如果θ \thetaθ设置合适，(4)和(5)的解应非常接近。此后，我们将这种方法称为基于惩罚的边界交叉(penalty-based boundary intersection, PBI)法。与Tchebycheff法相比，PBI法（或一般BI方法)的优点如下。
\qquad\qquad\qquad\qquad\qquad\qquad图2 基于惩罚的边界交叉法说明
在两个以上目标的情况下，设PBI法和Tchebycheff法使用同一组均匀分布的权重向量，PBI法得到的最优解应比Tchebycheff法得到的最优解分布更均匀，特别是当权重向量数量不多时。
如果x xx支配y yy，则仍有可能出现g t e ( x ∣ λ , z ∗ ) = g t e ( y ∣ λ , z ∗ ) g^{te}(x|\lambda,z^)=g^{te}(y|\lambda,z^)gte(x∣λ,z∗)=gte(y∣λ,z∗)，而g b i p g^{bip}gbip和其他BI聚合函数则很少出现。
具体步骤如下：
定义参考点： 选择一个参考点$ Z = (z_1, z_2, …, z_n)$。
构造一系列线段： 以参考点为起点，构造一系列方向不同的线段。这些线段的端点即为帕累托前沿上的点。
求解单目标优化问题： 对于每条线段，求解与之相交的帕累托前沿边界上的点，并将其作为帕累托最优解的一部分。
优点：
能够处理非凸帕累托前沿： BI Approach 能够有效地处理帕累托前沿非凸的情况。
能够保证解的均匀性： 通过合理地选择线段的方向和数量，可以保证解在帕累托前沿上的均匀分布。
缺点：
需要处理等式约束： BI Approach 需要处理与帕累托前沿边界相交的线段与帕累托前沿的等式约束。
计算量较大： BI Approach 需要求解一系列单目标优化问题，计算量可能较大。
应用场景：
需要处理等式约束： BI Approach 需要处理与帕累托前沿边界相交的线段与帕累托前沿的等式约束。
- 计算量较大： BI Approach 需要求解一系列单目标优化问题，计算量可能较大。
应用场景：
BI Approach 适用于帕累托前沿非凸，且目标函数数量较多的多目标优化问题。