下载掌阅APP，畅读海量书库
立即打开
本节主要介绍用于求解昂贵的多目标优化问题的贝叶斯优化方法的相关工作。因为本书的研究内容分别聚焦于低维和高维决策空间中的多目标贝叶斯优化方法，所以1.3.1节和1.3.2节分别对低维和高维多目标贝叶斯优化方法的相关研究进行综述。本节首先对低维决策空间中的基于自适应采样的批量多目标贝叶斯优化方法的相关研究进行介绍，如1.3.1节中“基于EGO的多目标贝叶斯优化方法”内容所示。其次分别对基于块坐标更新的、可加高斯结构的和变量交互分析的高维多目标贝叶斯优化方法的研究现状进行阐述（分别对应本节其他小节内容）。
多目标贝叶斯优化方法是求解昂贵黑盒问题的有效方法之一。根据获取函数的种类，当前典型的多目标贝叶斯优化方法可以大致分为3类，即基于有效全局优化（Efficient Global Optimization，EGO） [37] 、基于超体积改进（Hypervolume Improvement，HVI）和基于预测熵搜索（Predictive Entropy Search，PES）的多目标贝叶斯优化方法。下面分别对3种相关工作进行综述。
1．基于EGO的多目标贝叶斯优化方法
基于EGO的多目标贝叶斯优化方法将单目标EGO方法进行扩展用于求解多目标优化问题。该类方法主要包括ParEGO [38] 、SMS-EGO [39] 、MOEA/D-EGO [40] 及这3种方法的其他变形，如EGOMO [41] 、Simple-EGO [42] 、Multi-objective EGO [43] 和MOEA/D-ASS [44] 等。具体而言，ParEGO首先通过增广切比雪夫（the Augmented Tchebycheff）函数将原多目标优化问题的多个子目标对应的评估代价聚合为单目标标量代价。然后，ParEGO将已知观察点和标量代价值作为观测数据建立高斯代理模型，并最大化单目标期望改进（Expected Improvement，EI） [37] 用于推荐下一个候选解。为了近似整个帕累托前沿，ParEGO在每个算法迭代考虑不同的权重向量，然后用增广切比雪夫函数对多个子目标进行聚合。然而，ParEGO每次只随机选择一个权重向量，导致其不能很好地、均匀地搜索到多目标优化问题的整个帕累托前沿。为了避免上述情况，SMS-EGO [39] 采用超体积改进作为获取函数，并利用协方差矩阵自适应进化策略（Covariance Matrix Adaptation Evolution Strategy，CMA-ES） [45-46] 算法优化该获取函数得到下一个候选解。但当目标数量大于两个时，由于超体积（Hypervolume，HV） [47] 的高计算复杂度，SMS-EGO变得非常耗时。此外，无论是ParEGO还是SMS-EGO，都采用串行化函数评估，即每个算法迭代只选择一个解用于真实函数评估，不能充分利用现实世界中的并行硬件计算资源。为了实现并行化函数评估，MOEA/D-EGO [40] 将基于分解思想的MOEA/D算法 [15] 和高斯代理模型结合用于求解昂贵的多目标优化问题。具体而言，它首先将原问题分解为多个子问题，然后分别为每个子问题建立一个高斯代理模型和EI获取函数。接下来，其利用MOEA/D算法优化获取函数获得下一批候选解。然而，在当前基于EGO的多目标贝叶斯优化方法中，多目标EI通常因为使用多变量分段积分计算使得计算代价昂贵，且其代价随目标个数呈指数增长。为了解决上述问题，基于期望改进矩阵（Expected Improvement Matrix，EIM） [48] 的方法在单目标EI的基础上，提出了一种新的基于多目标获取函数EIM的优化方法，其中EIM中的元素是超过每个子目标中帕累托前沿逼近点的解的单目标EI。EIM不仅具有具体的数学表达形式，而且可以使用一维积分计算，使其计算复杂度随目标个数呈线性增加，大大降低原来EGO算法中EI的计算复杂度。不确定性逐步减少（Stepwise Uncertainty Reduction，SUR） [49] 算法将EGO中使用的EI获取函数用基于SUR算法的获取函数替代，旨在连续减少低于当前帕累托最优集的偏移集的超体积，从而更加高效地近似帕累托前沿。为求解目标个数大于3个的昂贵的多目标优化问题，K-RVEA [50] 将贝叶斯优化思想引入进化算法RVEA [51] 中，利用自适应的参考向量改进优化过程中收敛性与多样性的平衡关系，有效地求解了目标个数较多的多目标优化问题。
尽管基于EGO的多目标贝叶斯优化方法可以确保收敛到昂贵的多目标优化问题的全局最优，但这些方法的候选解仅由基于EI或HVI的获取函数以串行的方式进行推荐和评估，即每次只评估一个候选解。然而在一些昂贵的多目标问题条件设置中，可以以批处理的方式同时并行地评估多个候选解。此外，在许多现实世界环境中，如果硬件资源能够负担得起并行化计算的情况下，同时评估多个候选解既能加快收敛速度，又能节省大量的计算时间。在这种情况下，串行评估候选解不能充分地利用并行硬件计算资源环境，而一次推荐多个候选解进行真实函数评估能更充分地利用计算资源。由于现实中可用于函数评估的硬件资源数量通常是固定的、有限的，所以如何从一堆候选解中选择特定数量的解以有效地平衡利用和探索之间的关系 [52-53] 成为昂贵的多目标优化问题的另一个研究挑战。
2．基于HVI的多目标贝叶斯优化方法
基于HVI的多目标贝叶斯优化方法的主要特点是，其利用与HVI相关的策略作为获取函数推荐候选解。因为超体积具有优美的帕累托依从性（Pareto Compliance），即其专注于衡量帕累托前沿的收敛性，所以该类方法普遍具有良好的帕累托收敛性，从而进一步更好地平衡收敛性和多样性 [54] 。然而，超体积的计算复杂度随目标个数的增加呈指数形式增长；且在算法迭代过程中，该类算法需要多次计算该指标值导致其计算复杂度较高。TSEMO [55] 的高斯过程采用频谱采样技术，利用HVI的获取函数、NSGA-Ⅱ算法和汤普森采样在每次迭代中选择一个新的候选解进行评价。为了减少计算时间，基于超体积期望改进（Expected HVI，EHVI）的方法EHVI-MOBGO [56] 引入了HVI的多点机制。其首先将目标空间划分为几个子空间，然后以TEHVI（Truncted Expected HVI）为选择策略（获取函数），通过在每个子目标空间寻找最优解实现以批处理的方式推荐候选解。尽管EHVI-MOBGO能够更合理地、充分地利用CPU，并且能加快HV的计算速度，但在求解实际优化问题时计算成本仍然太高。为了进一步降低其计算复杂度，EHVIG [57] 利用EHVI每个组成成分可微的性质，提出基于预期超体积改进梯度（EHVI Gradient，EHVIG）的获取函数，并使用以下两种策略提高获取函数优化器的优化效率：将梯度下降法应用于多目标贝叶斯优化方法中；因为EHVIG的最优解可以认为是一个零向量，所以其将零向量作为全局优化过程的停止准则。尽管EHVIG取得了不错的优化效果，但是关于HVI的理论分析仍然存在很大发展空间。为了进一步更深入地对HVI进行分析，文献[58]引入了超体积聚合（Hypervolume Scalarization）的概念，首次将超体积和聚合函数联系在一起。同时，该方法利用超体积聚合与超体积的关系，从理论上推导出超体积遗憾界限（HV Regret Bound），并用实验证明了该方法关于帕累托前沿的完美收敛性，为多目标贝叶斯优化方法提供了有力的理论支撑。为了进一步从可分析梯度的角度对基于HVI的获取函数进行优化， q EHVI [59] 将原有的EHVI获取函数扩展到并行化函数评估的情况。该方法对 q 个新候选解的联合EHVI进行精确计算，使得误差最大为蒙特卡罗积分误差。该方法之前的EHVI计算依赖于无梯度或近似梯度获取函数优化，而 q EHVI通过自动差分计算蒙特卡罗估计器的精确梯度，从而能够使用一阶和准二阶方法对获取函数进行高效的、有效的优化。然而， q EHVI的优化性能在解决带约束的昂贵黑盒问题时性能大大降低。为了解决上述问题， q NEHVI [60] 进一步将 q EHVI扩展到带约束、并行（批量）采样的情况。具体而言， q NEHVI提出了一个新的并行获取函数NEHVI，通过对其优化可以生成多个候选解。同时， q NEHVI将并行EHVI的计算复杂度从相对于批处理大小的指数级降低到多项式级别。实验结果表明， q NEHVI可以通过样本平均逼近的梯度方法对获取函数进行优化，有效地求解了有噪声和无噪声的昂贵的多目标优化问题。为了进一步提升解的多样性，DGEMO [61] 采用近似方法表示片段连续的帕累托前沿，并利用HVI获取函数以批处理的方式推荐候选解。同时，该方法对候选解的多样性进行优化，以便有效地近似帕累托前沿的最优有希望的区域。为了有效地解决输入决策空间中的噪声问题，MVAR（Multivariate Value-at-risk） [62] 考虑了不确定目标的风险测量。由于在许多情况下直接优化MVAR在计算上是不可行的，所以在该方法中提出了一种可扩展的、有理论依据的方法，即利用随机标量优化MVAR，使得整个帕累托集在一个连续流形上，可以包含无限解。然而，在上述提到的多目标贝叶斯优化方法中，帕累托最优解的结构特性没有得到很好的利用。因此，为了更好地利用帕累托最优集，帕累托集合学习（Pareto Set Learning，PSL） [63] 利用基于学习的方法近似多目标优化问题的整个帕累托最优集。它将基于分解的多目标优化算法MOEA/D从有限种群进行推广，提出一种新的基于HVI的获取函数，从而实现并行化函数评估。
尽管基于HVI的多目标贝叶斯优化方法从理论和实际做出了一些贡献，但因其较高的计算复杂度，大多数方法仅仅局限于低维决策空间中的昂贵多目标优化问题。另外，当多目标优化问题的子目标个数大于或等于3个时，这些方法的优化性能会大大降低。
3．基于PES的多目标贝叶斯优化方法
基于PES的多目标贝叶斯优化方法将信息论中熵（Entropy） [64] 的概念引入了贝叶斯优化方法，并将其用于获取函数的构建推荐下一批候选解。为了求解单目标昂贵的优化问题，熵搜索（Entropy Search，ES） [65] 和预测熵搜索（Predictive Entropy Search，PES） [66] 选择能够最大化关于全局最大值的信息期望的解作为下一个候选解，用于真实函数评估。具体而言，PES用预测分布的差分熵的期望减少作为获取函数，使该方法获得的近似值比其他基于熵搜索的方法获得的近似值更准确、有效。此外，不同于ES，PES可以很容易地对模型的超参数进行完全贝叶斯式的处理。为了求解带约束的昂贵黑盒问题，约束预测熵搜索（PES with Constraints，PESC） [67] 的获取函数不再依赖于当前的最优可行解。所以，即使在没有可行解的情况下，该算法也可以搜索到最优解。同时，PESC在其获取函数中自然地分离了每个任务（目标或约束）的贡献，使得其在解耦的情况下也是有效的。多保真最大值熵搜索（Multi-fidelity Max-value ES，MF-MES） [68] 通过引入保真信息获得更可靠的信息增益，从而进一步提高获取函数的优化效率。
为了求解昂贵的多目标优化问题，PAL（Pareto Active Learning） [69] 根据已经建立的学习模型将输入解集分为3类，即帕累托最优解、非帕累托最优解和不确定性解。在每次迭代过程中，PAL选择能够最小化不确定集大小的解作为候选解进行真实函数评估。尽管PAL提供了理论上的保证，但它仅适用于具有有限离散点集输入空间的问题。 ε -PAL [70] 用超参数 ε 以一定粒度对决策变量空间进行自适应采样，以预测一组能够覆盖整个帕累托前沿的帕累托最优解。多目标优化PES（PES for Multi-objective Optimization，PESMO） [71] 将PES扩展到多目标优化的情况，选择能最大限度地减少关于帕累托前沿后验分布的熵的点作为候选解。具体而言，PESMO的获取函数被分解为特定目标的获取函数的总和，使得在解耦的情况下，即当不同目标函数有不同评估成本时，每个目标能被单独评估。这种解耦能力对于识别评估困难的目标非常有用。除此，PESMO算法的优化成本与目标个数呈线性增长关系，提高了优化效率。然而PESMO中获取函数的优化面临三大挑战：首先，近似优化极可能得到次优解而非最优解；其次，即使是使用近似方法对获取函数进行优化，优化成本依然高昂；最后，获取函数的优化性能强烈依赖于蒙特卡罗样本的数量。为了解决上述问题，MESMO（Max-value ES for Multi-objective Optimization） [72] 采用了基于输出空间熵的获取函数，用来有效地选择需要真实函数评估的候选解，以快速地、高质量地覆盖整个帕累托前沿。与基于输入空间熵搜索的算法相比，MESMO允许更严格的近似、计算成本明显降低、鲁棒性更强。然而，大多数上述方法需要复杂的近似值评估熵，或者因为采用过度简化的近似方法而忽略多个目标之间的权衡关系。帕累托前沿熵搜索（Pareto Front ES，PFES） [73] 考虑了目标空间中帕累托前沿的信息增益，而非像其他方法一样考虑决策空间的信息增益。采用这种方式，PFES能够更直接地实现多个优化目标之间的平衡，从而更准确地近似帕累托前沿。MFOSEMO [74] 选择候选解和保真度矢量对的序列使得每单位资源成本获得的关于帕累托前沿的信息最大化。虽然上述方法对昂贵的多目标优化问题的优化效果进行了改进，但并未考虑带约束的情况。为了处理约束多目标优化问题，MESMOC（MESMO with Constraints） [75] 采用基于输出空间熵的获取函数推荐候选解用于真实函数评估，使得这些解既能满足约束条件又能尽可能地覆盖整个帕累托前沿。为了综合利用输入和输出空间的信息，联合熵搜索（Joint Entropy Search，JES） [76] 提出了一种新的获取函数——联合熵，通过优化该获取函数得到的候选解能够评估一个候选解学习最优输入和输出的联合后验分布的信息多少。除此，该方法进一步从理论上证明了联合熵是基于信息熵的获取函数的一个上界。
虽然基于熵搜索的获取函数在多目标贝叶斯优化方法中进行了深入探索，但是当前基于熵搜索的多目标贝叶斯优化方法大多局限于低维决策空间。当求解高维昂贵的多目标优化问题时，由于维度灾难和熵计算的高复杂度，该类方法的优化性能大幅度降低。
因为当前的高维多目标贝叶斯优化方法大多从高维单目标贝叶斯优化方法扩展而来，所以本书首先阐述高维单目标贝叶斯优化方法的相关研究现状，然后针对高维多目标贝叶斯优化方法的研究现状进行概括和总结。
1．高维单目标贝叶斯优化方法
为了求解高维决策空间中的昂贵黑盒问题，许多目标贝叶斯优化方法对决策空间和目标空间做了各种假设，以缓解维度灾难问题。其中最具代表的一类是基于随机嵌入（Random Embedding） [77] 的方法。REMBO [77] 是该类方法最初最经典的算法代表。该方法假设决策变量可分为重要和不重要的变量，只有重要的变量会影响目标函数值。因此，其将高维决策空间嵌入低维空间，然后通过优化重要的变量对低维子问题进行求解。SIBO [78] 在低有效维度假设的前提下，利用低秩矩阵恢复技术学习未知优化目标的子空间，并利用高斯过程上置信域采样优化该未知函数。该方法只在低维子空间进行贝叶斯优化，降低了计算复杂度。基于Dropout的高维贝叶斯优化方法 [79] 借鉴神经网络中的Dropout机制，在每次算法迭代过程中随机地选择部分决策变量进行优化，从而有效地缓解了维度灾难问题。LineBO [80] 迭代地求解原问题一维子空间的低维子问题，然后利用贝叶斯优化方法对一维子问题进行优化获得最优解。SIR（Sliced Inverse Regression） [81] 将监督降维方法——切片逆回归引入高维贝叶斯优化，在优化过程中有效地学习目标函数的内在子结构。此外，该方法还利用核函数降低计算复杂度和学习未知目标函数的非线性子集。为了避免决策空间划分的过强假设，文献[82]通过引入映射矩阵将原高维决策空间映射到低维子空间，然后再在一个由多个低维子空间构成的限制性空间而非完整的搜索空间内最大化获取函数，避免了高维决策空间中的复杂计算。HeSBO（Hashing enhanced Subspace Bayesian Optimization） [83] 借助哈希函数实现高维决策空间的低维子空间映射，并用实验结果验证了其哈希映射的有效性。ALEBO（Adaptive Linear Embedding Bayesian Optimization） [84] 通过为线性嵌入的马氏核添加多胞形边界改进可建模性，实现了决策空间的自适应线性嵌入。具有自适应扩展子空间的贝叶斯优化方法BAxUS [85] 利用一系列嵌套的嵌入子空间增加优化领域的维度。如果存在一个活跃子空间，它可以利用该子空间而不需要用户猜测其维度。BAxUS是基于一种新型随机线性子空间嵌入的方法，提高了优化效率且提供了强有力的理论保证。与HeSBO相比，BAxUS为包含全局最优解提供了最坏情况的保证。具体而言，当输入维度 D →∞时，其包含最优解的概率接近HeSBO嵌入的概率。
另一类经典的高维单目标贝叶斯优化方法假设目标函数可加，即一个目标函数可表示为几个子目标函数的线性加权和。因此，优化器可对目标空间进行划分，从而降低优化难度。ADD-GP-UCB [86] 首次对目标函数可加性做了假设，扩展了GP-UCB [87] 算法。其利用UCB作为获取函数，并根据高斯过程优美的数学性质推导出可加均值和协方差函数，以及获取函数UCB的可加形式，从而大大降低获取函数的优化复杂度，提高其优化效率。然而，ADD-GP-UCB的假设性过强，PP-GP-UCB [26] 提出了映射可加性假设的概念用于处理更广泛的函数类别。因此，可加性假设和低维有效性假设成为映射可加性假设的特例。此外，ADD-GP-UCB是一种序列评估方法，即每次只能推荐和评估一个候选解。为了实现并行化采样候选解，Batch-ADD-GP-UCB [88] 利用多种并行采样机制，通过对目标函数划分添加先验知识，利用贝叶斯推理推导出目标函数划分的后验分布，避免了对目标函数可加性的过强假设。为了处理大规模输入问题，EBO（Ensemble Bayesian Optimization） [89] 使用高效的、基于分区的函数近似器（跨越数据和特征）简化并加速搜索和优化过程，并通过使用集合和随机的方法增强这些近似器的表示能力。为了确保高效和可扩展的优化，基于正交傅里叶变换（Quadrature Fourier Features，QFF） [90] 的贝叶斯优化方法利用基于傅里叶特征和数值积分方法的高保真近似方法，通过一个固定维度的线性核在一个转换空间内对静态核进行逼近，实现了高斯核函数的近似，降低了计算复杂度。文献[91]在假设目标函数可加的基础上，进一步考虑了不同子目标函数对应的决策空间之间的交互关系，提高了优化效率。
为了更有效地利用获取函数的梯度信息和提高获取函数的优化效率，Elastic GP [92] 通过自适应地调整高斯核的长度尺寸，合理地利用了获取函数梯度信息为零处的其他有用信息，既缓解了维度灾难，又实现了获取函数的高效优化。PCA-BO [93] 将机器学习中的主成分分析方法（Principal Component Analysis，PCA）引入贝叶斯优化用于缓解维度灾难。HD-GaBO [94] 利用非欧几里得搜索空间的几何形状学习结构保持映射，并优化低维子空间中的获取函数。该方法建立在黎曼流形理论的基础上，利用几何感知的高斯过程共同学习流形嵌入和潜在子空间中目标函数的表示形式。为了实现决策空间的划分，LA-MCTS [95] 利用蒙特卡罗树和二分类器学习决策空间的划分，通过二分类器将决策空间划分为好坏两类，然后通过逐步构建蒙特卡罗树实现决策空间的划分，从而降低计算复杂度。TurBO [96] 将置信域（Trust Region）的概念引入贝叶斯优化，并利用置信域实现决策空间的划分，通过在子空间建立局部模型缓解了维度灾难。
虽然上述现有方法能成功求解昂贵的单目标黑盒问题，但大多数方法对优化问题的假设性过强。此外，上述方法仅仅局限于昂贵的单目标黑盒优化问题，而未考虑多目标黑盒问题。
2．高维多目标贝叶斯优化方法
对于高维情况，目前只有少数关于高维多目标贝叶斯优化方法的研究，主要包括ReMO [97] 、MORBO [98] 和LaMOO [99] 。ReMO利用随机嵌入 [86，88] 将高维决策空间分解为多个低维子空间，然后求解低维子空间中的多目标优化问题。MORBO使用带有置信域的局部模型 [96] 进行局部贝叶斯优化，以搜索多样性高的候选解。LaMOO从观察样本中学习模型用于划分搜索空间，然后关注可能包含帕累托前沿子集的有希望的区域。其中，决策空间划分基于优势等级数，衡量了一个解在现有解中与帕累托前沿的接近程度。然而，关于这些方法主要有以下两点考虑：①ReMO对决策空间的假设性太强。一方面，它假设只有少数决策变量维度是有效的，而大多数变量维度对目标值没有影响，导致该方法只适用于特定的昂贵的多目标优化问题。另一方面，它对不同的优化目标做了同样的假设，即假设所有目标的有效维度是相同的，这对大多数优化问题来说显然是不合理的。②虽然MORBO对决策空间和目标空间不做任何假设，但其主要考虑高斯过程采样复杂度随数据点个数呈指数增长的问题，而未考虑获取函数采样复杂度随决策空间维度呈指数增长的问题。然而，因为维度灾难，非参数回归在高维决策空间中非常具有挑战性。即使样本量非常大，也不可能用有限多的样本点密集地填充整个搜索空间。此外，用于优化获取函数的启发式方法的计算复杂度随决策空间维度呈指数增长。
在具有高维决策空间的昂贵的多目标优化问题中，决策变量之间可能存在交互关系，共同影响目标空间。从决策变量之间是否存在交互关系的角度出发，昂贵的多目标优化问题可以分为可分问题和不可分问题。对于可分问题，尤其是在高维情况下，根据变量之间的交互关系可将决策变量空间划分为多个不相交的子空间，降低决策空间的维度，以减少采样复杂性、提高获取函数的优化效率。然而，在现实应用领域的昂贵的多目标优化问题中，变量之间是否相互依赖很难确定。