---

前言

模拟退火算法是一种通用的优化算法，是局部搜索算法的扩展，但是不同于局部搜索算法之处是以一定的概率选择领域中目标值较大的劣质解。模拟退火算法以优化问题的求解与物理系统退火过程的相似性为基础，利用Metropolis算法适当地控制温度的下降过程来实现模拟退火，从而达到求全局优化的问题。

一、模拟退火算法原理

模拟退火算法来源于固体退火原理，将高温物体徐徐冷却，慢慢达到一个稳定的状态。高温时，内部粒子内能大，粒子可能在固体内部的任何地方活动；当温度慢慢冷却，粒子内能减少，活跃度降低，活动范围慢慢减小；当固体冷却完毕或者达到平衡稳定，粒子的位置就固定，就可以获取最优解。
模拟退火算法的主要是思想是：在搜索区间随机游走，再利用Metropolis抽样准则，使随机游走逐渐收敛于局部最优解。而温度是Metropolis算法的重要参数，决定了随机过程收敛的快慢。

二、算法公式

1.Metropolis算法

对于目标函数f(x)，参数从x1变化到x2被接受的概率p为（以求最小值为例）：
　　　　当f2<f1时，p=1
　　　　当f2>f1时，p=exp(-Δf/T)
Δf=f1-f2为目标函数f(x1),f(x2)的值的差。
T为温度常数，随着时间慢慢减少，当温度很高时，取第二种概率高，随着温度降低，取第二种情况慢慢减少，直至几乎不会选择第二种情况。

2.退温函数

模拟退火算法的温度T是慢慢降低的常用公式更新函数为：
Ｔ(n+１)＝Ｋ＊Ｔ(ｎ)
K是一个非常接近１的常数，比如0.99．

3.马尔可夫链

参数X的在温度T下的迭代过程类似于马尔可夫链过程，即X(ｎ＋１)的值受X(ｎ)影响，Ｘ(ｎ＋１)＝ｇ(Ｘ(ｎ))。

三、算法步骤

a. 初始化：设置初始温度Ｔ（足够大，保证Metropolis算法可以取第二种情况），设置初始解状态x(0)，设置每个T值的迭代次数L，设置x更新函数，最优解best和最优解目标函数f(best)。
b. 对于１．．．L，重复c~f：
c. 计算出一个新的参数x(i)=g(x(i-1));
d. 计算目标函数增量Δf=f(x(i))-f(x(i-1));
e. 根据Metropolis算法选择是否接受新的解x(i),如果不接受，x(i)=x(i-1);
f. 如果f(x(i))<f(best),best=x(i);
g. 如果满足终止条件（T足够小或者目标函数f(best)达到指标），输出最优解best,结束；否则，更新温度T，转到b.

举个例子

求函数f=cos(xy)+xy+y^3 在区间[-5,5]的最小值，选取的T可以为100，初始状态x0,y0在区间随机取即可。
退温比例K可以取0.998，马尔可夫链迭代次数可以选取[200,2000]。
参数x,y更新函数可以选取 x(n+1)=x(n)+rand(-5,5)*step,step为步长。step的选取很麻烦，太大了最后收敛的时候可能取不到最优解，太小了跳不出局部最优解。实现过程中，我觉得可以设置step随着遍历次数慢慢减少，取[0.02,0.05]。
书本上给的例子还有一个旅行商问题（TSP问题），求旅行商人不充复拜访全国的最短路径。在实现上没什么区别，就是参数更新函数上，是选择了随机调换两个地点的顺序。

总结

这个算法是看书本写的，例子也是书本的，想看原版的可以去看看《智能优化算法及其MATLAB实例》