模拟退火算法算法

模拟火算法（MATLAB实现）

实验用例：

用模拟退火算法解决如下10个城市的TSP问题，该问题最优解为691.2optf。

表1 10个城市的坐标

城市 X坐标 Y坐标 城市 X坐标 Y坐标 1 0.6683 0.2536 6 0.2293 0.7610 2 0.6195 0.2634 7 0.5171 0.9414

3 0.4000 0.4439 8 0.8732 0.6536 4 0.2439 0.1463 9 0.6878 0.5219

5 0.1707 0.2293 10 0.8488 0.3609

编程实现

用MATLAB实现模拟退火算法时，共编制了5个m文件，分别如下 1、swap.m

function [ newpath , position ] = swap( oldpath , number )

% 对 oldpath 进 行 互 换 操 作

% number 为 产 生 的 新 路 径 的 个 数 % position 为 对 应 newpath 互 换 的 位 置

m = length( oldpath ) ; % 城 市 的 个 数

newpath = zeros( number , m ) ;

position = sort( randi( m , number , 2 ) , 2 ); % 随 机 产 生 交 换 的 位 置

for i = 1 : number newpath( i , : ) = oldpath ;

% 交 换 路 径 中 选 中 的 城 市

newpath( i , position( i , 1 ) ) = oldpath( position( i , 2 ) ) ;

newpath( i , position( i , 2 ) ) = oldpath( position( i , 1 ) ) ;

end

2、pathfare.m

第７卷第４期　２００８年４月　软件导刊　Ｓｏｆｔｗａｒｅ　Ｇｕｉｄｅ　ＶＯ１．７　ＮＯ．４　Ａｐｒ．２００８　

模拟退火算法原理及改进　

李香平，张红阳　（中国地质大学计算机学院，湖北武汉４３００７４）　摘要：模拟退火算法是一种强大的随机搜索算法，能应用于许多前提信．￥－￣ｔｔ少的问题，能渐进地收敛于最优值。对　ＳＡ算法进行了介绍，论述了ＳＡ算法的原理并对算法进行了改进，展示了计算实验的结果。　关键词：模拟退火；全局优化　中图分类号：ＴＰ３１２　文献标识码：Ａ　文章编号：１６７２—７８００（２００８）０４—００４７—０２　

Ｏ　引言　近年来．传统的单一算法越来越不适应大规模非线性规划　问题。它们要求目标函数是可微的和收敛的。ＳＡ能很好地弥补　它们的缺陷。　从用于统计力学的Ｍｏｎｔｅ　Ｃａｒｌｏ方法上受到启发，ＳＡ算法在　１９８３被Ｋｉｒｋｐａｔｒｉｃｋ提出来。对比传统局部搜索算法，ＳＡ在搜索　时会在搜索空间上下移动而不依赖初始条件，擅长解决多维问　题。此外，它能处理任意程度的非线性、不连续和随机的问题。　能处理任意边界和约束的评估函数。因此，它能轻易处理有脊　背和高地的函数。只要初温高、退火表适当，它就能得到全局最　优。ＳＡ成功应用于组合优化、神经网络、图像处理和代码设计。　１模拟退火算法原理　组合优化问题是在给定的约束条件下，求目标函数的最值　的问题。设（．ｓ，．厂）是组合优化问题的一个实例，ｉ叫∈Ｓ若对所有　ｉ∈５，都７￣ｆ（ｉ　）　），则袱　）≤　）为ｍｉ　ｉ）的最优解。　ＳＡ来源于物理热力学原理．综合了固体退火与组合优化　之间的类似性。类似固体的复杂系统，先被加热到一个物质粒　子能自由移动的很高的温度，当它慢慢冷却时，它的能量减少。　如果“冷却”过程足够慢，系统将忽略局部稳定构造，到达能量　最低状态．即基态。　在模拟的每一步中。新解的产生按照Ｍｅｔｒｏｐｏｌｉｓ　ｔｒａｎｓｉｔｉｏｎ　法则．一个新的状态从现有的状态中产生。这个法则能以一定　的概率接受能量上升（即产生劣解）的新状态，而能量下降是优　化的总目的。法则如下所示：　ｆ１，　．　厂‘），）　（　）　ｐ（　（＿错）＇　ｈｅｒｗ／ｓｅ　俜系统能量，　是温度。　ＳＡ的一般框架：　Ｇｅｎｅｒａｔｅｄ　ｉｎｉｔｉａｌ　ｓｔａｔｅ　ａｔ　ｒａｎｄｏｍ；　Ｇｅｎｅｒａｔｅｄ　ｉｎｉｔｉａｌ　ｔｅｍｐｅｒａｔｕｒｅ；　ＲＥＰＥＡＴ　ＲＥＰＥＡＴ　－　Ｙ　ｇｅｎｅｒａｔｅ（，）；　ＩＦ　ａｃｃｅｐｔ（，Ｙ，）ＴＨＥＮ＝Ｙ　ＵＮＴＩＬ　ｉｎｎｅｒ　ｌｏｏｐ　ｓｔｏｐ　ｃｒｉｔｅｒｉｏｎ　ｓａｔｉｓｆｉｅｄ　为了提高ＳＡ的性能，我们应该仔细处理控制参数的协调。　（１）初始温度的选择。初始温度太高会花费高昂的计算时　间，太低会拒绝劣解的接受，会丢失ＳＡ全局优化的优点。本文　提出了一个初始温度的公式：　一　０　一ｌ　ｌｎｘ　口／是函数增量的平均值，ｘ是初始的接受概率。　（２）温度降低策略。温度降低越快，陷入局部的概率就越　大。然而，温度降低太慢会导致算法速度慢得不能接受。本文采　用了一种快速的非线性降低法：　。一　￡Ｏ　“一Ｔ　（３）适当的邻域结构。在退火期问，步长太小导致算法在探　索相位空间效率低，太大新解总被拒绝。在持续优化时。新的等　价值均一地按间距分布在以　的坐标为中心的邻域中，沿轴的　间距的一半被看作步长向量毒。当点落在　定义域内时，就随　机产生新解。　（４）终止标准。内循环是单一温度下在各种条件下Ｍａｒｃｏｖ　链的一种渐进接近全局最优的模拟实现，即循环Ｍａｒｃｏｖ链长次　数结束。外循环取某个温度ｔ作为算法终止标准，或者是迭代若　作者简介：李香平（１９７８－），男，湖北监利人，中国地质大学计算机学院硕士研究生，研究方向为科学研究与可视化；张红阳（１９８２～），男，湖北成宁　人，中国地质大学计算机学院硕士研究生，研究方向为数据挖掘与数据仓库。

解析模拟退火算法

一.爬山算法(Hill Climbing)

介绍模拟退火前，先介绍爬山算法。爬山算法是一种简单的贪心搜索算法，该算法每次从当前解的临近解空间中选择一个最优解作为当前解，直到达到一个局部最优解。

爬山算法实现很简单，其主要缺点是会陷入局部最优解，而不一定能搜索到全局最优解。如图1所示：假设C点为当前解，爬山算法搜索到A点这个局部最优解就会停止搜索，因为在A点无论向那个方向小幅度移动都不能得到更优的解。

二.模拟退火(SA,Simulated Annealing)思想

爬山法是完完全全的贪心法，每次都鼠目寸光的选择一个当前最优解，因此只能搜索到局部的最优值。模拟退火其实也是一种贪心算法，但是它的搜索过程引入了随机因素。模拟退火算法以一定的概率来接受一个比当前解要差的解，因此有可能会跳出这个局部的最优解，达到全局的最优解。以图1为例，模拟退火算法在搜索到局部最优解A后，会以一定的概率接受到E的移动。也许经过几次这样的不是局部最优的移动后会到达D点，于是就跳出了局部最大值A。

模拟退火算法描述： 若J(Y(i+1))>=J(Y(i))(即移动后得到更优解)，则总是接受该移动

若J(Y(i+1))

这里的“一定的概率”的计算参考了金属冶炼的退火过程，这也是模拟退火算法名称的由来。

根据热力学的原理，在温度为T时，出现能量差为dE的降温的概率为P(dE)，表示为：

P(dE)=exp(dE/(kT))

其中k是一个常数，exp表示自然指数，且dE<0。这条公式说白了就 是：温度越高，出现一次能量差为dE的降温的概率就越大；温度越低，则出现降温的概率就越小。又由于dE总是小于0（否则就不叫退火了），因此dE/kT < 0 ，所以P(dE)的函数取值范围是(0,1) 。

随着温度T的降低，P(dE)会逐渐降低。

我们将一次向较差解的移动看做一次温度跳变过程，我们以概率P(dE)来接受这样的移动。

[键入文字]

[键入文字]

模拟退火算法

摘要：本文采用一种模拟退火算法（SAA），通过对热力学中退火过程的模拟，寻找全局极小值，可望在较短时间里求得更优近似解。

关键词：退火；迭代;

引言

金属物体被加热到一定程度后，它的所有分子在状态空间自由运动，随着温度的逐渐下降，分子停留在不同状态，分子运动逐渐趋于有序，最后以一定的结构排列。这种由高温向低温逐渐降低温度的热处理过程就称为退火。退火是一种物理过程，在退火过程中系统的熵值不断减小，系统能量随温度的降低趋于最小值，也就是说，金属物体从高能状态转移到低能状态，变得较为柔韧。一个退火过程一般由三个部分组成。

1．加温过程 目的是怎强分子的热运动使其偏离平衡位置。

2. 等温过程 这个过程是为了保证系统在每一个温度下都达到平衡态。最终达到固体的基态。

3. 冷却过程 其目的是使分子的热运动减弱并渐趋于有序，系统能量逐渐下降，当温度降至结晶温度后，分子运动变成了围绕晶格点的微小振动，液体凝固成固体的晶态，从而得到低能的晶体结构。

这个过程可以用蒙特卡洛（MonteCarlo）的方法加以模拟，该方法虽然比较简单，但需要大量采样才能获得比较精准的结果，计算量大。鉴于物理系统倾向于能量较低的状态，而热运动又妨碍它准确落到最低状态的物理形态，采样时只需着重取那些有贡献作用的状态，则可较快达到较好的结果。

在SAA中，优化问题中的一个解及其目标函数分别可以看成物理退火中物体的一个状态和能量函数，而最优解就是最低能量的状态。而设定一个初始高温、基于Metropolis准则的搜索和控制温度参数t的下降分别相当于物理退火的加温、等温和冷却过程。下表就描述了一个算法问题的对应关系。

表1

算法问题 物理退火

解 状态

目标函数 能量函数

最优解 最低能量的状态

设定初始高温 加温过程

基于metropolis准则的搜索 等温过程

温度参数t的下降 冷却过程