下载掌阅APP，畅读海量书库
立即打开
本节将从数学角度阐述本书的主要研究问题，即昂贵的多目标优化问题。其主要内容包括昂贵的多目标优化问题定义及与其相关的基础概念，即帕累托支配关系、帕累托最优集、帕累托前沿、 θ- 支配关系、交互变量、目标函数可分性和可分多目标优化问题。
不失一般性，本书考虑如下连续昂贵的多目标优化问题，即
其中，
是决策（变量）空间；
是目标空间；
是从决策向量
x
=（
x
1
，
x
2
，…，
x
D
）
T
到目标向量
F
（
x
）=（
f
1
（
x
），
f
2
（
x
），…，
f
M
（
x
））
T
的映射。决策空间包含
D
个决策变量维度，目标空间包含
M
个可能相互冲突的优化子目标。
F
（
x
）的单次评估代价昂贵，并且由于可用资源的有限性，只能进行有限次的函数评估。为了描述方便，本书将
D
记为决策变量空间的维度。特别地，当
D
≥10时，原昂贵的多目标优化问题被称为高维昂贵的多目标优化问题。图1.2给出了本书考虑的昂贵的多目标优化问题的示例。
图1.2 昂贵的多目标优化问题示例
昂贵的多目标优化问题的挑战性主要在于两方面。首先，因为多个子目标之间可能存在冲突性，即一个子目标的变动容易引起其他目标的变动，所以优化器很难搜索到一个最优解
能同时最小化或者最大化所有
M
个子目标。其次，该类问题的单次函数评估代价昂贵，但受限于现实资源，只能执行有限次的函数评估，导致查找全局最优解的难度大大增加。因为维度诅咒（the Curse of Dimensionality）
[21]
和边界问题（Boundary Issue）
[29]
，求解高维昂贵的多目标问题通常具有更高的挑战性。具体而言，维度诅咒又称维度灾难，在本书中体现在两方面：采样复杂度随着决策变量维度呈指数增长，即使样本量非常大也不可能用有限多的样本点密集地填充决策空间；高斯过程的采样复杂度随数据点个数呈指数增长。边界问题又称过度探索（Over Exploration），一般指优化算法搜索到的最终解大多位于搜索空间的边界区域，是不可行解或低质量的可行解，导致过多的函数评估代价耗费在搜索边界附近区域。
为描述方便，在此引出如下多目标优化问题中的相关概念。
定义1.1： 帕累托支配关系（Pareto Dominance） [30]
假设存在两个向量 u =（ u 1 ， u 2 ，…， u m ）和 v =（ v 1 ， v 2 ，…， v m ），当且仅当 u 偏序小于 v ，称 u 支配 v （记为 u ≤ v ），即∀ i ∈{1，2，…， m }， i ≤ v i ∧∃ i ∈{1，2，…， m }： u i < v i 。
定义1.2： 帕累托最优集（Pareto Optimal Set，POS） [31]
一个能够最好地平衡所有优化子目标的解
被称为帕累托最优解。即存在解
使得
v
=
F
（
x'
）=（
f
1
（
x'
），
f
2
（
x'
），…，
f
M
（
x'
））
T
支配
u
=
F
（
x
*
）=（
f
1
（
x
*
），
f
2
（
x
*
），…，
f
M
（
x
*
））
T
。一个多目标优化问题的所有帕累托最优解的集合称为帕累托最优集
P
*
。
定义1.3： 帕累托前沿（Pareto Front，PF） [32]
对于给定的如定义1.1所示的多目标优化问题 F （ x ）和其帕累托最优集 P * ， P * 对应的所有非支配目标向量的集合称为帕累托前沿 PF * ，即 PF * ={ u = F （ x ）| x ∈ P * }。
图1.3展示了一个最大化、有两个子目标的多目标优化问题的非支配解、被支配解和帕累托前沿。其中，黑色的点代表非支配解，其他颜色的点代表被支配解；由所有非支配解组成的前沿面为帕累托前沿，是对应于帕累托最优解集的非支配目标向量的集合。
图1.3 多目标优化问题中的非支配解、被支配解和帕累托前沿示意图（见彩插）
定义1.4： θ- 支配关系 [19]
给定
N
个均匀分布的权重向量
Λ
={
λ
1
，
λ
2
，…，
λ
N
}，使得
X
t
中的每个解
x
t
都与
N
个簇{
C
1
，
C
2
，…，
C
N
}中的一个簇相关联。设
，
j
∈[1，2，…，
N
]，其中
d
j
，1
（
x
t
）和
d
j
，2
（
x
t
）分别为
和
是多目标优化问题的归一化目标向量。给定两个解
被称为
θ-
支配
，记为≺
θ
，当且仅当
，且
，
j
∈[1，2，…，
N
]。
d
j
，2
（
x
t
）=0能够完美地保证多样性。当
d
j
，2
（
x
t
）=0时，
d
j
，1
（
x
t
）的值越小，表示收敛性越好。
定义1.5： 目标函数可分性 [35]
一个函数
f
（
x
）：
R
n
→
R
是部分可分的，如果其可以表示为多个子函数的和
f
（
x
）=
，每个子函数依赖于一组如定义1.5所示的相互依赖的变量，如果所有子函数都是一维函数，那么函数
f
（
x
）被称为完全可加可分的或完全可分的函数。如果
f
（
x
）既不部分可分，也不完全可分，就被称为不可分函数。