模拟退火算法课件.ppt

《模拟退火算法课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、模拟退火算法SimulatedAnnealingAlgorithmSAA模拟退火算法是什么？是怎样提出来的？模拟退火算法（SimulatedAnnealing，SA）是一种模拟物理退火的过程而设计的优化算法。它的基本思想最早在1953年就被Metropolis提出，但直到1983年Kirkpatrick等人才设计出真正意义上的模拟退火算法并进行应用。模拟退火算法的基本思想是怎样的？模拟退火算法采用类似于物理退火的过程，先在一个高温状态下（相当于算法随机搜索），然后逐渐退火，在每个温度下（相当于算法的每一次状态转移）徐徐冷却（相当于算法局部搜索

2、），最终达到物理基态（相当于算法找到最优解）。简介模拟退火算法的来源是根据复杂组合优化问题与固体的退火过程之间的相似之处。该算法在系统向着能量减小的趋势变化过程中，偶尔允许系统跳到能量较高的状态，以避开局部最小，最终稳定在全局最小。简介SAA属于随机模拟算法模拟统计物理学中物体加热后冷却这一退火过程而建立的随机优化算法，意图是避免陷入局部极小解，早期用于组合优化，后来发展成一种通用的优化算法。基本思想SAA是基于MenteCarlo迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。另一方面，

3、结合爬山法和随机行走。SAA在某一初温下，伴随温度参数的不断下降，结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部优解能概率性地跳出并最终趋于全局最优。模拟退火算法是一种通用的优化算法，目前已在工程中得到了广泛应用。基本思路首先在高温下进行搜索，此时各状态出现概率相差不大，可以很快进入“热平衡状态”，这时进行的是一种“粗搜索”，也就是大致找到系统的低能区域；随着温度的逐渐降低，各状态出现概率的差距逐渐被扩大，搜索精度不断提高。这就可以越来越准确的找到网络能量函数的全局最小点。一、模拟退火算法概述二、模拟退火算法的马氏链描述及收

4、敛性三、模拟退火算法关键参数和操作设计四、模拟退火算法的改进及其并行性五、模拟退火算法的实现及应用固体退火过程Metropolis准则组合优化与物理退火的相似性模拟退火算法的步骤第一节模拟退火算法概述1模拟退火算法概述算法的提出模拟退火算法最早的思想由Metropolis等（1953）提出，1983年Kirkpatrick等将其应用于组合优化。—Optimizationbysimulatedannealing,IBMResearchReport算法的目的解决NP复杂性问题提供有效近似算法；克服优化过程陷入局部极小；克服初值依赖性。1.1固体退

5、火过程1、源于对固体退火过程的模拟；2、采用Metropolis接受准则；3、用冷却进度表控制算法进程，使算法在多项式时间里给出一个近似解。固体退火过程的物理图像和统计性质是SAA的物理背景；Metropolis接受准则使算法跳离局部最优“险井”；而冷却进度表的合理选择是算法应用的前提。1模拟退火算法概述1.1固体退火过程算法的基础1模拟退火算法概述固体退火过程什么是退火：退火是指将固体加热到足够高的温度，使分子呈随机排列状态，然后逐步降温使之冷却，最后分子以低能状态排列，固体达到某种稳定状态。1.1固体退火过程固体退火是将固体加热至融化，再

6、徐徐冷却使之凝固成规整晶体的热力学过程，属于热力学与统计物理研究的范畴。由以下三部分组成：加温过程等温过程冷却过程固体在恒定温度下达到热平衡的过程！1模拟退火算法概述固体退火过程加温过程——增强粒子的热运动，使其偏离平衡位置，目的是消除系统原先可能存在的非均匀态；等温过程——退火过程中要让温度慢慢降低，在每一个温度下要达到热平衡状态，对于与环境换热而温度不变的封闭系统满足自由能较少定律，系统状态的自发变化总是朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡态；冷却过程——使粒子热运动减弱并渐趋有序，系统能量逐渐下降，从而得到低能的晶体

7、结构。当液体凝固为固体的晶态时退火过程完成。1.1固体退火过程1模拟退火算法概述数学表述在温度T，分子停留在状态r满足Boltzmann概率分布温度低时能量低的微观状态概率大，温度趋于零时，固体几乎处于概率最大能量最小的基态。1.1固体退火过程1模拟退火算法概述数学表述在同一个温度T，选定两个能量E101模拟退火算法概述数学表述若

8、D

9、为状态空间D中状态的个数，D0是具有最低能量的状态集合：(1)当温度很高时，每个状态概率基本相同，接近

10、平均值1/

11、D

12、；(2)状态空间存在超过两个不同能量时，具有最低能量状态的概率超出平均值1/

13、D

14、；(3)当温度趋于0时，分子停留在最低能量状态的概率趋于1。1.1