用MATLAB实现模拟退火算法PPT学习教案

1、会计学1用用MATLAB实现模拟退火算法实现模拟退火算法6.1 算法基本理论6.2 算法的MATLAB实现6.3 应用实例第1页/共30页简单了解退火算法特点简单了解退火算法特点 介绍模拟退火前，先介绍爬山算法。 爬山算法是一种简单的贪心搜索算法，该算法每次从当前解的临近解空间中选择一个最优解作为当前解，直到达到一个局部最优解。第2页/共30页简单了解退火算法特点简单了解退火算法特点爬山算法 如图所示：假设C点为当前解，爬山算法搜索到A点这个局部最优解就会停止搜索，因为在A点无论向那个方向小幅度移动都不能得到更优的解。 模拟退火算法 在搜索到局部最优解A后，会以一定的概率一定的概率接受到E的移

2、动。也许经过几次这样的不是局部最优的移动后会到达D点，于是就跳出了局部最大值A。第3页/共30页 工程中许多实际优化问题的目标函数都是非凸的，存在许多局部最优解。 求解全局优化问题的方法可分为两类： 确定性方法和随机性方法。 确定性算法适用于求解具有一些特殊特征的问题，而梯度法和一般的随机搜索方法则沿着目标函数下降方向搜索，因此常常陷入局部而非全局最优解。 第4页/共30页 模拟退火算法（SA）是一种通用概率算法。用来在一个大的搜索空间内寻找问题的最优解。 1953年，Metropolis等提出了模拟退火的思想。 1983年，Kirkpatrick等将SA引入组合优化领域。 第5页/共30页

3、退火，俗称固体降温 先把固体加热至足够高温，使固体中所有粒子处于无序的状态，然后将温度缓慢下降，粒子渐渐有序，这样只要温度上升得足够高，冷却过程足够慢，则所有粒子最终会处于最低能态。第6页/共30页 算法试图随着控制参数T的降低，使目标函数值f（内能E）也逐渐降低，直至趋于全局最小值（退火中低温时的最低能量状态），算法工作过程就像固体退火过程一样。6.1 算法基本理论算法基本理论模拟退火算法的由来模拟退火退火解粒子状态最优解能量最低的状态目标函数f内能控制参数温度T第7页/共30页以概率接受新状态 第8页/共30页新状态的内能当前状态的内能温度EjEi（更差的解）时，0P10000 结束，输出

4、当前解 YNYNNYYN扰动：数随机产生01的数二变换法三变换法NY第19页/共30页 第20页/共30页 第21页/共30页while t=tf for r=1:Markov_length if (rand 0.5) %随机产生01的数，若小于，则二变换 ind1 = 0; ind2 = 0; while (ind1 = ind2) ind1 = ceil(rand.*amount); ind2 = ceil(rand.*amount); end tmp1 = sol_new(ind1); sol_new(ind1) = sol_new(ind2); sol_new(ind2) = tmp1

5、; else %否则，三变换 ind1 = 0; ind2 = 0; ind3 = 0; while (ind1 = ind2) | (ind1 = ind3) . | (ind2 = ind3) | (abs(ind1-ind2) = 1) ind1 = ceil(rand.*amount); ind2 = ceil(rand.*amount); ind3 = ceil(rand.*amount); end tmp1 = ind1;tmp2 = ind2;tmp3 = ind3; 第22页/共30页 if (ind1 ind2) & (ind2 ind3) elseif (ind1

6、ind3) & (ind3 ind2) ind2 = tmp3;ind3 = tmp2; elseif (ind2 ind1) & (ind1 ind3) ind1 = tmp2;ind2 = tmp1; elseif (ind2 ind3) & (ind3 ind1) ind1 = tmp2;ind2 = tmp3; ind3 = tmp1; elseif (ind3 ind1) & (ind1 ind2) ind1 = tmp3;ind2 = tmp1; ind3 = tmp2; elseif (ind3 ind2) & (ind2 ind1) in

7、d1 = tmp3;ind2 = tmp2; ind3 = tmp1; end % ind1 ind2 ind3 tmplist1 = sol_new(ind1+1):(ind2-1); %u、v之间的城市 sol_new(ind1+1):(ind1+ind3-ind2+1) = . sol_new(ind2):(ind3); %将v到w的城市移到u后面 sol_new(ind1+ind3-ind2+2):ind3) = . tmplist1; %u、v之间的城市移到w后面 end第23页/共30页 第24页/共30页 % 计算目标函数即内能 E_new = 0; for i = 1 : (a

8、mount-1) E_new = E_new + . dist_matrix(sol_new(i),sol_new(i+1); end %从第一个城市到最后一个城市的距离 E_new = E_new + . dist_matrix(sol_new(amount),sol_new(1);第25页/共30页 第26页/共30页if E_new E_current E_current = E_new; sol_current = sol_new; if E_new E_best % 冷却过程中最好的解保存下来 E_best = E_new; sol_best = sol_new; end else % 若新解的目标函数大于当前解的， % 则以一定的概率接受新解 if rand exp(-(E_new-E_current)./t) E_current = E_new; sol_current = sol_new; else sol_new = sol_current; end end第27页/共30页