最近被问到一个问题，是关于线性拟合的。但是不巧，我忘记了最小二乘法的公式表达，虽然这是一个很简单的求导再解一次方程，但在手头没有草稿纸的情况下，我还是口算不出来的。在忘记了数学的情况下，总还是有办法去求极值的，比如用梯度下降法去找误差函数
其中为待拟合的函数，包含
个参数
。对于线性拟合，
，对于更一般的情况，
的形式更复杂。我们可以预计，对于任意一组
，只要
还没有满足最佳拟合，误差
就还不是最小的。因此拟合的本质就是求取一组
使得误差函数最小。求函数的最小值可以通过求一阶导与二阶导数得到，但是这个方法可以更加无脑一些。比如我们看一个简单的函数图像
从任意一点出发（例如图示
），寻找最小值。模拟退火的方法出发点在于，
可以在原有的基础上进行一个随机涨落，例如
，其中
。显然从图中可以看出，
时，函数值增大，但
时函数值减小。对于这一次涨落，为了最小化函数值，我们接受
，现在
。为了保证
最后能够走到极小值，步长
也应该是不断变化的。我们期望当
越接近最小值点
，步长
就越短，下面将引入【退火】的核心，也就是一个控制步长（以及方向，后面会提到）的函数。这个函数是时间依赖的，在循环刚开始运行时，它所控制的步长应该较长，而循环运行得比较久时，步长就应该稍短。一个简单的思路是令
。那么模拟退火算法的伪代码可以写成：
# 对于n维情况
steps = 0
temperature(s) = 1/(s+1)
a = {a1, a2, a3, ..., an}
while temperature(s) >= T_min
delta_a = temperature(steps) * (2*rand(n)-1) # n维数组
if f(a + delta_a) <= f(a)
a = a + delta_a
end
steps ++
end
print(a)
我们会发现，模拟退火算法实际上完全是一个物理过程：是一个随着时间不断下降的量，在
比较大的时候，涨落
可以更大，而当
比较小的时候，
变得更小。这实际上就是【退火】名字的由来，就相当于对一个铁块降温，随着温度不断降低，铁块内部的原子排列分布也慢慢变得有规律起来。
模拟退火的思路其实和梯度下降有一点点类似，都是从一个初始值出发，不断向使得函数值减小的地方移动。它相比梯度下降更大的优点是，模拟退火在编程方面是异常简单的，完全不依赖于传统找极值的一切数学。编写一个模拟退火求极值的程序所花费的时间也是极短的。对于个变量的模拟退火，在每轮迭代中平均需要
次才能找到正确的方向，而不像梯度下降那样一次就能找到，另外模拟退火的步长也可能会过短，这是它相比梯度下降的劣势。但避免数值导数这一优势是巨大的。当然，梯度下降的传统老大难问题对于上面的算法，也是同样老大难问题，比如我们把上面的函数
多画一段区间
如果继续使用上面那个单调变换的算法，同样从出发，最后找到的极小值点一定是局域的最小值，也就是大概在2附近的那个值。严格意义上，前面的算法还不是模拟退火的完全体，我们其实可以从物理的角度讲，如果这个函数曲线表示一个势能，例如，把这个函数曲线作为一个真正的过山车轨道0。在温度较高的时候，待拟合的数量（就像过山车）有更高的能量，或者速度，那么它很有可能有能力越过6附近的那一个峰，进入函数值更小的局域最小值。回到之前的伪代码，这意味着我们要对a = a + delta_a的判断条件进行修改
if (f(a + delta_a) <= f(a)) or (f(a + delta_a) >= f(a) and mean(delta_a)<temperature(steps))
# 用delta_a的平均数与温度相比
a = a + delta_a
end
修改后的算法允许a向使得函数值增大的地方移动，但是移动的步长取决于温度。在程序运行初期，温度较高，可以接受的反向运动步长更长；而在运行的后期，我们就不那么能接受反向运动了。这表明的模拟退火一个独特的思想：为了变得更好，可以先变得更差。通过这个方法就可以尽量回避落入局域最小值的问题。
另外一个重要的优化是，变得更差会不会一失足成千古恨？可以加入的一点是，在执行反方向运行的时候，记录当前a的值，一段时间以后再与原来的进行对比，如果还是没有原来的a好，就换回原来的a。这实际上就像手残党玩游戏用SL大法。将这一判断加入其中，就可以避免随机涨落走到了太过离谱的地方。
