模拟退火法(SAA )是一种非导数优化方法.doc

模拟退火法(SAA )是一种非导数优化方法.doc

ID:28956469

大小:71.50 KB

页数:8页

时间:2018-12-15

模拟退火法(SAA )是一种非导数优化方法.doc_第1页
模拟退火法(SAA )是一种非导数优化方法.doc_第2页
模拟退火法(SAA )是一种非导数优化方法.doc_第3页
模拟退火法(SAA )是一种非导数优化方法.doc_第4页
模拟退火法(SAA )是一种非导数优化方法.doc_第5页
资源描述:

《模拟退火法(SAA )是一种非导数优化方法.doc》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、基于MATLAB的模拟退火算法的实现一、概述旅行商问题(TSP)是指旅行商必须轮流到N个城市去旅游,每个城市仅去一次,最后返回原出发城市,任务是为旅行商找到一条满足上述条件的最短路径。模拟退火算法是解决TSP问题的有效方法之一,其最初的思想由Metropolis在1953年提出,Kirkpatrick在1983年成功地将其应用在组合最优化问题中。本文以著名的旅行商问题(TSP)为例说明如何利用MATLAB语言实现模拟退火算法。模拟退火算法(SAA)是一种非导数优化方法由于它对组合优化问题像对连续问题一样适用,因而近年来

2、得到广泛的关注。模拟退火来源于拉丝玻璃的物理特性,原理类似于以一定的速率冷却金属时所发生的现象。缓慢下降的温度使融化金属中的原子排成行,形成具有高密度低能量的有规则的晶体结构。但是,如果温度下降过快,原子没有足够的时模拟退火法间排成有规则的结构,结果将产生具有较高能量的非晶体结构。在模拟退火中,本文试图最优化的目标函数类似于热力学系统中的能量。温度高时,模拟退火算法允许对远处的点求函数值,并且有可能接受一个具有较高能量的新点。这对应于具有高活动性的原子,它力图与其他非局部原子一起将自己定位,能量状态可以偶尔上升。温度低

3、时,模拟退火算法只在局部处求目标函数值,它接受较高能量新点的可能性非常小。这类似于具有低活动性原子只能与局部原子一起定位的情况。模拟退火算法包含的基本步骤:(l)选取一个起始点:并设一个较高的起始温度T_ini=50,令迭代次数T_end等于1;(2)求目标函数(能量函数)E=f(x)的函数值;(3)按照由生成函数g(△x,T)确定的概率选择△x,令新点等于x+△x;(4)计算新的目标函数值=f():(5)按照由接收函数h(△E,T)确定的概率将x设为,E设为,其中,△E=一E;(6)按照退火时间表降低温度T;(7)增

4、加迭代次数T_end,如果T_end达到最大迭代次数,停止迭代。否则返回步骤(3)。二、用MATLAB实现模拟退火算法MATLAB是由美国Mathworks公司推出的仿真软件,经过不断发展,现在已成为国际上公认的最优秀数值计算仿真软件之一MATLAB的数值计算能力非常强,对复杂间题往往只需写很短的代码就能实现。此外,他还提供了交互式编程环境,以及丰富可靠的矩阵运算、图形绘制、数据处理、图像处理、模糊控制等工具箱。利用MATLAB提供的强大矩阵处理能力及优秀的绘图功能编制模拟退火算法有着强大的优势。本文以著名的旅行商问题

5、(TSP)为例说明如何利用MATLAB语言实现模拟退火算法。旅行商问题即TSP问题(TravellingSalesmanProblem)是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市,他必须选择所要走的路径,路经的限制是每个城市只能拜访一次,而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。具体实现函数包括:1、%初始化函数city_n=30;fori=1:30solution(i)=i;endfori=1:60pos_a=round(29*rand)+1;%随机变换城市

6、序列pos_b=round(29*rand)+1;ifpos_a~=pos_btemp=solution(pos_a);solution(pos_a)=solution(pos_b);solution(pos_b)=temp;endend%=========================================================%计算创建最近邻表fori=1:city_nforj=1:city_nx1=pos(i,1);y1=pos(i,2);x2=pos(j,1);y2=pos(j,2);di

7、s_table(i,j)=sqrt((x1-x2)^2+(y1-y2)^2);endendfori=1:city_ndis_table(i,i)=inf;endfori=1:round(city_n/10)%创建最近邻表forj=1:city_nm=min(dis_table(j,:));m_pos=min(find(m==dis_table(j,:)));neighbor_table(j,i)=m_pos;dis_table(j,m_pos)=inf;endendcleari;clearj;clearm;clearm

8、_pos;clearpos_a;clearpos_b;cleartemp;clearx1;clearx2;cleary1;cleary2;cleardis_table;2、%退温函数T_cur=0。95*T_cur;3、%状态接收函数ifadapt_cur<=adapt_lastsolution=solution_temp;%若当

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。