文档介绍：关于模拟退火算法
第1页，此课件共31页哦
一、模拟退火算法的基本思想
启发
注意到一个自然规则：物质总是趋于最低的能态。
水总是向低处流。
电子总是向最低能级的轨道排布。
最低能态是最稳定的状态。物质会”自动”地趋向的最低能关于模拟退火算法
第1页，此课件共31页哦
一、模拟退火算法的基本思想
启发
注意到一个自然规则：物质总是趋于最低的能态。
水总是向低处流。
电子总是向最低能级的轨道排布。
最低能态是最稳定的状态。物质会”自动”地趋向的最低能态。
第2页，此课件共31页哦
模拟退火算法的设计与原理 猜想
物质自动趋向的最低能态与函数最小值之间有相似性！！！
我们能不能设计一种算法求函数最小值，就像物质”自动”地趋向最低能态？
降温图像
离散函数图像
相似性?
最小值
最低能态
第3页，此课件共31页哦
模拟退火算法的设计与原理 物理模型——固体退火
退火俗称固体降温
先把固体加热至足够高温，使固体中所有粒子处于无序的状态（最高的熵值），然后将温度缓慢下降，粒子渐渐有序（熵值下降），这样只要温度上升得足够高，冷却过程足够慢，则所有粒子最终会处于最低能态（最低的熵值）。
最低能态
时间
温度
第4页，此课件共31页哦
Metropolis准则（1953）——以概率接受新状态
p=exp[-(Ej-Ei)/kBT]
在高温下，可接受与当前状态能量差较大的新状态；
在低温下，只接受与当前状态能量差较小的新状态。
第6页，此课件共31页哦
模拟退火算法的设计与原理提出
模拟退火算法(SA) 就是这样一个将退火过程中系统熵值类比为目标函数值F，来模拟这个退火系统的算法。
第7页，此课件共31页哦
二、模拟退火算法的实现
SA 算法在Markov 链长度内持续进行“产生新解—判断—接受/舍弃”的迭代过程，对应着固体在某一恒定温度下趋于热平衡的过程。算法终止时的当前解即为所得近似最优解。
这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。
第10页，此课件共31页哦
相似性比较
优化问题
金属物体
解
粒子状态
最优解
能量最低的状态
设定初温
熔解过程
Metropolis抽样过程
等温过程
控制参数的下降
冷却
目标函数
能量
组合优化与物理退火的相似性
第12页，此课件共31页哦
模拟退火算法的优化 回火技术
如图所示，若粒子开始处于D状态，若让能量逐渐减小，则粒子最终到达的是A 点(局部最低点)而不是B(全局最低点)点，这是我们所不希望的。
解决的办法是对系统经常地”摇动”一下，就很可能把粒子从D点越过C点摇到B 点，而把它摇到A点的可能性减小。
这就是回火技术：降温后以一定概率升温，引入产生函数扰动因子，来控制搜寻全局最优值的范围。
A
B
C
D
第16页，此课件共31页哦
模拟退火算法的应用前景 算法特性
优点
可并行性
扩展性和通用性 它可以高效的解决几乎所有的组合优化问题。
高效率，高性价比
逼近速度快，可极快的求得很好的近似值
SA算法比传统算法速度快的多了，解也以1的概率趋于最优解。在解的质量与时间的比上效果良好。 传统算法要运行几年的情况，SA只需几秒。
具有全局优化特性
第18页，此课件共31页哦
三、模拟退火算法的应用
30城市TSP问题（d*= 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
第19页，此课件共31页哦
算法流程
第20页，此课件共31页哦
初始温度的计算
for i=1:100
route=randperm(CityNum);
fval0(i)=CalDist(dislist,route);
end
t0=-(max(fval0)-min(fval0))/log();
三、模拟退火算法的实现与应用
30城市TSP问题（d*= by D B Fogel）
第21页，此课件共31页哦
状态产生函数的设计