第9章 现代优化算法简介ppt课件.ppt

《第9章 现代优化算法简介ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第九章现代优化算法简介遗传算法、模拟退火算法、禁忌算法、人工神经网络统称20世纪80年代初产生的现代优化算法．它主要解决优化问题中的难解的问题，下面分别介绍遗传算法、模拟退火算法、禁忌算法、人工神经网络．§9.1模拟退火算法一、模拟退火算法基本原理模拟退火算法（SimalatedAnnealing，简称SA）属于一种通用的随机探索算法，1953年N.Metropolis等人提出了模拟退火算法，其基本思想是把某类优化问题的求解过程与统计热力学中的热平衡问题进行对比试图通过模拟高温物体退火过程，来找到优化问题的全局最

2、优解或近似全局最优解．一个物体（如金属）的退火过程大体如下：首先对该物体高温加热（熔化），显然物体内原子处于高速运行的高能状态．然而作为一个实际的物理系统，原子的运动又总是趋于最低的能量状态，在退火的初始状态，由于温度较高，物体处于高能状态，随着温度的逐渐降低，物体内部原子运动化学能趋于低能状态，这种由高能向低能逐渐降温的过程称为退火．当温度降至结晶温度后，物体由原子运动变为围绕晶体格点的微小振动，液体凝固成固体，退火过程结束．对于一个优化问题当我们把目标函数看成定义在可行集（解空间）上的能量曲面，而整个曲面凹凸

3、不平，如果让一个光滑圆球在曲面上自由滚动，这个圆球十有八九会滚到最近的凹处停止运动，但该低谷并不一定是最深的一个凹谷，模拟退火方法就类似于沿水平方向给圆球一个水平方向作用力，若作用于小球的作用力足够大且小球所处的低谷并不很深．小球受水平力作用会从该低谷流出，落入另一低谷，然后受水平力作用又滚出，如此不断滚动，如果作用小球的水平力掌握得适当，小球很有可能停留在最深的低谷之中，这个最深低谷就是优化问题的全局最优解或接近于全局最优解．作用于小球上的水平力相应于模拟退火中的温度T，水平作用力减小相应于温度降低，如图9.1

4、所示．图9.1二、模拟退火算法基本迭代步骤(1)给定初始温度及初始点X，计算该点的函数值．(2)随机产生扰动得新点计算新点函数值及函数值差(3)若，则接受新点，作为下一次模拟的初始点．(4)若则计算新点接受概率，在区间[0,1]上产生服从均匀分布的伪随机数．如果有，则接受新点作为下一次模拟的初始点；否则放弃新点，仍取原来的点作为下一次模拟的初始点．以上步骤，称为Metropolis过程．按照一定的退火方案逐渐降低温度，重复Metropolis过程，就构成模拟退火迭代法．当系统的温度足够低时，就认为达到了全局最优解

5、．在模拟退火算法中，降温的方式对算法有很大的影响．如果温度下降过快，可能会丢失极值点，如果温度下降过慢，算法的收敛速度又大大降低，为了提高模拟退火算法的有效性，许多学者提出了多种退火方案，如(1)经典退火方案：降温公式为，特点是温度下降很缓慢，因此，算法收敛程度很慢．(2)快速退火方式：降温公式为，特点是在高温区温度下降比较快，而在低温区降温的速度较慢．这符合热力学分子运动理论，即分子在高温时，具有较低能量的概率要比在低温时小得多，因此寻优的重点应在低温区，其中参数可以改善退火曲线的形态．三、模拟退火马氏链模型令

6、为所有状态构成的解空间，又令由所可得随机序列若随机序列满足下式则模拟退火状态序列为马氏链．马氏链是一个时间离散，状态离散的时间序列，其特点是具有无后效应．马氏链从某一时刻的某一状态变为另一时刻的另一状态称为状态的转移，而从当前状态经一次转移到下个状态的可能性称为一步转移概率，可记为.从当前转态经n步转移到下一状态的概率，可记为．若解空间有限，马氏链称为有限状态马氏链，若，马氏链称为时齐的．以下讨论的模拟退火算法算法为有限状态马氏链．由前述模拟退火算法的迭代过程可知，算法是从一个初始状态开始后，前一步状态转移均是在

7、当前状态i的邻域中随机产生新状态j，然后以一定概率进行接受．可见接受概率仅依赖于新状态和当前状态，并由温度加以控制．因此模拟退火算法算法显然对应一个马氏链．若固定每一温度T，算法均计算马氏链的变化直系平稳分布，然后下降温度，称这种算法为时齐算法．若无需各温度下算法均达到平稳分布，但温度需按一定的速度下降，称这料算法为非时齐或非平稳马氏链算法．马氏链可用一个有的图表示，其中，V为所有状态构成的顶点集，为边集，其中是以顶点i为起点的有向线段的终点集合．记为由状态i产生j概率，则其中，．通常与温度无关．若新状态在当前状

8、态的邻域中以等同概率产生，则，其中为状态的i邻域中状态总数．记为由当前状态i接受状态j的概率，接受概率通常定义为.其中为目标函数，T为温度参数．记为由状态i到状态j的转移概率，则模拟退火马氏链模型为综上所述，模拟退火算法要实现全局收敛必须满足如下三个条件：（1）状态可达性，即无论起点如何，任何一个状态都可以到达，由此有求得最优解可能．（2）初值鲁棒性，即算法的最终结果不依