用MATLAB实现模拟退火算法PPT课件

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

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

3、Metropolis等提出了模拟退火的思想。 1983年，Kirkpatrick等将SA引入组合优化领域。 第5页/共30页6.1 算法基本理论算法基本理论二、基本思想二、基本思想 退火，俗称固体降温 先把固体加热至足够高温，使固体中所有粒子处于无序的状态，然后将温度缓慢下降，粒子渐渐有序，这样只要温度上升得足够高，冷却过程足够慢，则所有粒子最终会处于最低能态。第6页/共30页 算法试图随着控制参数T的降低，使目标函数值f（内能E）也逐渐降低，直至趋于全局最小值（退火中低温时的最低能量状态），算法工作过程就像固体退火过程一样。6.1 算法基本理论算法基本理论模拟退火算法的由来模拟退火退火解粒子

4、状态最优解能量最低的状态目标函数f内能控制参数温度T第7页/共30页6.1 算法基本理论算法基本理论 Metropolis准则以概率接受新状态 第8页/共30页新状态的内能当前状态的内能温度EjEi（更差的解）时，0P10000 结束，输出当前解 YNYNNYYN扰动：数随机产生01的数二变换法三变换法NY第19页/共30页6.2 算法的算法的MATLAB实现实现一、算法设计步骤一、算法设计步骤 第20页/共30页6.2 算法的算法的MATLAB实现实现一、算法设计步骤一、算法设计步骤 第21页/共30页6.2 算法的算法的MATLAB实现实现一、算法设计步骤一、算法设计步骤while t=t

5、f 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; else %否则，三变换 ind1 = 0; ind2 = 0; ind3 = 0; while (ind1 = ind2) | (ind1

6、 = 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页6.2 算法的算法的MATLAB实现实现一、算法设计步骤一、算法设计步骤 if (ind1 ind2) & (ind2 ind3) elseif (ind1 ind3) & (ind3 ind2) ind2 = tmp3;

7、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) ind1 = tmp3;ind2 = tmp2; ind3 = tmp1;

8、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页6.2 算法的算法的MATLAB实现实现一、算法设计步骤一、算法设计步骤 第24页/共30页6.2 算法的算法的MATLAB实现实现一、算法设计步骤一、算法设计步骤 %

9、 计算目标函数即内能 E_new = 0; for i = 1 : (amount-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页6.2 算法的算法的MATLAB实现实现一、算法设计步骤一、算法设计步骤 第26页/共30页6.2 算法的算法的MATLAB实现实现一、算法设计步骤一、算法设计步骤if E_new E_current E_current =

10、 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页6.3 应用实例：背包问题的求解应用实例：背包问题的求解一、一、0-1背包问题背包问题 例： 假设有12件物品，质量分别为2磅、5磅