(元)启发式方法的含义

计算科学 优化 启发式
2021-12-19 05:29:18
  1. 为了优化,来自维基百科

    在计算机科学中,元启发式指定了一种计算方法,该方法通过迭代地尝试改进关于给定质量度量的候选解决方案来优化问题。元启发式对正在优化的问题做出很少或没有假设,并且可以搜索非常大的候选解决方案空间。然而,元启发式并不能保证找到最佳解决方案。许多元启发式算法实现了某种形式的随机优化。

    与元启发式具有相似含义的其他术语是:无导数、直接搜索、黑盒或实际上只是启发式优化器。已经出版了几本关于该主题的书籍和调查论文。

    • 我想知道如何判断优化方法是否是元启发式的?例如,

      (1) 线性规划的单纯形法是元启发式的吗?

      (2)大多数非线性规划方法,如梯度下降法、拉格朗日乘子法、惩罚法、内点法(障碍法)、元启发式?

      (3) 所有无梯度方法,例如 Nelder-Mead 方法或下坡单纯形法,都是元启发式的吗?

    • 有哪些不是元启发式的优化方法?

  2. 更一般地(超越优化)用于解决问题的技术,来自Wikipedia

    启发式是指基于经验的解决问题、学习和发现的技术在穷举搜索不切实际的情况下,启发式方法用于加快寻找满意解决方案的过程。这种方法的例子包括使用经验法则、有根据的猜测、直觉判断或常识。

    更准确地说,启发式是使用易于访问但应用松散的信息来控制人类和机器解决问题的策略。

    我想知道如何理解“启发式”的含义?

    • 我如何判断“问题解决、学习和发现”技术是否是启发式的?

    • 有哪些非启发式的“问题解决、学习和发现”技术?

谢谢并恭祝安康!

2个回答

启发式在实践中的许多情况下都有效,尽管没有详细的论据来说明为什么它应该很好地工作。

元启发式不是一种算法,而是一种通用的启发式方案或思想,可以在特定算法中使用。

例如,线性规划的单纯形算法既不是启发式算法也不是元启发式算法,因为它具有完善的收敛理论。sqame 适用于顺序二次规划或内点方法。(内点方法是一种通用方案,但不是启发式的,因此也不是元启发式的,因为有一个非常强大的理论与之相关。)

用于最小化函数的 Nelder-Mead = 下坡单纯形算法是启发式算法(它实际上可能在更高维度的非常简单的问题上失败),禁忌搜索是元启发式算法(因为可以编写很多不同的算法来使用禁忌搜索,但是否则质量完全不同。

因为@ArnoldNeumaier 已经给出了很好的解释,所以我不会重复单纯形和 Nelder-Mead,但想加上我的 2 美分。

我前段时间听到的最好的引语之一,用于描述启发式和元启发式之间的区别:启发式是一个非常好的规则。元启发式是一个很好的规则,可以找到很好的规则。

你应该把它看作是为特定问题找到好的启发式方法;基本上,如果您问自己以下问题之一,您正在谈论元启发式:

  • 我应该如何调整此启发式的参数以提高该问题的性能?
  • 这个启发式比那个启发式更好吗?

有一堆元启发式算法可以用于解决问题、学习和发现,即:

我发现大多数元启发式都受到自然现象的启发,这些自然现象很难严格解释,但具有良好的收敛性。

如果您想了解更多关于其他元启发式技术的信息,这是一个很好的链接