模拟退火

1最优化方法与最优控制模拟退火算法杨航俞枭辰李金龙2最优化方法与最优控制模拟退火算法模拟退火算法来源于金属退火原理，将金属加温至充分高，再让其徐徐冷却，加温时，金属内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。模拟退火（simulatedannealing，简称SA）是一种通用的随机搜索算法，1953年Metropolis等人提出。其基本思想是把某类优化问题的求解过程与统计热力学的热平衡问题进行对比，试图通过模拟高温物体退火的过程来找到优化问题的全局最优解或近似全局最优解。3最优化方法与最优控制模拟退火算法对于一个优化问题，我们可把目标函数看成定义在解空间上的能量曲面，而整个曲面凹凸不平，如果让个光滑圆球在曲面上自由滚动，这个圆球十有八九会滚到附近的凹处停止运动，但该低谷并不一定是最深的一个凹谷。模拟退火方案就是类似于沿水平方向给圆球一个作用力，若该力足够大且小球所处的低谷并不很深，小球受水平力作用会从该低谷滚出，落入另一个低谷，然后受水平力作用又滚出，如此不断滚动。如下图所示如果作用小球的水平力掌握适当，小球很有可能停留在最深得低谷中，这个最深的低谷就是最优化问题的全局最优解或近似全局最优解。局部最优解全局最优解局部最优解局部最优解模拟退火的基本原理：模拟退火算法利用模拟热力学中经典粒子系统的降温过程来求解规划问题的极值。Metropolis过程基本步骤如下：1、给定初始温度及初始点，计算该点的函数值；2、随机产生扰动，得到新点，计算新点的函数值及函数差值；3、若，则接受新点，作为下一次模拟退火的初始点；4、若，则计算新点的接受概率，产生[0,1]区间的均匀分布的伪随机数r，，若，则接受新点作为下一次模拟的初始点，否则放弃新点，仍取原来的点作为下一次模拟的初始点。4最优化方法与最优控制模拟退火算法0t0x)(0xfxxxx0)(xf)()(0xfxff0f0f()exp(/)kpfft]1,0[rrfp)(1、初始温度的控制:温度的初始值设置是影响模拟退火算法全局搜索性能的重要因素之一、初始温度高，则搜索到全局最优解的可能性大，但因此要花费大量的计算时间；反之，则可节约计算时间，但全局搜索性能可能受到影响,使搜索到全局最优解的可能性减小。实际应用过程中，初始温度一般需要依据实验结果进行若干次调整，一般温度初值取较大值。5最优化方法与最优控制模拟退火算法模拟退火的有关说明（关键参数调控）模拟退火的执行过程中，算法效果取决于一组控制参数的选择。模拟退火的关键参数包括初始温度，温度下降方法，每一温度迭代长度，终止准则。0t2、温度下降方法的控制温度下降方法的确定是模拟退火中影响全局搜索性能的重要因素。如果温度下降过快可能就会丢失极值点；如果温度下降过慢，收敛速度又会大大降低，导致计算时间过长。在实际问题中，通常采用两种非常直观的下降方法；(1)每一步温度以相同比率下降，即，其中，为降温系数(2)每一步温度以相同迭代长度下降，即，其中为初始温度，为温度下降的总次数6最优化方法与最优控制模拟退火算法模拟退火的有关说明（关键参数调控）模拟退火的执行过程中，算法效果取决于一组控制参数的选择。模拟退火的关键参数包括初始温度，温度下降方法，每一温度迭代长度，终止准则。kktt110,0kNkNttk/)(00tN7最优化方法与最优控制模拟退火算法3、每一温度迭代长度的控制模拟退火的全局搜索行与每一温度的迭代长度密切相关。一般的，同一温度下的充分搜索是必要的，但需以计算时间增加为代价。实际中常根据问题的特点来设置合理的迭代长度，常用两种方法：（1）固定的迭代步数，即在每一温度都设置相同的迭代步数；（2）高温时，各状态被接受的概率基本相同，且几乎都被接受，可使同一温度的迭代步数尽量少；温度逐渐变低后，越来越多的状态被拒绝，则可相应增加迭代的步数。可给定一个迭代步数上限S和接受次数上限R，当某一温度的实际接受次数等于R时，不再迭代，否则迭代到上限步数S。模拟退火的有关说明（关键参数调控）模拟退火的执行过程中，算法效果取决于一组控制参数的选择。模拟退火的关键参数包括初始温度，温度下降方法，每一温度迭代长度，终止准则。4、终止准则模拟退火的终止准则主要采用比较直观的方法，如下：（1）零度法：给定一个比较小的正数，当温度，算法终止，表示达到了最低温度；（2）循环总数控制法：设置温度下降的次数为一定值，当温度迭代次数达到N时，算法终止。（3）基于不改进规则的控制法：在一个温度和给定的迭代次数内没有改进当前的局部最优解，则算法终止。（4）接受概率终止准则：给定一个较小的概率P。在一个温度和给定的迭代步数内，除当前局部最优解外，其他状态的接受概率都小于P，算法终止。8最优化方法与最优控制模拟退火算法模拟退火的有关说明（关键参数调控）模拟退火的执行过程中，算法效果取决于一组控制参数的选择。模拟退火的关键参数包括初始温度，温度下降方法，每一温度迭代长度，终止准则。Nnntk9最优化方法与最优控制模拟退火算法