给给给给给给给给
给 给 给 给 给 给 给 给 给 给 给 给 给 给 给 给 k=0
算法流程
tk+1=update(tk)
Y
给 k=k+1
Y
给给给给给给给给给给
N
Metropolis给 给 给 给 给 给 给 给 给 给
N
给 给 给 给 给 Si给 给 给 给 给 Sj
给 给 给 给 给 给 给 s*
N
给给给给给给 给给
给给 min{1,exp[-(C(sj)-C(si))/tk]}
>=random[0,1]
Y
给 Si给 Sj， 给 给 给 给 给 给 给 给 s*
三、模拟退火算法的实现与应用 3.1 30城市TSP问题（d*=423.741 by D B Fogel）
初始温度的计算
for i=1:100 route=randperm(CityNum); fval0(i)=CalDist(dislist,route);
解决的办法是对系统经常地”摇 动”一下，就很可能把粒子从D 点越过C点摇到B 点，而把它摇 到A点的可能性减小。
这就是回火技术：降温后以一 定概率升温，引入产生函数扰 动因子，来控制搜寻全局最优 值的范围。
C D A
B
模拟退火算法的应用前景
算法特性
优点
1. 可并行性 2. 扩展性和通用性
它可以高效的解决几乎所有的组合优化问题。
这是基于蒙特卡罗迭代求解法的一种启发 式随机搜索过程。
组合优化与物理退火的相似性
相似性比较
优化问题 解
最优解 设定初温 Metropolis抽样过程 控制参数的下降 目标函数
金属物体 粒子状态
能量最低的状态 熔解过程 等温过程 冷却 能量
模拟退火算法的优化 回火技术
如图所示，若粒子开始处于D状 态，若让能量逐渐减小，则粒 子最终到达的是A 点(局部最低 点)而不是B(全局最低点)点，这 是我们所不希望的。
第三篇 模拟退火算法
一、模拟退火算法的基本思想 二、模拟退火算法的实现 三、模拟退火算法的应用
一、模拟退火算法的基本思想
启发 注意到一个自然规则：物质总是趋于最低 的能态。
水总是向低处流。 电子总是向最低能级的轨道排布。
最低能态是最稳定的状态。物质会”自动” 地趋向的最低能态。
模拟退火算法的设计与原理 猜想
三、模拟退火算法的应用
3.1 30城市TSP问题（d*=423.741 by D B Fogel） 运行过程
三、模拟退火算法的应用 3.1 30城市TSP问题（d*=423.741 by D B Fogel） 运行过程
三、模拟退火算法的应用 3.1 30城市TSP问题（d*=423.741 by D B Fogel） 运行过程
TSP Benchmark 问题 41 94;37 84;54 67;25 62; 7 64;2 99;68 58;71 44;54 62;83 69;64 60;18 54;22 60;83 46;91 38;25 38;24 42;58 69;71 71;74 78;87 76;18 40;13 40;82 7;62 32; 58 35;45 21;41 26;44 35;4 50
3. 高效率，高性价比
1. 逼近速度快，可极快的求得很好的近似值 2. SA算法比传统算法速度快的多了，解也以1的概率趋
于最优解。在解的质量与时间的比上效果良好。 传统算法要运行几年的情况，SA只需几秒。 3. 具有全局优化特性
三、模拟退火算法的应用
3.1 30城市TSP问题（d*=423.741 by D B Fogel）
end t0=-(max(fval0)-min(fval0))/log(0.9);
三、模拟退火算法的应用 3.1 30城市TSP问题（d*=423.741 by D B Fogel）
状态产生函数的设计
（1）互换操作，随机交换两个城市的顺序；
283591467
281593467
（2）逆序操作，两个随机位置间的城市逆序；
使固体中所有粒子处于无
序的状态（最高的熵值），
15
然后将温度缓慢下降，粒
子渐渐有序（熵值下降）， 温度 10
最低能态
这样只要温度上升得足够
T(t)
高，冷却过程足够慢，则
5
所有粒子最终会处于最低
能态（最低的熵值）。
0
0
10
20
30
时间 t
Metropolis准则（1953）——以概率接受新状态
p=exp[-(Ej-Ei)/kBT] 在高温下，可接受与当前状态能量差较大的新状态； 在低温下，只接受与当前状态能量差较小的新状态。
小结
模拟退火： 模仿自然界的物理行为，来求 解函数最小值的方法
小结
创意独特 摒弃旧思维----从函数性质分析 创造新思维----从自然规律入手 个人认为这个创意是独特的，独辟蹊径。 向自然学习，利用了物理的理论来解决数学问题。 效率高 虽不是最优解，但其优性较速度来说，效率是极 高的。
时间就是金钱。在现代市场中这很重要。
三、模拟退火算法的应用
3.1 30城市TSP问题（d*=423.741 by D B Fogel） 运行过程
三、模拟退火算法的应用 3.1 30城市TSP问题（d*=423.741 by D B Fogel） 运行过程
三、模拟退火算法的应用 3.1 30城市TSP问题（d*=423.741 by D B Fogel） 运行结果
最低能态
相似性?
最小值
降温图像
离散函数图像
物质自动趋向的最低能态与函数最小值之间有相 似性！！！
我们能不能设计一种算法求函数最小值，就 像物质”自动”地趋向最低能态？
模拟退火算法的设计与原理
物理模型——固体退火
退火俗称固体降温
t0 7 a 0.187 H 5
先把固体加热至足够高温， T(t) H (t0 H)e a(tt0)
283591467
283419567
（3）插入操作，随机选择某点插入某随机位置。
283591467
235981467
三、模拟退火算法பைடு நூலகம்应用 3.1 30城市TSP问题（d*=423.741 by D B Fogel）
参数设定
截止温度 tf=0.01; 退温系数 alpha=0.90; 内循环次数 L=200*CityNum;
模拟退火算法的设计与原理提出
模拟退火算法(SA) 就是这样一个将退 火过程中系统熵值类比为目标函数值F， 来模拟这个退火系统的算法。
二、模拟退火算法的实现
SA 算法在Markov 链长度内持续进行“产 生新解—判断—接受/舍弃”的迭代过程， 对应着固体在某一恒定温度下趋于热平衡 的过程。算法终止时的当前解即为所得近 似最优解。