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

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

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

此外,我正在考虑一种情况,即SA将胜过GA或GA将胜过SA.只有一个简单的例子可以帮助我理解就足够了.

严格来说,这两件事 - 模拟退火(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 = 0时,行为与简单的爬山算法相同(即,只有当前最好的解决方案)解决方案被接受).

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

那些是GA和SA之间的算法差异.性能差异如何？

在实践中:(我的观察仅限于组合优化问题)GA几乎总是胜过SA(从成本函数返回较低的'最佳'返回值 - 即接近解空间全局最小值的值),但是更高计算成本.据我所知,教科书和技术出版物在决议上都有相同的结论.

但事情就是这样:GA本质上是可并行化的; 更重要的是,这样做是微不足道的,因为构成每个群体的个体"搜索代理"不需要交换信息 - 即,它们彼此独立地工作.显然,这意味着GA计算可以分布,这意味着在实践中,您可以获得更好的结果(更接近全局最小值)和更好的性能(执行速度).

SA在什么情况下可以胜过GA？我认为一般情况是那些具有小解空间的优化问题,因此SA和GA的结果实际上是相同的,但执行上下文(例如,批处理模式下运行的数百个类似问题)有利于更快的算法(应该永远是SA).

由于他们受到不同领域的启发,因此很难对这两者进行比较.

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

另一方面,模拟退火仅跟踪可能解决方案空间中的一个解决方案,并且在每次迭代时根据一些概率(随时间衰减)考虑是否移动到相邻解决方案或保持在当前解决方案中.这与启发式搜索(比如贪婪搜索)的不同之处在于它不会遇到局部最优的问题,因为它可以从所有相邻解决方案都是当前最差解决方案的情况中解脱出来.