《模拟退火算法与MATLAB实现PPT教案.pptx》由会员分享，可在线阅读，更多相关《模拟退火算法与MATLAB实现PPT教案.pptx（30页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、模拟退火算法模拟退火算法(sun f)与与MATLAB实现实现第一页，共30页。第第6 6章章 模拟退火算法模拟退火算法(sun f)(sun f)及其及其MATLABMATLAB实现实现6.1算法(sunf)基本理论6.2算法(sunf)的MATLAB实现6.3应用实例第1页/共30页第二页，共30页。简单简单(jindn)(jindn)了解退火算法特点了解退火算法特点介绍(jisho)模拟退火前，先介绍(jisho)爬山算法。爬山算法是一种简单的贪心搜索算法，该算法每次从当前解的临近解空间中选择一个最优解作为当前解，直到达到一个局部最优解。第2页/共30页第三页，共30页。简单简单(jin
2、dn)(jindn)了解退火算法特点了解退火算法特点爬山算法如图所示：假设C点为当前解，爬山算法搜索到A点这个局部(jb)最优解就会停止搜索，因为在A点无论向那个方向小幅度移动都不能得到更优的解。模拟退火算法在搜索到局部最优解A后，会以一定的概率接受到E的移动。也许经过几次这样的不是局部最优的移动后会到达D点，于是(ysh)就跳出了局部最大值A。第3页/共30页第四页，共30页。6.1 算法算法(sun f)基本理论基本理论一、算法一、算法(sun f)概述概述工程中许多实际优化问题的目标函数都是非凸的，存在许多局部最优解。求解全局优化问题的方法可分为两类：确定性方法和随机性方法。确定性算法适
3、用于求解具有一些特殊特征的问题，而梯度法和一般的随机搜索方法则沿着目标函数下降(xijing)方向搜索，因此常常陷入局部而非全局最优解。第4页/共30页第五页，共30页。6.1 算法算法(sun f)基本理论基本理论一、算法一、算法(sun f)概述概述模拟退火算法（SA）是一种通用概率算法。用来在一个大的搜索空间内寻找问题的最优解。1953年，Metropolis等提出了模拟退火的思想(sxing)。1983年，Kirkpatrick等将SA引入组合优化领域。第5页/共30页第六页，共30页。6.1 算法基本算法基本(jbn)理论理论二、基本二、基本(jbn)思思想想退火，俗称固体(gt)降
4、温先把固体加热至足够高温，使固体中所有粒子处于无序的状态，然后将温度缓慢下降，粒子渐渐有序，这样只要温度上升得足够高，冷却过程足够慢，则所有粒子最终会处于最低能态。第6页/共30页第七页，共30页。算法试图随着控制参数T的降低，使目标函数值f（内能E）也逐渐降低，直至趋于全局(qunj)最小值（退火中低温时的最低能量状态），算法工作过程就像固体退火过程一样。6.1 算法基本算法基本(jbn)理论理论模拟退火算法(sunf)的由来模拟退火模拟退火退火退火解粒子状态最优解能量最低的状态目标函数f内能控制参数温度T第7页/共30页第八页，共30页。6.1 算法基本算法基本(jbn)理论理论Metro
5、polis准则(zhnz)以概率接受(jishu)新状态第8页/共30页第九页，共30页。新状态(zhungti)的内能当前状态(zhungti)的内能温度(wnd)EjEi（更差的解）时，0P10000结束，输出当前解YNYNNYYN扰动：数0.5随机产生01的数二变换法三变换法NY第19页/共30页第二十页，共30页。6.2 6.2 算法算法算法算法(sun f)(sun f)的的的的MATLABMATLAB实现实现实现实现一、算法一、算法(sun f)设计步骤设计步骤第20页/共30页第二十一页，共30页。6.2 6.2 算法算法算法算法(sun f)(sun f)的的的的MATLABM
6、ATLAB实现实现实现实现一、算法设计一、算法设计(shj)步骤步骤2.新解的产生（扰动(rodng)）（1）二变换法：任选序号交换之间的访问顺序。（2）三变换法：任选序号将之间的路径插到之后访问第21页/共30页第二十二页，共30页。6.2 算法算法(sun f)的的MATLAB实现实现一、算法一、算法(sun f)设计步骤设计步骤whilet=tfforr=1:Markov_lengthif(rand0.5)%随机(suj)产生01的数，若小于0.5，则二变换ind1=0;ind2=0;while(ind1=ind2)ind1=ceil(rand.*amount);ind2=ceil(ra
7、nd.*amount);endtmp1=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)|(abs(ind1-ind2)=1)ind1=ceil(rand.*amount);ind2=ceil(rand.*amount);ind3=ceil(rand.*amount);endtmp1=ind1;tmp2=ind2;tmp3=ind3;第22页/共30页第二十三页，共30页。6.
8、2 算法算法(sun f)的的MATLAB实现实现一、算法一、算法(sun f)设计步骤设计步骤if(ind1ind2)&(ind2ind3)elseif(ind1ind3)&(ind3ind2)ind2=tmp3;ind3=tmp2;elseif(ind2ind1)&(ind1ind3)ind1=tmp2;ind2=tmp1;elseif(ind2ind3)&(ind3ind1)ind1=tmp2;ind2=tmp3;ind3=tmp1;elseif(ind3ind1)&(ind1ind2)ind1=tmp3;ind2=tmp1;ind3=tmp2;elseif(ind3ind2)&(ind
9、2ind1)ind1=tmp3;ind2=tmp2;ind3=tmp1;end%ind1ind2ind3tmplist1=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页。6.2 6.2 算法算法算法算法(sun f)(sun f)的的
10、的的MATLABMATLAB实现实现实现实现一、算法一、算法(sun f)设计步骤设计步骤3.目标函数访问所有城市的路径(ljng)总长度：模拟退火算法求出目标函数的最小值第24页/共30页第二十五页，共30页。6.2 6.2 算法算法算法算法(sun f)(sun f)的的的的MATLABMATLAB实现实现实现实现一、算法一、算法(sun f)设计步骤设计步骤%计算目标函数即内能E_new=0;fori=1:(amount-1)E_new=E_new+.dist_matrix(sol_new(i),sol_new(i+1);end%从第一个城市到最后(zuhu)一个城市的距离E_new=E
11、_new+.dist_matrix(sol_new(amount),sol_new(1);第25页/共30页第二十六页，共30页。6.2 算法算法(sun f)的的MATLAB实现实现一、算法一、算法(sun f)设计步骤设计步骤第26页/共30页第二十七页，共30页。6.2 算法算法(sun f)的的MATLAB实现实现一、算法一、算法(sun f)设计步骤设计步骤ifE_newE_currentE_current=E_new;sol_current=sol_new;ifE_newE_best%冷却过程中最好的解保存下来E_best=E_new;sol_best=sol_new;endels
12、e%若新解的目标函数大于当前解的，%则以一定的概率(gil)接受新解ifrandexp(-(E_new-E_current)./t)E_current=E_new;sol_current=sol_new;elsesol_new=sol_current;endend第27页/共30页第二十八页，共30页。6.3 应用实例应用实例(shl)：背包问题的求解：背包问题的求解一、一、0-1背包背包(bibo)问题问题有一个贼在偷窃一家商店时发现有N件物品：第i件物品值元，重磅()，此处和都是整数。他希望带走的东西越值钱越好，但他的背包小，最多只能(zhnn)装下W磅的东西（W为整数）。如果每件物品或被带走或被留下，小偷应该带走哪几样东西？例：假设有12件物品，质量分别为2磅、5磅、18磅、3磅、2磅、5磅、10磅、4磅、11磅、7磅、14磅、6磅，价值分别为5元、10元、13元、4元、3元、11元、13元、10元、8元、16元、7元、4元，包的最大允许质量是46磅第28页/共30页第二十九页，共30页。模拟退火算法(sunf)及其MATLAB实现谢谢(xixie)大家！第29页/共30页第三十页，共30页。