模拟退火算法

模拟退火算法SimulatedAnnealingAlgorithmSAA模拟退火算法是什么？是怎样提出来的？模拟退火算法（SimulatedAnnealing，SA）是一种模拟物理退火的过程而设计的优化算法。它的基本思想最早在1953年就被Metropolis提出，但直到1983年Kirkpatrick等人才设计出真正意义上的模拟退火算法并进行应用。模拟退火算法的基本思想是怎样的？模拟退火算法采用类似于物理退火的过程，先在一个高温状态下（相当于算法随机搜索），然后逐渐退火，在每个温度下（相当于算法的每一次状态转移）徐徐冷却（相当于算法局部搜索），最终达到物理基态（相当于算法找到最优解）。简介模拟退火算法的来源是根据复杂组合优化问题与固体的退火过程之间的相似之处。该算法在系统向着能量减小的趋势变化过程中，偶尔允许系统跳到能量较高的状态，以避开局部最小，最终稳定在全局最小。简介SAA属于随机模拟算法模拟统计物理学中物体加热后冷却这一退火过程而建立的随机优化算法，意图是避免陷入局部极小解，早期用于组合优化，后来发展成一种通用的优化算法。基本思想SAA是基于MenteCarlo迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。另一方面，结合爬山法和随机行走。SAA在某一初温下，伴随温度参数的不断下降，结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部优解能概率性地跳出并最终趋于全局最优。模拟退火算法是一种通用的优化算法，目前已在工程中得到了广泛应用。基本思路首先在高温下进行搜索，此时各状态出现概率相差不大，可以很快进入“热平衡状态”，这时进行的是一种“粗搜索”，也就是大致找到系统的低能区域；随着温度的逐渐降低，各状态出现概率的差距逐渐被扩大，搜索精度不断提高。这就可以越来越准确的找到网络能量函数的全局最小点。一、模拟退火算法概述二、模拟退火算法的马氏链描述及收敛性三、模拟退火算法关键参数和操作设计四、模拟退火算法的改进及其并行性五、模拟退火算法的实现及应用固体退火过程Metropolis准则组合优化与物理退火的相似性模拟退火算法的步骤第一节模拟退火算法概述1模拟退火算法概述算法的提出模拟退火算法最早的思想由Metropolis等（1953）提出，1983年Kirkpatrick等将其应用于组合优化。—Optimizationbysimulatedannealing,IBMResearchReport算法的目的解决NP复杂性问题提供有效近似算法；克服优化过程陷入局部极小；克服初值依赖性。1.1固体退火过程1、源于对固体退火过程的模拟；2、采用Metropolis接受准则；3、用冷却进度表控制算法进程，使算法在多项式时间里给出一个近似解。固体退火过程的物理图像和统计性质是SAA的物理背景；Metropolis接受准则使算法跳离局部最优“险井”；而冷却进度表的合理选择是算法应用的前提。1模拟退火算法概述1.1固体退火过程算法的基础1模拟退火算法概述固体退火过程什么是退火：退火是指将固体加热到足够高的温度，使分子呈随机排列状态，然后逐步降温使之冷却，最后分子以低能状态排列，固体达到某种稳定状态。1.1固体退火过程固体退火是将固体加热至融化，再徐徐冷却使之凝固成规整晶体的热力学过程，属于热力学与统计物理研究的范畴。由以下三部分组成：加温过程等温过程冷却过程固体在恒定温度下达到热平衡的过程！1模拟退火算法概述固体退火过程加温过程——增强粒子的热运动，使其偏离平衡位置，目的是消除系统原先可能存在的非均匀态；等温过程——退火过程中要让温度慢慢降低，在每一个温度下要达到热平衡状态，对于与环境换热而温度不变的封闭系统满足自由能较少定律，系统状态的自发变化总是朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡态；冷却过程——使粒子热运动减弱并渐趋有序，系统能量逐渐下降，从而得到低能的晶体结构。当液体凝固为固体的晶态时退火过程完成。1.1固体退火过程1模拟退火算法概述数学表述在温度T，分子停留在状态r满足Boltzmann概率分布温度低时能量低的微观状态概率大，温度趋于零时，固体几乎处于概率最大能量最小的基态。1.1固体退火过程DsBBBTksETZTZkrrEETkrETZrEEP)(exp)()(Boltzmann0)()(exp)(1)}({子：为概率分布的标准化因常数。为的能量，表示状态机变量，表示分子能量的一个随1模拟退火算法概述数学表述在同一个温度T，选定两个能量E1E2，有在同一个温度，分子停留在能量小的状态的概率比停留在能量大的状态的概率要大。1.1固体退火过程TkEETkETZEEPEEPBB12121exp1exp)(1}{}{101模拟退火算法概述数学表述若|D|为状态空间D中状态的个数，D0是具有最低能量的状态集合：(1)当温度很高时，每个状态概率基本相同，接近平均值1/|D|；(2)状态空间存在超过两个不同能量时，具有最低能量状态的概率超出平均值1/|D|；(3)当温度趋于0时，分子停留在最低能量状态的概率趋于1。1.1固体退火过程能量最低状态非能量最低状态1模拟退火算法概述Metropolis准则（1953）——以概率接受新状态固体在恒定温度下达到热平衡的过程可以用MonteCarlo方法（计算机随机模拟方法）加以模拟，虽然该方法简单，但必须大量采样才能得到比较精确的结果，计算量很大。1.2Metropolis准则MonteCarlo模拟退火过程蒙特卡罗(MonteCarlo)方法，或称计算机随机模拟方法，是一种基于“随机数”的计算方法。这一方法源于美国在第一次世界大战中研制原子弹的“曼哈顿计划”。该计划的主持人之一、数学家冯·诺伊曼用驰名世界的赌城—摩纳哥的MonteCarlo—来命名这种方法，为它蒙上了一层神秘色彩。MonteCarlo方法MonteCarlo方法的基本思想很早以前就被人们所发现和利用。早在17世纪，人们就知道用事件发生的“频率”来决定事件的“概率”。Buffon试验：19世纪人们用投针试验的方法来求解圆周率π。本世纪40年代电子计算机的出现，特别是近年来高速电子计算机的出现，使得用数学方法在计算机上大量、快速地模拟这样的试验成为可能。MonteCarlo方法用民意测验来作一个不严格的比喻。民意测验的人不是征询每一个登记选民的意见，而是通过对选民进行小规模的抽样调查来确定可能的优胜者。其基本思想是一样的。它需要一个良好的随机数源。这种方法往往包含一些误差，但是随着随机抽取样本数量的增加，结果也会越来越精确。1模拟退火算法概述Metropolis准则（1953）——以概率接受新状态若在温度T，当前状态i→新状态j若EjEi，则接受j为当前状态；否则，若概率p=exp[-(Ej-Ei)/kBT]大于[0,1)区间的随机数，则仍接受状态j为当前状态；若不成立则保留状态i为当前状态。1.2Metropolis准则01-(Ej-Ei)/kTp1953年提出重要性采样法----以概率接受新状态.1expktEEPPrijij设固体的初态为，其状态能量为，然后用一扰动装置随机选取某个微粒的微小变化，得到一新状态，其能量为:(1)当，则该新状态为“重要状态”，并接受它；(2)当，该状态是否为“重要状态”，要依据固体处于该状态的概率来判断。记固体处于状态和状态的概率比值为，则iEijjEijEEjijEEjijr在[0,1)之间随机产生一随机数。若，则新状态作为重要状态，并接受它；否则舍弃新状态。rjMetropolis准则r若，则接受j，否则接受i。)1,0[随机数)exp(ktEErij在温度t，初始状态i，该状态的能量为,iE随机选取某个粒子的位移随机地产生一微小变化，得到一个新状态j，新状态的能量为jEijEEijEE则接受新状态j则考虑到热运动的影响Metropolis准则由的定义可知，高温下可接受与当前状态能差较大的状态为重要状态，而在低温下只能接受与当前状态能差较小的新状态为重要状态。在温度趋于零时，就不再接受的新状态了。ijEEjr如此反复，达到系统在此温度下的热平衡。这个过程称作Metropolis抽样过程。Metropolis抽样过程就是在一确定温度下，使系统达到热平衡的过程。退火过程（降温过程）在Metropolis抽样过程中温度T缓慢的降低。模拟退火过程就是通过T参数的变化使状态收敛于最小能量处。因而，T参数的选择对于算法最后的结果有很大影响。初始温度和终止温度设置的过低或过高都会延长搜索时间。降温步骤太快，往往会漏掉全局最优点，使算法收敛至局部最优点。降温步骤太慢，则会大大延长搜索全局最优点的计算时间，从而难以实际应用。因此，T可以理解为一个控制参数。为寻找在有限时间逼近全局最优的模拟退火算法，设置了许多控制算法收敛的参数。在退火过程中指定了有限的退火温度值和在每一温度下的转移数目。Kirlpatrick等人在退火步骤中设定的参数如下：（1）初始温度值：初始温度值T0要选的足够高，保证模拟退火算法中所有可能的转移都能被接受。（2）温度的下降：原先使用指数函数实现温度的下降。但是这种方法使降温幅度过小，从而延长搜索时间。在实际中，通常使用下式：此处λ是一小于却接近于1的常数。λ通常的取值在0.8至0.99之间。在每一温度下，实验足够多的转移次数。（3）终止温度：如果在连续的若干个温度下没有可接受的新状态，系统冻结或退火停止。,2,1,1kTTkkSAA提出依据固体模拟退火与组合优化问题的相似性退火过程的状态组合优化问题的解能量目标值能量的取舍目标值的取舍能量的最小值目标值的最小值根据这种相似性，并依据Metropolis准则进行迭代就形成了模拟退火算法1模拟退火算法概述相似性比较1.3组合优化与固体退火的相似性组合优化问题金属物体退火解粒子状态最优解能量最低的状态设定初温熔解过程Metropolis抽样过程等温过程控制参数的下降冷却目标函数能量物理退火过程•物体内部的状态•状态的能量•温度•熔解过程•退火冷却过程•状态的转移•能量最低状态模拟退火算法•问题的解空间•解的质量•控制参数•设定初始温度•控制参数的修改•解在邻域中的变化•最优解物理退火过程模拟退火算法类比关系SAA机理优化问题的解视为固体的状态；随机给定优化问题的初始解；给定初始温度；根据当前的解产生新的解；依据Metropolis准则对两个解进行取舍；重复以上两步直到达到热平衡；降低温度继续上述过程直到温度降到最低，最后的状态就认为是问题的解。1模拟退火算法概述基本步骤给定初温t=t0，随机产生初始状态s=s0，令k=0；RepeatRepeat产生新状态sj=Genete(s)；ifmin{1,exp[-(C(sj)-C(s))/tk]}=randrom[0,1]s=sj;Until抽样稳定准则满足；退温tk+1=update(tk)并令k=k+1；Until算法终止准则满足；输出算法搜索结果。1.4模拟退火算法的步骤1模拟退火算法概述影响优化结果的主要因素给定初温t=t0，随机产生初始状态s=s0，令k=0；RepeatRepeat产生新状态sj=Genete(s)；ifmin{1,exp[-(C(sj)-C(s))/tk]}=randrom[0,1]s=sj;Until抽样稳定准则满足；退温tk+1=update(tk)并令k=k+1；Until算法终止准则满足；输出算法搜索结果。1.4模拟退火算法的步骤三函数两准则初始温度三函数两准则状态产生函数状态接受函数退温函数抽样稳定准则退火结束准则SAA流程确定初温随机给定初始解收敛准则满足否？输出结果Y抽样稳定准则满足否？