退火
模拟退火是一个<一个href="//www.parkandroid.com/wiki/heuristics/" class="wiki_link" title="启发式" target="_blank">启发式求函数的全局最优解的一种方法。这是一个<一个href="//www.parkandroid.com/wiki/probabilistic-algorithms/" class="wiki_link" title="概率方法" target="_blank">概率方法类似于<一个href="//www.parkandroid.com/wiki/monte-carlo/" class="wiki_link" title="蒙特卡罗方法" target="_blank">蒙特卡罗方法.实际上,模拟退火是根据<一个href="//www.parkandroid.com/wiki/metropolis-hastings-algorithm/" class="wiki_link" title="pmmh算法" target="_blank">pmmh算法,一种蒙特卡罗方法。
其他技术,如<一个href="//www.parkandroid.com/wiki/hill-climbing-algorithm/" class="wiki_link" title="希尔攀登" target="_blank">希尔攀登,<一个href="//www.parkandroid.com/wiki/gradient-descent/" class="wiki_link" title="梯度下降法" target="_blank">梯度下降法,或使用蛮力搜索查找<一个href="//www.parkandroid.com/wiki/local-extrema/" class="wiki_link" title="本地最大值/最小值" target="_blank">本地最大值/最小值比寻找全局极大值/极小值更重要。这些技术比模拟退火快,但它们不能保证它们的结果是全局最优的。
在下图中,模拟退火<一个target="_blank" rel="nofollow" href="#algorithm">算法用于寻找图的全局最大值。它选择一个随机值并计算其代价。然后,它选择一个邻近的解并计算它的代价。如果新的成本更好,就会选择新的解决方案,即使它没有更好,有时也会选择新的解决方案。当找到所需的成本时,它就停止了。
模拟退火是一种很好的概率技术,因为它不会意外地认为局部极值是全局极值。因此,当搜索空间有许多局部极大/极小值以及搜索函数是非线性的时候,它特别有用。许多场合都采用模拟退火<一个href="//www.parkandroid.com/wiki/algorithm/" class="wiki_link" title="algorithm-related" target="_blank">algorithm-related诸如<一个href="//www.parkandroid.com/wiki/set-cover-problem/?wiki_title=set cover problem" class="wiki_link new" title="集合覆盖问题" target="_blank" rel="nofollow">集合覆盖问题,<一个href="//www.parkandroid.com/wiki/maximum-cut-problem/?wiki_title=maximum cut problem" class="wiki_link new" title="最大减少问题" target="_blank" rel="nofollow">最大减少问题,或者是<一个href="//www.parkandroid.com/wiki/independent-set-problem/?wiki_title=independent set problem" class="wiki_link new" title="独立集问题" target="_blank" rel="nofollow">独立集问题.它也被用来解决设计问题,如水的运输和柴油发动机的设计<年代up>[2].
退火的概述
退火是一种启发式。启发式是经验法则,可用于找到问题的好答案。它们常用于求解大型、非大型<一个href="//www.parkandroid.com/wiki/linear-transformations/" class="wiki_link" title="线性" target="_blank">线性和非<一个href="//www.parkandroid.com/wiki/convex/" class="wiki_link" title="凸" target="_blank">凸问题。启发式方法不能保证得到最优答案,但它们可以非常接近,而且通常是精度和计算之间的一个很好的权衡。它们通常包含随机化。退火引入了适量的随机性和概率,帮助它逃离那些局部最优。
有两种启发式:<年代trong>建设和<年代trong>改进.构造启发式方法找到一个可行的解并加以改进。改进启发式从一些可行的解开始,并且只尝试改进它。退火算法是一种改进的启发式算法。
退火是为了反映原子的冷却到能量最小的状态。这类似于冷却一个系统,使它达到最低的能量状态,并为该系统找到一个全局最优状态。如果液体冷却和退火过快,那么材料就会凝固成次优配置。然而,如果它被缓慢冷却,那么里面的晶体将会以最佳的方式凝固成能量最小的状态。这种最小能量状态类似于模拟退火所分析的函数的最小成本。
退火是在1983年作为一种求解方法引入的<一个href="//www.parkandroid.com/wiki/combinatorial-optimization/" class="wiki_link" title="组合优化" target="_blank">组合优化运用统计力学。
算法
退火需要一些东西来开始:
退火使用以下元素:
- 成本函数-这个函数是通过退火最小化的。
- 搜索空间-可能解的空间。
- 温度-系统的“温度”,一个迭代退火过程的函数。
举个例子<一个href="//www.parkandroid.com/wiki/traveling-salesperson-problem/" class="wiki_link" title="旅行推销员问题" target="_blank">旅行推销员问题.在这个问题中,目标是找到一个销售人员可以穿过多个城市的路径,访问每个城市一次,然后返回原来的城市。给定旅行的成本函数(结束于起点的路径)就是旅行的长度。搜索空间将是所有可能的旅行的集合。这个过程的温度由程序员决定,但它通常从1开始,然后衰减,遵循某种规律冷却时间.一个典型的冷却计划可能只是把温度乘以一些<年代pan class="katex"> (通常是0.99或0.8)。退火过程在温度达到某一点时停止。
退火算法的工作原理如下:
- 选择一个初始的随机解,<年代pan class="katex"> .
- 计算解决方案的成本,<年代pan class="katex"> .
- 选择一个与当前解决方案相邻的新解决方案,<年代pan class="katex"> .
- 计算新解决方案的成本,<年代pan class="katex"> .
- 比较当前和新的解决方案的成本。如果<年代pan class="katex"> ,转向新的解决方案。否则,用概率转移到新的解<年代pan class="katex"> .
- 更新系统的温度。
- 重复步骤3 - 6,直到达到所需的温度。
关于介绍中的gif(搜索最高点),下面是正在发生的事情:
- 在图上找到一个随机点<年代pan class="katex"> .
- 这一点的“代价”可能是它的高度的倒数<年代pan class="katex"> .
- 在两边随机选择一个解<年代pan class="katex"> ,<年代pan class="katex"> .
- 计算这个新解决方案的成本。
- 如果<年代pan class="katex"> ,搬到<年代pan class="katex"> .如果不是,那就转到<年代pan class="katex"> 的概率<年代pan class="katex"> .
- 更新系统的温度。在这种情况下,它降低了温度同时也降低了<年代pan class="katex"> .通过降低<年代pan class="katex"> ,随着时间的推移,它减少了选择次最优解的机会。
- 重复
这个程序的主要魅力在于第五步,你可能会次优的在两个选择中选择。这使得退火可以避免局部最优的潜在陷阱。<年代pan class="katex"> ,这个过程次优选择新解决方案的机会,是两个潜在解决方案的成本差和当前系统温度的函数。
在出差销售人员的情况下,如果一条新路径比另一条更短,退火将倾向于切换到那条路径<年代pan class="katex"> 将会很高。然而,如果它们是相似的,那么两者的机会都是均等的。此外,随着退火过程的继续(温度下降),退火应该更关注于低成本的解决方案,而不是逃离局部最优——所以,<年代pan class="katex"> 增加。
邻解的概念很重要,但它的含义在不同的解空间中是不同的。对于出差销售人员问题,有很多方法可以定义两个相邻的解。例如,两个相邻的解可能是两条路径,这两条路径的可能截面最小。解空间中设计不良的邻近系统(如随机配置)会对退火过程的结果产生不利影响。然而,这可以通过更多的计算来减轻。
这个一般的过程是非常基本的,步骤经常被修改以达到最好的结果。例如,可以使用较慢的温度冷却计划,从而导致退火过程花费更长的时间。然而,这将给它更多的时间来逃离局部的最大值和最小值。而且,退火的生产级实现经常在每次迭代中比较多对邻居。
伪代码
下面的伪代码是一个更面向计算机科学的方法来理解这个算法。
12 3 4 5 6 7 8 9 10 11 12 |
|
该算法的一般过程是从当前状态中寻找要移动到的邻居。一般情况下,选择最优邻居,但有时选择不太优的邻居,以避免局部的最大值和最小值。这里,beta是一个布尔术语,它是由两个候选解的两个成本函数和t之间的关系选择的如果
行语句10
工作
Python实现
下面的代码是退火的快速实现。在这个例子中,生成一组可能的解,然后通过退火,找到最优解。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17日18 19 20 21日22日23日24日25日26日27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
|
这个退火过程的最佳解决方案是什么?在运行代码或检查答案之前,尝试从代码中找出它。
最佳答案是
401
.如果你看看里面成本()
函数,它检查候选解与数字401的距离有多近。
应用程序
退火可以用于任何优化场景。如果全局最优不是目标,还有更快的技术,比如<一个href="//www.parkandroid.com/wiki/hill-climbing-algorithm/" class="wiki_link" title="爬山算法" target="_blank">爬山算法.然而,当需要全局最优解时,特别是当输入信号是非线性的,有许多局部最大值/最小值时,退火是有用的,因为它将做最接近最优解的工作。
退火可以用来找到一个最优解的图相关问题,如<一个href="//www.parkandroid.com/wiki/set-cover-problem/?wiki_title=set cover problem" class="wiki_link new" title="集合覆盖问题" target="_blank" rel="nofollow">集合覆盖问题,<一个href="//www.parkandroid.com/wiki/maximum-cut-problem/?wiki_title=maximum cut problem" class="wiki_link new" title="最大减少问题" target="_blank" rel="nofollow">最大减少问题,或者是<一个href="//www.parkandroid.com/wiki/independent-set-problem/?wiki_title=independent set problem" class="wiki_link new" title="独立集问题" target="_blank" rel="nofollow">独立集问题.例如套套,就可以用很多<一个href="//www.parkandroid.com/wiki/heuristics/" class="wiki_link" title="启发式" target="_blank">启发式.模拟退火的输出比模拟退火的输出更好<一个href="//www.parkandroid.com/wiki/greedy-algorithm/" class="wiki_link" title="贪婪启发式" target="_blank">贪婪启发式,如果这对应用程序很重要的话。耦合退火与<一个href="//www.parkandroid.com/wiki/recursive-backtracking/" class="wiki_link" title="递归回溯" target="_blank">递归回溯将保证一个最佳的结果,尽管它将更多的计算<一个href="//www.parkandroid.com/wiki/computation-cost/?wiki_title=expensive" class="wiki_link new" title="昂贵的" target="_blank" rel="nofollow">昂贵的.
退火在系统设计中也经常使用。通常,系统有一组需求和成本限制。退火可以帮助找到给定成本限制的最大值。这和<一个href="//www.parkandroid.com/wiki/knapsack-problem/" class="wiki_link" title="背包问题" target="_blank">背包问题在计算机科学。例如,一个建筑可能有一定的预算,但它仍然需要达到一定水平的结构支持。退火可以找到相关函数的全局最大值。
参考文献
- 13日,K。模拟退火.2016年6月14日,从<一个href="https://en.wikipedia.org/wiki/Simulated-annealing">https://en.wikipedia.org/wiki/Simulated-annealing
- 格拉夫。柴油机尾气后处理技术的系统建模、分析与优化.2016年6月28日,从<一个href="http://strategic.mit.edu/docs/SM-21-Graff-C-2006.pdf">http://strategic.mit.edu/docs/SM-21-Graff-C-2006.pdf
- 尽情。模拟退火.2016年6月28日,从<一个href="http://ocw.mit.edu/courses/engineering-systems-division/esd-77-multidisciplinary-system-design-optimization-spring-2010/lecture-notes/MITESD_77S10_lec10.pdf">http://ocw.mit.edu/courses/engineering-systems-division/esd-77-multidisciplinary-system-design-optimization-spring-2010/lecture-notes/MITESD_77S10_lec10.pdf