模拟退火
维基百科,自由的 encyclopedia
模拟退火(英语:Simulated annealing,缩写作SA)是一种逼近给定函数全局最优的通用概率算法,具体来说,它是一种元启发算法,常用来在一定时间内,寻找在一个很大搜寻空间中的近似全局最優解。在有大量局部最优解时,模拟退火算法可以找到全局最优解。[1] 模拟退火常用于搜索空间离散的情形(如旅行推销员问题、布尔可满足性问题、蛋白质结构预测、作业车间调度问题等)。对于在固定时间内找到近似全局最优优先于找到精确局部最优的问题,模拟退货算法可能优于梯度下降法或分支定界等精确方法。
模拟退火算法解决的问题包含多元目标函数与若干约束。实践中,约束可作为目标函数的一部分进行惩罚。
Pincus (1970)、[2]Khachaturyan et al (1979,[3] 1981[4])、Kirkpatrick、Gelatt及Vecchi (1983)、Cerny (1985)等人先后提出过类似技术。[5]现在的“模拟退火”算法在1983年为S. Kirkpatrick, C. D. Gelatt和M. P. Vecchi解决旅行推销员问题所发明[6],V. Černý也在1985年独立发明此算法。
模拟退火算法中的慢冷却是指在探索解空间的过程中,接受较差解的概率会缓慢下降。接受较差解可以更广泛地搜索全局最优解。总的来说,模拟退火算法的工作原理如下:温度从初始值逐渐降低到0,每个时间步长内,算法随机选择一个与当前解接近的解,并根据与温度相关的概率选择更优的。搜索过程中,这概率会趋近于1。
可通过求解概率密度函数的动力方程[7][8]或随机采样法进行模拟。[6][9]这种方法是N. Metropolis et al. (1953)发表的梅特罗波利斯-黑斯廷斯算法的改进版,是一种生成热力学系统样本状态的蒙特卡罗方法。[10]