使用模拟退火的日常生活应用示例有哪些?

人工智能 搜索 应用 模拟退火
2021-11-15 05:19:36

在 AIMA 第 3 版第 125 页中,模拟退火被描述为:

永远不会使“下坡”移动到具有较低值(或较高成本)的状态的爬山算法保证是不完整的,因为它可能会卡在局部最大值上。相比之下,纯随机游走——即从一组后继者中随机选择一个后继者——是完整的,但效率极低。因此,尝试以某种方式将爬山与随机游走结合起来,以产生效率和完整性似乎是合理的。模拟退火就是这样一种算法。在冶金、退火是通过将金属和玻璃加热到高温然后逐渐冷却来回火或硬化金属和玻璃的过程,从而使材料达到低能结晶状态。为了解释模拟退火,我们将观点从爬山转变为梯度下降(即最小化成本)并想象将乒乓球打入崎岖不平表面最深裂缝的任务。如果我们只是让球滚动,它将在局部最小值处停止。如果我们摇晃表面,我们可以将球弹出局部最小值。诀窍是用力摇晃以将球弹出局部最小值,但又不足以将其从全局最小值中移开。模拟退火方案是先用力摇动(即高温),然后逐渐降低摇动的强度(即降低温度)

我知道它的例子,但我只想要更多在日常生活中使用受激退火的例子

2个回答

2010 年代模拟退火的例子

这是几个例子。

问题中的引用分析

问题中的引述来自《人工智能:现代方法》第 125 页,Stuart Russell 和 Peter Norvig,2010 年,第 3 版。

引用以这样的声明开头,“永远不会使'下坡'移动到具有较低价值(或较高成本)的状态的爬山算法保证是不完整的,”这并不完全正确。所述保证至少有两个重要的例外。

  • 被攀登的山峰只有一个峰
  • 使用缩放的并行计算架构执行搜索,使得搜索粒度包括每个处理单元不超过一个峰值

正如 Stuart 和 Norvig 解释的那样,使用结合倒爬山和随机游走的类比来描述模拟退火并不像原始类比那样清晰和技术准确。找到想法的原始来源并阅读它们通常比阅读简化的解释更好。最初的想法可能与教科书的释义一样容易或更容易理解(这就是为什么最好的教科书只引用原作者的原因)。

术语来源

称为模拟退火的原始算法在通过模拟退火、Kirkpatrick 等进行的优化中介绍。人。1,这可能不符合人工智能研究人员或从业者每天明确雇用的条件。在退火过程中模拟金属的原子运动是将伪随机扰动注入收敛机制的几种方法中的第一种。一个近似值χ2分布与k自由度是一个更渐进的注入源。

这些方法的共同目标是避免将损失表面中的局部最小值误认为其全局最小值。这种错误的结论导致无法根据损失函数所代表的标准达到最佳学习状态。

从下面的摘录中可以看出,原始文章是一本很好的阅读文章,并为理解奠定了基础。这样的基础将有助于理解所有使用随机注入避免局部最小值的方法。

迭代改进包括在该坐标空间中搜索导致下坡的重排步骤。由于这种搜索通常会陷入局部而非全局最优,因此习惯上会多次执行该过程,从不同的随机生成配置开始,并保存最佳结果。

...

Metropolis 等人2在科学计算的早期,引入了一种简单的算法,可用于对给定温度下处于平衡状态的原子集合进行有效模拟。

...

均匀分布在区间 (0,l) 中的随机数是实现算法随机部分的便捷方式。

...

使用成本函数代替能量并通过一组参数定义配置{xi},使用 Metropolis 程序可以直接在某个有效温度下生成给定优化问题的一组配置。该温度只是与成本函数相同单位的控制参数。模拟退火过程包括首先在高有效温度下“熔化”正在优化的系统,然后缓慢降低温度,直到系统“冻结”并且不再发生变化。

...

使用 Z 移动的模拟退火将随机路由提高了 57%,平均了 x 和 y 链路的结果。


参考

[1]模拟退火优化,科学 S. Kirkpatrick,CD Gelatt 和 MP Vecchi,科学新系列,卷。220,第 4598 号,1983 年 5 月,第 671-680 页

[2] N. Metropolis、A. Rosenbluth、M. Rosenbluth.、A. Teller。E.泰勒,J.化学。物理。21. 1087 110511

模拟退火只是优化问题的一种方法:

  • 给定一个函数 f( X ),您想找到一个X,其中 f( X ) 是最优的(具有最大值或最小值)。

当仅找到次优解(局部最小值或局部最大值)时,抖动(一种用于在退火过程中引入一定程度的随机性的隐喻)用于防止算法过早停止。

我曾经用它来为老师找到最佳的课程安排。优化功能考虑到了窗口之间的“时间窗口”,让老师不用等待太多。