文档介绍：模拟退火算法和遗传算法
你现在浏览的是第一页，共78页
模拟退火算法及模型
算法的提出
模拟退火算法最早的思想由Metropolis等（1953）提出，1983年Kirkpatrick等将其应用于组合优化。
算法的目的
解决NP复杂性问题；
克服优化过程陷入局部极小；
克服初值依赖性。
物理退火过程
你现在浏览的是第二页，共78页
模拟退火算法及模型
物理退火过程
什么是退火：
退火是指将固体加热到足够高的温度，使分子呈随机排列状态，然后逐步降温使之冷却，最后分子以低能状态排列，达到某种稳定状态。
物理退火过程
你现在浏览的是第三页，共78页
模拟退火算法及模型
物理退火过程
加温过程——增强粒子的热运动，消除系统原先可能存在的非均匀态；
等温过程——对于与环境换热而温度不变的封闭系统，系统状态的自发变化总是朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡态；
冷却过程——使粒子热运动减弱并渐趋有序，系统能量逐渐下降，从而得到低能的晶体结构。
物理退火过程
你现在浏览的是第四页，共78页
模拟退火算法的基本原理
数学表述
在温度T，分子停留在状态r满足Boltzmann概率分布
物理退火过程
你现在浏览的是第五页，共78页
模拟退火算法的基本原理
数学表述
在同一个温度T，选定两个能量E1<E2，有
在同一个温度，分子停留在能量小的状态的概率比停留在能量大的状态的概率要大。
你现在浏览的是第六页，共78页
模拟退火算法的基本原理
数学表述
若|D|为状态空间D中状态的个数，D0是具有最低能量的状态集合：
当温度很高时，每个状态概率基本相同，接***均值1/|D|；
状态空间存在超过两个不同能量时，具有最低能量状态的概率超出平均值1/|D| ；
当温度趋于0时，分子停留在最低能量状态的概率趋于1。
你现在浏览的是第七页，共78页
模拟退火算法的基本原理
Metropolis准则（1953）——以概率接受新状态
若在温度T，当前状态i → 新状态j
若Ej<Ei，则接受 j 为当前状态；
否则，若概率 p=exp[-(Ej-Ei)/kBT] 大于[0,1)区间的随机数，则仍接受状态 j 为当前状态；若不成立则保留状态 i 为当前状态。
你现在浏览的是第八页，共78页
模拟退火算法的基本原理
模拟退火算法的基本思想
将一个优化问题比拟成一个金属物体，将优化问题的目标函数比拟成物体的能量，问题的解比拟成物体的状态，问题的最优解比拟成能量最低的状态，然后模拟金属物体的退火过程，从一个足够高的温度开始，逐渐降低温度，使物体分子从高能量状态缓慢的过渡到低能量状态，直至获得能量最小的理想状态为止，从而得到优化问题的全局最优解。
你现在浏览的是第九页，共78页
组合优化
你现在浏览的是第十页，共78页