具有大量局部极小值的多参数优化

Question

我正在寻找算法来找到一组“最佳”的参数值。所讨论的函数有很多局部极小值，并且变化很快。更糟糕的是，测试一组参数非常缓慢--大约1分钟--而且我不能直接计算梯度。

这种优化有什么著名的算法吗？

我只是尝试了一些随机值，取得了一定的成功。我想知道我是否可以通过使随机参数选择器获得更低的选择参数的机会来提高性能，以接近那些在过去产生不良结果的参数。是否有这个方法的名称，以便我可以搜索特定的建议？

更多信息：

• 参数是连续的
• 有5-10个参数的阶数。当然不超过10。

Answer 1

我尝试过模拟退火和粒子群优化。(提醒您，我不能使用梯度下降，因为无法计算梯度)。

我还尝试了一种算法，该算法执行以下操作：

• 选择一个随机点和一个随机方向
• 评价功能
• 只要结果不断改善，就沿着随机方向前进，在每一次成功的迭代中加快速度。
• 当结果停止改善时，后退一步，尝试以相同的距离向正交方向移动。

这个“正交方向”是通过创建一个具有必要维数的随机正交矩阵(适配这段代码)而产生的。

如果向正交方向移动改进了结果，则该算法只需继续该方向。如果没有一个方向改进结果，则跳跃距离减半，并尝试一组新的正交方向。最后，该算法得出结论，它必须是一个局部最小值，记住它，并在一个新的随机点重新启动整批。

这种方法比模拟退火和粒子群的性能要好得多:为了达到同样的质量，需要对(非常慢的)功能进行更少的评估。

当然，我对S.A.和P.S.O.的实现很可能有缺陷--这些都是棘手的算法，有很大的调整参数的空间。但我想我应该提一下最后对我最有用的事情。

Answer 2

有多少个参数--例如，搜索空间中有多少个维度？它们是连续的还是离散的--例如，实数，整数，还是几个可能的值？

我见过的处理这类问题的方法具有相似的总体结构--获取大量样本点，并将它们全部调整到具有“好”答案的区域。因为你有很多点，它们的相对差异是一个临时的梯度。

• 模拟退火：经典的方法。取一堆点，可能会将一些点移动到随机选择的相邻点，这取决于它有多好。
• 粒子群优化：以搜索空间中速度的“粒子群”为例，很可能是随机地移动一个粒子；如果这是一个改进，让整个粒子群知道。
• 遗传算法：这有点不同。与其像上面那样使用邻居的信息，你每次都会得到最好的结果，并且希望他们能得到最好的特征。

维基百科的链接有前两个的伪代码；GA方法种类繁多，很难只列出一个算法，但您可以从其中跟踪链接。请注意，上述所有内容都有实现，您可以使用或接受这些实现作为起点。

请注意，所有这些--实际上，任何一种大维搜索算法的方法--都是启发式的，这意味着它们的参数必须调整到您的特定问题。这可能会很乏味。

顺便说一句，函数计算成本太高这一事实可以为您提供一点帮助；由于上述所有方法都涉及到许多独立的函数评估，所以该算法的这一部分可以与OpenMP或类似的东西并行，以使用机器上的多个核。

Answer 3

您的情况似乎类似于优化/校准启发式算法性能的软件的海报，我也会给您提供同样的建议，我给了那里：考虑一种具有多个步行者的类似大都市-黑斯廷斯的方法，以及步长的模拟退火。

在您的情况下使用蒙特卡罗方法的困难是对每个候选人进行昂贵的评估。和你手头的时间相比，有多贵？如果你在几分钟内需要一个好的答案，这是不够快的。如果你能让它通宵运行，它会相当好的工作。

考虑到复杂的搜索空间，我会推荐一个随机的初始分布。你的最终答案可能只是在整个跑步过程中记录到的最佳个人结果，或者是步行者的平均位置和最佳结果。

不要被我在讨论最大化的事情耽搁了，你想要最小化:优点的数字可以被否定或倒置。