昂贵目标函数的全局最大化

计算科学 优化
2021-12-22 01:33:40

我对全局最大化许多()实参数(复杂模拟的结果)的函数很感兴趣。但是,所讨论的函数的评估成本相对较高,每个参数集大约需要 2 天。我正在比较不同的选项,想知道是否有人有建议。30

我知道有一套用于这种过程的方法,包括开发近似函数,然后最大化那些(例如Jones 等人“昂贵的黑盒函数的有效全局优化”)。但是,这似乎相对涉及到代码。

我确实有能力并行运行大量模拟(50+)。这似乎建议使用诸如遗传算法之类的东西来进行这种优化——因为我可以尽可能快地创建一组候选解决方案。

以下是我的问题: 1) 有没有人有免费实现这种全局求解器/建议的经验?2)这里是否有理由选择或避免遗传算法?

这是一个物理问题,我早期的实验表明,当我更改参数时,品质因数的变化相当平稳。

更新:

感谢您的帮助!更多细节:我不需要超出最大位置的任何信息。模拟是确定性的,而不是蒙特卡洛,因此复杂性不是什么大问题。参数没有明确的界限或约束。我拥有的另一条信息(之前没有提到)是对所需最大值的大小的感觉。虽然我正在寻找全局最大值,但我也会对这种规模或更大的任何东西感到满意 - 我不知道这是否会提供任何帮助。希望如果我更系统地进行筛选(Brian Borchers 建议的拉丁超立方体),这将会出现。

4个回答

当目标函数的评估成本非常高时,遗传算法是一个非常糟糕的选择——这些方法需要在每一代(并行性可以帮助)和很多代(本质上是顺序的)中进行大量的函数评估。在两天内每一代,这将非常缓慢。

你没有提到这个问题是从哪里来的。您是在统计分析似然面(在这种情况下,您需要的不仅仅是最优参数和目标值)还是只是优化目标函数?

您还没有提到目标函数计算是精确还是不准确。通常情况下,当通过蒙特卡罗模拟计算目标函数时,这些值非常嘈杂。这会误导许多优化算法。响应面方法通过消除噪声来帮助解决这个问题。

您没有提到对参数的任何限制。他们有界吗?参数之间是否存在线性或非线性约束?

很有可能你的 30 个参数中的大多数对问题来说并不是那么重要。我建议使用实验设计筛选方法,首先确定 30 个参数中的哪些参数在优化中真正重要,然后在为不重要的参数设置合理值后,对重要参数进行优化。拉丁超立方采样等方法对于筛选出相对不重要的参数非常有帮助。在这个筛选阶段,您可以轻松使用数百个处理器。

在将参数数量减少到更合理的大小后,我会使用响应面方法来优化剩余参数。如果响应曲面确实是多模态的,并且您使用了过于简单的响应曲面模型(通常人们只是拟合二次模型),那么您很容易被误导并错过全局最大值。当心!在这个阶段,您可以通过使用可以很好地覆盖参数空间的实验设计再次利用大量处理器。寻找拟合模型远离计算值的设计点——这表明响应面在该区域中运行不佳。您可能必须在参数空间的不同区域中构建响应曲面。

作为最后一步,您可以从响应面优化中的参数开始,并尝试通过一次调整一个(坐标下降)来改进筛选出的参数的值。

我将支持 DAKOTA 的建议作为这种优化的框架。如果您只打算进行一次优化,那么手动组织计算可能会更容易,但如果您要重复进行,那么 DAKOTA 将非常有帮助。

  1. 我对这类求解器没有任何经验;我的一些同事使用过它们。DAKOTA似乎是推荐用于此类任务的软件包。它包括一个界面,允许用户重复提交作业到提交队列,并将输出用于参数研究、敏感性分析等。我对它还不够熟悉,不知道它是否会利用运行许多模拟同时。

  2. 假设您的参数是连续的,如果品质因数随着参数的变化而平滑变化,那么代理模型应该可以合理地拟合品质因数,并且代理导数信息应该有助于改进收敛。对于 30 个参数,确定性无导数优化方法也应该有用;再一次,平滑度应该会有所帮助。相比之下,遗传算法根本不会使用衍生信息,并且通常需要调整突变率、重组率和选择参数等参数才能获得良好的性能。作为算法选择,我会使用遗传算法作为后备,因为我希望精心设计的代理优化或确定性无导数优化方法具有更好的收敛行为。

查看 TOMLAB、DAKOTA 和 OpenMDAO 进行黑盒优化。


编辑#3:贝叶斯优化与 EGO 非常相似:

https://github.com/mwhoffman/pybo

https://github.com/hyperopt/hyperopt

有限许可:

https://github.com/rmcantin/bayesopt

https://github.com/HIPS/Spearmint


编辑#2:

第一种方法是围绕昂贵的函数构建元模型/代理(使用克里金法/GP),并使用这些附加信息更快地找到全局最优点,并且评估次数更少(EGO)。

MDAS 中的第二种方法是通过在多个级别上进行一些巧妙的调整来进行直接搜索。

启发式方法本质上是遗传的/随机的,没有任何保证。


编辑#1:

TOMLAB 是基于 MATLAB 的工具,根据 Sahinidis 的论文,它具有最佳的优化速度/质量。但这是具有重要企业用途的商业工具。我不使用这个。

除了一般优化之外,DAKOTA 更适合不确定性量化。基于 c++ 和一些遗留的 Fortran 代码。虽然在 LGPL 许可下和可供下载的二进制文件,但至少从我在 Win7 上使用 GCC 或 MSVS/ifort 的经验来看,很难重新编译。依赖于 boost、lapack、cmake 进行构建。基本上,这是许多开源求解器和少数商业求解器的包装器。这是 SNL 产品,与 Sandia NL 的其他项目紧密集成。我能够成功地集成这个而不是一些 IMSL 例程。Sahinidis 的论文错过了与 DAKOTA 可能的大规模并行性。

OpenMDAO 是 NASA 在 APACHE 许可下用 Python 开发的基于优化的设计软件。我目前正在尝试这个。

如果你负担不起 30 次运行,每次变化一个参数,请分组改变它们:
例如,8 次运行,每个变化 4 个参数一起,然后优化最好的 2 次运行/8 个参数......
(我不知道如何权衡信息增益与总运行时间; 多臂强盗?)