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

Question

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

我知道SA可以看作是GA，人口总数只有一个，但是我不知道两者之间的主要区别。

另外，我正在尝试考虑SA胜过GA或GA胜过SA的情况。只需一个简单的示例即可帮助我理解就足够了。

Answer 1

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

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

这两种元启发式方法用于解决优化问题，尤其是（尽管不是排他性的）组合优化（又名约束满足编程）。组合优化是指通过从一组离散项中进行选择来进行优化-换句话说，没有连续函数可将其最小化。背包问题，旅行商问题，裁员问题都是组合优化问题。

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

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


编码特定于域的详细信息
在成本函数中（这是
逐步降低价值
从该函数返回
构成了C / O的“解决方案”
问题）;
评估成本函数传递
在最初的“猜测”中（开始
迭代）;
根据从
成本函数，生成后续
候选解决方案（或超过
一个，取决于
元启发式）
功能;
通过评估每个候选解决方案
将其传递到参数集中
成本函数；
重复步骤（iii）和（iv），直到
一些收敛准则是
满意或最大数量
达到迭代。


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

非正式地，针对组合优化解决方案的算法的本质是它如何处理其候选函数的成本函数返回的值比当前最佳候选函数差（从成本函数返回最小值的候选函数）差。优化算法处理这种候选解决方案的最简单方法是完全拒绝它-这就是爬山算法的作用。但是通过这样做，简单的爬坡将总是错过一个更好的解决方案，而该解决方案与当前的解决方案被一个小山隔开。换句话说，一种复杂的优化算法必须包括一种技术，用于（暂时）接受比当前最佳解决方案差的（即从当前最佳解决方案上坡）的候选解决方案，因为比当前最佳解决方案更好的解决方案可能会沿着这种情况出现。解。



那么SA和GA如何生成候选解决方案？

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

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

或在python中：

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

“温度”一词是一个变量，其值在优化过程中会衰减-因此，SA接受较差解的可能性会随着迭代次数的增加而降低。

换句话说，当算法开始迭代时，T很大，如您所见，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）。