大学物理学-计算物理-模拟退火.

1、计算物理学模拟退火概论n模拟退火算法是物理学当中的重要应用。n主要应用于光学领域n主要讲模拟退火，顺带先讲一下“散射光角分散射光角分布布”反演微粒粒径分布。根据吸收定律 称为光学厚度 ，反应了被测颗粒物的消光能力。取值范围：0-无穷大。称为消光截面。反应了的消光能力。可以由Mie散射理论计算获得。rQ, )2()(),(maxmindrrnrQrr ) 1 (expioII rn 真实分布 分50等分离散后n如果分成50分，那么可以这样处理： 0.1-0.2um的微粒用0.1um近似代替 0.2-0.3um的微粒用0.2um近似代替 。 ) 3(),(1iKiinrQ drrnrQrr)(),

2、(maxmin 那么：变为了个区间是一个常量，例如，第近似认为，每一个子区间个分为若干子区间将半径区间,)(,maxmininrnirnKrr变为了n问题转化为了解矩阵：但该矩阵严重病态，普通方法得到的结果可能不可靠，需要选一种合适的方法。 KKSSSKKSnnnrQrQrQrQrQrQrQrQrQ2121222121211121, KKSSSKKSnnnrPrPrPrPrPrPrPrPrPFFF2121222121211121, drrnrPFrr)(),(maxmin模拟退火算法n全局随机搜索n局部搜索n模拟退火算法 模拟退火算法模拟退火算法(Simulated Annealing Alg

3、orithm, SAA)是一种适合解决大规模组合优化问题，特别是是一种适合解决大规模组合优化问题，特别是NP完全类问题的通用有效近似算法。模拟退火算法完全类问题的通用有效近似算法。模拟退火算法的特点可概括为：高效、稳健、通用、灵活。与局部的特点可概括为：高效、稳健、通用、灵活。与局部搜索算法相比，模拟退火算法可望在较短时间里求得搜索算法相比，模拟退火算法可望在较短时间里求得更优近似解。模拟退火算法与遗传算法一样，采用随更优近似解。模拟退火算法与遗传算法一样，采用随机的初始解为起点，因此大大降低了求解组合优化问机的初始解为起点，因此大大降低了求解组合优化问题的前期工作量。模拟退火算法的解和题的前

4、期工作量。模拟退火算法的解和CPU时间均随时间均随问题规模的增大而趋于稳定，且不受初始解和随机数问题规模的增大而趋于稳定，且不受初始解和随机数序列的影响，其性能不因问题的不同而蜕变。序列的影响，其性能不因问题的不同而蜕变。模拟退火算法（起源）物理退火原理n物理退火过程物理退火过程 什么是退火：什么是退火： 退火是指将固体加热到足够高的温度，使分子呈随机退火是指将固体加热到足够高的温度，使分子呈随机排列状态，然后逐步降温使之冷却，最后分子以低能排列状态，然后逐步降温使之冷却，最后分子以低能状态排列，固体达到某种稳定状态。状态排列，固体达到某种稳定状态。 n物理退火过程物理退火过程 加温过程加温过

5、程增强粒子的热运动，消除系统原先可能增强粒子的热运动，消除系统原先可能存在的非均匀态；存在的非均匀态； 等温过程等温过程对于与环境换热而温度不变的封闭系统，对于与环境换热而温度不变的封闭系统，系统状态的自发变化总是朝自由能减少的方向进行，系统状态的自发变化总是朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡态；当自由能达到最小时，系统达到平衡态； 冷却过程冷却过程使粒子热运动减弱并渐趋有序，系统能使粒子热运动减弱并渐趋有序，系统能量逐渐下降，从而得到低能的晶体结构。量逐渐下降，从而得到低能的晶体结构。模拟退火算法起源n物理退火过程：q加温过程q等温过程q冷却（退火）过程n等温下热平衡过

6、程可用Monte Carlo方法模拟，计算量大。n1953年，Metropolis提出重要性采样法，即以概率接受新状态，称Metropolis准则，计算量相对Monte Carlo方法显著减少。n1983年，Kirkpatrick等提出模拟退火算法，并将其应用于组合优化问题的求解。模拟退火算法与物理退火过程的相似关系模拟退火物理退火解粒子状态最优解能量最低态设定初温熔解过程Metropolis采样过程 等温过程控制参数的下降冷却目标函数能量模拟退火一般过程n1，设置一个较高温度T，降温速度S，终止温度。n2，给出解的初始值P1，计算该初始值的适应度值f1n3，令T=T*S，得到一个新的较低温度

7、T，此时给P1一个微扰，得到P2，计算出P2所对应的适应度值f2n4，如果f2优于f1，则无条件接收P2为新的解；如果f2f1，则按照。这个概率可以是类似于如下的形式： exp-(1/ T)n重复3,4步，当温度降到足够低的时候，有希望获得全局优化解。n注意，要求随着温度降低，接收恶化解的概率越来越小，最后趋近于0。n不难看出，实际上所谓模拟退火算法，其实就是在局部搜索的基础之上加入了一个安一定的概率接收恶化解。n局部搜索一般过程： 1，给出解的初始值P1，计算该初始值的适应度值f1 2，给P1一个微扰，得到P2，计算出P2所对应的适应度值f2 3，如果f2优于f1，则无条件接收P2为新的解；如果f2劣于f1，则无条件放弃P2，当前解依然是P1。 重复2,3步。 那么为什么通过一定的概率接收恶化解，可以进一步逼近全局最优解？很简单，因为在恶化解所在的那个局部可能存在好的解。n模拟退火的直观理解：在一定程度上接收恶化解是SA具有全局搜索能力的一个主要原因。n当x=？，y最大？n全局随机搜索： 随机给出若干组解，计算这些解的适应度值，取适应度最好的那组解。n下面看看，全局随机搜索，局部搜索和模拟退火的算法在30个城市的货郎担问题中的应用。n货郎担问题： N个城市，走遍所有城