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