全局优化算法：模拟退火算法

本文主要是介绍全局优化算法：模拟退火算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

序言

前面讨论过一些迭代算法，包括牛顿法、梯度方法、共轭梯度方法和拟牛顿法，能够从初始点出发，产生一个迭代序列。很多时候，迭代序列只能收敛到局部极小点。因此，为了保证算法收敛到全局最小点，有时需要在全局极小点附近选择初始点。此外，这些方法需要计算目标函数。

全局优化算法又称现代启发式算法，是一种具有全局优化性能、通用性强且适合于并行处理的算法。
这种算法一般具有严密的理论依据，而不是单纯凭借专家经验，理论上可以在一定的时间内找到最优解或近似最优解。
遗传算法属于智能优化算法之一。

常用的全局优化算法有：
遗传算法、模拟退火算法、禁忌搜索算法、粒子群算法、蚁群算法。

1、随机搜索算法

模拟退火算法是一种随机搜索算法，随机搜索方法也称作概率搜索算法，这很好理解，是一种能够在优化问题的可行集中随机采样，逐步完成搜索的算法。German首次将模拟退火算法应用在凸显处理领域。论文地址后续有时间我可以是这翻译一下。

朴素随机搜索算法步骤：

1）令K：=0，选定初始点 $x^{(0)}\in \Omega$
2）从 $N(x^{(k)})$ 中随机选定一个备选点 $z^{(k)}$
3）如果 $f(z^{(k)})<f(x^{(k)}),$ 则令 $x^{(k+1)}=z_{(k)}$ ，否则 $x^{(k+1)}=x_{(k)}。$
4）如果满足停止条件，则停止迭代
5）令k=k+1，回到第2步

算法分析：朴素随机搜索算法面临的问题在于领域 $N(x^{(k)})$ 的设计，一方面要保证领域足够大，否则算法可能会在局部点”卡住”；但如果使领域太大的话，会使得搜索过程变得很慢。另一种，对领域问题的解决方案是对朴素随机搜索算法进行修改，使其能够”爬出”局部极小点的”领域”。这意味着两次迭代中，算法产生的新点可能会比当前点要差。模拟退火算法就设计了这样的机制。

2、模拟退火算法

算法步骤

1）令K：=0，选定初始点 $x^{(0)}\in \Omega$
2）从 $N(x^{(k)})$ 中随机选定一个备选点 $z^{(k)}$
3）设计一枚特殊的硬币，使其在一次抛投过程中出现正面的概率为 $P(k,f(z^{(k)}),f(x^{(k)}))$ 。抛一次硬币，如果出现正面，则令 $x^{(k+1)}=z^{(k)}$ ，否则 $x^{(k+1)}=x_{(k)}。$
4）如果满足停止条件，则停止迭代
5）令k=k+1，回到第2步
注：其中所说的”抛硬币”实际可理解成一种随机决策。

算法进行中，第k次迭代，可以追踪到目前最好的点 $x_{best}^{(k)}$ ，即能够对所有的 $i \in \{0,\cdots ,k \},$ 都有 $f(x^{(j)})\leqslant f(x^{(i)})$ 成立的 $x^{(j)}$ 。

$x_{best}^{(k)}$ 按照以下方式进行更新

这里写图片描述

通过持续追踪并更新当前为止最好的点，可以将模拟退火算法简单视为一个搜索过程，搜索过程的最终目的是出处当前为止最好的点。这种说法适合绝大部分启发式算法。

3、模拟退火算法与朴素随机搜索算法的区别

模拟退火算法与朴素随机搜索算法区别在于步骤3，该步骤中，模拟退火算法以一定的概率选择备选点作为下一次迭代点，即使这个备选点比当前的迭代点要差。这一概率被称作接受概率，接受概率要合理设定，才能保证迭代过程正确进行。

P (k, f (z (k)), f (x (k))) = m i n (1, e x p (- f ( x ( k ) ) + f ( z ( k ) ) T k))

$P(k,f(z^{(k)}),f(x^{(k)}))=min(1,exp(\frac{-f(x^{(k)})+f(z^{(k)})}{T_k}))$

Tk $T_k$ 称为冷却温度

从上式我们至少可以推出，如果 $f(z^{(k)})\leqslant f(x^{(k)})$ ，则p=1，即 $x^{(k+1)}=z^{(k)}$ 。
如果 $f(z^{(k)}) >f(x^{(k)})$ ，则仍有一定概率使得 $x^{(k+1)}=z^{(k)}$ ，这一概率为, $exp(\frac{-f(x^{(k)})+f(z^{(k)})}{T_k})$ 。

$f(z^{(k)}) 与f(x^{(k)})$ 之间差异越大，采用 $z^{(k)}$ 作为下一迭代点的概率就越小。类似的， $T_k$ 越小，采用 $z^{(k)}$ 作为下一迭代点的概率就越小。通常的做法是令温度 $T_k$ 递减到0（表示冷却过程）。也就是说，随着迭代次数的增加，算法趋于更差点的概率越来越小。

对于温度参数的研究，可以参考论文

4、模拟退火算法伪代码

/*
* J(y)：在状态y时的评价函数值
* Y(i)：表示当前状态
* Y(i+1)：表示新的状态
* r： 用于控制降温的快慢
* T： 系统的温度，系统初始应该要处于一个高温的状态
* T_min ：温度的下限，若温度T达到T_min，则停止搜索
*/
while( T > T_min )
{dE = J( Y(i+1) ) - J( Y(i) ) ; if ( dE >=0 ) //表达移动后得到更优解，则总是接受移动
Y(i+1) = Y(i) ; //接受从Y(i)到Y(i+1)的移动else{
// 函数exp( dE/T )的取值范围是(0,1) ，dE/T越大，则exp( dE/T )也
if ( exp( dE/T ) > random( 0 , 1 ) )
Y(i+1) = Y(i) ; //接受从Y(i)到Y(i+1)的移动}T = r * T ; //降温退火 ，0<r<1 。r越大，降温越慢；r越小，降温越快/** 若r过大，则搜索到全局最优解的可能会较高，但搜索的过程也就较长。若r过小，则搜索的过程会很快，但最终可能会达到一个局部最优值*/i ++ ;
}