模拟退火算法课件

1、模拟退火算法模拟退火算法模拟退火算法1、模拟退火算法概述1.1 基本思想1.2 固体退火过程1.3 Metropolis准则1.4 模拟退火算法与物理退火的相似性2、模拟退火算法的实现和应用2.1 模拟退火算法的步骤2.2 模拟退火算法的优缺点2.3 模拟退火算法应用举例模拟退火算法1、模拟退火算法概述1、模拟退火算法概述1.1基本思想模拟退火算法(Simulated Annealing Algorithm，SAA)是一种基于迭代求解策略的随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火算法从某一较高初温出发，伴随温度参数的不断下降,结合概率突跳特性

2、在解空间中随机寻找目标函数的全局最优解，即在局部最优解能概率性地跳出并最终趋于全局最优。模拟退火算法是一种通用的优化算法，理论上算法具有概率的全局优化性能,目前已在工程中得到了广泛应用，诸如VLSI、生产调度、控制工程、机器学习、神经网络、信号处理等领域。模拟退火算法是通过赋予搜索过程一种时变且最终趋于零的概率突跳性，从而可有效避免陷入局部极小并最终趋于全局最优的串行结构的优化算法。1、模拟退火算法概述1.1基本思想模拟退火算法(Simu1、模拟退火算法概述1.1基本思想 用一种形象的比喻来描述模拟退火：兔子喝醉了。它随机地跳了很长时间。这期间，它可能走向高处，也可能踏入平地。但是，它渐渐清醒

3、了并朝最高方向跳去。这就是模拟退火。 模拟退火算法以一定的概率来接受一个比当前解要差的解，因此有可能会跳出这个局部的最优解，达到全局的最优解。以图1为例，模拟退火算法在搜索到局部最优解A后，会以一定的概率接受到E的移动。也许经过几次这样的不是局部最优的移动后会到达D点，于是就跳出了局部最大值A。 图11、模拟退火算法概述1.1基本思想 用一种形起源：物理退火过程 模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而冷却时粒子渐趋有序，最后分子以低能状态排列，固体达到某种稳定状态。加温过程等温过程冷却过程1、模拟退火算法概述1.2

4、固体退火过程 模拟退火算法来源于固体退火原理，将固体加温至模拟退火算法采用Metropolis接受准则以概率接受新状态 若在温度T，当前状态i 新状态j 若EjEi，则接受j为当前状态； 否则，若概率 p=exp-(Ej-Ei)/kT大于0,1)区间的随机数，则仍接受状态j为当前状态；若不成立则保留状态i为当前状态。 1、模拟退火算法概述1.3 Metropolis准则模拟退火算法采用Metropolis接受准则以概率接受新1、模拟退火算法概述1.4 模拟退火算法与物理退火的相似性1、模拟退火算法概述1.4 模拟退火算法与物理退火的相似1、模拟退火算法概述1.4 模拟退火算法与物理退火的相似性

5、物理退火过程物体内部的状态状态的能量温度熔解过程退火冷却过程状态的转移能量最低状态模拟退火算法问题的解空间解的质量控制参数设定初始温度控制参数的修改解在邻域中的变化最优解物理退火过程模拟退火算法类比关系1、模拟退火算法概述1.4 模拟退火算法与物理退火的相似根据热力学的原理，在温度为T时，出现能量差为dE的降温的概率为P(dE)，表示为：P(dE) = exp( dE/(kT) )其中k是一个常数，exp表示自然指数，且dE0。这条公式说白了就是：温度越高，出现一次能量差为dE的降温的概率就越大；温度越低，则出现降温的概率就越小。又由于dE总是小于0（否则就不叫退火了），因此dE/kT= J(

6、Y(i) (即移动后得到更优解)，则总是接受该移动若J(Y(i+1) Tmin，满足则对当前最优解S,按照某一邻域函数， 产生一新的解j。计算新的目标函数值J(j) ， 并计算目标函数值的增量E= J(j) - J(i) 。4) 如果E0，则接受新解，令S= j； 如果E0，则p = exp(- E /TK); 并判断 p random0,1 ，成立则接受新解S = j; 否则S=i。5) 降温T=T*r,0r1，回到步骤3)6) 若T T_min ) dE = J( Y(i+1) ) - J( Y(i) ) ; if ( dE =0 ) %表达移动后得到更优解，则总是接受移动 Y(i+1)

7、= Y(i) ; %接受从Y(i)到Y(i+1)的移动else if ( exp( dE/T ) random( 0 , 1 ) ) Y(i+1) = Y(i) ; %接受从Y(i)到Y(i+1)的移动 T = r * T ; %降温退火 ，0r1 。i + ; 伪代码如下：2、模拟退火算法的实现和应2.1 模拟退火算法的优缺点1）优点：可以保证全局最优特别适合组合优化问题可以随机选择初始解对问题本身没有特别要求，不会因为问题实例的改变影响性能简单易行，通用性好2）缺点： 模拟退火算法在求解规模较大的实际问题时，往往存在以下缺点： （1）收敛速度比较慢。 （2）尽管理论上只要计算时间足够长，模

8、拟退火法就可以保证以概率1收敛于全局最优点。但是在实际算法的实现过程中，由于计算速度和时间的限制，在优化效果和计算时间二者之间存在矛盾，因而难以保证计算结果为全局最优点，优化效果不甚理想。 （3）在每一温度下很难判定是否达到了平衡状态2、模拟退火算法的实现和应2.1 模拟退火算法的优缺点12、模拟退火算法的实现和应用2.3 模拟退火算法应用举例TSP问题： 一个商人欲到n个城市推销商品，每两个城市i和j之间的距离为dij，如何选择一条道路使得商人每个城市走一遍后回到起点且所走路经最短。解空间目标函数初始解选为2、模拟退火算法的实现和应用2.3 模拟退火算法应用举例新解的产生(3种方法)1、互换操作(SWAP)随机交换两个不同城市的位置。2、逆序操作(INV)两个不同随机位置的城市逆序。3、插入操作(INS)随机选择某个城市插入到不同随机位置。新解的产生(3种方法)1、互换操作(SWAP)随机交换两个不TSP 30个城市坐标如下：41 94; 37 84; 54 67; 25 62; 7 64; 2 99;68 58; 71 44; 54 62; 83 69; 64 60; 18 54;22 60; 83 46; 91 38; 25