物理退火

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

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

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

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

\mathrm { P } ( \mathrm { dE } ) = \exp ( \frac{dE } { kT }  )

其中dE总是小于0(因为退火的过程是温度逐渐下降的过程),因此dE/kT < 0 ,所以P(dE)的函数取值范围是(0,1).随着温度T的降低,P(dE)会逐渐降低

模拟退火(Simulate Anneal)

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

p=\begin{cases}
1 & \quad E \left( x _ { n e w } \right) < E \left( x _ { o l d } \right)\\
\exp \left( - \frac { E \left( x _ { n e w } \right) - E \left( x _ { o l d } \right) } { T } \right) & \quad  E \left( x _ { n e w } \right) \geq E \left( x _ { o l d } \right)
\end{cases}

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

T ( n ) = \lambda T ( n ) , n = 1,2,3 , \ldots .

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

T ( n ) = \frac { T ( 0 ) } { \log ( 1 + t ) }

T ( n ) = \frac { T ( 0 ) } { 1 + t }

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

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

编程示例

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()

image.png


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

posted @ 2019-01-16 20:36:49
评论加载中...

发表评论