优化｜优化求解器自动调参

原文信息：MindOpt Tuner: Boost the Performance of Numerical Software by Automatic Parameter Tuning

作者：王孟昌 （达摩院决策智能实验室MindOpt团队成员）

一个算法开发者，可能会幻想进入这样的境界：算法只用开发一次，但可以到处部署交付。这种 ROI 无穷大的壮丽景象，不光开发者很喜欢，老板们更喜欢。

但是，早在 1997 年，IBM 两位学者就给这个幻想泼下一盆冷水，他们在一篇论文里证明了一个结论：著名的「没有免费午餐定理」。在这篇论文里，他们写道 (大意)：「如果算法在某一类问题上性能特别好，那在其它问题上就会很糟糕」。

所以，现实中一个算法的性能表现，往往在有的场景里性能非常好，但在有的场景里却非常糟糕，有些客户能收到惊喜，而有些客户可能会受到惊吓。对于这些受到惊吓的客户，他们场景里的需求该怎么交付呢？

聪明的开发者们在算法中引入了算法参数，使用可变的算法参数来刻画不同场景里面的关键特征，这使得算法具备了适应多种场景的能力。通过小心地配置这些算法参数，我们可以让算法的实际性能达到或超出期待的水平，这样来实现一次算法开发，然后通过参数配置达成在多个场景里面交付的效果。

以求解优化问题为例，优化求解器里就内置了很多参数，这些参数的引入，使得求解器拥有了支持多种不同场景的潜力。在有些场景中，求解器的默认参数就能很好地适应；但在一些新场景里，默认参数可能不再与场景特征相匹配，甚至会明显拖慢求解效率。这时候，我们可以将新场景中的优化模型输入到调参器，让它寻找与场景更匹配的求解器参数配置，这样就能充分释放求解器在新场景中的潜力。

调参器背后的算法模拟了人类认识问题然后解决问题的过程，它通过观测参数对应的输出 (性能) 数据来拟合或学习参数与输出之间隐含的数量关系，再根据学习到的关系，来推测最有潜力的参数，然后对参数进行验证。如此反复，不断积累关于参数与性能之间关系的知识，从而作出更优的推测。

这类算法在未知的数量关系上进行优化，所以通常也称之为黑盒优化算法，因为在优化过程中没有梯度信息可以利用，所以也称为无梯度优化算法。此外，在某些应用场景里它还被称为仿真优化算法、零阶优化算法等。

我们测试了一个算例（neos-2978193-inde），这个算例来自混合整数规划的标准测试集 MIPLIB2017，它有 2 万多个变量，近 400 个约束。使用开源的优化求解器 Cbc 直接进行求解，需要 24000 秒，而使用老牌霸主级商业求解器 CPLEX 进行求解，只需要 46 秒 —— 不愧是商用求解器，效率是开源求解器的 512 倍。

而使用我们的调参器 (MindOpt Tuner) 推荐的参数，Cbc 的求解耗时居然下降到了 20 秒，足足提速 1200 倍。从 24000 秒到 20 秒，1200 倍提速！也就是说，在这个问题上，使用调参器推荐的参数，开源的 Cbc 一举反超 CPLEX，实现 2.3 倍的效率领先。

我们对 MIPLIB2017 中的 240 个算例进行了测试，如果把每个模型的求解时间放开到 3 万秒，Cbc 使用默认参数只能解出 106 个模型，而使用我们的调参器推荐的参数，Cbc解出了 121 个模型，最大加速倍数达到 1226 倍，这106 个算例的平均求解时间从 4209 秒下降到 1196 秒，平均加速倍数达到 17.85 倍。

所以，对于你设计的算法或程序，倘若一时性能不如意，千万不要妄自菲薄，不调一下参数，你咋知道它不会使出惊世骇俗的洪荒之力呢？

调参器本质上是在对输入输出关系进行学习，并在此之上进行推理，因此，除了对求解器进行参数优化，只要我们的算法或程序能对参数输入进行响应，我们就能借助调参器 (或者说黑盒优化算法) 找到最符合我们需求的输入。

如果把矿石的投料配比作为参数，我们可以通过冶炼化学反应过程的模拟器，来计算某一配比下铁水的成份和冶炼的成本，接入调参器，我们就能得到能满足成份要求且成本最低的配比方案。如果把药物的分子结构编码为参数，我们可以把生物化学反应的模拟程序接入调参器，我们就能得到最有潜力的药物成份。如果把工件加工顺序作为参数，我们可以通过生产仿真程序来推演订单交付的准时率，把仿真模型接入调参器，我们就能得到交付最及时的生产计划。

总之，如果某个业务场景可以进行模拟或验证，那么调参器（黑盒优化算法）就可以帮助我们找到最佳的答案。

参考文献

[1] Wolpert & Macready (1997). No Free Lunch Theorems for Optimization. IEEE Transactions on Evolutionary Computation, 1(1), 67-82

[2] Zhang et al (2023). MindOpt Tuner: Boost the Performance of Numerical Software by Automatic Parameter Tuning. arXiv.2307.08085

[3] Cbc: https://github.com/coin-or/Cbc

[4] CPLEX: https://www.ibm.com/cn-zh/products/ilog-cplex-optimization-studio

[5] MindOpt: https://opt.aliyun.com/

[6] MIPLIB2017: https://miplib.zib.de/