computer-science - 启发式和元启发式有什么区别？

Question

在对算法进行了一些研究之后，我发现了两个让我感到困惑的术语。我已经阅读了至少 20 篇论文，但两者都没有明确的定义。我希望有人可以帮助我区分启发式算法和元启发式算法之间的区别。如果可能的话，添加它的来源。

ps：我已经知道这些词的含义，但我不知道它们在计算机科学中的确切区别是什么。

提前致谢

Answer 1

您可以将启发式算法视为问题的近似（而非近似）解决方案。近似和近似之间的区别在于，第一个是关于对问题的解决方案进行很好的猜测，但您并不真正知道它有多好。第二个是关于获得一个解决方案，您可以证明它与最佳解决方案有多接近。

因此，启发式方法通常取决于问题，也就是说，您为给定问题定义启发式方法。元启发式是与问题无关的技术，可以应用于广泛的问题。例如，启发式方法是在快速排序中选择一个随机元素进行旋转。元启发式对将要应用的问题一无所知，它可以将函数视为黑匣子。

您可以说启发式利用与问题相关的信息来为特定问题找到“足够好”的解决方案，而元启发式就像设计模式一样，是可以应用于广泛问题的通用算法思想。

Answer 2

为了给出正确的报价，相对于亚历杭德罗的回答：

« 元启发式是一个高级别的独立于问题的算法框架，它提供了一套指导方针或策略来开发启发式优化算法 [...] 根据元启发式框架中表达的指导方针，启发式优化算法的特定问题实现也称为元启发式 »（Sörensen，Glover 在http://scholarpedia.org/article/Metaheuristics上）

要完全完整。我们应该区分精确算法、近似算法和启发式算法。精确算法找到精确解。近似算法应在可接受的时间内找到近似解，并指出其与假设最优解的差异范围。启发式方法只是在可接受的时间内找到足够好的解决方案。

顺便说一句，由于两三个不同的原因，Alejandro 快速排序的示例似乎并不完全合适。

1. 事实上，启发式和元启发式是优化领域的一部分。因此，他们试图解决的问题是搜索最优，而不是排序。
2. 当您想要解决的问题在计算意义上太复杂时，通常会使用启发式算法——排序问题不是这样。
3. 如果我理解得很好，通过快速排序示例指出的是随机元素。原则上，您可以使用确定性启发式算法——我从未遇到过确定性元启发式算法，但可能有人可以对其进行编码。这可能有点“玩文字游戏”，但是随机元素比（元）启发式更恰当地描述了“随机搜索”。

Answer 3

详细解释见：

索伦森，K.（2015 年）。元启发式——暴露的隐喻。运筹学国际交易，22（1），3-18。

元启发式是一种高级的独立于问题的算法框架，它提供了一组指导或策略来开发启发式优化算法。该术语还用于指根据此类框架中表达的指南（Sörensen，2015）的启发式优化算法的特定问题实现。

启发式是指导方针，元启发式是使用这些指导的框架。