数学建模社区-数学中国

标题: 关于模拟退火通俗解释 [打印本页]

作者: jaypu1991 时间: 2011-8-7 01:05
标题: 关于模拟退火通俗解释
一. 爬山算法 ( Hill Climbing )

介绍模拟退火前，先介绍爬山算法。爬山算法是一种简单的贪心搜索算法，该算法每次从当前解的临近解空间中选择一个最优解作为当前解，直到达到一个局部最优解。

爬山算法实现很简单，其主要缺点是会陷入局部最优解，而不一定能搜索到全局最优解。如图1所示：假设C点为当前解，爬山算法搜索到A点这个局部最优解就会停止搜索，因为在A点无论向那个方向小幅度移动都不能得到更优的解。

二. 模拟退火(SA,Simulated Annealing)思想

      爬山法是完完全全的贪心法，每次都鼠目寸光的选择一个当前最优解，因此只能搜索到局部的最优值。模拟退火其实也是一种贪心算法，但是它的搜索过程引入了随机因素。模拟退火算法以一定的概率来接受一个比当前解要差的解，因此有可能会跳出这个局部的最优解，达到全局的最优解。以图1为例，模拟退火算法在搜索到局部最优解A后，会以一定的概率接受到E的移动。也许经过几次这样的不是局部最优的移动后会到达D点，于是就跳出了局部最大值A。

      模拟退火算法描述：

      若J( Y(i+1) )>= J( Y(i) )  (即移动后得到更优解)，则总是接受该移动

      若J( Y(i+1) )< J( Y(i) )  (即移动后的解比当前解要差)，则以一定的概率接受移动，而且这个概率随着时间推移逐渐降低（逐渐降低才能趋向稳定）

　　这里的“一定的概率”的计算参考了金属冶炼的退火过程，这也是模拟退火算法名称的由来。

　　根据热力学的原理，在温度为T时，出现能量差为dE的降温的概率为P(dE)，表示为：

　　　　P(dE) = exp( dE/(kT) )

　　其中k是一个常数，exp表示自然指数，且dE<0。这条公式说白了就是：温度越高，出现一次能量差为dE的降温的概率就越大；温度越低，则出现降温的概率就越小。又由于dE总是小于0（否则就不叫退火了），因此dE/kT < 0 ，所以P(dE)的函数取值范围是(0,1) 。

　　随着温度T的降低，P(dE)会逐渐降低。

　　我们将一次向较差解的移动看做一次温度跳变过程，我们以概率P(dE)来接受这样的移动。

　　关于爬山算法与模拟退火，有一个有趣的比喻：

　　爬山算法：兔子朝着比现在高的地方跳去。它找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。这就是爬山算法，它不能保证局部最优值就是全局最优值。

　　模拟退火：兔子喝醉了。它随机地跳了很长时间。这期间，它可能走向高处，也可能踏入平地。但是，它渐渐清醒了并朝最高方向跳去。这就是模拟退火。

作者: bai402728119 时间: 2011-8-8 23:42
好东西顶一个

作者: 马拥华 时间: 2011-8-14 22:17
很形象，谢谢

作者: coolboy94psj 时间: 2011-8-15 08:47
lz把退火吃得很透啊，小白前来观摩

作者: luuuz 时间: 2011-8-15 09:40
很好的东西，很容易理解~

作者: 我就在你背后 时间: 2011-8-15 13:53
太好了。。。。。。。。。。。。。

作者: 啾啾 时间: 2011-8-24 10:08
好东西，谢谢

作者: dailifeng 时间: 2011-8-25 19:04
ddddddddddddddddddddddddddddddddddddddddddddd

作者: dailifeng 时间: 2011-8-25 19:05
dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd

作者: 傆始ょ誋忆 时间: 2011-8-25 21:21

沙发沙发

作者: 川帘秀 时间: 2011-8-29 07:05
顶。。。。

作者: liaoqshanshan 时间: 2011-9-6 16:23
太好了。。。。。。。。。。。。。

作者: xieyun 时间: 2011-9-6 17:09
沙发已过，居然长度不够，囧

作者: 371523154 时间: 2011-9-6 22:22
回复，得体力

作者: tianxiawuquan 时间: 2011-9-26 15:28
...原来这就是退火算法...取这么高深的名字...结果实际中都不自觉的用了n次了...><

作者: 爱在期待 时间: 2011-10-8 11:32
比喻很贴切。。问一个，温度，降低幅度，终止温度。。。不好确定啊。。

作者: 爱在期待 时间: 2011-10-8 11:32
我刚入门的。。。

作者: 爱在期待 时间: 2011-10-8 11:33
我刚入门的。。。

作者: 豪蛋 时间: 2011-11-6 15:57
讲的太好了太好了谢谢楼主！

作者: 随心所渔 时间: 2011-11-6 17:40
我刚入门的。。。

作者: xiao小鬼 时间: 2011-11-6 23:29
非常感谢楼主

作者: 123WQY123wqy 时间: 2011-11-7 20:45

作者: strongsi12 时间: 2011-11-12 11:28
讲得好

作者: scotelong 时间: 2011-11-13 00:27
好啊！！！！！

作者: 无忘鱼 时间: 2011-11-13 23:20
通俗易懂很生动

作者: colinxue 时间: 2011-11-15 15:24
这个貌似以前看过，还不是很懂

作者: 奚鑫 时间: 2011-11-16 10:01
解释的太好了。

作者: sunday922 时间: 2011-11-25 15:02
很好的东西，很容易理解~

作者: msfds 时间: 2011-12-7 15:00
厉害人真多，虚心学习

作者: winerson 时间: 2011-12-17 14:33
很好理解谢谢楼主！

作者: xjsfuture 时间: 2011-12-20 23:45
呵呵，很形象，留名

作者: 胖儿7895123 时间: 2011-12-23 22:48
这个不错啊，让人一看就明白很多啊

作者: renee576662 时间: 2011-12-31 21:37
真是不错，易懂

作者: zx4811057 时间: 2012-1-4 16:52
很好~~~~~~~~~~~~~~~

作者: 2012美赛 时间: 2012-1-10 20:41
学习了，谢谢楼主~

作者: liu123456cn 时间: 2012-1-14 16:36
支持一下，必须滴

作者: 一角钱被扣 时间: 2012-1-14 21:37
好东西，值得顶

作者: li_meng41 时间: 2012-1-14 22:51
支持楼主~向楼主学习~

作者: cufejinrong 时间: 2012-1-15 17:23
通俗易懂！厉害厉害

作者: solemn7 时间: 2012-1-23 13:23
终于了解了。谢谢。

作者: 枫泯 时间: 2012-1-23 20:08
图文并茂，生动形像

作者: 一万年的光焰 时间: 2012-1-25 16:51
观摩一下！！！

作者: roger10 时间: 2012-1-27 00:31
顶楼主，很是形象啊

作者: 824236601 时间: 2012-1-27 23:23
通俗！

作者: 小米369577846 时间: 2012-2-2 16:13
很形象啊，谢谢楼主~！~~

作者: cherrydons 时间: 2012-2-2 21:42
原创吧强啊。，。

作者: qicheng 时间: 2012-2-3 17:04
好贴哈，谢谢哈

作者: qicheng 时间: 2012-2-3 17:08
好贴哈，谢谢哈

作者: 历史的天空 时间: 2012-2-3 21:27
谢楼主，

作者: 也可 时间: 2012-2-4 13:03
很有帮助。。。。

作者: 李牙刷儿 时间: 2012-2-4 15:36
学习了，谢谢楼主的分享

作者: 李牙刷儿 时间: 2012-2-4 15:38
11111111111111111111111111111111

作者: 菁菁草 时间: 2012-2-4 22:18
讲解的不错！

作者: howu 时间: 2012-2-28 20:21

相当清楚明了

作者: xia了夏天 时间: 2012-4-2 17:05
菜鸟想飞学习了

作者: 1543484355 时间: 2012-4-3 10:08
好东西，顶一个。

作者: wllzq126 时间: 2012-4-4 17:34
不错，学习了，谢谢楼主

作者: 荆梦 时间: 2012-4-4 20:07

作者: 荆梦 时间: 2012-4-4 20:10

作者: Medichen0 时间: 2012-4-8 16:24
谢谢楼主，，解释的很好。受教了

作者: ashi_248 时间: 2012-5-24 13:59
很好啊

作者: y^3 时间: 2012-5-24 16:17
很清晰，一下就懂了

作者: 沫影 时间: 2012-5-29 01:41
讲得很明白~很好~

作者: 杰姐 时间: 2012-5-29 21:25

作者: vectoring 时间: 2012-6-10 00:04
受教了，顶个！

作者: huanghai 时间: 2012-7-15 16:26
厉害。。。。。。。。。。。。。。。。。。。。。。。。

作者: winecar 时间: 2012-7-17 16:05
很通俗，基本思想知道了。

作者: zuster 时间: 2012-7-23 00:04
关于遗传算法和模拟退火算法更加详细的资料大家不妨看看下面这篇帖子
《遗传算法@模拟退火算法（算法简介+编程技巧+工具箱+应用大全）（含源代码）》
http://www.madio.net/forum.php?m ... &fromuid=498319

作者: 鞋呈亮 时间: 2012-7-23 11:09
好像有点懂了

作者: chqk921 时间: 2012-7-24 16:16
说的挺好的e

作者: pengkingli 时间: 2012-7-25 22:30
楼主讲的真好！！

作者: 北斗七星 时间: 2012-7-26 12:00
讲的很好，通俗易懂

作者: 新平 时间: 2012-7-30 11:25
能理解。。。

作者: oppo603 时间: 2012-8-1 17:11
thanks very much

作者: 墨雨金岚 时间: 2012-8-4 10:55
想分享来着，可惜我级别不够

作者: yi6ban 时间: 2012-8-4 12:06
学习ing~~~~~~~~~~~~

作者: zyccxsy 时间: 2012-8-4 21:47
真好O(∩_∩)O~

作者: 邹婷 时间: 2012-8-4 23:20
很贴切，容易理解！呼呼

作者: 梦天涯M 时间: 2012-8-5 09:44
非常好的解释啊！！！

作者: Aphrodite._Sens 时间: 2012-8-5 13:03
理解一些了~~谢谢楼主啊~~

作者: 宝鼎幽窗 时间: 2012-8-5 15:09
很形象啊

作者: 诸葛八戒 时间: 2012-8-6 10:42
这篇帖子太赞了

作者: XxYLxG 时间: 2012-8-8 23:10

…

作者: 不羁地风 时间: 2012-8-9 02:39
我顶啊啊啊啊

作者: 郭菲菲 时间: 2012-8-12 14:14
嗯，解释的好好啊

作者: leaves77 时间: 2012-8-12 16:52
不错！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！

作者: RK2412 时间: 2012-8-13 12:20
讲的很直接，形象

作者: bekate 时间: 2012-8-17 13:57
简单易懂，很容易的了解了模拟退火的意义~~~

作者: LIN_hebei 时间: 2012-8-17 17:09
真不错~~~~

作者: tianyaokai 时间: 2012-8-18 17:23
说的好容易啊、、谢楼主虽然还是不太懂

作者: as1234bs 时间: 2012-8-19 15:10
谢谢

作者: maoyushiren 时间: 2012-8-19 23:40
顶一个~~~~~

作者: 泉┈→.づ 时间: 2012-8-21 09:03
很形象，很好的解释//

作者: juany 时间: 2012-8-21 22:07
终于明白了，谢谢楼主！！！

作者: hzs2012 时间: 2012-8-22 16:27
受教。。。。。。。。。。。。

作者: 川頭☆壹號 时间: 2012-8-22 20:00
挺形象的，算是收获不少啦。

作者: 月泪娃娃 时间: 2012-8-22 23:40
顶，简单易懂。

作者: monai 时间: 2012-8-23 16:13
很好理解，谢谢楼主！

作者: lhm6167 时间: 2012-8-23 20:28
不错不错生动形象具体哈

作者: 流水无味 时间: 2012-8-24 11:08
楼主解释不错，受教了

欢迎光临数学建模社区-数学中国 (http://www.madio.net/)