最新模拟退火算法详解PPT课件.ppt

《最新模拟退火算法详解PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、模拟退火算法详解3.1模拟退火算法及模型3.1.1物理退火过程3.1.2组合优化与物理退火的相似性3.1.3模拟退火算法的基本思想和步骤3.2模拟退火算法的马氏链描述3.2.1马尔可夫链3.2.2模拟退火算法与马尔可夫链3.3模拟退火算法的关键参数和操作的设计3.3.1状态产生函数3.3.2状态接受函数3.3.3初温3.3.4温度更新函数3.3.5内循环终止准则3.3.6外循环终止准则现代优化计算3.4模拟退火算法的改进3.4.1模拟退火算法的优缺点3.4.2改进内容3.4.3一种改进的模拟退火算法3.5模拟退火算法实现与应

2、用3.5.130城市TSP问题（d*=423.741byDBFogel）3.5.2模拟退火算法在管壳式换热器优化设计中的应用现代优化计算热力学中的退火现象指物体逐渐降温时发生的物理現象：温度越低，物体的能量状态越低，到达足够的低点时，液体开始冷凝与结晶，在结晶状态时，系统的能量状态最低。缓慢降温（退火，annealing）时，可达到最低能量状态；但如果快速降温（淬火，quenching），会导致不是最低能态的非晶形。大自然知道慢工出细活：缓缓降温，使得物体分子在每一温度时，能够有足够时间找到安顿位置，则逐渐地，到最后可得到最

3、低能态，系统最稳定。3.1模拟退火算法及模型3.1.1物理退火过程现代优化计算模仿自然界退火現象而得，利用了物理中固体物质的退火过程与一般优化问题的相似性从某一初始温度开始，伴随温度的不断下降，结合概率突跳特性在解空间中随机寻找全局最优解3.1模拟退火算法及模型3.1.1物理退火过程现代优化计算3.1模拟退火算法及模型现代优化计算数学表述在温度T，分子停留在状态r满足Boltzmann概率分布3.1.1物理退火过程3.1模拟退火算法及模型现代优化计算数学表述在同一个温度T，选定两个能量E1

4、>0模拟退火算法基本思想：在一定温度下，搜索从一个状态随机地变化到另一个状态；随着温度的不断下降直到最低温度，搜索过程以概率1停留在最优解3.1模拟退火算法及模型3.1.1物理退火过程现代优化计算Boltzman概率分布告诉我们：（1）在同一个温度，分子停留在能量小状态的概率大于停留在能量大状态的概率（2）温度越高，不同能量状态对应的概率相差越小；温度足够高时，各状态对应概率基本相同。（3）随着温度的下降，能量最低状态对应概率越来越大；温度趋于0时，其状态趋于13.1模拟退火算法及模型现代优化计算数学表述若

5、D

6、为状态空间D

7、中状态的个数，D0是具有最低能量的状态集合：当温度很高时，每个状态概率基本相同，接近平均值1/

8、D

9、；状态空间存在超过两个不同能量时，具有最低能量状态的概率超出平均值1/

10、D

11、；当温度趋于0时，分子停留在最低能量状态的概率趋于1。3.1.1物理退火过程能量最低状态非能量最低状态3.1模拟退火算法及模型现代优化计算Metropolis准则（1953）——以概率接受新状态固体在恒定温度下达到热平衡的过程可以用MonteCarlo方法（计算机随机模拟方法）加以模拟，虽然该方法简单，但必须大量采样才能得到比较精确的结果，计算量很大。

12、3.1.1物理退火过程3.1模拟退火算法及模型现代优化计算Metropolis准则（1953）——以概率接受新状态若在温度T，当前状态i→新状态j若Ej

13、与当前状态能量差较小的新状态。3.1.1物理退火过程3.1模拟退火算法及模型现代优化计算相似性比较3.1.2组合优化与物理退火的相似性组合优化问题金属物体解粒子状态最优解能量最低的状态设定初温熔解过程Metropolis抽样过程等温过程控制参数的下降冷却目标函数能量3.1模拟退火算法及模型现代优化计算基本步骤给定初温t=t0，随机产生初始状态s=s0，令k=0；RepeatRepeat产生新状态sj=Genete(s)；ifmin{1,exp[-(C(sj)-C(s))/tk]}>=randrom[0,1]s=sj;Unti

14、l抽样稳定准则满足；退温tk+1=update(tk)并令k=k+1；Until算法终止准则满足；输出算法搜索结果。3.1.3模拟退火算法的基本思想和步骤3.1模拟退火算法及模型现代优化计算影响优化结果的主要因素给定初温t=t0，随机产生初始状态s=s0，令k=0；RepeatRepeat