模拟退火和遗传算法之间有什么区别？

Question

在模拟退火（带有豆类搜索）和遗传算法之间，在性能和用例方面，相关差异是什么？

我知道可以将SA视为人口规模的GA，但我不知道两者之间的关键区别。

另外，我试图想到SA将胜过GA或GA的情况会超越SA。只是一个简单的示例，它可以帮助我理解就足够了。

Answer 1

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

两者都是 元赫尔术- 在抽象量表上以上的“算法”高于“算法”。换句话说，这两个术语都涉及高级隐喻 - 一种是从冶金中借来的，另一种是从进化生物学上借来的。在元海疗法分类法中，SA是一个 单态方法 而GA是一个 人口法 （在子类中与PSO，Aco等人一起，通常称为 受生物学启发的元映体).

这两种荟萃术用于解决优化问题，尤其是（尽管不是仅限） 组合优化 （又名 约束 - 满意度编程）。组合优化是指从一组离散项目中选择的优化 - 换句话说，没有连续的函数可以最小化。背包问题，旅行推销员问题，减少库存问题 - 所有组合优化问题。

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

无论算法如何，解决CAP问题的任何解决方案技术基本上都由这些步骤组成（通常将其编码为递归环内的单个块）：

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非常大，您可以看到，这会导致该算法转移到每个新创建的候选解决方案，无论是比当前最佳解决方案更好或更糟糕的解决方案 - IE，它正在做一个 随机步行 在解决方案空间中。随着迭代数量的增加（即，随着温度冷却）算法对解决方案空间的搜索变得越来越少，直到在t = 0时，该行为与简单的爬山算法相同（即，仅比电流最好的解决方案要好解决方案被接受）。

遗传算法 非常不同。一方面 - 这是一件大事 - 它不是产生单个候选解决方案，而是整个“人口”。它的工作原理：GA调用人口的每个成员（候选解决方案）上的成本函数。然后，它将它们从最佳到更糟的是，从成本函数返回的值（'Best'具有最低的值）。从这些排名的值（及其相应的候选解决方案）中，创建了下一个人群。新人口的新成员是通过三种方式之一创建的。第一个通常称为“精英主义”，实际上通常是指采用最高排名的候选解决方案并将其直接通过 - 未经改装 - 到下一代。新人口中新成员通常称为“突变”和“跨界”的其他两种方式。突变通常涉及从当前人群中候选溶液向量中的一个元素的变化，以在新人群中创建溶液向量，例如[4，5，1，0，2] => [4，5，5，2，0 ，2]。交叉操作的结果就像媒介可以发生性关系的情况 - 一个新的儿童矢量，其元素由两个父母中的每一个组成。

因此，这些是GA和SA之间的算法差异。性能差异呢？

实际上：（我的观察结果仅限于组合优化问题）GA几乎总是击败SA（从成本函数中返回较低的“最佳”回报值 - IE，接近解决方案空间的全局最小值的值计算成本。据我所知，教科书和技术出版物背诵了关于解决方案的相同结论。

但这就是事实：GA本质上是可行的；更重要的是，这样做是很微不足道的，因为包括每个人群的个体“搜索代理”不需要交换消息 - i，他们彼此独立地工作。显然这意味着 GA计算可以分布, ， 意思是 在实践中，您可以获得更好的结果（更接近全球最低限度）和更好的性能（执行速度）。

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

Answer 2

由于两者的灵感来自不同的域。

遗传算法维持一系列可能的解决方案，并且在每个步骤中选择了可能的溶液对，将它们组合在一起（交叉），并应用一些随机变化（突变）。该算法是基于“优胜党生存”的概念，其中选择过程是根据适应性标准完成的（通常在优化问题中，仅仅是使用当前解决方案评估的目标函数的值）。跨界车是希望两个好的解决方案结合在一起的，可以提供更好的解决方案。

另一方面，模拟退火仅在可能的解决方案的空间中跟踪一个解决方案，并且在每次迭代中，都考虑是移至相邻的解决方案还是根据某些概率（随着时间的推移衰减）留在当前的解决方案中。这与启发式搜索（例如贪婪的搜索）不同，因为它不会遇到当地最佳的问题，因为它可以从所有相邻解决方案最糟糕的情况下消除。

Answer 3

我远非这些算法专家，但我会尽力而为。

我认为两者之间的最大区别是在GA中的交叉构想，因此，与SA更适合GA的学习任务的任何例子都将取决于这种情况下的交叉含义以及如何实施。

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

我认为很难为一个人提出一个引人注目的案例，因为它们确实是非常相似的算法，也许是从截然不同的起点开发的。