猫史档案馆

之前姐姐在社区中看到有小朋友发帖写求函数最小值的方法：梯度下降法，通俗来讲就是下山算法，把函数比作山，不断地向山的低处迈步，最后找到山谷。但那个方法存在一定局限性，今天姐姐就给大家分享一种新的求函数最小值的算法。

我们先来谈谈梯度下降法的局限性。

比如求下面这个函数的最小值：

如果我们用下山算法，设置起始点为B：

那么函数值就会下降到红圈处（全局最小值）。但如果很不巧，我们选择了A点，函数值就会下降到另一个山谷，虽然这个值已经很小了，但依旧只是局部最优解。而且下山算法到达这个山谷后就会停止，也无法继续迭代，那我们就将掉入这个谷底永远无法找到全局最小值。

那么怎才能在即使初始点选择A的时候的时候依旧尽可能的找到全最优解呢？

这个时候我们就要引入一个新的算法：退火算法。

退火：在物流学上讲指物体逐渐降温的物理现象，温度愈低，物体的能量状态会低；够低后，液体开始冷凝与结晶，在结晶状态时，系统的能量状态最低。大自然在缓慢降温时，可“找到”最低能量状态：结晶。

似乎，大自然知道慢工出细活：缓缓降温，使得物体分子在每一温度时，能够有足够时间找到安顿位置，则逐渐地，到最后可得到最低能态，系统最稳定。

这如同我们日常生活中的食盐，将食盐融化，等它慢慢凝固后又将形成原来的完美的正六面体结构。

如果无法从物理角度上理解，这样子理解也可以：一个锅底凹凸不平有很多坑的大锅，晃动这个锅使得一个小球使其达到全局最低点。一开始晃得比较厉害，小球的变化也就比较大，在趋于全局最低的时候慢慢减小晃锅的幅度，直到最后不晃锅，小球达到全局最低。

那么姐姐就可以模拟一个这样的退火过程，现将模型的“温度加至很高”让模型自由探索函数，但当模型“温度”逐渐降低时，模型便能找到“最低的能量状态”即函数最小值。

算法描述如下：

如果x经过移动后获得比原来更低的损失函数，就接受这个移动。

如果x经过移动后损失函数反而变高，就按照一定概率接受这个移动（温度越低，接受的概率也越低）。只有这样才有可能跳出局部最优解。

算法流程如下：

假设func（）为损失函数。T为当前模型“温度”

随机初始化起始x坐标

当温度=1°前：

生成一个-1~1的随机数a

如果func(x+a) <= func(x)：

将x赋值为x+a

否则：

    P1=exp(-(func(x+a)-func(x)/T))

    P2 = 生成0~1的数。

    如果P1>P2:

    将x赋值为x+a

        T = T * delta（0~1之间，代表温度衰减率）

算法唯一的难点就是exp(-(func(x+a)-func(x)/T))。这个公式用大白话讲就是：模型温度越高，出现温度差时降温的概率就越大；温度越低，则出现降温的概率就越小。换句话说，就是损失函数越高时，摇晃锅的幅度就要越大，反之越小。

通过这个公式，我们可以让模型在初期几乎遍历整个损失函数，最后还能稳定在全局最优。

Python实现：

import numpy as np
from matplotlib import pyplot as plt
import matplotlib.animation as animation
def func(x):
    return (x-3)*(x+2)*(x+8)*(x-10)
#原函数
mes = np.linspace(-10,10,100)
mes_func = func(mes)
plt.plot(mes,mes_func)
plt.show()

tem = 1000
low = 1
iteration = 1000
delta = 0.98
k = 1
x = -6
value = func(x)
P = 0
alllist = []
funclist = []
temlist = []

while tem>low:
    for i in range(iteration):
        change = 2 * np.random.rand() - 1
        if -10<x+change<10:
            if value >= func(x+change):
                x = x + change
            else:
                P = np.exp(-((func(x+change)-func(x))/tem))
                if np.random.rand()<P:
                    x = x + change
    alllist.append([x,func(x),tem])
    temlist.append(tem)
    funclist.append(func(x))
    tem = tem*delta
print("结果：:" + str(x))

fig = plt.figure()
movement = fig.add_subplot(111)
movement.plot(mes,mes_func)
def update(data):
    movement.scatter(data[0],data[1])
    movement.set_title("Model tempereture " + str(int(data[2])))
    return
ani = animation.FuncAnimation(fig,update,alllist,interval=100)
plt.show()

附上退火过程运图：

有啥不会的可以在下面提问，姐姐可以试着回答！