如何检查哪种算法最能解决我的问题?
给定一个优化问题,我应用不同的众所周知的优化算法(遗传算法、模拟退火、蚁群等)来解决我的问题。但是,我如何知道我的实现(例如成本函数)是否适用于每种情况?在我的问题的背景下,我如何比较算法或它们的优点?
如何检查哪种算法最能解决我的问题?
给定一个优化问题,我应用不同的众所周知的优化算法(遗传算法、模拟退火、蚁群等)来解决我的问题。但是,我如何知道我的实现(例如成本函数)是否适用于每种情况?在我的问题的背景下,我如何比较算法或它们的优点?
这是一个非常大的问题,可以根据上下文以多种方式回答。
对于在特定条件下运行的一些优化问题,您可以从理论上保证您的优化将解决您的问题。一个具体的例子是在凸函数上运行梯度下降算法。如果被优化的函数是凸的,那么梯度下降保证会收敛到正确的解。鉴于凸函数的良好特性,有许多类型的优化可以让您做出这些理论上的保证。
当运行进化算法(以及许多基于非导数的优化)时,做出这些类型的保证要困难得多。我经常在文献中看到人们在几个基线优化函数上尝试他们的函数并报告找到的最小值或最大值。其中许多都包含在 Facebook 的nevergrad优化库中,用于评估。下面包括这些功能之一的示例,
即使您可以证明您的算法最小化了您可以测试的几个目标函数,也可能需要考虑其他属性。其中一些包括以下内容:算法收敛的速度;目标函数的评估次数(如果不是封闭形式),甚至是优化所需的内存空间量。在评估您的算法时,所有这些(以及更多)因素都可能发挥作用。
科学家们可以使用像这样的函数来评估他们的优化并将其与其他类似的算法进行比较。不过,要回答您的最后一个问题,“我如何才能查看我的优化是否适用于每个问题”,我会说这是一个有点棘手的问题。大多数时候,这些优化需要某种约束来做出一般化的保证。我会看看你的问题的限制,然后从那里开始。
如果你有兴趣,这里有一篇比我在这里更深入的好论文。