「引言」随着多目标优化应用的广泛推进，对实际应用中的昂贵优化问题的关注也日益增加，例如工业设计中的空气动力学性能优化、机器学习中的超参数优化问题等。在昂贵多目标优化中，当不同优化目标的评价成本不一致时，这类问题被称为异构多目标优化问题。目前，对具有异构目标的多目标优化问题的研究相对比较少，且集中在具有快速目标和慢速目标不一致的双目标问题上。为了更有效地解决该类问题，近日西湖大学工学院可信及通用人工智能实验室（TGAI）与德国比勒菲尔德大学合作，在计算智能的顶级期刊IEEE TSMC期刊上发表了一篇题为《Alleviating Search Bias in Bayesian Evolutionary Optimization with Many Heterogeneous Objectives》的文章。该文为两个以上的黑盒异构目标的昂贵优化问题提出了新的解决方案。该文着重应对由于不同目标允许的函数评估次数不同而导致的搜索偏差问题，从获取函数设计和代理模型构建两个角度提出了一种新的贝叶斯优化算法。让我们一起来看看吧。
原文链接：https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=10242008
01
研究背景
贝叶斯优化是一种处理黑盒优化问题的有效方法，在处理昂贵的黑盒问题上展现出了强大的优化能力，广泛用于工业设计、化学分子及药物设计、机器学习中的超参数优化等领域[1]。如图1所示，贝叶斯优化的核心包含两部分：首先，构建随机代理模型模型（如高斯过程）去学习昂贵的黑盒函数，该模型在提供均值预测的同时也给出所预测值的不确定性/可信度。其次，基于随机代理模型，构造获取函数，然后通过优化获取函数来确定最有潜力的观测位置，并采用计算机仿真或实验来采集新的训练数据。获取函数的构造需要考虑平衡搜索过程的开发和探索，通常基于统计模型的均值和不确定量来设计。
图1 贝叶斯优化
随着对多目标优化问题（MOPs）的需求不断增加，多目标贝叶斯优化引起了广泛关注。与此同时，基于种群的进化算法在多目标优化中显示出优势，因此被广泛应用于优化多目标贝叶斯方法的获取函数。然而，目前大部分多目标优化问题都基于一个假设，即每个目标的评价成本相似。这一假设使得候选解能够相互比较，从而选择在各个目标上表现良好的帕累托非支配解。然而，在许多实际优化问题中，这种假设往往难以满足。以小王考虑购车为例，他既希望车辆价格便宜（目标1），又期望驾驶舒适（目标2）。在这种情况下，价格可以通过简单查看得知，但驾驶舒适性则需要花费时间进行试驾，因而两个目标的评价成本差异显著。
图2 一个简单的异构问题
这样的异构问题对于多目标优化会带来什么影响呢？研究表明，由于评价速度较快的目标在单位时间内可以进行多次评价，从而获取更多信息，最终优化过程可能会偏向这些目标。因此，处理昂贵的异构多目标优化面临两大主要挑战：1. 如何有效利用各个目标不同的评价次数？2. 如何缓解搜索偏移？
目前，这方面的研究较少，主要可以分为基于代理模型和不基于代理模型的方法来处理这两个挑战。前者主要在进化算法中对不同评价次数的利用进行了初步的探索[2]。例如，先用单目标优化评价快的目标，再用其优化解去初始化另一个慢目标的优化。后者则开始考虑昂贵黑盒优化的大背景，用代理模型来解决该问题带来的挑战[3,4]。一个非常有趣的研究方向是如何从数据多的快目标（源域）迁移知识到数据少的慢目标（目标域），其研究动机来源于两个目标的优化解在帕累托面上是有很强的关系的。尽管这些尝试为解决异构多目标优化提供了一些思路，但是它们大都局限在两目标优化问题上，即一个目标评价成本高，另一个评价成本低。随着异构目标的数量增多，目标之间的关系更难捕捉，基于迁移学习的方法也更难回答“迁移什么”和“如何迁移”的问题。因此，处理异构的昂贵超多目标优化问题 （heterogeneous expensive MOPs, HE-MOPs）变得更加具有挑战性。本文首次利用目标的评价时间定义了HE-MOPs，并对不同的异构程度展开了讨论。基于此，本文提出了缓解搜索偏差的贝叶斯优化（SBP-BO）。该算法的主要思想是首先重新设计了快目标的代理模型的构造，并通过获取函数的设计来缓解搜索偏移。
02
研究方法
图3 SBP-BO的算法框架
针对第一个挑战，本文指出在贝叶斯优化中，评价速度快的目标相较于评价速度慢的目标多出来的评价次数主要涉及两个方面：
初始化采样阶段：由于所有目标在初始阶段都需要进行真实评价，异构的评价时间导致快速目标在单位时间内能够进行更多次评价，从而可用于其自身的单目标优化。
新样本评价阶段：同样地，相对于评价速度慢的目标，快速目标在相同时间内可以进行更多次评价。通常来说，高斯过程的训练数据不能过多，因为其复杂度随着训练数据个数的增加而增大。因此，本文提出针对这两部分额外数据分别构建代理模型，使得评价速度快的目标可以形成一个ensemble模型。
具体而言，在第一阶段，多出来的数据构成了快速目标的代理模型1，而随后的数据构成了快速目标的代理模型2。模型1将不再更新，而模型2会随着新数据的加入而重训练。需要注意的是，由于代理模型通常是轻量级模型，而高斯过程的训练复杂度随着训练数据数量的增加而增大，因此通常需要对所有训练数据进行选择，以限制其数量。
对于非异构的多目标问题，选择训练数据直接影响模型的质量，因此需要综合考虑训练数据的收敛性和多样性。然而，在异构多目标问题中，很多决策变量只被部分目标进行了真实评价（即快速目标），导致评价其收敛性和多样性变得困难。因此，本文提出的训练ensemble模型的优势在于解决了高斯过程在处理异构数据上可扩展性不佳的问题（因为模型1不再更新），从而实现了充分利用所有数据的目标。此外，也可以应用常用的训练数据的选择方法。
因此，对于决策变量X，ensemble提供的评价成本低的函数均值预测公式如下：
其中, 表示第j个评价成本低的目标的模型1，
表示第j个评价成本低的目标的模型2。最终的均值预测由两个模型根据其不确定性加权得到，即确定性高的预测的权重大，反之则权重小。
惩罚搜索偏移的获取函数
由于评价快的目标对应的代理模型预测更准确，多目标优化会慢慢偏向于快目标，为了解决这一问题，本文在贝叶斯优化的框架下，从加强对评价成本高的目标进行探索的角度，提出了一个新的获取函数 (search bias penalized acquistion function, AFSBP）。该获取函数由两部分组成，一个传统获取函数AFLCB用于平衡开发和探索，另一个惩罚函数SBP用于惩罚造成搜索偏移的快目标的搜索。因此，AFSBP的公式为：
那么，如何设计这样一个惩罚函数呢？
为了回答这个问题，本文利用指数分布函数的数学性质对每个目标定义与其评价时间的异构情况和预测均值相关的指数分布。这里，SBP的公式如下：
这里的均值是归一化之后的均值，π代表的是指数分布，即：
上式的指数分布中，λ由评价次数和每个目标的评价成本来控制：随着评价次数增多，优化接近尾声，SBP的影响需要逐渐减小，以覆盖整个帕累托面；评价的成本越低，那么算法可能对其偏移较大，因此需要较大的惩罚函数：
根据指数分布函数的性质（如图4所示），SBP的工作原理如下：
图4 指数分布函数
对于评价成本越低的目标，其对应的w值越大，从而λ越小：这种情况下，π代表的指数分布对应的概率越小，则SBP越大，因为是最小化问题，说明惩罚函数值越大。类似的，当评价成本越大时，目标值的惩罚越小，使得在该方向上更可能探索。随着优化的进行，评价次数增大，λ则减小，惩罚项就接近1，逐渐减少获取函数对于评价成本低的目标的惩罚，从而覆盖整个帕累托面。为了更加具体的展示SBP在不一样的目标上随着目标值和评价次数的变化，本文提供了SBP的等高线图，见图5。
图5 异构两目标优化的SBP的等高线图
03
实验结果
为了证实SBP-BO的有效性，本文采用了DTLZ和WFG两组多目标测试函数[5,6]。鉴于传统测试函数并未包含异构目标设置，本文通过控制评价次数，设计了专门用于测试异构目标的测试函数。实验中考察了不同的目标数量和异构程度对SBP-BO算法性能的影响，从而证实了该算法在处理异构昂贵多目标和超多目标优化问题上的有效性。
表1 在DTLZ和WFG上的实验结果
表2 不同的异构和不同快慢目标的划分对算法的影响
此外，该文还进一步测试了不同的异构情况和对于快慢目标的不同划分对于算法性能的影响，如表2所示，验证了SBP-BO可以应对不同异构的昂贵超多目标优化问题。本文进一步刻画了不同算法在同一个测试函数的不同的异构程度上找到的非支配解，如图6所示，证实了SBP-BO可以缓解搜索偏移。
图6 HK-RVEA和SBP-BO在DTLZ5上的实验结果
04
总结
该文重点研究了在昂贵的多目标/超多目标优化中涉及的异构目标优化问题，特别关注由异构目标的评价成本不一致引起的搜索偏差。为应对这一问题，本文提出了一种新的贝叶斯优化算法，即SBP-BO，用于处理两个以上的黑盒异构目标的优化问题。该算法的核心思想在于重新设计快目标的代理模型构造和获取函数设计，以缓解搜索偏移问题。在当前工作的基础上，未来可进一步研究如何更有效地利用评价快的目标上的额外数据，将本文提出的算法扩展到处理更多的异构目标，并深入研究异构目标之间更为复杂的关系，包括非线性关系，以提高模型的适应性并更全面地适应实际应用中的复杂优化问题。
参考文献
[1]Wang, Xilu, Yaochu Jin, Sebastian Schmitt, and Markus Olhofer. "Recent advances in Bayesian optimization." ACM Computing Surveys 55, no. 13s (2023): 1-36.
[2]Allmendinger, Richard, Julia Handl, and Joshua Knowles. "Multiobjective optimization: When objectives exhibit non-uniform latencies." European Journal of Operational Research 243, no. 2 (2015): 497-513.
[3]Chugh, Tinkle, Yaochu Jin, Kaisa Miettinen, Jussi Hakanen, and Karthik Sindhya. "A surrogate-assisted reference vector guided evolutionary algorithm for computationally expensive many-objective optimization." IEEE Transactions on Evolutionary Computation 22, no. 1 (2016): 129-142.
[4]Wang, Xilu, Yaochu Jin, Sebastian Schmitt, Markus Olhofer, and Richard Allmendinger. "Transfer learning based surrogate assisted evolutionary bi-objective optimization for objectives with different evaluation times." Knowledge-Based Systems 227 (2021): 107190.
[5]Huband, Simon, Philip Hingston, Luigi Barone, and Lyndon While. "A review of multiobjective test problems and a scalable test problem toolkit." IEEE Transactions on Evolutionary Computation 10, no. 5 (2006): 477-506.
[6]Deb, Kalyanmoy, Lothar Thiele, Marco Laumanns, and Eckart Zitzler. "Scalable multi-objective optimization test problems." In Proceedings of the 2002 Congress on Evolutionary Computation. CEC'02 (Cat. No. 02TH8600), vol. 1, pp. 825-830. IEEE, 2002.
END
初稿 | 王曦璐
复审 | 颜学明
终审 | 金耀初
