第 26卷 第 3期
2003年 6月
鞍 山 科 技 大 学 学 报
Journal of Anshan University of Science and Technology
V01．26 No．3
Jun．，2003
基于 MATLAB的模拟退火算法的实现
曲 强 ，陈雪波
(鞍山科技大学 电子信息与工程学院，辽宁 鞍山 114o~)
摘 要 ：阐述了模拟退火算法的基本原理及实现过程，运用 MATLAB语言实现了该算法．并将其运用到解决
旅行商问题的优化之 中．数值仿真的结果表明了该方法能够对函数进行全局寻优 ，有效克服了基 于导数的优
化算法容 易陷入局部最优的问题．该方法既可以增加对 MATLAB语言的了解又可以加深对模拟退火过程的认
识 ，并达 到以此 来设 计智 能 系统的 目的 ．
关键词 ：MATLAB模拟退火；优化；旅行商
中图分类号 ：TP273 文献标识码 ：A 文章编号 ：1672-4410(2003)03-0196-04
模拟退火法(SAA)⋯是一种非导数优化方法．由于它对组合优化问题像对连续问题一样适用，因而
近年来得到广泛的关注 ．模拟退火来源于拉丝玻璃的物理特性，原理类似于以一定的速率冷却金属
时所发生的现象．缓慢下降的温度使融化金属中的原子排成行，形成具有高密度低能量的有规则的晶体
结构．但是，如果温度下降过快，原子没有足够的时间排成有规则的结构，结果将产生具有较高能量的非
晶体结构 ．
在模拟退火中，本文试图最优化的目标函数类似于热力学系统中的能量．温度高时，模拟退火算法
允许对远处的点求函数值 ，并且有可能接受一个具有较高能量的新点．这对应于具有高活动性的原子，
它力图与其他非局部原子一起将 自己定位，能量状态可以偶尔上升．温度低时，模拟退火算法只在局部
处求目标函数值，它接受较高能量新点的可能性非常小．这类似于具有低活动性原子只能与局部原子一
起定位 的情况 ．
模拟退火算法包含的基本步骤 】：(1)选取一个起始点 ，并设一个较高的起始温度 ，令迭代次数
k等于 1；(2)求 目标函数(能量函数)E=f( )的函数值；(3)按照由生成函数 g(Ax， )确定的概率选
择 △ ，令新点 等于 +△ ；(4)计算新的目标函数值 E =
．
厂( )；(5)按照由接收函数 h(AE， )确
定的概率将 设为 ，E设为E ，其中，AE=E 一E；(6)按照退火时间表降低温度 T；(7)增加迭代次
数 k，如果 k达到最大迭代次数，停止迭代．否则返回步骤(3)．
1 用 MATLAB实现模拟退火算法
MATLAB是由美国 Math works公司推出的仿真软件，经过不断发展，现在已成为国际上公认的最优
秀数值计算仿真软件之一 ．MATLAB的数值计算能力非常强，对复杂问题往往只需写很短的代码就能实
现．此外 ，他还提供了交互式编程环境，以及丰富可靠的矩阵运算、图形绘制、数据处理、图像处理、模糊
控制等工具箱．利用 MATLAB提供的强大矩阵处理能力及优秀的绘图功能编制模拟退火算法有着强大
的优势 ．
本文以著名的旅行商问题( P)为例说明如何利用 MATLAB语言实现模拟退火算法．
旅行商问题是指旅行商必须轮流到 J7、r个城市去旅游，每个城市仅去一次，最后返回原出发城市，任
务是为旅行商找到一条满足上述条件的最短路径．
收稿日期：2OO2—11—01．
作者简介：曲 强(1972一)，男，辽宁海城人，讲师
1 羽| l_ ■誓 啊 Ⅱ
维普资讯 http://www.cqvip.com
第 3期 曲 强 ，等 ：基 于 MATLAB的模拟退火算法的实现 ·197 ·
1．1 选取起始点并初始化变量
在利用模拟退火算法进行优化之前，必须首先选取一个优化的起始点 ，优化起始点可以随机选取也
可根据经验选取．随机选取一个起始点，实现这部分功能的程序为(注：凡是本程序 自定义的变量、函数
开头字母均大写，MATLAB中的库函数均小写)：
f0r，=1：NumCity
f0r， =1：NumCity
Distance(，，，)=norm(Location(，，：)一Location(，，：))；
end
end
Path=randperm(NumCity)：
Energy=sum(Distance((Path—I) NumCity+[Path(I：NumCity)Path(I)]))；
在上述代码中，首先根据需要旅游的城市总数 NumCity和各城市的位置矩阵 Location计算各城市间
的距离(即上面的两个 f0r循环)，然后利用 MATI_AB函数 randperm随机产生一条旅行路线，最后计算该
路线 的总长度 Distance．
1．2 固定温度的模拟退火子 函数
首先，在温度为一个较高值时，利用生成函数确定新的搜索点，常用生成函数有：Boltzman机使用的
高斯密度函数，Cauchy机使用的 Cauchy分布函数等．为了确定新数据是否能够被接受，必须选择一个适
当的接受函数 ．
function[MaxE，Mine，Path]=Annealing(Path，Energy，Temp，MaxE，Mine)
TrialN =0；
while TrialN
StopTolemnee，
[MaxE，MinE]-Annealing(Path，Energy，Temp，MaxE，MinE)；
Temp=Temp TempRatio：
end
从上述程序可知。采用旅行路径最大值与最小值之间的相对误差作为停止推理条件，即当路径的相
对误差(Ma](E—MinE)／MaxE小于停止误差 StopTolerance时，结束模拟退火推理过程．温度下降律为
0．5．
2 仿真实例
为了验证用 MATLAB实现的模拟退火算法的有效性，选择 30个点作为仿真研究对象，它们在坐标
平面的坐标(Location)如表 1所示 ．
表 1 仿真 用数据
采用上述程序中随机排列的方法产生初始路径 ，其排列结果如图 1所示 ．选择接受 函数为 Boltzmann
概率分布函数 ，温度的起始值为 70，温度下降律为 0．5，经过运行最终得到结果如图 2所示 ，由该 图可知
经过优化后找到了最小路径 ．
图 1 初 始路 径分布 图 2 最 终路径分 布
Fig．1 Initial path distribution Fig．2 Terminal path distribution
3 结 论
利用 MATLAB语言实现的模拟退火程序 ，能够找到系统的最优解，仿真结果
证明
住所证明下载场所使用证明下载诊断证明下载住所证明下载爱问住所证明下载爱问
了该方法的有效
性．采用该方法既可使大家熟悉 MATLAB语言，又可以加深对模拟退火算法的认识和理解。以此来设计
智能系统．
1 ．18l 疆硼r_嗣翻I『I1咽■眭
维普资讯 http://www.cqvip.com
第3期 曲 强，等：基于 MATLAB的模拟退火算法的实现
参 考 文 献 ：
[1]LAI P F，PRAWER S，BURSILLL A．Recovery of diamond after irradiation at high energy and annealing[J]．Diamond and Rel8led
Materials。2001，lo(1)：82—86．
[2]ZHANG Muxiang。MA Fulog．Simulated annealing approach to the m~nimm distance of error-correcting codes[J]．Electronics，1994，
76(3)：377—384．
[3]郭茂祖，姜俊峰 ，李静海 ．模拟退火算法中冷却调度选取方法的研究[J]．计算机工程，2002，26(9)：63，64．
[4]陈万里，程家兴．基于模拟退火算法(SSA)求解列车控制问题[J]．安徽 大学学报。2000．24(3)：46—49．
[5]刘向群 ，仇越 ．模拟退火算法和遗传算法在航空直流测速发 电机优化设计中的应用与性能比较[J]．航空学报 ，2OOO．21
(6)：516—563．
[6]张智星，孙春在 ，水谷英二，等 ．神经．模糊和软计算[M]．西安 ：西安交通大学出版社，20O0：126—130．
【7]廖明，吴宁，谢品芳，等，MATLAB在人工神经网计算机仿真中的应用【J]．计算技术与自动化，1999，18(1)：l8—21．
Simulated annealing algorithm based on M ATLAB
Qu Qiang．CHEN Xue-bo
(School of Electronic and Information Engineering，Anshan University of Science and Technology，Anshan 1 14044，China)
Abstract：This paper realized simulated annealing algorithm in MATLAB．The simulation results demonstrated effi—
ciency of the method and showed it Can find out the global optimization．rI1lis kind of method can not only help peo·
ple to undemtand MATLAB lan guage but also deepen cognition to simulated annealing process．Furthermore，the in·
telligence system Can be design by it．
Key Words：MATLAB；simulated ann ealing；optimization；traveling salesman problem
．
(Received November 1。2002)
待发表论文预报
DHTML技术的研究与应用
郭 秋 ，石 阳 ，李 游
(1．鞍山科技大学 计算机科学与工程学院，辽宁 鞍山 114044；2．鞍山科技大学 成人教育学院．辽宁 鞍山 ll404g)
摘 要：介绍了基于脚本语言JavaScript的Dynamic hyper text mark“p language(DHTML)的技术进行了分析，讨
论 了其特点及在未来的页面上的应用，阐述了活用这些页面技术来实现一些页面效果设置，并以创建新窗口
为例 模拟 Windows系统的部 分 实现 ．
有限元法计算开洞连续墙梁的内应力
何 晓慧 ．孟 达
(鞍山科技大学 土木与交通工程学院．辽宁 鞍山 11a044)
摘 要 ：对广泛应用的开洞连续墙粱，运用有限元方法，通过对比，分析了居中开洞、偏开洞和无洞口情况的
内力、应力分布以及变化规律，计算开洞口连续墙粱与托粱之间的相互作用力，及其 内部应力的分布情况，得
到 了与 实验 一致的结 果 ，为开洞 口墙 粱的设计提供 较精确 的理论依 据 ．
维普资讯 http://www.cqvip.com
浙公网安备 33021202002483