在优化问题上使用元启发式算法有什么优势?

人工智能 比较 优化 应用 元启发式
2021-10-28 11:26:04

在优化问题上使用元启发式算法的优缺点是什么?简单地说,为什么我们要使用元启发式算法,如 PSO,而不是传统的数学技术,如线性、非线性和动态规划?

我实际上对元启发式算法有很好的理解,并且我知道它们是如何工作的。例如,这种算法的一个优点是它们可以在合理的时间内找到最优解。

但是,由于我对其他方法和技术的了解不足,我想到了这个问题。

1个回答

元启发式算法特别适用于组合优化问题,因为尽管它们通常不能保证找到最优的全局解决方案,但它们通常可以在相当长的时间内找到足够好的解决方案。因此,它们是穷举搜索的替代方案,这需要指数级的时间。例如,蚁群优化算法已被用于近似(或精确地,在中小型实例的情况下)解决旅行商问题,其决策版本是一个 NP 完全问题(这意味着,除非 P= NP,没有多项式时间解决方案来解决它)。

元启发式也可以很容易地应用于许多问题,因为它们不是特定于问题的。例如,在遗传算法的情况下,您只需要对可能的解决方案进行编码,但原则上,您可以将遗传算法应用于广泛的问题,尽管它们可能并不总是这些问题的最佳解决方案. 此外,与基于梯度的优化算法相反,不需要目标函数的梯度。例如,在遗传算法的情况下,您只需要一种评估解决方案的方法(例如适合度或新颖性)。

元启发式通常包含某种形式的随机性,以逃避局部最小值。蚁群优化算法或模拟退火是这种方法的两个很好的例子。

如果您仍然对元启发式算法感兴趣,Clever Algorithms: Nature-Inspired Programming Recipes(Jason Brownlee 着)一书是了解它们的非常好的资源。还有一个Github 存储库,其中包含本书中描述的算法的实现。