用MATLAB实现模拟退火算法

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

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

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

4、最低的状态目标函数f内能控制参数温度Ta96.1 算法基本理论算法基本理论 Metropolis准则以概率接受新状态 a10新状态的内能当前状态的内能温度EjEi（更差的解）时，0P10000 结束，输出当前解 YNYNNYYN扰动：数0.5随机产生01的数二变换法三变换法NYa216.2 算法的算法的MATLAB实现实现一、算法设计步骤一、算法设计步骤 a226.2 算法的算法的MATLAB实现实现一、算法设计步骤一、算法设计步骤 a236.2 算法的算法的MATLAB实现实现一、算法设计步骤一、算法设计步骤while t=tf for r=1:Markov_length if (rand

5、0.5) %随机产生01的数，若小于0.5，则二变换 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 = ind3) . | (ind2 = ind3) | (

6、abs(ind1-ind2) = 1) ind1 = ceil(rand.*amount); ind2 = ceil(rand.*amount); ind3 = ceil(rand.*amount); end tmp1 = ind1;tmp2 = ind2;tmp3 = ind3; a246.2 算法的算法的MATLAB实现实现一、算法设计步骤一、算法设计步骤 if (ind1 ind2) & (ind2 ind3) elseif (ind1 ind3) & (ind3 ind2) ind2 = tmp3;ind3 = tmp2; elseif (ind2 ind1) &

7、; (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; end % ind1 ind2 ind3 tmplist1 = sol_

8、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后面 enda256.2 算法的算法的MATLAB实现实现一、算法设计步骤一、算法设计步骤 a266.2 算法的算法的MATLAB实现实现一、算法设计步骤一、算法设计步骤 % 计算目标函数即内能 E_new = 0; for i = 1 : (amount-1) E_n

9、ew = E_new + . dist_matrix(sol_new(i),sol_new(i+1); end %从第一个城市到最后一个城市的距离 E_new = E_new + . dist_matrix(sol_new(amount),sol_new(1);a276.2 算法的算法的MATLAB实现实现一、算法设计步骤一、算法设计步骤 a286.2 算法的算法的MATLAB实现实现一、算法设计步骤一、算法设计步骤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 enda296.3 应用实例：背包问题的求解应用实例：背包问题的求解一、一