模拟退火

✍ dations ◷ 2025-08-26 18:29:45 #算法,最优化算法,蒙地卡罗方法

模拟退火是一种通用概率算法,常用来在一定时间内寻找在一个很大搜寻空间中的近似最优解。模拟退火是S. Kirkpatrick, C. D. Gelatt和M. P. Vecchi在1983年所发明。而V. Černý在1985年也独立发明此算法。

模拟退火来自冶金学的专有名词退火。退火是将材料加热后再经特定速率冷却,目的是增大晶粒的体积,并且减少晶格中的缺陷。材料中的原子原来会停留在使内能有局部最小值的位置,加热使能量变大,原子会离开原来位置,而随机在其他位置中移动。退火冷却时速度较慢,使得原子有较多可能可以找到内能比原先更低的位置。

模拟退火的原理也和金属退火的原理近似:我们将热力学的理论套用到统计学上,将搜寻空间内每一点想像成空气内的分子;分子的能量,就是它本身的动能;而搜寻空间内的每一点,也像空气分子一样带有“能量”,以表示该点对命题的合适程度。算法先以搜寻空间内一个任意点作起始:每一步先选择一个“邻居”,然后再计算从现有位置到达“邻居”的概率。

可以证明,模拟退火算法所得解依概率收敛到全局最优解。

由一个产生函数从当前解产生一个位于解空间的新解,并定义一个足够大的数值作为初始温度。

迭代过程是模拟退火算法的核心步骤,分为新解的产生和接受新解两部分:

模拟退火算法与初始值无关,算法求得的解与初始解状态S(是算法迭代的起点)无关;模拟退火算法具有渐近收敛性,已在理论上被证明是一种以概率1收敛于全局最优解的全局优化算法;模拟退火算法具有并行性。

迭代过程的停止准则:温度T降至某最低值时,完成给定数量迭代中无法接受新解,停止迭代,接受当前寻找的最优解为最终解。

在某个温度状态T下,当一定数量的迭代操作完成后,降低温度T,在新的温度状态下执行下一个批次的迭代操作。

寻找能量 E ( s ) {\displaystyle E(s)} 最低的状态 s {\displaystyle s}

相关

  • 汤(约前17世纪-前16世纪),商朝开国之君,子姓,名履,今人多称商汤,又称武汤、天乙、成汤、成唐,商代金文和甲骨文称为唐、成、大乙(太乙),又称高祖乙,原商部落首领,与有莘氏通婚后,任贤臣伊尹
  • 慢性疲劳慢性疲劳(倦)症候群(英语:chronic fatigue syndrome, CFS、myalgic encephalomyelitis (ME)),又称为肌痛性脑脊髓炎(myalgic encephalomyelitis),(脊髓炎是有争议的,另一种说法为可
  • 1991年 札幌第十五届冬季世界大学生运动会于1991年3月2日至3月10日在日本的札幌举行,这也是冬季大学生运动会首次在亚洲举行。吉祥物为沙比(Sappy,是一种鹿)值得注意的是,一种以检测DNA的方
  • 北京大学人民医院北京大学人民医院是位于中国北京市西城区的三级甲等医院,为北京大学的附属医院。该医院的前身为中央医院,1915年由伍连德倡议兴建,1916年奠基,1917年建成,1918年1月27日正式开业,
  • 阿鲁群岛阿鲁群岛(印尼语:Kepulauan Aru)是大洋洲的一组约95个低洼岛屿组成的群岛,位于印尼东部的马鲁古省。群岛同时也是马鲁古省下的一个县。行政上,阿鲁群岛属于阿鲁群岛县(印尼语:Kabup
  • 朝鲜劳动党总书记朝鲜民主主义人民共和国主题共和国永远的主席-金日成劳动党永远的总书记-金正日朝鲜劳动党永远的总书记(朝鲜语:조선로동당의 영원한 총비서/朝鮮勞動黨 永遠한 總秘書)是作为朝鲜
  • 杭嘉湖平原杭嘉湖平原是浙江省内最大的平原,面积约7620平方千米,地理上为长江三角洲的组成部分。位于太湖以南,钱塘江和杭州湾以北,天目山以东。包括嘉兴市全部,湖州市大部以及杭州市的东北
  • 咬合咬合,又称�(Occlusion),是牙科术语,即是牙齿对应;通常是指上颌骨与下颌骨的牙齿对应,当咀嚼或休息时两者的接触时间。�字由四川大学华西口腔医学院第二任院长邹海帆在1920年代、1930
  • 中非剪切带中非剪切带(CASZ)是一套陆内巨型右旋走滑断层体系,东北东方向从几内亚湾通过喀麦隆北部、乍得与中非共和国边界、到苏丹。近年发现一系列油气裂谷盆地,截至2015年6月,探明石油储
  • 原锥蜗牛原锥蜗牛(学名:),是柄眼目钻头螺科钻头螺属的一种。主要分布于越南、印度尼西亚、台湾,常栖息在为落叶覆盖较为潮湿的腐殖质土底,陆生。