0 前言

多目标优化在推荐系统、物流配送、路径规划等中有广泛的应用
一些多目标优化算法主要就是求解问题的 Pareto 前沿或者近似前沿。从目标空间来看，就是他的边界了。

1. 优化问题

1.1 无约束的单目标优化问题

minxf(x),x∈RN(1)min_x \quad f(x), x \in R^N \tag{1}minxf(x),x∈RN(1)
其中，x 的取值为 n 维实数空间 R^N, f(x) 为连续一阶可导函数

1.2 无约束的多目标优化问题

minxF(x)=[f1(x),f2(x),...,fK(x)],x∈RN(2)min_x \quad F(x) = [f_1(x), f_2(x), ... , f_K(x)], x \in R^N \tag{2}minxF(x)=[f1(x),f2(x),...,fK(x)],x∈RN(2)
其中，K 为子目标的个数，xxx 的取值为 N 维实数空间，fk(x)f_k(x)fk(x) 为连续一阶可导函的子目标函数。

1.3 带约束的单目标优化问题

minxf(x)min_x \quad f(x)minxf(x)
s.t.gi(x)≥0,i∈[1,M](3)s.t. g_i(x) \geq 0, i \in [1, M] \tag{3}s.t.gi(x)≥0,i∈[1,M](3)
hj(x)=0,j∈[1,L]h_j(x) = 0, j \in [1, L]hj(x)=0,j∈[1,L]

其中 s.t.s.t.s.t. 为 subject to 的缩写，表示受限于的意思

令 DDD 为上述多目标优化问题的可行域，即：
D={x∣gi(x)≥0,i∈[1,M],hj(x)=0,j∈[1,L]}D = \{ x | g_i(x) \geq 0, i \in [1, M], h_j(x) = 0, j \in [1, L]\}D={x∣gi(x)≥0,i∈[1,M],hj(x)=0,j∈[1,L]}

1.4 带约束的多目标优化问题

带约束的多目标问题 MOP (multi-objective optimization problem)
minxF(x)=[f1(x),f2(x),...,fK(x)]min_x \quad F(x) = [f_1(x), f_2(x), ... , f_K(x)]minxF(x)=[f1(x),f2(x),...,fK(x)]
s.t.gi(x)≥0,i∈[1,M](4)s.t. g_i(x) \geq 0, i \in [1, M] \tag{4}s.t.gi(x)≥0,i∈[1,M](4)
hj(x)=0,j∈[1,L]h_j(x) = 0, j \in [1, L]hj(x)=0,j∈[1,L]
令 DDD 为上述多目标优化问题的可行域，即
D={x∣gi(x)≥0,i∈[1,M],hj(x)=0,j∈[1,L]}D = \{ x | g_i(x) \geq 0, i \in [1, M], h_j(x) = 0, j \in [1, L]\}D={x∣gi(x)≥0,i∈[1,M],hj(x)=0,j∈[1,L]}

2. 多目标优化的解集:解集定义

对于多目标优化问题 MOP，通常不存在解 x∗∈Dx^* \in Dx∗∈D,使得目标 fi(x),∀i∈[1,K]f_i(x), \forall i \in [1, K]fi(x),∀i∈[1,K], 同时达到最小值
在描述 MOP 的解集之前，我们先来定义多目标里面的相等、严格小于、小于、小于且不相等的含义：
设 RNR^NRN 为 NNN 维实向量空间，y=(y1,y2,...,yN)T,z=(z1,z2,...,zN)Ty = (y_1, y_2, ..., y_N)^T, z = (z_1, z_2, ..., z_N)^Ty=(y1,y2,...,yN)T,z=(z1,z2,...,zN)T
f(n)={相等y=z⇔yi=zi,i=1,2,...,N严格小于y

2.1 可行解

对于某个 x∈Xx \in Xx∈X，如果 x 满足（4）中的约束条件 gi(x)≥0,i∈[1,M]和hj(x)=0,j∈[1,L]g_i(x) \geq 0, i \in [1, M] 和 h_j(x) = 0, j \in [1, L]gi(x)≥0,i∈[1,M]和hj(x)=0,j∈[1,L] 则称 xxx 为可行解

两个目标函数

三个目标函数

2.2 可行解集合

由 XXX 中的所有的可行解组成的集合称为可行解集合，记为XfX_fXf，且 Xf⊆XX_f \subseteq XXf⊆X

2.3 Pareto 支配 (Pareto Dominance)

定义：∀x1,x2∈Xf\forall x_1, x_2 \in X_f∀x1,x2∈Xf，如果对于 ∀i∈[1,M]\forall i \in [1, M]∀i∈[1,M]，都有 fi(x1)≤fi(x2)f_i(x_1) \leq f_i(x_2)fi(x1)≤fi(x2) 并且, ∃j∈[1,L]\exists j \in [1, L]∃j∈[1,L]，使得 fj(x1)

2.4 Pareto 最优解

一个解 x∗∈Xfx^* \in X_fx∗∈Xf，若 ¬∃x∈Xf：x支配x∗\neg\exists x \in X_f：x 支配 x^*¬∃x∈Xf：x支配x∗，则 x∗x^*x∗ 被称为 Pareto 最优解（或非支配解）

2.5 Pareto 最优解集

Pareto 最优解集是所有 Pareto 最优解的集合，定义如下：
P∗={x∗∣¬∃x∈Xf：x支配x∗}P^* = \{x^*|\neg\exists x \in X_f：x 支配 x^*\}P∗={x∗∣¬∃x∈Xf：x支配x∗}

2.6 Pareto 前沿面

Pareto 最优解集 P∗P^*P∗ 中的所有 Pareto 最优解对应的目标矢量组成的曲面称为 Pareto 前沿面 PF∗PF^*PF∗：
PF∗={F(x∗)=(f1(x∗),f1(x∗),...,fm(x∗))T∣x∗∈P∗}PF^* = \{F(x^*) = (f_1(x^*), f_1(x^*), ..., f_m(x^*))^T|x^* \in P^*\}PF∗={F(x∗)=(f1(x∗),f1(x∗),...,fm(x∗))T∣x∗∈P∗}

3. 实例阐述 Pareto

3.1 第一个实例

1：解 A 优于解 B（解 A 强帕累托支配解 B）

假设现在有两个目标函数，解 A 对应的目标函数值都比解 B 对应的目标函数值好，则称解A比解 B 优越，也可以叫做解 A 强帕累托支配解 B，举个例子

下图中代表的是两个目标的的解的情况，横纵坐标表示两个目标函数值，E 点表示的解所对应的两个目标函数值都小于 C，D 两个点表示的解所对应的两个目标函数值，所以解 E 优于解 C,D

2：解 A 无差别于解 B（解 A 能帕累托支配解 B）A,B两点严格意义上是非支配关系

同样假设两个目标函数，解 A 对应的一个目标函数值优于解 B 对应的一个目标函数值，但是解 A 对应的另一个目标函数值要差于解 B 对应的一个目标函数值，则称解 A 无差别于解B，也叫作解 A 能帕累托支配解 B，举个例子，还是上面的图，点 C 和点 D 就是这种情况，C 点在第一个目标函数的值比 D 小，在第二个函数的值比 D 大。

3：最优解

假设在设计空间中，解 A 对应的目标函数值优越其他任何解，则称解 A 为最优解，举个例子，下图的 x1x_1x1 就是两个目标函数的最优解，使两个目标函数同时达到最小，但实际生活中这种解是不可能存在的，由此提出了帕累托最优解

4：帕累托最优解

同样假设两个目标函数，对于解 A 而言，在变量空间中找不到其他的解能够优于解A（这里的优于一定要两个目标函数值都优于 A 对应的函数值），那么解 A 就是帕累托最优解，举个例子，下图中应该找不到比对应的目标函数都小的解了吧，即找不到一个解优于 x1x_1x1 了，同理也找不到比 x2x_2x2 更优的解了，所以这两个解都是帕累托最优解，实际上，这个范围的解都是帕累托最优解。因此对于多目标优化问题而言，帕累托最优解只是问题的一个可接受解，一般都存在多个帕累托最优解，这个时候就需要自己决策了。