模拟退火算法（Simulated Annealing Method）

Arzie100

模拟退火方法（Simulated Annealing Method）

组合优化（Multivariate or combinatorial optimization）

组合优化：发展高效率的寻找具有若干独立变量的的多元函数极值的技巧。

The traveling Saleman Problem 是一个经典的优化问题。
  寻找旅行推销员以此不重复访问N个城市的最短循环路线。

包容在微型硅片上数十万计的电路元件之间干扰达到最小。

组合优化就是寻求多元函数的极大值或极小值，此函数称为评估函数或目标函数(cost function or objective function).

• 函数的形式取决于所研究的问题，独立变量与系统自由度相对应
  
• 函数值涉及系统组态的具体细节
  
• 对于NP问题，严格求解只能涉及规模较小的问题
  

Difficulty of finding the groud state: Many local minima.
P/NP Problem

P 类问题： 计算机所需要的运行时间增长速度不高于此问题初始规模的P次幂.

• 排序问题算法是一个P类问题.约为2次方量级增长.
  

P类问题可以用计算机高效求解，而非P类问题无法用计算机高效求解
非P类问题：计算规模的增长不能用多项式来表达.

• The Travelling saleman problem 通常被认为是NP问题.
  
• 找出某一整数的素因子.
  

但是上述问题是非P类并没有被证明.因为我们不能分析某一个算法，而必须证明所有算法都是非P的.
已经得到的最好结果是：一大类可能的非P问题属于统一级别，如果其中任何一个问题能在多项式时间内解决，那么其余所有问题也可以.此即NP完备
NP类问题： 具有非确定性的多项式运行时间的问题称为NP类(non-deterministic Polynomial time complete problem)

注：NP类并不一定是非P类，因为没有给出证明。但是NP类问题属于统一级别，可以杀一破万.
NP类与非P类不是一回事：如果可以在多项式时间内检查某一算法是否正确，那么这个问题就是NP类，这个要求比在多项式时间内求得解答（P类）要宽松.
P/NP问题：探讨P和NP类问题是否相同.若在多项式时间内解决任何一个NP完备问题，则解决所有NP问题，即NP问题与P问题等价.
“扫雷者游戏自洽性问题也是NP完备问题.”
Metropolis 算法

在 Metropolis Monte Carlo 模拟中，我们想找到某一体系的系综平均.

• 产生系统的一个组态（configuration）
  
• 对已有组态进行某种操作产生新组态.使用势能函数计算新组态的能量.
  

• 如果新组态能量比原组态能量低，则接收新组态.
  
• 如果新组态能量比原来能量高，计算能量差的Boltzmann因子 $\exp{-(E_{new}-E_{old})/k_BT}$.
  
  
  
  • 产生[0,1]之间的随机数，如果此随机数比Boltzmann因子大，则不接受新组态
    
  • 如果此随机数比Boltzmann因子小，则接收该组态，计算 $A(\vec{r})$
    
  • 重复2.直至N足够大，计算待求物理量的值
    
  
  

此算法在MC算法部分应该会有详细介绍，这里借此引出Simulated Annealing Method
Simulated Annealing Algorithm

Motivation：来源于固体高温退火原理. 缓慢冷却时，粒子逐渐趋于有序，每个温度下都达到平衡态，最后讲到目标温度时即可到达基态，内能减为最小。

• 退火：一系列的递减温度上都达到平衡态，有足够的时间通过扩散过程，在微观尺度上进行结构的合理调整. Dissolve crystalline defects.
  
• 淬火：快速降温，最终很可能停留在能量较高的亚稳态上；出现多晶，晶体缺陷，甚至没有晶序的无定型态.
  

We can use this method to find the ground state of multi-valley state space structure with its many local minima.
Simulate the thermal relaxation by Metropolis algorithm.

• Let $\vec X$=initial configuration
  
• Let $E=E(\vec X)$
  
• Let i = random move from the moveset
  
• Let $E_i=E(\vec{X_i})$
  

• if $E_i>E$,then $X=X_i,E=E(\vec{X_i})$
  
• if $E_i<E$: accept the worse move with some probability $\exp(-(E-E_i)/k_BT_i)$
  

where is a gradually decrese temperature parameter.

温度为T时，扰动被接收的概率为
统计力学与优化组合二者的中心思想有很多类似：统计力学告诉我们，即使一个没有温度概念的系统，将评估函数与温度类比后，也可在其优化的意义上进一步引入等价温度。组合优化问题与统计力学中论证最可几组态建立了深刻联系.
产生新解  计算目标函数  接收或以一定概率接收
这是基于MC迭代求解法的一种启发式随机搜索过程.
Simulated Annealing Algorism 小结: 1. 首先在足够高的起始温度  下,用Metropolis算法使系统在较高能量的组态间游走，相当于“融化”，对随机产生的系统组态进行优化. 2. 由  温度以一系列的递降到预期的低温$T_f$,每一个温度都达到稳态（Metropolis次数足够多），在每一个温度下进行多次Metropolis，得到优化组态. 足够多可以导致系统的组态分布趋于Boltzmann分布，即


3.经过冷却过程，系统已经优化并具备凝固态的特征.任何一个组态作为起点，经过SA优化后，最终可以成为接近基态能量并主宰系统低温统计行为的极少数组态集合中的一员
低温下，具有不可忽略概率权重的系统组他都具有接近基态的能量，在系统相空间中只占有一小部分体积.T的降低代表着非零概率空间的收缩。通过SA算法，把系统的组态抽样冻结在相空间中的这个有效部位。
首先模拟退火包含了分区战胜的思想。温度区分了系统重排的任务，那些使目标函数值引起大变化的重排在高温时出现，而那些使目标函数值发生小变化的重排被推迟到低温出现。这也是分区战胜的一种类型：先在高温进行的重排，使系统在总体上初具凝聚特征; 而后在低温进行的重排，勾画系统凝聚状态的细节。
其次模拟退火包含了迭代改善，或者说，迭代改善是模拟退火的一个特例。迭代改善方法本身的限制决定了它只能使系统达到局域最优；而模拟退火使用 Metropolis法则代替迭代改善中的只改善（improve only），因而模拟退火法可使系统达到全局最优。   
Properties of SA: global optimum.
idea: escape local maxima by allowing some bad moves but gradually decrease their size and frequency.

• It has usually used with discrete patameters as well as continuous variables.
  
• 在解决类似旅行推销员问题时，SA算法计算时间随N或N的较小此幂增长
  

使用SA算法时需要以下四项基本要素： 1. 对系统的组态进行简单的描述 2. 使系统组态中元素进行重排的随机生成函数-这些重排是提供给系统的选择，即moveset 3. 目标函数E（类似能量），其极小化过程的目的 4. 控制参数T（类似温度）和退火计划     * 线性退火      * 指数型退火     * Adaptive annealing schedule
参数控制的三个问题 初始温度T的设置     * 初始温度高，更容易找到全局最优，但是耗时     * 初始温度低，节约时间，但是全局性受限     * 实际应用中，初始温度一般需要根据实验结果进行若干次调整 退火速度问题     * 充分搜索（缓慢降温）是必要的 * 退火策略问题     * 通常采用指数退火策略 ,其中k为一略小于1的常熟