2010 年代模拟退火的例子
这是几个例子。
问题中的引用分析
问题中的引述来自《人工智能:现代方法》第 125 页,Stuart Russell 和 Peter Norvig,2010 年,第 3 版。
引用以这样的声明开头,“永远不会使'下坡'移动到具有较低价值(或较高成本)的状态的爬山算法保证是不完整的,”这并不完全正确。所述保证至少有两个重要的例外。
- 被攀登的山峰只有一个峰
- 使用缩放的并行计算架构执行搜索,使得搜索粒度包括每个处理单元不超过一个峰值
正如 Stuart 和 Norvig 解释的那样,使用结合倒爬山和随机游走的类比来描述模拟退火并不像原始类比那样清晰和技术准确。找到想法的原始来源并阅读它们通常比阅读简化的解释更好。最初的想法可能与教科书的释义一样容易或更容易理解(这就是为什么最好的教科书只引用原作者的原因)。
术语来源
称为模拟退火的原始算法在通过模拟退火、Kirkpatrick 等进行的优化中介绍。人。1,这可能不符合人工智能研究人员或从业者每天明确雇用的条件。在退火过程中模拟金属的原子运动是将伪随机扰动注入收敛机制的几种方法中的第一种。一个近似值χ2分布与ķ自由度是一个更渐进的注入源。
这些方法的共同目标是避免将损失表面中的局部最小值误认为其全局最小值。这种错误的结论导致无法根据损失函数所代表的标准达到最佳学习状态。
从下面的摘录中可以看出,原始文章是一本很好的阅读文章,并为理解奠定了基础。这样的基础将有助于理解所有使用随机注入避免局部最小值的方法。
迭代改进包括在该坐标空间中搜索导致下坡的重排步骤。由于这种搜索通常会陷入局部而非全局最优,因此习惯上会多次执行该过程,从不同的随机生成配置开始,并保存最佳结果。
...
Metropolis 等人2在科学计算的早期,引入了一种简单的算法,可用于对给定温度下处于平衡状态的原子集合进行有效模拟。
...
均匀分布在区间 (0,l) 中的随机数是实现算法随机部分的便捷方式。
...
使用成本函数代替能量并通过一组参数定义配置{X一世},使用 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