作者简介：李香平（１９７８￣），男，湖北监利人，中国地质大学计算机学院硕士研究生，研究方向为科学研究与可视化；张红阳（１９８２￣），男，湖北咸宁
人
，中国地质大学计算机学院硕士研究生，研究方向为数据挖掘与数据仓库。
模拟退火算法原理及改进
李香平，张红阳
（中国地质大学计算机学院，湖北武汉４３００７４）
摘要：模拟退火算法是一种强大的随机搜索算法，能应用于许多前提信息很少的问题，能渐进地收敛于最优值。对
ＳＡ算法进行了介绍，论述了ＳＡ
算法的原理并对算法进行了改进，展示了计算实验的结果。
关键词
：模拟退火；全局优化
中图分类号：ＴＰ３１２文献标识码：Ａ文章编号：１６７２－７８００（２００８）
０４－００４７－０２
０
引言
近年来，传统的单一算法越来越不适应大规模非线性规划
问题。它们要求目标函数是可微的和收敛的。ＳＡ能很好地弥补
它们的缺陷。
从用于统计力学的
ＭｏｎｔｅＣａｒｌｏ方法上受到启发，ＳＡ
算法在
１９８３被Ｋｉｒｋｐａｔｒｉｃｋ提出来。对比传统局部搜索算法，ＳＡ
在搜索
时会在搜索空间上下移动而不依赖初始条件
，擅长解决多维问
题。此外，它能处理任意程度的非线性、不连续和随机的问题。
能处理任意边界和约束的评估函数。因此，它能轻易处理有脊
背和高地的函数。只要初温高、退火表适当
，它就能得到全局最
优。ＳＡ成功应用于组合优化、神经网络、图像处理和代码设计。
１
模拟退火算法原理
组合优化问题是在给定的约束条件下，求目标函数的最值
的问题。设
（Ｓ，ｆ）是组合优化问题的一个实例，ｉｏｐｔ∈Ｓ若对所有
ｉ∈Ｓ，都有ｆ（ｉｏｐｔ）≥ｆ（ｉ），则称ｆ（ｉｏｐｔ）≤ｆ（ｉ）为ｍｉｎｆ（ｉ
）的最优解。
ＳＡ
来源于物理热力学原理，综合了固体退火与组合优化
之间的类似性。类似固体的复杂系统
，先被加热到一个物质粒
子能自由移动的很高的温度，当它慢慢冷却时，它的能量减少。
如果“冷却”过程足够慢，系统将忽略局部稳定构造，到达能量
最低状态
，即基态。
在模拟的每一步中，新解的产生按照
Ｍｅｔｒｏｐｏｌｉｓｔｒａｎｓｉｔｉｏｎ
法则，一个新的状态从现有的状态中产生，这个法则能以一定
的概率接受能量上升
（即产生劣解）的新状态，而能量下降是优
化的总目的。法则如下所示：
ｐ（ｘ＝＞ｙ）＝
１，ｆ$%ｙ≤ｆ
$%
ｘ
ｅｘｐ－ｆ$%ｘｆ$%ｙ$%，ｏｔｈｅｒｗｉｓ&ｅ
ｆ
是系统能量，ｔ是温度。
ＳＡ
的一般框架：
Ｇｅｎｅｒａｔｅｄｉｎｉｔｉａｌｓｔａｔｅａｔｒａｎｄｏｍ；
Ｇｅｎｅｒａｔｅｄｉｎｉｔｉａｌｔｅｍｐｅｒａｔｕｒｅ；
ＲＥＰＥＡＴ
ＲＥＰＥＡＴ
ｙ＝ｇｅｎｅｒａｔｅ（，）；
ＩＦａｃｃｅｐｔ（，ｙ，）ＴＨＥＮ＝ｙ
ＵＮＴＩＬ＇ｉｎｎｅｒｌｏｏｐｓｔｏｐｃｒｉｔｅｒｉｏｎ＇ｓａｔｉｓｆｉｅｄ
为了提高ＳＡ的性能，我们应该仔细处理控制参数的协调。
（１）初始温度的选择。初始温度太高会花费高昂的计算时
间，太低会拒绝劣解的接受，会丢失ＳＡ全局优化的优点。本文
提出了一个初始温度的公式：
ｔ０＝
’
ｆ
＋
ｌｎｘ
－１
’
ｆ
＋
是函数增量的平均值，χ是初始的接受概率。
（２）温度降低策略。温度降低越快，陷入局部的概率就越
大。然而
，温度降低太慢会导致算法速度慢得不能接受。本文采
用了一种快速的非线性降低法：
ｔｋ＝ｔ０１＋ｋｋ＝１，２，３
，……
（３）适当的邻域结构。在退火期间，步长太小导致算法在探
索相位空间效率低
，太大新解总被拒绝。在持续优化时，新的等
价值均一地按间距分布在以ｘｉ的坐标为中心的邻域中，沿轴的
间距的一半被看作步长向量ξ。当点落在ｆ的定义域内时，就随
机产生新解。
（４）终止标准。内循环是单一温度下在各种条件下
Ｍａｒｃｏｖ
链的一种渐进接近全局最优的模拟实现，即循环Ｍａｒｃｏｖ链长次
数结束。外循环取某个温度
ｔ
作为算法终止标准，或者是迭代若
软件导刊
ＳｏｆｔｗａｒｅＧｕｉｄｅ第７卷第４期２００８年４月Ｖｏｌ．７Ｎｏ．４Ａｐｒ．２００８
２００８
年
软件导刊
ＩｍｐｒｏｖｅｍｅｎｔｏｆＳｉｍｕｌａｔｅｄＡｎｎｅａｌｉｎｇＡｌｇｏｒｉｔｈｍ
Ａｂｓｔｒａｃｔ：ｓｉｍｕｌａｔｅｄａｎｎｅａｌｉｎｇｉｓａｐｏｗｅｒｆｕｌｓｔｏｃｈａｓｔｉｃｓｅａｒｃｈａｌｇｏｒｉｔｈｍａｐｐｌｉｃａｂｌｅｔｏａｗｉｄｅｒａｎｇｅｏｆｐｒｏｂｌｅｍｓｆｏｒｗｈｉｃｈｌｉｔｔｌｅｐｒｉｏｒ
ｋｎｏｗｌｅｄｇｅｉｓａｖａｉｌａｂｌｅ，ａｎｄｉｔａｓｙｍｐｔｏｔｉｃａｌｌｙｐｒｏｂａｂｉｌｉｓｔｉｃａｌｌｙｃｏｎｖｅｒｓｅｔｏａｇｌｏｂａｌｏｐｔｉｍｕｍ．Ｉｎｔｈｅｐａｐｅｒ，ｉｔｗｉｌｌｇｉｖｅａｂｒｉｅｆｉｎｔｒｏｄｕｃｔｉｏｎｔｏ
ｓｉｍｕｌａｔｅｄａｎｎｅａｌｉｎｇａｎｄｉｔｓｉｍｐｒｏｖｅｍｅｎｔ，ｒｅｐｏｒｔｅｄｃｏｍｐｕｔａｔｉｏｎａｌｅｘｐｅｒｉｅｎｃｅ．Ｔｈｉｓｒｅｓｕｌｔｓｈｏｗｓｔｈａｔｔｈｅａｐｐｌｉｃａｔｉｏｎｏｆｓｉｍｕｌａｔｅｄａｎｎｅａｌｉｎｇ
ｔｏｃｏｍｐｕｔａｔｉｏｎｏｆｏｐｔｉｍｉｚａｔｉｏｎｐｒｏｂｌｅｍｓｉｓｅｎｃｏｕｒａｇｉｎｇａｎｄｉｔｄｅｓｅｒｖｅｓｆｕｒｔｈｅｒｒｅｓｅａｒｃｈ．
ＫｅｙＷｏｒｄｓ：ＳｉｍｕｌａｔｅｄＡｎｎｅａｌｉｎｇＡｌｇｏｒｉｔｈｍ；ｇｌｏｂａｌｏｐｔｉｍｕｍ
干连续的Ｍａｒｃｏｖ链后解的变化小于某个小数值结束，本文取第２种作为算法终止标注。２算法的改进及数值例子在ＳＡ算法中，搜索机制是很重要的部分。尽管先前的方法很容易实现，但它的效率较低。本文对此做出了一些改进，使用了一种更具有适应性的搜索方法：!ｘｋ＋１＝!ｋ＋１"!ｘｋ，ｆｘｋ＋"#１＜ｆｘ"$ｋ－!ｋ＋１"!ｘｋｏｔｈｅｒｗｉｓｅ%ξ是均匀分布在［０，１］区间的任意变量，!ｋ＋１是第ｋ＋１次循环的步长参数。!ｘｋ是第ｋ次循环时的增量。本文以如下优化为例测试改进后的ＳＡ算法的性能：ｍｉｎｆ（ｘ）＝ｓｉｎｘｙ＋ｘ２＋ｙ２，－１００≤ｘ，ｙ≤１００（全局最优点是（０，０））冷却进度表取为：ｔ０＝５０，Ｌｋ＝５００，ｔｐ＝０．０００００５，α＝０．９５。初始解取（１００，１００），（２０，－２０），（０．５，－０．５），迭代结果如表１所示。由表１可知，在任意的初值下，经过一定次数的迭代后，结果非常接近，都能找到最优解，最初解与结果关系不大，好的初
值并非肯定有好的结果，充分表明ＳＡ算法对初值不敏感。
３
结束语
ＳＡ
是一种强大的随机搜索算法，具有对初始点的不依赖
性
，可以任意选取初始解和随机序列，应用广泛。ＳＡ普及的最
重要的原因是能在复杂的情况下产生更高质量的解，因此，它
特别适用于非线性和复杂的系统。在多目标优化领域，ＳＡ还处
于起步阶段
，在种群选择以及如何与Ｐａｒｅｔｏ前沿结合等方面，还
需要进一步地研究，ＳＡ具有广阔的发展前景。
参考文献：
［１］
ＬＩＨＵＡＷＵａｎｄＹＵＹＵＮＷＡＮＧ．ＡｎＩｎｔｒｏｄｕｃｔｉｏｎｔｏＳｉｍｕｌａｔｅｄ
ＡｎｎｅａｌｉｎｇＡｌｇｏｒｉｔｈｍｓｆｏｒｔｈｅＣｏｍｐｕｔａｔｉｏｎｏｆＥｃｏｎｏｍｉｃＥｑｕｉｌｉｂｒｉ－
ｕｍ．ＩｎｓｔｉｔｕｔｅｏｆＳｙｓｙｅｍＳｃｉｅｎｃｅ，ＡｃａｄｅｍｉａＳｉｎｉｃａ，Ｂｅｉｊｉｎｇ１０００８０
，
Ｐ．Ｒｃｈｉｎａ，１９９７
［２］ＤＳＪｏｈｎｓｏｎ，ＣＲＡｒａｇｏｎ，
ＬＡＭｃＧｅｏｃｈ．ＣＳｃｈｅｖｏｎ．Ｏｐｔｉｍｉｚａ－
ｔｉｏｎｂｙｓｉｍｕｌａｔｅｄａｎｎｅａｌｉｎｇ：ａｎｅｘｐｅｒｉｍｅｎｔａｌｅｖａｌｕａｔｉｏｎ，Ｐａｒｔ１
，
ＡＴ＆ＴｂｅｌｌＬａｂｏｒａｔｏｒｉｅｓ，ＭｕｒｒａｙＨｉｌｌ（ＮＪ），１９９９．
［３］ＰＪＭＶａｎｌａａｒｈｏｖｅｎ，
ＥＨＬＡａｒｔｓ．ｓｉｍｕｌａｔｅｄａｎｎｅｎｌｉｎｇ：ｔｈｅｏｒｙ
ａｎｄａｐｐｌｉｃａｔｉｏｎｓ
，ＤＲｅｉｄｅｌ，
１９８７．
（责任编辑：杜能钢）
初值（ｘ０，ｙ０）（１００．０，１００．０）（２０．０，－２０．０）（０．５，－０．５）
求解结果（ｘ，ｙ）
函数值ｆ（ｘ，ｙ）
（０．００００１１，０．００００１４）０．０００００００００２（０．０００００４，０．００００１２）０．０００００００００１３（０．０００００８，０．００００１５）
０．０００００００００１５
表１不同初值下的模拟退火算法求解的结果
４８
・・