文档介绍：模拟退火算法算法
你现在浏览的是第一页，共114页
二页，共114页
1 模拟退火算法概述
固体退火过程
加温过程——增强粒子的热运动，使其偏离平衡位置，目的是消除系统原先可能存在的非均匀态；
等温过程——退火过程中要让温度慢慢降低，在每一个温度下要达到热平衡状态，对于与环境换热而温度不变的封闭系统满足自由能较少定律，系统状态的自发变化总是朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡态；
冷却过程——使粒子热运动减弱并渐趋有序，系统能量逐渐下降，从而得到低能的晶体结构。当液体凝固为固体的晶态时退火过程完成。
固体退火过程
你现在浏览的是第十三页，共114页
1 模拟退火算法概述
数学表述
在温度T，分子停留在状态r满足Boltzmann概率分布
温度低时能量低的微观状态概率大，温度趋于零时，
固体几乎处于概率最大能量最小的基态。
固体退火过程
你现在浏览的是第十四页，共114页
1 模拟退火算法概述
数学表述
在同一个温度T，选定两个能量E1<E2，有
在同一个温度，分子停留在能量小的状态的概率比停留在能量大的状态的概率要大。
固体退火过程
<1
>0
你现在浏览的是第十五页，共114页
1 模拟退火算法概述
数学表述
若|D|为状态空间D中状态的个数，D0是具有最低能量的状态集合：
(1) 当温度很高时，每个状态概率基本相同，接***均值1/|D|；
(2) 状态空间存在超过两个不同能量时，具有最低能量状态的概率超出平均值1/|D| ；
(3) 当温度趋于0时，分子停留在最低能量状态的概率趋于1。
固体退火过程
能量最低状态
非能量最低状态
你现在浏览的是第十六页，共114页
1 模拟退火算法概述
Metropolis准则（1953）——以概率接受新状态
固体在恒定温度下达到热平衡的过程可以用Monte Carlo方法（计算机随机模拟方法）加以模拟，虽然该方法简单，但必须大量采样才能得到比较精确的结果，计算量很大。
Metropolis准则
你现在浏览的是第十七页，共114页
Monte Carlo模拟退火过程
蒙特卡罗(Monte Carlo)方法，或称计算机随机模拟方法，是一种基于“随机数”的计算方法。这一方法源于美国在第一次世界大战中研制***的“曼哈顿计划”。该计划的主持人之一、数学家冯·诺伊曼用驰名世界的赌城—摩纳哥的Monte Carlo—来命名这种方法，为它蒙上了一层神秘色彩。
你现在浏览的是第十八页，共114页
Monte Carlo方法
Monte Carlo方法的基本思想很早以前就被人们所发现和利用。
早在17世纪，人们就知道用事件发生的“频率”来决定事件的“概率”。
Buffon试验：19世纪人们用投针试验的方法来求解圆周率π。
本世纪40年代电子计算机的出现，特别是近年来高速电子计算机的出现，使得用数学方法在计算机上大量、快速地模拟这样的试验成为可能。
你现在浏览的是第十九页，共114页
Monte Carlo方法
用民意测验来作一个不严格的比喻。民意测验的人不是征询每一个登记选民的意见，而是通过对选民进行小规模的抽样调查来确定可能的优胜者。其基本思想是一样的。
它需要一个良好的随机数源。这种方法往往包含一些误差，但是随着随机抽取样本数量的增加，结果也会越来越精确。
你现在浏览的是第二十页，共114页
1 模拟退火算法概述
Metropolis准则（1953）——以概率接受新状态
若在温度T，当前状态i → 新状态j
若Ej<Ei，则接受 j 为当前状态；
否则，若概率 p=exp[-(Ej-Ei)/kBT] 大于[0,1)区间的随机数，则仍接受状态 j 为当前状态；若不成立则保留状态 i 为当前状态。
Metropolis准则
你现在浏览的是第二十一页，共114页
1953年提出重要性采样法----以概率接受新状态.
设固体的初态为 ，其状态能量为 ，然后用一扰动装置随机选取某个微粒的微小变化，得到一新状态 ，其能量为 : (1) 当 ，则该新状态 为“重要状态”，并接受它；(2)当