启发式和元启发式之间有什么区别？

Question

经过一些关于算法的研究，我发现了两个术语让我很困惑。我至少阅读了20篇论文，然而，没有一个清晰的定义可以说明它们之间的差异。我希望有人能帮助我解释启发式算法和元启发式算法之间的区别。如果可能的话，请附上信息来源。

注：我已经知道这些词的意思，但我不知道它们在计算机科学中的确切区别。

提前感谢您。

- Nico Liu

---

这真的取决于上下文。启发式是有用的规则，它们近似于完美的答案/行为。没有上下文，添加元信息并不会赋予它任何特殊含义，它只是意味着它是元信息，即关于启发式的启发式。 - Jeremy Salwen

这是关于算法的内容。 - Nico Liu

在某种程度上，它仍然取决于上下文，这意味着你永远不会得到一个直接的答案，因为它们没有明确定义。在AI领域中，启发式是用作更大（通常是搜索）算法构建块的“好猜测”函数。元启发式本身就是一种“好猜测”系统，可以不断地提高其猜测能力。但这只是我的看法——这些东西如此不确定，即使是在进行启发式与元启发式比较评估的论文中，也要么没有定义，要么只提供宽泛的定义。基本上，你得亲眼看见才知道这是什么。 - Novak

Answer 1

启发式方法是指解决问题的近似（不是精确）解决方案。"近似"和"近似度"的区别在于前者是为了得到一个问题的良好猜测解，但你并不真正知道它有多好。而后者则是为了得到一个解决方案，你可以证明它与最优解有多接近。

因此，启发式方法通常是与特定问题相关的，也就是说，你需要针对给定问题定义一种启发式方法。元启发式方法是一种独立于问题的技术，可应用于广泛的问题范围内。例如，在快速排序中选择随机元素作为枢轴点就是一种启发式方法。而元启发式方法对它将要应用的问题一无所知，它能够将函数视为黑盒子来处理。

可以说，启发式方法利用问题相关信息来找到特定问题的“合适”的解决方案，而类似设计模式的元启发式方法是可应用于广泛问题集合的通用算法思想。

- Alejandro Piad

---

你也有这方面的资料吗？ - Nico Liu

“El-Ghazali Talbi”写了一本有关元启发式的很好的入门书，书名为《Metaheuristics》，你可以查看一下。在书的引言中，他表达了跟这段话差不多的观点。 - Alejandro Piad

所以，根据你所说的，NSGAII是一种元启发式算法，因为它可以适用于许多问题，甚至包括我自己的复杂问题。但是，如果我编写利用自己复杂问题信息的算法，那么这意味着它是一种启发式算法吗？我理解和区别对了吗？（抱歉我的英语不好） - Aerox

@Aerox，NSGAII是遗传算法的一个变种，因此通常不依赖于特定问题。正如Touki所说，元启发式的具体实现（与书中的抽象实现相对）也是一种元启发式，即使您需要做出与表示、成本函数等相关的决策，这些决策通常是与问题相关的。在这种情况下，您正在使用自己的问题“实例化”元启发式，就像填写模板一样。不同之处在于，您没有利用特定于问题结构的信息来设计一次性解决方案。 - Alejandro Piad

@Aerox，不确定我是否理解了你的陈述。如果算法利用有关问题结构的信息（无论是隐式还是显式），这些信息并不适用于广泛的（优化）问题，则其为特定的启发式算法。正如我之前所说，差异微妙，边界相当模糊。 - Alejandro Piad

Answer 2

为了给出正确的报价，与Alejandro的回答相关：

“元启发式(metaheuristic)”是一种高层次的、独立于问题的算法框架，提供一组指导方针或策略来开发启发式优化算法[...]根据元启发式框架中表达的指南，启发式优化算法的特定问题实现也被称为元启发式(Sörensen, Glover on http://scholarpedia.org/article/Metaheuristics)。

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

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

1. 事实上，启发式和元启发式是优化领域的一部分。它们试图解决的问题是寻找最优解，而不是排序。
2. 当你要解决的问题在计算意义上过于复杂时，通常会使用启发式——但这并不适用于排序问题。
3. 如果我理解得正确，在快速排序示例中指出的是随机因素。原则上，您可以使用确定性的启发式方法——我从未遇到过确定性的元启发式，但可能可以编写一种。这可能有点“玩弄文字”，但随机因素更恰当地描述了“随机搜索”而不是（元）启发式。

- Touki

---

嗯，我认为A星是一种可能的确定性启发式方法？ - reyman64

@Touki，感谢您的深入补充。只是想指出，即使是一个不切实际的例子，您也可以将排序公式化为找到最小化逆序对数量的排列。通过这种公式化，您可以应用任何组合元启发式算法（例如GA或SA）来解决它。当然，快速排序会更好，因为它利用了问题结构。从这个意义上讲，也许快速排序本身可以被认为是排序问题的一种启发式方法。我知道，在实践中这不是一个有用的公式化，但它达到了指出差异的目的。 - Alejandro Piad

作为一个例子，可以看看Nelder-Mead算法，我认为它可以被视为一种元启发式算法（对各种黑盒优化问题具有广泛适用性），而且它是完全确定性的。它是启发式的，因为与Simplex算法相反，它不能保证收敛到全局最优解。 - Alejandro Piad

他们试图解决的问题是寻找最优解，而不是排序。这是一个很好的答案！应该将其标记为此问题的解决方案。 - Rubem Pacelli

Answer 3

详细说明请参见：

Sörensen, K. (2015). Metaheuristics—the metaphor exposed. International Transactions in Operational Research, 22(1), 3-18.

元启发式是一种高级的问题无关的算法框架，它提供一组指导方针或策略来开发启发式优化算法。这个术语也用来指代一个根据这样一个框架所表达的指南实现启发式优化算法的特定问题的实现(Sörensen，2015)。

启发式是指南，元启发式是使用这些指南的框架。

- dorien