用MATLAB实现模拟退火算法

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,模拟退火算法及其,MATLAB,实现,模拟退火,第,6,章 模拟退火算法及其,MATLAB,实现,6.1,算法基本理论,6.2,算法的,MATLAB,实现,6.3,应用实例,简单了解退火算法特点,介绍模拟退火前，先介绍爬山算法。,爬山算法是一种简单的贪心搜索算法，该算法每次从,当前解的临近解空间中选择一个最优解作为当前解，直到,达到一个局部最优解。,简单了解退火算法特点,爬山算法,如图所示：假设,C,点为当前解，爬山算法搜索,到,A,点这个局部最优解就会停止搜索，因为在,A,点无,论向那个方向小幅度移动都不能得到更优的解。,模拟,退火算法,在搜索到局部最优解,A,后，会以,一定的概率,接受到,E,的移动。也许经过几次这样的不是局部最优的移动后会,到达,D,点，于是就跳出了局部最大值,A,。,6.1,算法基本理论,一、算法概述,工程中许多实际优化问题的目标函数都是非凸的，,存在许多局部最优解。,求解全局优化问题的方法可分为两类：,确定性方法和随机性方法。,确定性算法适用于求解具有一些特殊特征的问题，,而梯度法和一般的随机搜索方法则沿着目标函数下降方,向搜索，因此常常陷入局部而非全局最优解。,6.1,算法基本理论,一、算法概述,模拟退火算法（,SA,）是一种通用概率算法。用来,在一个大的搜索空间内寻找问题的最优解,。,1953,年，,Metropolis,等提出了模拟退火的思想。,1983,年，,Kirkpatrick,等将,SA,引入组合优化领域。,6.1,算法基本理论,二、基本思想,退火，俗称固体降温,先把固体加热至足够高温，使固体中所有粒子处,于无序的状态，然后将温度缓慢下降，粒子渐渐有序，,这样只要温度上升得足够高，冷却过程足够慢，则所,有粒子最终会处于最低能态。,算法试图随着控制参数,T,的降低，使目标函,数值,f,（内能,E,）也逐渐降低，直至趋于全局最,小值（退火中低温时的最低能量状态,），算法,工作过程就像固体,退火过程,一样。,6.1,算法基本理论,模拟退火算法的由来,模拟退火,退火,解,粒子状态,最优解,能量最低的状态,目标函数,f,内能,控制参数,温度,T,6.1,算法基本理论,Metropolis,准则,以概率接受新状态,新状态的内能,当前状态的内能,温度,EjEi,（更差的解）时，,0P10000,结束，输出当前解,Y,N,Y,N,N,Y,Y,N,扰动：,数,0.5,随机产生,01,的数,二变换法,三变换法,N,Y,6.2,算法的,MATLAB,实现,一、算法设计步骤,6.2,算法的,MATLAB,实现,一、算法设计步骤,6.2,算法的,MATLAB,实现,一、算法设计步骤,while t=tf,for r=1:Markov_length,if(rand 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)|(abs(ind1-ind2)=1),ind1=ceil(rand.*amount);,ind2=ceil(rand.*amount);,ind3=ceil(rand.*amount);,end,tmp1=ind1;tmp2=ind2;tmp3=ind3;,6.2,算法的,MATLAB,实现,一、算法设计步骤,if,(ind1 ind2)&(ind2 ind3),elseif(ind1 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),ind1=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,6.2,算法的,MATLAB,实现,一、算法设计步骤,6.2,算法的,MATLAB,实现,一、算法设计步骤,%,计算目标函数即内能,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);,6.2,算法的,MATLAB,实现,一、算法设计步骤,6.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,end,6.3,应用实例：背包问题的求解,一,、,0-1,背包问题,例：,假设有,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,磅,模拟退火算法及其,MATLAB,实现,谢谢大家！,