智能算法及其应用2.3模拟退火算法

《智能算法及其应用2.3模拟退火算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第三章模拟退火算法智能优化计算西安建科大学信控学院2010年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外循环终止准则智能优化计算西安建科大学信控学院2010年3.4模拟退火算法的改进3.4.1模拟退火算法的优缺点3.4

2、.2改进内容3.4.3一种改进的模拟退火算法3.5模拟退火算法实现与应用30城市TSP问题（d*=423.741byDBFogel）智能优化计算西安建科大学信控学院2010年3.1模拟退火算法及模型智能优化计算西安建科大学信控学院2010年算法的提出模拟退火算法最早的思想由Metropolis等（1953）提出，1983年Kirkpatrick等将其应用于组合优化。算法的目的解决NP复杂性问题；克服优化过程陷入局部极小；克服初值依赖性。3.1.1物理退火过程3.1模拟退火算法及模型智能优化计算西安建科大学信控学院2010年物理退

3、火过程什么是退火：退火是指将固体加热到足够高的温度，使分子呈随机排列状态，然后逐步降温使之冷却，最后分子以低能状态排列，固体达到某种稳定状态。3.1.1物理退火过程3.1模拟退火算法及模型智能优化计算西安建科大学信控学院2010年物理退火过程加温过程——增强粒子的热运动，消除系统原先可能存在的非均匀态；等温过程——对于与环境换热而温度不变的封闭系统，系统状态的自发变化总是朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡态；冷却过程——使粒子热运动减弱并渐趋有序，系统能量逐渐下降，从而得到低能的晶体结构。3.1.1物理退火

4、过程3.1模拟退火算法及模型智能优化计算西安建科大学信控学院2010年数学表述在温度T，分子停留在状态r满足Boltzmann概率分布3.1.1物理退火过程3.1模拟退火算法及模型智能优化计算西安建科大学信控学院2010年数学表述在同一个温度T，选定两个能量E103.1模拟退火算法及模型智能优化计算西安建科大学信控学院2010年数学表述若

5、D

6、为状态空间D中状态的个数，D0是具有最低能量的状态集合：当温度很高时，每个状

7、态概率基本相同，接近平均值1/

8、D

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

10、D

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

12、法及模型智能优化计算西安建科大学信控学院2010年Metropolis准则（1953）——以概率接受新状态若在温度T，当前状态i→新状态j若Ej

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

14、sj)-C(s))/tk]}>=randrom[0,1]s=sj;Until抽样稳定准则满足；退温tk+1=update(tk)并令k=k+1；Until算法终止准则满足；输出算法搜索结果。3.1.3模拟退火算法的基本思想和步骤3.1模拟退火算法及模型智能优化计