物理退火

在热力学上，退火现象指物体逐渐降温的物理现象，温度愈低，物体的能量状态会低；够低后，液体开始冷凝与结晶，在结晶状态时，系统的能量状态最低。大自然在缓慢降温（亦即，退火）时，可"找到"最低能量状态：结晶。但是，如果过程过急过快，快速降温（亦称「淬炼」）时，会导致不是最低能态的非晶体。

如下图所示，首先（左图）物体处于非晶体状态。我们将固体加温至充分高（中图），再让其徐徐冷却，也就退火（右图）。加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小（此时物体以晶体形态呈现）。

如果我们把物体的能量用一个函数表示出来,退火过程就是找这个函数的最低点.这个函数有非常多的局部最低点(非晶体),而晶体状态是这个函数全局最低点.神奇的大自然是如何找到全局最低点,而没有陷入到局部最低点的呢?

物理退火过程会随机改变结晶的结构,随之能量就会改变,如果新结构所蕴含的能量比原来低,那么就接受这种结构,如果新结构所蕴含的能量比原来高,会以一定的概率接受这种结构,这个概率与能量差和当前的温度有关:

其中总是小于0（因为退火的过程是温度逐渐下降的过程），因此，所以的函数取值范围是.随着温度的降低，会逐渐降低

模拟退火（Simulate Anneal）

受到物理退火现象的启发,人们用这种方式来找函数的全局最优解.模拟退火算法通过蒙特卡洛法(随机采样)寻找找最优解,并且以一定的概率来接受一个比当前解要差的解，因此有可能会跳出这个局部的最优解，达到全局的最优解。这种以一定概率接收新状态的方式被称为Metropolis准则,其接收概率表示为:

其中是当前的温度,初始时温度较高,会逐渐下降,最简单的下降方式是指数式下降:

其中是小于1的正数，一般取值为0.8到0.99之间。使的对每一温度，有足够的转移尝试，指数式下降的收敛速度比较慢，其他下降方式如下：

关于普通贪心算法与模拟退火，有一个有趣的比喻：

普通贪心算法：兔子朝着比现在低的地方跳去。它找到了不远处的最低的山谷。但是这座山谷不一定最低的。这就是普通贪心算法，它不能保证局部最优值就是全局最优值。
模拟退火：兔子喝醉了。它随机地跳了很长时间。这期间，它可能走向低处，也可能踏入平地。但是，它渐渐清醒了并朝最低的方向跳去。这就是模拟退火。

编程示例

import matplotlib.pyplot as plt
import numpy as np
import random


temperature = 4.0
iterations = 100
coolrate = 0.95
energy = 100
xs = []
ys = []
while iterations > 0:

    # 随机采样
    x = random.uniform(-2, 5)
    
    # 计算能量
    newenergy = x*(x-1)*(x-2)*(x-4)
    
    
    # 如果能量减小则修改,否则以一定概率接受修改
    if newenergy < energy:
        energy = newenergy
        xs.append(x)
        ys.append(energy)
    else:
        prob = 1.1
        if temperature != 0:
            prob = np.exp((energy - newenergy) / temperature)
        if prob >= (random.randint(0, 1000) + 0.0) / 1000:
            energy = newenergy
            xs.append(x)
            ys.append(energy)

    temperature *= coolrate
    iterations -= 1

print(energy)
x = np.linspace(-1, 4.5, 100)
y= x*(x-1)*(x-2)*(x-4)
plt.plot(x, y)
plt.scatter(xs, ys)
plt.show()

参考:
https://www.cnblogs.com/ranjiewen/p/6084052.html

模拟退火算法

物理退火

模拟退火（Simulate Anneal）

编程示例

发表评论