模拟退火算法及其MATLAB实现第6章模拟退火算法及其MATLAB实现第6章模拟退火算法及其MATLAB实现6.1算法基本理论6.2算法的MATLAB实现6.3应用实例简单了解退火算法特点介绍模拟退火前，先介绍爬山算法。爬山算法是一种简单的贪心搜索算法，该算法每次从当前解的临近解空间中选择一个最优解作为当前解，直到达到一个局部最优解。简单了解退火算法特点爬山算法如图所示：假设C点为当前解，爬山算法搜索到A点这个局部最优解就会停止搜索，因为在A点无论向那个方向小幅度移动都不能得到更优的解。模拟退火算法在搜索到局部最优解A后，会以一定的概率接受到E的移动。也许经过几次这样的不是局部最优的移动后会到达D点，于是就跳出了局部最大值A。6.1算法基本理论6.1算法基本理论一、算法概述一、算法概述工程中许多实际优化问题的目标函数都是非凸的，存在许多局部最优解。求解全局优化问题的方法可分为两类：确定性方法和随机性方法。确定性算法适用于求解具有一些特殊特征的问题，而梯度法和一般的随机搜索方法则沿着目标函数下降方向搜索，因此常常陷入局部而非全局最优解。6.1算法基本理论6.1算法基本理论一、算法概述一、算法概述模拟退火算法（SA）是一种通用概率算法。用来在一个大的搜索空间内寻找问题的最优解。1953年，Metropolis等提出了模拟退火的思想。1983年，Kirkpatrick等将SA引入组合优化领域。6.1算法基本理论6.1算法基本理论二、基本思想二、基本思想退火，俗称固体降温先把固体加热至足够高温，使固体中所有粒子处于无序的状态，然后将温度缓慢下降，粒子渐渐有序，这样只要温度上升得足够高，冷却过程足够慢，则所有粒子最终会处于最低能态。算法试图随着控制参数T的降低，使目标函数值f（内能E）也逐渐降低，直至趋于全局最小值（退火中低温时的最低能量状态），算法工作过程就像固体退火过程一样。6.1算法基本理论6.1算法基本理论模拟退火算法的由来模拟退火算法的由来模拟退火退火解粒子状态最优解能量最低的状态目标函数f内能控制参数温度T6.1算法基本理论6.1算法基本理论Metropolis准则Metropolis准则——–以概率接受新状态若在温度T，当前状态i(解1)→新状态j(解2)若()，则接受j为当前状态；若，概率大于[0,1)区间的随机数，则仍接受状态j为当前状态；若不成立，则保留状态I为当前状态。新状态的内能当前状态的内能温度Ej>Ei（更差的解）时，0
