模拟退火法-Read.DOC

基于MATLAB的模拟退火算法的实现 一、概述 旅行商问题（TSP）是指旅行商必须轮流到N个城市去旅游，每个城市仅去一次，最后返回原出发城市，任务是为旅行商找到一条满足上述条件的最短路径。模拟退火算法是解决TS问题的有效方法之一，其最初的思想由Metropolis在1953年提出，Kirkpatrick在1983年成功地将其应用在组合最优化问题中。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)增加迭代次数T_end，如果T_end达到最大迭代次数，停止迭代。否则返回步骤(3)。 二、用MATLAB实现模拟退火算法 MATLAB是由美国Math works公司推出的仿真软件，经过不断发展，现在已成为国际上公认的最优秀数值计算仿真软件之一MATLAB的数值计算能力非常强，对复杂间题往往只需写很短的代码就能实现。此外，他还提供了交互式编程环境，以及丰富可靠的矩阵运算、图形绘制、数据处理、图像处理、模糊控制等工具箱。利用MATLAB提供的强大矩阵处理能力及优秀的绘图功能编制模拟退火算法有着强大的优势。 本文以著名的旅行商问题(TSP)为例说明如何利用MATLAB语言实现模拟退火算法。旅行商问题即TSP问题（Travelling Salesman Problem）是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路经的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。city_n=30; for i=1:30 solution(i)=i; end for i=1:60 pos_a=round(29*rand)+1; %随机变换城市序列 pos_b=round(29*rand)+1; if pos_a~=pos_b temp=solution(pos_a); solution(pos_a)=solution(pos_b); solution(pos_b)=temp; end end %========================================================= %计算创建最近邻表 for i=1:city_n for j=1:city_n x1=pos(i,1); y1=pos(i,2); x2=pos(j,1); y2=pos(j,2); dis_table(i,j)=sqrt((x1-x2)^2+(y1-y2)^2); end end for i=1:city_n dis_table(i,i)=inf; end for i=1:round(city_n/10) %创建最近邻表 for j=1:city_n m=min(dis_table(j,:)); m_pos=min(find(m==dis_table(j,:))); neighbor_table(j,i)=m_pos; dis_table(j,m_pos)=inf; end end clear i; clear j; clear m; clear m_pos; clear pos_a; clear pos_b; clear temp; clear x1; clear x2; clear y1; clear y2; clear dis_table; 2、% 退温函数 T_cur=0。95*T_cur;if adapt_cur=adapt_last solution=solution_temp; %若当前解优于上代解，则以概率1接收 else if randexp((adapt_cur-adapt_last)/T_cur) %概率接收 solution=solution_temp; end end 4、%适应值计算函数 dis=0; dis_sum=0; x1=0; x2=0; y1=0; y2=0; for j=1:(city_n-1) %计算前39段距离 x1=pos(solu