19

在性能和用例方面，模拟退火（使用 bean 搜索）和遗传算法之间有哪些相关差异？

我知道 SA 可以被认为是人口规模只有一个的 GA，但我不知道两者之间的关键区别。

此外，我正在尝试考虑 SA 将优于 GA 或 GA 将优于 SA 的情况。一个简单的例子可以帮助我理解就足够了。

4

3 回答 3

72

严格来说，这两件事——模拟退火（SA）和遗传算法既不是算法，也不是它们的目的“数据挖掘”。

两者都是元启发式- 在抽象尺度上比“算法”高几个级别。换句话说，这两个术语都指的是高级隐喻——一个来自冶金学，另一个来自进化生物学。在元启发式分类法中，SA 是一种单态方法，而 GA 是一种种群方法（与 PSO、ACO 等一起属于一个子类，通常称为受生物启发的元启发式方法）。

这两个元启发式用于解决优化问题，特别是（但不限于）组合优化（又名约束满足编程）。组合优化是指通过从一组离散项中进行选择来进行优化——换句话说，没有可以最小化的连续函数。背包问题、旅行商问题、库存问题——都是组合优化问题。

与数据挖掘的联系是，许多（大多数？）监督机器学习（ML）算法的核心是优化问题的解决方案——（例如多层感知机和支持向量机）。

任何解决上限问题的解决方案技术，无论算法如何，都将基本上由以下步骤组成（通常在递归循环中编码为单个块）：

  1. 在成本函数中编码特定领域的细节（这是从该函数返回的值的逐步最小化，构成了 c/o 问题的“解决方案”）；

  2. 评估传入初始“猜测”的成本函数（开始迭代）；

  3. 基于从成本函数返回的值，生成成本函数的后续候选解决方案（或多个，取决于元启发式）；

  4. 通过将参数集传递给成本函数来评估每个候选解决方案；

  5. 重复步骤 (iii) 和 (iv)，直到满足某个收敛标准或达到最大迭代次数。

元启发式针对上述步骤 (iii)；因此，SA 和 GA 的不同之处在于它们如何生成用于通过成本函数进行评估的候选解决方案。换句话说，这是了解这两种元启发式方法有何不同的地方。

非正式地，针对组合优化解决方案的算法的本质是它如何处理从成本函数返回的值更差的候选解决方案比当前的最佳候选解决方案（从成本函数返回最小值的解决方案）。优化算法处理这种候选解决方案的最简单方法是彻底拒绝它——这就是爬山算法所做的。但是这样做，简单的爬山总是会错过一个更好的解决方案，与当前的解决方案相隔一个山丘。换句话说，一个复杂的优化算法必须包含一种技术，用于（暂时）接受比当前最佳解决方案更差的候选解决方案（即，上坡），因为比当前解决方案更好的解决方案可能位于更差的路径上解决方案。

那么 SA 和 GA 是如何生成候选解的呢？

SA 的本质通常用成本更高的候选解决方案被接受的概率来表示（双括号内的整个表达式是一个指数：

p = e((-highCost - lowCost)/temperature)

或者在 python 中：

p = pow(math.e, (-hiCost - loCost) / T)

“温度”项是一个变量，其值在优化过程中衰减——因此，随着迭代次数的增加，SA 接受较差解决方案的概率会降低。

换句话说，当算法开始迭代时，T 非常大，如您所见，这导致算法移动到每个新创建的候选解决方案，无论是比当前最佳解决方案更好还是更差——即，它正在做一个在解空间中随机游走。随着迭代次数的增加（即，随着温度的降低），算法对解空间的搜索变得不那么允许，直到 T = 0，行为与简单的爬山算法相同（即，只有比当前最佳的解更好解决方案被接受）。

遗传算法非常不同。一方面——这是一件大事——它产生的不是单一的候选解决方案，而是整个“他们的群体”。它的工作原理是这样的：GA 调用总体中每个成员（候选解决方案）的成本函数。然后，它按照从成本函数返回的值（“最佳”具有最低值）对它们进行排序，从最好到最差。从这些排名值（及其相应的候选解决方案）创建下一个总体。人口的新成员基本上是通过以下三种方式之一产生的。第一种通常被称为“精英主义”，在实践中通常是指仅采用排名最高的候选解决方案并将它们直接传递——未经修改——传递给下一代。人口中的新成员通常被称为“ 突变”和“交叉”。突变通常涉及从当前总体中更改候选解向量中的一个元素以在新总体中创建解向量，例如 [4, 5, 1, 0, 2] => [4, 5, 2, 0 , 2]。交叉操作的结果就像如果向量可以有性会发生什么 - 即，一个新的子向量，其元素由来自两个父母中的每一个的一些组成。

所以这些是GA和SA之间的算法差异。性能上的差异呢？

在实践中：（我的观察仅限于组合优化问题）GA 几乎总是优于 SA（从成本函数返回较低的“最佳”返回值——即接近解决方案空间的全局最小值的值），但在更高的计算成本。据我所知，教科书和技术出版物对分辨率的结论相同。

但事情是这样的：GA 本质上是可并行的；更重要的是，这样做是微不足道的，因为组成每个群体的各个“搜索代理”不需要交换消息——即，它们彼此独立工作。显然这意味着GA 计算可以是分布式的，这意味着在实践中，您可以获得更好的结果（接近全局最小值）和更好的性能（执行速度）。

在什么情况下 SA 可能优于 GA？我认为一般情况是那些具有较小解决方案空间的优化问题，因此 SA 和 GA 的结果实际上是相同的，但执行上下文（例如，以批处理模式运行的数百个类似问题）有利于更快的算法（应始终为 SA）。

于 2010-11-04T20:42:23.703 回答
6

真的很难比较两者，因为它们的灵感来自不同的领域。

遗传算法维护一组可能的解决方案，并且在每一步中，选择可能的解决方案对，将它们组合（交叉），并应用一些随机变化（突变）。该算法基于“适者生存”的思想，其中选择过程是根据适应度标准完成的（通常在优化问题中，它只是使用当前解决方案评估的目标函数的值）。完成交叉是希望两个好的解决方案结合起来可能会提供更好的解决方案。

另一方面，模拟退火只跟踪可能解空间中的一个解，并且在每次迭代时根据一些概率（随时间衰减）考虑是移动到相邻解还是停留在当前解。这与启发式搜索（例如贪婪搜索）不同，因为它不会受到局部最优问题的影响，因为它可能会因所有相邻解决方案都比当前解决方案最差的情况而陷入困境。

于 2010-11-04T18:38:33.940 回答
3

我远不是这些算法的专家，但我会尽力提供帮助。

我认为两者之间最大的区别是 GA 中的交叉概念，因此任何比 SA 更适合 GA 的学习任务示例都将取决于交叉在这种情况下意味着什么以及它是如何实现的。

交叉的想法是您可以有意义地结合两种解决方案来产生更好的解决方案。我认为这只有在以某种方式构建问题的解决方案时才有意义。例如，我可以想象，在多类分类中，采用两个（或多个）擅长对特定类进行分类的分类器，并通过投票将它们组合起来，形成一个更好的分类器。另一个例子可能是遗传编程，其中解决方案可以表示为一棵树，但我发现很难想出一个可以组合两个程序来创建一个更好的程序的好例子。

我认为很难提出一个令人信服的案例，因为它们确实是非常相似的算法，可能是从非常不同的起点开发的。

于 2010-11-04T13:14:58.893 回答