黑箱优化 (BBO)

注意

“事实上，我们认为无导数优化是计算科学与工程领域最重要、最开放、最具挑战性的领域之一，并且具有巨大的实践潜力。当然，特别是由于困难且重要的应用广泛存在，这预示着在未来许多年里，它将是一个激动人心、有趣且充满挑战的领域。”——[Conn et al., 2009, Introduction to Derivative-Free Optimization, MOS-SIAM Series on Optimization]

许多现实世界中的优化问题之所以具有黑箱性质，源于以下一个或多个因素，正如经典著作《无导数优化导论》或开创性论文《凸函数的随机无梯度最小化》中所述（仅举几例）：

  • 数学建模的复杂性日益增加，

  • 科学计算的复杂程度越来越高，

  • 存在大量遗留代码或专有代码（修改成本过高或无法修改），

  • 函数评估存在噪声，

  • 内存限制，因为快速微分需要所有中间计算过程，

  • 昂贵的人工时间（计算偏导数的人工时间通常比计算时间昂贵得多），

  • 将梯度概念扩展到非光滑情况并非易事，

  • 简单的准备阶段。

注意

“这些方法有一个明显的优势，即准备阶段简单（计算函数值的程序总是比计算梯度向量的程序简单得多）。”——[Nesterov&Spokoiny, 2017, FoCM]

下面介绍了一些黑箱优化的常见问题特征：

简而言之，对于黑箱问题，算法唯一能获取的信息是通过采样评估，而采样点可以由算法自由选择，这便引出了黑箱优化 (BBO)、零阶优化 (ZOO)、无导数优化 (DFO)、无梯度优化 (GFO) 或全局优化 (GO)。“我们……仍然觉得需要一个统一的视角。……这无疑是有趣和充满挑战的，而且顺便说一句，非常有用。”

没有免费午餐定理 (NFL)

注意

“在实践中，事实证明，在收敛速度、预期解的质量以及对适应度景观中局部次优解的敏感性等问题上找到特定领域的正确权衡至关重要。”——[Wierstra et al., 2008]

正如[Wolpert&Macready, 1997, TEVC]在数学上证明的那样，“对于任何算法，其在一类问题上的优越性能，都会被在另一类问题上的性能所抵消。”

这或许部分解释了为什么实践中存在大量来自不同研究社区的优化算法。然而，不幸的是，并非所有优化器都设计良好并被广泛接受。相关讨论请参阅设计哲学部分。

大规模黑箱优化 (LBO) 的维度灾难

可以说，所有黑箱优化器都可能面临臭名昭著的“维度灾难”（在组合优化场景中也称为组合爆炸）的风险，因为所有黑箱优化器的本质（驱动力）都基于实践中的有限采样。理论分析请参考，例如[Nesterov&Spokoiny, 2017, FoCM]。

幸运的是，对于一些现实世界的应用，可能存在一些可用的结构。如果能通过精心设计的优化策略以自动化的方式有效利用这种结构，那么收敛速度可能会显著提高（如果可能的话）。因此，任何通用的黑箱优化器可能仍需要在利用具体问题结构和探索优化器的整个设计空间之间保持一种微妙的平衡。

通用优化算法

注意

“鉴于存在大量的黑箱优化算法和优化问题，我们如何才能最好地将算法与问题相匹配。”——[Wolpert&Macready, 1997, TEVC]

“显然，仅在单个问题上评估和比较算法不足以确定其质量，因为它们的大部分优势在于其泛化到大类问题上的性能。可以说，优化的研究目标之一是为从业者提供可靠、强大和通用的算法。” 作为一个用于黑箱优化的库，一个自然的选择是首先偏好并覆盖通用优化算法（相较于高度定制化的版本），因为对于大多数现实世界的黑箱优化问题，（可能有用的）问题结构通常是事先未知的。

通用优化算法通常需要满足以下常见标准/原则：

  • 有效性和效率，

  • 优雅（美感），

  • 灵活性（多功能性），

  • 鲁棒性（可靠性），

  • 可扩展性，

  • 简洁性。

可以说，通用黑箱优化器的美感应来自于理论深度和/或实践广度，尽管审美判断在某种程度上是主观的。我们相信，设计精良的优化器能够经受住黑箱优化历史上的时间考验。关于近期的批判性讨论，请参考例如《基于隐喻的元启发式算法，呼吁行动：房间里的大象》和《演化计算方法基准测试与分析中的一个关键问题》。

关于连续优化器的基准测试，请参考例如[Hillstrom, 1977, ACM-TOMS]、[More et al., 1981, ACM-TOMS]、[Hansen et al., 2021, OMS]、[Meunier et al., 2022, TEVC]。正如[More et al., 1981, ACM-TOMS]中所述，“不在大量函数上测试算法，很容易让愤世嫉俗的观察者得出结论，即该算法是针对特定函数进行调整的”。

基于种群的优化 (POP)

注意

“解决问题的演化方法的本质是将可能的解决方案等同于种群中的个体，并根据解决方案的质量引入适应度的概念。”——[Eiben&Smith, 2015, Nature]

“无导数算法和演化策略似乎是完全不同的算法，因为它们的动机来自不同的思想。然而，它们是密切相关的。”——[Ye&Zhang, 2019]

基于种群的优化器（特别是基于演化和群体的优化器，POP）对于黑箱问题通常具有以下优势，尤其是与基于个体的对应方法相比：

  • 很少的先验假设（例如，知识偏见有限），

  • 灵活的框架（易于通过例如模因算法与特定问题知识集成），

  • 鲁棒的性能（例如，对于噪声扰动或超参数），

  • 多样化的解决方案（例如，用于多模态/多目标/动态优化），

  • 新颖性（例如，超越设计问题的直觉）。

关于POP的详细信息（模型、算法、理论和应用），请参考例如以下撰写精良的综述或书籍（仅举几例）：

  • Miikkulainen, R. and Forrest, S., 2021. A biological perspective on evolutionary computation. Nature Machine Intelligence, 3(1), pp.9-15.

  • Schoenauer, M., 2015. Chapter 28: Evolutionary algorithms. Handbook of Evolutionary Thinking in the Sciences. Springer.

  • Eiben, A.E. and Smith, J., 2015. From evolutionary computation to the evolution of things. Nature, 521(7553), pp.476-482.

  • De Jong, K.A., Fogel, D.B. and Schwefel, H.P., 1997. A history of evolutionary computation. Handbook of Evolutionary Computation. Oxford University Press.

  • Forrest, S., 1993. Genetic algorithms: Principles of natural selection applied to computation. Science, 261(5123), pp.872-878.

关于连续随机搜索的原则性设计，请参考例如[Nikolaus&Auger, 2014]；[Wierstra et al., 2014, JMLR]，仅举几例。

对于每个算法家族，我们尽力在其自身的API文档中提供一些广为认可的参考文献。您也可以查看这个在线项目，其中包含一个（不断增长的）演化计算 (EC) 和群体智能 (SI) 论文列表，这些论文发表在许多（虽然不是全部）顶级以及专注于 EC/SI 的期刊和会议上。

黑箱优化的局限性

注意

“如果您能够获得清晰的导数（即使需要付出相当大的努力），并且定义您问题的函数是光滑且无噪声的，那么您不应该使用无导数方法。也许无导数方法最主要的局限性在于，在串行计算机上，尝试优化超过几十个变量的问题通常是不合理的，尽管一些最新的技术可以处理数百个变量的无约束问题。”——[Conn et al., 2009, Introduction to Derivative-Free Optimization]

非常重要的一点是，并非所有优化问题都能很好地适应黑箱优化器。事实上，它们在科学和工程领域的滥用已导致广泛的批评。尽管并非总是如此，黑箱优化器通常被视为“搜索方法的最后选择”。当然，“需要梯度知识的一阶方法在实践中并非总是可行的。”（引自 [Mhanna&Assaad, 2023, ICML]）