模拟退火

✍ dations ◷ 2025-12-07 17:08:39 #算法,最优化算法,蒙地卡罗方法

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

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

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

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

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

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

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

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

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

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

相关

猝死猝死（sudden cardiac death，简称SCD）指突然的死亡，其定义是“非因自杀、他杀或事故而发病、24小时内意外出现的内因性死亡”。一个人由于过度兴奋或过度疲劳而导致的突然死亡。
意第绪语意第绪语（ייִדיש yidiš，又译“依地语”）属于日耳曼语族。全球大约有三百万人在使用，大部分的使用者是犹太人，而且其中主要是阿什肯纳兹犹太人在操用此语。意第绪（语）这个称
人型总科猿是灵长目人猿总科（学名：Hominoidea）动物的通称，包括两个科。虽然人们常把猿猴并称，有时候将猴也称为猿，而猿有时也会称做是猴，不过他们在生物学上是不同的动物。两者的主要区别在
101号美国国道101号美国国道（英语：U.S. Route 101）俄勒冈州段是俄勒冈州一条南北方向的美国国道。全长347英里。
安努安努（阿卡德语：
沃拉大屠杀沃拉大屠杀（ Rzeź Woli）是发生于波兰首都华沙沃拉，纳粹德国军队于1944年在华沙起义期间有系统地杀害大约40,000-50,000人。1944年8月5日至12日之间，数以万计的波兰平民与地下军
鄂伦春鄂伦春族（满语：ᠣᡵᠣᠨᠴᠣ，穆麟德：Oronco，太清：Oronqo）是中国55个少数民族之一，使用鄂伦春语，分布在内蒙古自治区的大小兴安岭中。人口约8700人（2010年）。“鄂伦春”是民族自称，意为“
浮士德的微笑张立昂、刘奕儿、阳咏存、邵翔、洪诗《浮士德的微笑》（英语：Behind Your Smile），2016年三立华人电视剧周日十点档系列第三十九部作品。由张立昂、刘奕儿、阳咏存、邵翔、洪诗领
明斯特和约明斯特和约（Vrede van Münster），签定于1648年，和约中西班牙国王费利佩四世正式承认荷兰为主权国家。明斯特和约被视为威斯特伐利亚和约的一部分，三十年战争和八十年战争结束的里
中文自动分词中文自动分词指的是使用计算机自动对中文文本进行词语的切分，即像英文那样使得中文句子中的词之间有空格以标识。中文自动分词被认为是中文自然语言处理中的一个最基本的环节