《数学建模模拟退火算法PPT课件》由会员分享，可在线阅读，更多相关《数学建模模拟退火算法PPT课件（11页珍藏版）》请在金锄头文库上搜索。
1、数学建模模拟退火算法PPT课件 数学建模模拟退火算法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模拟退火算法实现与应用3.5.130城市TSP
2、问题（d*=423.741by DB Fogel）3.5.2模拟退火算法在管壳式换热器优化设计中的应用智能优化计算浙江大学3.1模拟退火算法及模型智能优化计算浙江大学?算法的提出模拟退火算法最早的思想由Metropolis等 （1953）提出，1983年Kirkpatrick等将其应用于组合优化。 ?算法的目的解决NP复杂性问题；克服优化过程陷入局部极小；克服初值依赖性。 3.1.1物理退火过程3.1模拟退火算法及模型智能优化计算浙江大学?物理退火过程什么是退火退火是指将固体加热到足够高的温度，使分子呈随机排列状态，然后逐步降温使之冷却，最后分子以低能状态排列，固体达到某种稳定状态。 3.1.
3、1物理退火过程3.1模拟退火算法及模型智能优化计算浙江大学?物理退火过程加温过程增强粒子的热运动，消除系统原先可能存在的非均匀态；等温过程对于与环境换热而温度不变的封闭系统，系统状态的自发变化总是朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡态；冷却过程使粒子热运动减弱并渐趋有序，系统能量逐渐下降，从而得到低能的晶体结构。 3.1.1物理退火过程3.1模拟退火算法及模型智能优化计算浙江大学?数学表述在温度T，分子停留在状态r满足Boltzmann概率分布布3.1.1物理退火过程?D sBBBTks ETZT Zkr rE ETkr ETZr EE P)(exp)()(Boltzman
4、n0)()(exp) (1)(子为概率分布的标准化因常数。 为的能量，表示状态机变量，表示分子能量的一个随3.1模拟退火算法及模型智能优化计算浙江大学?数学表述在在同一个温度T，选定两个能量E1 3.1.1物理退火过程?T kEET kETZE EP EE PB B12121exp1exp)(103.1模拟退火算法及模型智能优化计算浙江大学?数学表述若若|D|为状态空间D中状态的个数，D0是具有最低能量的状态集合当温度很高时，每个状态概率基本相同，接近平均值值1/|D|；状态空间存在超过两个不同能量时，具有最低能量状态的概率超出平均值1/|D|；当温度趋于0时，分子停留在最低能量状态的概率趋于
5、1。 3.1.1物理退火过程能量最低状态非能量最低状态3.1模拟退火算法及模型智能优化计算浙江大学?Metropolis准则 （1953）以概率接受新状态固体在恒定温度下达到热平衡的过程可以用Monte Carlo方法（计算机随机模拟方法）加以模拟，虽然该方法简单，但必须大量采样才能得到比较精确的结果，计算量很大。 3.1.1物理退火过程3.1模拟退火算法及模型智能优化计算浙江大学?Metropolis准则 （1953）以概率接受新状态若在温度T，当前状态i新状态j若E j 3.1.1物理退火过程01-(Ej-Ei)/kTp3.1模拟退火算法及模型智能优化计算浙江大学?Metropolis准则
6、 （1953）以概率接受新状态p=exp-(E j-E i)/k BT在高温下，可接受与当前状态能量差较大的新状态；在低温下，只接受与当前状态能量差较小的新状态。 3.1.1物理退火过程3.1模拟退火算法及模型智能优化计算浙江大学?相似性比较3.1.2组合优化与物理退火的相似性3.1模拟退火算法及模型智能优化计算浙江大学?基本步骤给定初温t=t0，随机产生初始状态s=s0，令k=0；Repeat Repeat产生新状态s j=Gee(s)；if min1,exp-(C(s j)-C(s)/t k=randrom0,1s=s j;Until抽样稳定准则满足；退温t k+1=update(t k)
7、并令k=k+1；Until算法终止准则满足；输出算法搜索结果。 3.1.3模拟退火算法的基本思想和步骤3.1模拟退火算法及模型智能优化计算浙江大学?影响优化结果的主要因素给定初温t=t0，随机产生初始状态s=s0，令k=0；Repeat Repeat产生新状态s j=Gee(s)；if min1,exp-(C(s j)-C(s)/t k=randrom0,1s=s j;Until抽样稳定准则满足；退温t k+1=update(t k)并令k=k+1；Until算法终止准则满足；输出算法搜索结果。 3.1.3模拟退火算法的基本思想和步骤三函数两准则初始温度3.2模拟退火算法的马氏链描述智能优化计
8、算浙江大学?定义3.2.1马尔科夫链)1()(Pr)1(,)1(,)0()(Pr)()(,1021i n X j n Xi n Xi Xi X j nXZ nk Xkk Xss?，满足称为马尔可夫链，若随机序列时刻状态变量的取值。 为间，为所有状态构成的解空令3.2模拟退火算法的马氏链描述智能优化计算浙江大学?定义一步转移概率n步转移概率若解空间有限，称马尔可夫链为有限状态；若，称马尔可夫链为时齐的。 3.2.1马尔科夫链)1()(Pr)1(,inXjnXn pji?)1()(,?n pn pZ nji ji)0()(Pr)(,i XjnX pnji?3.2模拟退火算法的马氏链描述智能优化计算
9、浙江大学?模拟退火算法对应了一个马尔可夫链模拟退火算法新状态接受概率仅依赖于新状态和当前状态，并由温度加以控制。 若固定每一温度，算法均计算马氏链的变化直至平稳分布，然后下降温度，则称为时齐算法；若无需各温度下算法均达到平稳分布，但温度需按一定速率下降，则称为非时齐算法。 ?分析收敛性3.2.2模拟退火算法与马尔科夫链3.3模拟退火算法关键参数和操作的设计智能优化计算浙江大学?原则产生的候选解应遍布全部解空间?方法在当前状态的邻域结构内以一定概率方式（均匀分布、正态分布、指数分布等）产生3.3.1状态产生函数3.3模拟退火算法关键参数和操作的设计智能优化计算浙江大学?原则 (1)在固定温度下，
10、接受使目标函数下降的候选解的概率要大于使目标函数上升的候选解概率； (2)随温度的下降，接受使目标函数上升的解的概率要逐渐减小； (3)当温度趋于零时，只能接受目标函数下降的解。 ?方法具体形式对算法影响不大一般采用min1,exp(-?C/t)3.3.2状态接受函数3.3模拟退火算法关键参数和操作的设计智能优化计算浙江大学?收敛性分析通过理论分析可以得到初温的解析式，但解决实际问题时难以得到精确的参数；初温应充分大；?实验表明初温越大，获得高质量解的机率越大，但花费较多的计算时间；3.3.3初温3.3模拟退火算法关键参数和操作的设计智能优化计算浙江大学?方法（ （1）均匀抽样一组状态，以各状
11、态目标值得方差为初温； （2）随机产生一组状态，确定两两状态间的最大目标值差，根据差值，利用一定的函数确定初温； （3）利用经验公式。 3.3.3初温3.3模拟退火算法关键参数和操作的设计智能优化计算浙江大学?时齐算法的温度下降函数（ （1），越接近11温度下降越慢，且其大小可以不断变化； （2），其中t0为起始温度，K为算法温度下降的总次数。 3.3.4温度更新函数10,0,1?k ttk k0tKk Kt k?3.3模拟退火算法关键参数和操作的设计智能优化计算浙江大学?非时齐模拟退火算法每个温度下只产生一个或少量候选解?时齐算法常用的Metropolis抽样稳定准则（ （1）检验目标函数的
12、均值是否稳定； （2）连续若干步的目标值变化较小； （3）按一定的步数抽样。 3.3.5内循环终止准则3.3模拟退火算法关键参数和操作的设计智能优化计算浙江大学?常用方法（ （1）设置终止温度的阈值； （2）设置外循环迭代次数； （3）算法搜索到的最优值连续若干步保持不变； （4）概率分析方法。 3.3.6外循环终止准则3.4模拟退火算法的改进智能优化计算浙江大学?模拟退火算法的优点质量高；初值鲁棒性强；简单、通用、易实现。 ?模拟退火算法的缺点由于要求较高的初始温度、较慢的降温速率、较低的终止温度，以及各温度下足够多次的抽样，因此优化过程较长。 3.4.1模拟退火算法的优缺点3.4模拟退火算
13、法的改进智能优化计算浙江大学?改进的可行方案（ （1）设计合适的状态产生函数； （2）设计高效的退火历程； （3）避免状态的迂回搜索； （4）采用并行搜索结构； （5）避免陷入局部极小，改进对温度的控制方式； （6）选择合适的初始状态； （7）设计合适的算法终止准则。 3.4.2改进内容3.4模拟退火算法的改进智能优化计算浙江大学?改进的方式（ （1）增加升温或重升温过程，避免陷入局部极小； （2）增加记忆功能（记忆“Best sofar”状态）； （3）增加补充搜索过程（以最优结果为初始解）； （4）对每一当前状态，采用多次搜索策略，以概率接受区域内的最优状态； （5）结合其它搜索机制的算法
14、； （6）上述各方法的综合。 3.4.2改进内容3.4模拟退火算法的改进智能优化计算浙江大学?改进的思路（ （1）记录“Best sofar”状态，并即时更新； （2）设置双阈值，使得在尽量保持最优性的前提下减少计算量，即在各温度下当前状态连续m1步保持不变则认为Metropolis抽样稳定，若连续m2次退温过程中所得最优解不变则认为算法收敛。 3.4.3一种改进的模拟退火算法3.4模拟退火算法的改进智能优化计算浙江大学?改进的退火过程（ （1）给定初温t0，随机产生初始状态s，令初始最优解s*=s，当前状态为s (0)=s，i=p=0； （2）令t=t i，以t，s*和s(i)调用改进的抽样过程，返回其所得最优解s*和当前状态s(k)，令当前状态s(i)=s(k)； （3）判断C(s*) （4）退温t i+1=update(t i)，令i=i+1； （5）判断pm2?若是，则转第 (6)步；否则，返回第 (2)步； （6）以最优解s*作为最终解输出，停止算法。 3.4.3一种改进的模拟退火算法3.4模拟退火算法的改进智能优化计算浙江大学?改进的抽样过程（ （1）令k=0时的初始当前状态为s (0)=s(i)，q=0； （2）由状态s通过状态产生函数产生新状态s，计算增量?C=C(s)-C(s)； （3）
