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

1、会计学1用用MATLAB实现实现(shxin)模拟退火算法模拟退火算法第一页，共30页。6.1 算法基本(jbn)理论6.2 算法(sun f)的MATLAB实现6.3 应用实例第1页/共30页第二页，共30页。简单了解退火算法简单了解退火算法(sun f)(sun f)特点特点 介绍模拟退火前，先介绍爬山算法。 爬山算法是一种简单的贪心搜索算法，该算法每次从当前(dngqin)解的临近解空间中选择一个最优解作为当前(dngqin)解，直到达到一个局部最优解。第2页/共30页第三页，共30页。简单了解退火简单了解退火(tu hu)(tu hu)算法特点算法特点爬山算法 如图所示：假设C点为当前

2、解，爬山算法搜索(su su)到A点这个局部最优解就会停止搜索(su su)，因为在A点无论向那个方向小幅度移动都不能得到更优的解。 模拟退火算法 在搜索到局部最优解A后，会以一定的概率接受到E的移动。也许(yx)经过几次这样的不是局部最优的移动后会到达D点，于是就跳出了局部最大值A。第3页/共30页第四页，共30页。 工程中许多实际优化问题的目标函数都是非(shfi)凸的，存在许多局部最优解。 求解全局优化问题的方法可分为两类： 确定性方法和随机性方法。 确定性算法适用于求解具有一些特殊特征的问题，而梯度法和一般的随机搜索方法则沿着目标函数下降方向搜索，因此常常陷入局部而非全局最优解。 第4

3、页/共30页第五页，共30页。 模拟退火算法（SA）是一种通用概率算法。用来在一个大的搜索空间内寻找(xnzho)问题的最优解。 1953年，Metropolis等提出了模拟退火的思想。 1983年，Kirkpatrick等将SA引入组合优化领域。 第5页/共30页第六页，共30页。 退火(tu hu)，俗称固体降温 先把固体加热至足够高温，使固体中所有粒子处于无序的状态，然后将温度缓慢下降，粒子渐渐有序，这样只要温度上升得足够高，冷却过程足够慢，则所有粒子最终会处于最低能态。第6页/共30页第七页，共30页。 算法试图随着控制参数T的降低，使目标(mbio)函数值f（内能E）也逐渐降低，直至

4、趋于全局最小值（退火中低温时的最低能量状态），算法工作过程就像固体退火过程一样。6.1 算法算法(sun f)基本理论基本理论模拟退火算法(sun f)的由来模拟退火退火解粒子状态最优解能量最低的状态目标函数f内能控制参数温度T第7页/共30页第八页，共30页。以概率接受(jishu)新状态 第8页/共30页第九页，共30页。新状态(zhungti)的内能当前(dngqin)状态的内能温度(wnd)EjEi（更差的解）时，0P10000 结束，输出当前解 YNYNNYYN扰动：数随机产生01的数二变换法三变换法NY第19页/共30页第二十页，共30页。 第20页/共30页第二十一页，共30页。

5、 第21页/共30页第二十二页，共30页。while t=tf for r=1:Markov_length if (rand 0.5) %随机(su j)产生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; i

6、nd3 = 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页第二十三页，共30页。 if (ind1 ind2) & (ind2 ind3) elseif (ind1 ind3) & (ind3 ind2) i

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

8、d3 = tmp1; end % ind1 ind2 ind3 tmplist1 = sol_new(ind1+1):(ind2-1); %u、v之间的城市(chngsh) sol_new(ind1+1):(ind1+ind3-ind2+1) = . sol_new(ind2):(ind3); %将v到w的城市(chngsh)移到u后面 sol_new(ind1+ind3-ind2+2):ind3) = . tmplist1; %u、v之间的城市(chngsh)移到w后面 end第23页/共30页第二十四页，共30页。 第24页/共30页第二十五页，共30页。 % 计算目标函数(hnsh)即内

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页第二十六页，共30页。 第26页/共30页第二十七页，共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 % 若新解的目标函数大于当前(dngqin)解的， % 则以一定的概率接受新解 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页第二十八页，共30页。 例： 假设(j