Ch2 模拟退火算法

Ch2 模拟退火算法

引言

模拟退火算法(simulated annealing SA)，由Metropoli于1953年提出来，Kirkpatric在1983年将其用于离散问题的最优化。

它基于概率统计学中著名的Mente Carlo迭代求解策略的一种随机寻优算法。 其出发点是基于物理中固体物质的退火过程，与一般优化问题之间的相似性。 模拟退火算法是在某一参数(温度)的初值(初温)，伴随着该参数(温度)不断下降，结合概率突跳特性，在解空间中随机寻找目标函数的最优解。

能概率性地跳出局部优解，达到全局最优解。

在VLSI、生产调度、控制工程、机器学习、神经网络、图像处理有应用实例。

1、盲目搜索还是启发式搜索？ 按照预定的控制策略实际搜索，在搜索过程中获取的中间信息不用来改进控制策略，称为盲目搜索，反之为启发式搜索。启发式搜索有助于加速求解过程，但是找到的解可能不是最优解。

盲目搜索：深度优先、广度优先、代价优先、向前、向后、双向。

启发式搜索：爬山法、模拟退火、遗传、粒子群、蚁群等智能优化算法。 2、贪心算法

(1)随机选定一个初始解x0; (2)do while (中止条件不满足) (2.1)在某个邻域函数所定义的领域范围内，按照某个(随机)扰动 产生策略，得到一个新解xi'；

(2.2)对新解进行评估或计算，得到f(xi')； (2.3)如果f(xi')>f(xi)（或f(xi')< f(xi)，即新解比老解好，则xi+1=xi'，否则xi+1=xi。 (3)enddo

3、爬山法

模拟退火算法

目的：(1)为具有NP复杂性的问题提供有效的近似算法；(2)避免陷入局部极小；(3)避免初值依赖性。

真实物质退火即物理退火的过程

先加热金属，然后慢慢以冷却它，同时将其铁片锤打成指定的形状。

如果该快速冷却铁片则不同成份的物质会形成补巴。 如果在成型时慢慢冷却，各组成物质将形成均匀的合金。

(1)加温过程

增强粒子的热运动，使其偏离平衡位置。

当温度足够高时，炽热状态，固体熔解为液体。 消除原来的非均匀状态。

熔解过程是温度、能量不断增加的过程，类似其他系统的熵增过程。

(2)等温过程

当温度达到一定的境界，尽管与环境的热交换仍在进行，则温度却不再变化，这就是等温过程。

处于这种状态的封闭系统，系统状态的自发变化总是朝着自由能减少的方向进行。 当自由能达到最小时，系统达到平衡状态。

“等温过程”与“平衡状态”不是一回事，温度是一个表面现象，平衡状态是物质的分子结构状态，它与“非均匀状态”相对的状态。

(3)退温过程

使粒子的热运动减弱，渐趋有序，系统的能量逐渐下降，最终得到能量较低的晶体结构。 晶体是物质中的实际质点(原子、离子或分子)的排列非常规则，具有很好的延展性。

Metropolis规则

固体在恒定温度下达到热平衡的过程，可用Monte Carlo模拟。

但采用Monte Carlo方法计算，必须大量采样才得到比较精确的结果，大量的试算中，

总会出现所需要的精确结果。效率低下，因此需要开辟新的方法。

考虑到物理系统倾向于能量较低的状态，而热运动阻止它落到所需要的最低状态，因此要采取非正常手段，使之快速降温，从而达到超越混沌状态而达到晶体状态。

Metropolis在1953年提出达到此目标的规则：

在温度t，由当前状态xold跳转到新状态xnew，接受新状态的概率为：

1E(xnew) E(xold)

p E(xnew) E(xold)

exp( )E(x) E(x)newold kt

1 1p

exp(newold) kt

E(xnew) E(xold)E(xnew) E(xold)

新状态的能量低则肯定接受，这是达到最优解，尤其局部最优的必要条件。

若新状态的能量不低于旧状态，则按以上概率接受新状态，使之具有爬山的能力，跳出局部最优解的能力。

公式中的k为Boltzmann常数。 以上过程经过多次重复，系统将趋于能量较低的平衡状态，各状态的概率分布满足某种正则分布。

(1)温度t很高，[E(xnew)-E(xold)]/(kt)很小，exp(

E(xnew) E(xold)

)很小，其倒数很大，

kt

即其概率越高。因此在高温状态，系统易于跳转到能量高的状态。

(2)温度t不高时，[E(xnew)-E(xold)]越小，即新状态的能量超过旧状态的能量越少，则

exp(

E(xnew) E(xold)

)越小，其倒数越大，即其概率越高，系统易于跳到能量相近的状态。

kt

E(xnew) E(xold)

)<1，其倒当[E(xnew)-E(xold)]小到为负数时，由于Exp(0)为1,则exp(

kt

(3)温度很小时，[E(xnew)-E(xold)]/(kt)很大，exp(

数>1，肯定跳转新状态xnew，由于概率值必须在[0，1]之间，所以强行取为1。

E(xnew) E(xold)

)很大，其倒数很小，

kt

即其概率很低。因此在低温状态，系统难以跳转到能量高的状态。具体算时往往将k取为1

以上接受规则称为Metropolis准则，似乎非常符合实际情况，其实这也是一个建模的过程，是一个对实际过程进行去伪存真的过程，其计算量显著少于Monte Carlo方法。

组合优化与物理退火的类比

模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却。

加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序。 在每个温度都达到平衡态，最后在常温时达到基态， …… 此处隐藏：10749字，全部文档内容请下载后查看。喜欢就下载吧 ……