模拟退火算法.ppt
- 文档编号:15597985
- 上传时间:2023-07-05
- 格式:PPT
- 页数:31
- 大小:432KB
模拟退火算法.ppt
《模拟退火算法.ppt》由会员分享,可在线阅读,更多相关《模拟退火算法.ppt(31页珍藏版)》请在冰点文库上搜索。
,模拟退火算法,姓名:
盛媛媛班级:
研控计1322学号:
1132227140指导老师:
黄从智,爬山算法,介绍模拟退火前,先介绍爬山算法。
爬山算法是一种简单的贪心搜索算法,该算法每次从当前解的临近解空间中选择一个最优解作为当前解,直到达到一个局部最优解。
假设C点为当前解,爬山算法搜索到A点这个局部最优解就会停止搜索,因为在A点无论向那个方向小幅度移动都不能得到更优的解爬山算法实现很简单,其主要缺点是会陷入局部最优解,而不一定能搜索到全局最优解。
爬山算法,爬山法是完完全全的贪心法,每次都鼠目寸光的选择一个当前最优解,因此只能搜索到局部的最优值。
模拟退火其实也是一种贪心算法,但是它的搜索过程引入了随机因素。
模拟退火算法以一定的概率来接受一个比当前解要差的解,因此有可能会跳出这个局部的最优解,达到全局的最优解。
什么是模拟退火算法呢?
简介,模拟退火算法(SimulateAnnealArithmetic,SAA)最早的思想是由N.Metropolis等人于1953年提出。
1983年,S.Kirkpatrick等成功地将退火思想引入到组合优化领域。
它是基于Monte-Carlo(蒙特卡罗)迭代求解策略的一种随机寻优算法,其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。
模拟退火算法从某一较高初温出发,伴随温度参数的不断下降,结合概率突跳特性在解空间中随机寻找目标函数的全局最优解,即在局部最优解能概率性地跳出并最终趋于全局最优。
模拟退火算法是一种通用的优化算法,理论上算法具有概率的全局优化性能,目前已在工程中得到了广泛应用,诸如生产调度、控制工程、机器学习、神经网络、信号处理等领域。
物理退火,模拟退火来自冶金学的专有名词退火。
什么是退火呢?
退火是将材料加热后再经特定速率冷却,目的是增大晶粒的体积,并且减少晶格中的缺陷。
材料中的原子原来会停留在使内能有局部最小值的位置,加热使能量变大,原子会离开原来位置,而随机在其他位置中移动。
退火冷却时速度较慢,使得原子有较多可能可以找到内能比原先更低的位置。
物理退火,物理退火过程:
加温过程-增强粒子的热运动,消除系统原先可能存在的非均匀态;等温过程-对于与环境换热而温度不变的封闭系统,系统状态的自发变化总是朝自由能减少的方向进行,当自由能达到最小时,系统达到平衡。
冷却过程-是例子热运动减弱并渐趋于有序,系统能量逐渐下降,从而得到低能的晶体结构。
原理,模拟退火的原理也和金属退火的原理近似:
将热力学的理论套用到统计学上,将搜寻空间内每一点想像成空气内的分子;分子的能量,就是它本身的动能;而搜寻空间内的每一点,也像空气分子一样带有“能量”,以表示该点对命题的合适程度。
演算法先以搜寻空间内一个任意点作起始:
每一步先选择一个“邻居”,然后再计算从现有位置到达“邻居”的概率。
定义:
将固体加温至充分高,再让其徐徐冷却,加温时,固体内部粒子随温升变为无序状,内能增大,而徐徐冷却时粒子渐趋有序,在每个温度都达到平衡态,最后在常温时达到基态,内能减为最小。
模拟退火算法思想,模拟退火算法描述:
若J(Y(i+1)=J(Y(i)(即移动后得到更优解),则总是接受该移动若J(Y(i+1)J(Y(i)(即移动后的解比当前解要差),则以一定的概率接受移动,而且这个概率随着时间推移逐渐降低(逐渐降低才能趋向稳定)这里的“一定的概率”的计算参考了金属冶炼的退火过程,这也是模拟退火算法名称的由来。
根据热力学的原理,在温度为T时,出现能量差为E的降温的概率为P(E),表示为:
P(E)=exp(E/(kT)其中k是一个常数,exp表示自然指数,且E0。
这条公式说白了就是:
温度越高,出现一次能量差为E的降温的概率就越大;温度越低,则出现降温的概率就越小。
又由于E总是小于0(否则就不叫退火了),因此E/kT0,所以P(E)的函数取值范围是(0,1)。
随着温度T的降低,P(E)会逐渐降低。
我们将一次向较差解的移动看做一次温度跳变过程,我们以概率P(E)来接受这样的移动。
爬山算法,仍以上图为例,模拟退火算法在搜索到局部最优解A后,会以一定的概率接受到E的移动。
也许经过几次这样的不是局部最优的移动后会到达D点,于是就跳出了局部最大值A。
关于爬山算法与模拟退火,有一个有趣的比喻:
爬山算法:
兔子朝着比现在高的地方跳去。
它找到了不远处的最高山峰。
但是这座山不一定是珠穆朗玛峰。
这就是爬山算法,它不能保证局部最优值就是全局最优值。
模拟退火:
兔子喝醉了。
它随机地跳了很长时间。
这期间,它可能走向高处,也可能踏入平地。
但是,它渐渐清醒了并朝最高方向跳去。
这就是模拟退火。
步骤,模拟退火算法可以分解为解空间、目标函数和初始解三部分。
模拟退火的基本步骤:
(1)初始化:
初始温度T(充分大),初始解状态S(是算法迭代的起点),每个T值的迭代次数L
(2)对k=1,L做第(3)至第6步:
(3)产生新解S(4)计算增量t=C(S)-C(S),其中C(S)为评价函数(5)若t0,然后转第2步。
流程图,外循环终止准则,1、设置终止温度的阈值2、设置外循环迭代次数3、算法搜索到的最优值连续若干步保持不变4、概率分析方法,内循环终止准则,常用Metropolis抽样稳定准则1、检验目标函数的均值是否稳定2连续若干步的目标值变化较小3、按一定的步数抽样,模拟退火算法的参数控制问题,模拟退火算法的应用很广泛,可以求解NP完全问题,但其参数难以控制,其主要问题有以下三点:
(1)温度T的初始值设置问题。
温度T的初始值设置是影响模拟退火算法全局搜索性能的重要因素之一、初始温度高,则搜索到全局最优解的可能性大,但因此要花费大量的计算时间;反之,则可节约计算时间,但全局搜索性能可能受到影响。
实际应用过程中,初始温度一般需要依据实验结果进行若干次调整。
(2)退火速度问题。
模拟退火算法的全局搜索性能也与退火速度密切相关。
一般来说,同一温度下的“充分”搜索(退火)是相当必要的,但这需要计算时间。
实际应用中,要针对具体问题的性质和特征设置合理的退火平衡条件。
(3)温度管理问题。
温度管理问题也是模拟退火算法难以处理的问题之一。
实际应用中,由于必须考虑计算复杂度的切实可行性等问题,常采用如下所示的降温方式:
T(t+1)=K*T(t)式中k为正的略小于1.00的常数,t为降温的次数。
模拟退火算法评价,1、模拟退火算法是一种随机算法,并不一定能找到全局的最优解,可以比较快的找到问题的近似最优解。
如果参数设置得当,模拟退火算法搜索效率比穷举法要高。
2、模拟退火算法是通过赋予搜索过程一种时变且最终趋于零的概率突跳性,从而可有效避免陷入局部极小并最终趋于全局最优的串行结构的优化算法。
旅行商问题,TSP,即TravelingSalemanProblem,也就是旅行商问题,又译为旅行推销员问题、货郎担问题,简称为TSP问题,是数学领域著名的问题之一。
TSP问题是最基本的路线问题,该问题是在寻求单一旅行者由起点出发,通过所有给定的需求点之后,最后再回到原点的最小路径成本。
旅行商问题,模拟退火解决TSP的思路:
1.产生一条新的遍历路径P(i+1),计算路径P(i+1)的长度L(P(i+1);2.若L(P(i+1)L(P(i),则接受P(i+1)为新的路径,否则以模拟退火的概率接受P(i+1),然后降温;3.重复步骤1,2直到满足退出条件产生新的遍历路径的方法有很多,下面列举其中3种:
1.随机选择2个节点,交换路径中的这2个节点的顺序。
2.随机选择2个节点,将路径中这2个节点间的节点顺序逆转。
3.随机选择3个节点m,n,k,然后将节点m与n间的节点移位到节点k后面。
交换,交换又称2-OPT算法,是最常用的一种算法,其主要思想是在所有城市中随机选取两个城市,然后将2个城市在路径中的序列交换位置产生新的路径。
例如:
解空间S是边防每个城市恰好一次的所有路径,解乐意表示为W1,W2,Wn是1,2,的一个排列,表明W1城市出发,经过W2,Wn城市,在返回W1城市。
新路径的产生:
随机产生1和n之间的两相异数k和m。
不妨设km,则将原路径W1,W2,Wk,W(k+1),Wm,W(m+1),Wn变为新路径:
W1,W2,Wm,W(k+1),Wk,W(m+1),Wn,置换,置换的主要思想是:
随即在路径中选出两个城市,然后将两个城市之间的城市顺序完全倒置得出新的路径。
如上例:
产生两个相异数k和m(假设km),则将原路径W1,W2W(k-1),Wk,W(k+1),W(m-1),Wm,W(m+1),Wn变为新路径:
W1,W2W(k-1),Wm,W(m-1),W(k+1),Wk,W(m+1),Wn,移位,移位的主要思想是随机选出两个城市,两城市之间的城市同意向右移一位。
如:
随机选出城市Wk和Wm(假设km),则将原路径W1,W2W(k-1),Wk,W(k+1),W(m-1),Wm,W(m+1),Wn变为新路径:
W1,W2W(k-1),Wm+1,Wk,W(m-1),Wm,W(m+1),Wn,实例,用模拟退火算法解决如下10个诚实的TSP问题,Swap.m,functionnewpath,position=swap(oldpath,number)%对oldpath进行互换操作%number为产生的新路径的个数%position为对应newpath互换的位置m=length(oldpath);%城市的个数newpath=zeros(number,m);position=sort(randi(m,number,2),2);%随机产生交换的位置fori=1:
numbernewpath(i,:
)=oldpath;%交换路径中选中的城市newpath(i,position(i,1)=oldpath(position(i,2);newpath(i,position(i,2)=oldpath(position(i,1);End,Pathfare.m,functionobjval=pathfare(fare,path)%计算路径path的代价objval%path为1到n的排列,代表城市的访问顺序;%fare为代价矩阵,且为方阵。
m,n=size(path);objval=zeros(1,m);fori=1:
mforj=2:
nobjval(i)=objval(i)+fare(path(i,j-1),path(i,j);endobjval(i)=objval(i)+fare(path(i,n),path(i,1);end,Distance.m,functionfare=distance(coord)%根据各城市的距离坐标求相互之间的距离%fare为各城市的距离,coord为各城市的坐标,m=size(coord);%m为城市的个数fare=zeros(m);fori=1:
m%外层为行forj=i:
m%内层为列fare(i,j)=.(sum(coord(:
i)-coord(:
j).2)0.5;fare(j,i)=fare(i,j);%距离矩阵对称endend,Myplot.m,function=myplot(path,coord,pathfar)%做出路径的图形%path为要做图的路径,coord为各个城市的坐标%pathfar为路径path对应的费用len=length(path);clf;holdon;title(近似最短路径如下,费用为,num2str(pathfar);plot(coord(1,:
),coord(2,:
),ok);pause(0.4);forii=2:
lenplot(coord(1,path(ii-1,ii),coord(2,path(ii-1,ii),-b);x=sum(coord(1,path(ii-1,ii)/2;y=sum(coord(2,path(ii-1,ii)/2;text(x,y,(,num2str(ii-1),);pause(0.4);endplot(coord(1,path(1,len),coord(2,path(1,len),-b);x=sum(coord(1,path(1,len)/2;y=sum(coord(2,path(1,len)/2;text(x,y,(,num2str(len),);pause(0.4);holdoff;,Mysaa.m,%模拟退火算法(SimulatedAnnealingAlgorithm)MATLAB程序clear;%程序参数设定Coord=.%城市的坐标Coordinates0.66830.61950.40.24390.17070.22930.51710.87320.68780.8488;.0.25360.26340.44390.14630.22930.7610.94140.65360.52190.3609;t0=1;%初温t0iLk=20;%内循环最大迭代次数iLkoLk=50;%外循环最大迭代次数oLklam=0.95;%lambdaistd=0.001;%若内循环函数值方差小于istd则停止ostd=0.001;%若外循环函数值方差小于ostd则停止ilen=5;%内循环保存的目标函数值个数olen=5;%外循环保存的目标函数值个数%程序主体m=length(Coord);%城市的个数mfare=distance(Coord);%路径费用farepath=1:
m;%初始路径pathpathfar=pathfare(fare,path);%路径费用pathfareores=zeros(1,olen);%外循环保存的目标函数值e0=pathfar;%能量初值e0t=t0;%温度tforout=1:
oLk%外循环模拟退火过程ires=zeros(1,ilen);%内循环保存的目标函数值forin=1:
iLk%内循环模拟热平衡过程newpath,=swap(path,1);%产生新状态e1=pathfare(fare,newpath);%新状态能量,%Metropolis抽样稳定准则r=min(1,exp(-(e1-e0)/t);ifrandrpath=newpath;%更新最佳状态e0=e1;endires=ires(2:
end)e0;%保存新状态能量%内循环终止准则:
连续ilen个状态能量波动小于istdifstd(ires,1)istdbreak;endendores=ores(2:
end)e0;%保存新状态能量%外循环终止准则:
连续olen个状态能量波动小于ostdifstd(ores,1)ostdbreak;endt=lam*t;endpathfar=e0;%输入结果fprintf(近似最优路径为:
n)%disp(char(path,path
(1)+64);disp(path)fprintf(近似最优路径费用tpathfare=);disp(pathfar);myplot(path,Coord,pathfar);,运行结果,运行结果,谢谢观赏,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 模拟 退火 算法