模拟退火算法SA课件

1、模拟退火算法一、模拟退火算法概述 模拟退火算法是近年发展起来的全局最优化算法，其主要优点是:不用求目标函数的偏导数及解大型矩阵方程组，即能找到一个全局最优解，而且易于加人约束条件，编写程序简单。模拟退火算法的特点 模拟退火方法避免了线性化反演方法结果强烈依赖于初始模型的选取，而导致解落入局部极值的情况。目前此法已开始用于解决非线性地球物理反问题，如波形反演、静校正、叠前偏移速度分析等非线性反演中，并取得了较好的效果。然而，这种方法存在着计算效率低的缺陷，严重地影响着它的广泛应用。模拟退火算法基本原理 模拟退火算法(SA,Simulated Annealing)是一种启发式的蒙特卡罗(Monte

2、 Carlo)方法。这种算法是在给定的模型空间内搜索目标函数达到全局极小值的最优模型，它已用于各种最优化问题计算。常规的模拟退火法即Kirkpatrick等(1983)提出的Metropolis算法(Metropo-lis SA)。 1983午Kirkpatrick等意识到组合优化与物理退火的相似性，并受到Metropolis准则的启迪，提出了模拟退火算法。归纳而言，SA算法是基于Monte Carlo迭代求解策略的一种随机寻优算法，其出发点是基于物理退火过程与组合优化之间的相似性，SA由某一较高初温开始，利用具有概率突跳特性的Metropolis抽样策略在解空间中进行随机搜索，伴随温度的不断

3、下降重复抽样过程，最终得到问题的全局最优解。模拟退火算法步骤标准模拟退火算法的一般步骤可描述如下：(1)给定初温ttk，随机产生初始状态s=s0，令k=0;(2)Repeat；(21)Repeat；(211)产生新状态slGenete(s)；(212)if min1，exp-(C(sl) - C(s)/tk random0，1 s=sl；(213)Until抽样稳定准则满足；(22)退温tk+1= update(tk)并令k=k+1；(3)Until算法终止淮则满足；(4)输出算法搜索结果。也可以这样描述模拟退火算法步骤(1)给定模型每一参数变化范围，在这个范围内随机选择一个初始模型m0，并计

4、算相应的目标函数值E(m0) 。(2)对当前模型m0进行扰动产生一个新模型m，计算相应的目标函数值 E (m)，得到E=E(m)一E(m0)。(3)若E0，则新模型m按概率Pexp( - E/T) 进行接收，T为温度。当模型被接收时，置m0=m，E(m0)=E(m) 。(4)在温度T下，重复一定次数的扰动和接收过程，即重复步骤(2)、(3)。(5)缓慢地降低温度T。(6)重复步骤(2)、(5)，直至收敛条件满足为止。 上面的程序中，关键的是(1)新状态产生函数，(2)新状态接受函数，(3)抽样稳定准则，(4)退温函数，(5)退火结束准则（简称三函数两准则）是直接影响优化结果的主要环节。虽然实验

5、结果证明初始值对于最后的结果没有影响，但是初温越高，得到高质量解的概率越大。所以，应该尽量选取比较高的初温。 算法实现与应用 模拟退火算法的应用很广泛，可以较高的效率求解最大截问题(Max Cut Problem)、0-1背包问题(Zero One Knapsack Problem)、图着色问题(Graph Colouring Problem)、调度问题(Scheduling Problem)、组合优化问题、函数优化问题。等等。 模拟退火算法应用示例 求解TSP的模拟退火算法模型可描述如下： 解空间 解空间S是遍访每个城市恰好一次的所有回路，是1，n的所有循环排列的集合，S中的成员记为(w1,w2 ,，wn)，并记wn+1= w1。初始解可选为(1，n)。 此时的目标函数即为访问所有城市的路径总长度或称为代价函数。我们要求此代价函数的最小值。新解的产生 随机产生1和n之间的两相异数k和m，若km，则将(w1, w2 ,，wk , wk+1 ,，wm ,，wn)变为(wm, wm-1 ,，w1 , wm+1 ,，wk-1