下载
加入VIP
  • 专属下载券
  • 上传内容扩展
  • 资料优先审核
  • 免费资料无限下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 第三章 模拟退火算法

第三章 模拟退火算法.pdf

第三章 模拟退火算法

山水树涛
2012-12-21 0人阅读 举报 0 0 0 暂无简介

简介:本文档为《第三章 模拟退火算法pdf》,可适用于IT/计算机领域

第三章模拟退火算法智能算法导论浙江大学模拟退火算法及模型物理退火过程组合优化与物理退火的相似性模拟退火算法的基本思想和步骤模拟退火算法的马氏链描述马尔可夫链模拟退火算法与马尔可夫链模拟退火算法的关键参数和操作的设计状态产生函数状态接受函数初温温度更新函数内循环终止准则外循环终止准则智能算法导论浙江大学模拟退火算法的改进模拟退火算法的优缺点改进内容一种改进的模拟退火算法模拟退火算法实现与应用城市TSP问题(d*=byDBFogel)模拟退火算法在管壳式换热器优化设计中的应用智能算法导论浙江大学模拟退火算法及模型智能算法导论浙江大学算法的提出模拟退火算法最早的思想由Metropolis等()提出年Kirkpatrick等将其应用于组合优化。算法的目的解决NP复杂性问题克服优化过程陷入局部极小克服初值依赖性。物理退火过程模拟退火算法及模型智能算法导论浙江大学物理退火过程什么是退火:退火是指将固体加热到足够高的温度使分子呈随机排列状态然后逐步降温使之冷却最后分子以低能状态排列固体达到某种稳定状态。物理退火过程模拟退火算法及模型智能算法导论浙江大学物理退火过程加温过程增强粒子的热运动消除系统原先可能存在的非均匀态等温过程对于与环境换热而温度不变的封闭系统系统状态的自发变化总是朝自由能减少的方向进行当自由能达到最小时系统达到平衡态冷却过程使粒子热运动减弱并渐趋有序系统能量逐渐下降从而得到低能的晶体结构。物理退火过程模拟退火算法及模型智能算法导论浙江大学数学表述在温度T分子停留在状态r满足Boltzmann概率分布物理退火过程DsBBBTksETZTZkrrEETkrETZrEEP)(exp)()(Boltzmann)()(exp)()}({子:为概率分布的标准化因常数。为的能量表示状态机变量表示分子能量的一个随模拟退火算法及模型智能算法导论浙江大学数学表述在同一个温度T选定两个能量E<E有在同一个温度分子停留在能量小的状态的概率比停留在能量大的状态的概率要大。物理退火过程TkEETkETZEEPEEPBBexpexp)(}{}{<>模拟退火算法及模型智能算法导论浙江大学数学表述|D|为状态空间D中状态的个数D是具有最低能量的状态集合:当温度很高时每个状态概率基本相同接近平均值|D|状态空间存在超过两个不同能量时具有最低能量状态的概率超出平均值|D|当温度趋于时分子停留在最低能量状态的概率趋于,非最低能量状态的概率趋于。见例物理退火过程能量最低状态非能量最低状态模拟退火算法及模型智能算法导论浙江大学Metropolis准则()以概率接受新状态固体在恒定温度下达到热平衡的过程可以用MonteCarlo方法(计算机随机模拟方法)加以模拟虽然该方法简单但必须大量采样才能得到比较精确的结果计算量很大。物理退火过程模拟退火算法及模型智能算法导论浙江大学物理退火过程模拟退火算法及模型智能算法导论浙江大学Metropolis准则()以概率接受新状态若在温度T当前状态i→新状态j若Ej<Ei则接受j为当前状态否则若概率p=exp(EjEi)kBT大于,)区间的随机数则仍接受状态j为当前状态若不成立则保留状态i为当前状态。物理退火过程(EjEi)kTp即若满足min{,exp(EjEi)tk}>=randrom,接受状态J模拟退火算法及模型智能算法导论浙江大学Metropolis准则()以概率接受新状态在高温下可接受与当前状态能量差较大的新状态在低温下只接受与当前状态能量差较小的新状态。物理退火过程(EjEi)kTpp=exp(EjEi)kBT低温区域高温区域模拟退火算法及模型智能算法导论浙江大学相似性比较组合优化与物理退火的相似性组合优化问题金属物体解粒子状态最优解能量最低的状态设定初温熔解过程Metropolis抽样过程等温过程控制参数的下降冷却目标函数能量模拟退火算法及模型智能算法导论浙江大学基本步骤给定初温t=t随机产生初始状态s=s令k=RepeatRepeat产生新状态sj=Genete(s)ifmin{,exp(C(sj)C(s))tk}>=randrom,s=sjUntil抽样稳定准则满足退温tk=update(tk)并令k=kUntil算法终止准则满足输出算法搜索结果。模拟退火算法的基本思想和步骤模拟退火算法及模型智能算法导论浙江大学影响优化结果的主要因素给定初温t=t随机产生初始状态s=s令k=RepeatRepeat产生新状态sj=Genete(s)ifmin{,exp(C(sj)C(s))tk}>=randrom,s=sjUntil抽样稳定准则满足退温tk=update(tk)并令k=kUntil算法终止准则满足输出算法搜索结果。模拟退火算法的基本思想和步骤三函数两准则初始温度模拟退火算法的马氏链描述智能算法导论浙江大学定义马氏链模型是关于随机动态系统的一类模型适用于时间、状态都离散并具有无后效性(或马尔可夫性)的场合。所谓无后效性就是系统未来的状态只与系统现在的状态有关与以前的状态无关。马尔科夫链})()(Pr{})(,,)(,)()(Pr{)}({)(},,{inXjnXinXiXiXjnXZnkXkkXss满足称为马尔可夫链若随机序列时刻状态变量的取值。为间为所有状态构成的解空令条件概率、状态转移模拟退火算法的马氏链描述智能算法导论浙江大学定义一步转移概率:n步转移概率:若解空间有限称马尔可夫链为有限状态若称马尔可夫链为时齐的。马尔科夫链})()(Pr{)(,inXjnXnpji)()(,,,npnpZnjiji})()(Pr{)(,iXjnXpnji模拟退火算法的马氏链描述智能算法导论浙江大学Markov链的性质一步转移概率:马尔科夫链,,,,,,()nijiijnpjnpPnP模拟退火算法的马氏链描述智能算法导论浙江大学模拟退火算法对应了一个马尔可夫链模拟退火算法:新状态接受概率仅依赖于新状态和当前状态并由温度加以控制。若固定每一温度算法均计算马氏链的变化直至平稳分布然后下降温度则称为时齐算法若无需各温度下算法均达到平稳分布但温度需按一定速率下降则称为非时齐算法。模拟退火算法与马尔科夫链模拟退火算法的马氏链描述智能算法导论浙江大学可达性:无论起点如何任何一个状态都是可达的。渐进不依赖于起点分布平稳性:温度不变时概率具有极限分布收敛到最优解例子P=,,matlab马尔科夫链描述模拟退火应满足条件模拟退火算法关键参数和操作的设计智能算法导论浙江大学原则产生的候选解应遍布全部解空间方法在当前状态的邻域结构内以一定概率方式(均匀分布、正态分布、指数分布等)产生状态产生函数模拟退火算法关键参数和操作的设计智能算法导论浙江大学原则()在固定温度下接受使目标函数下降的候选解的概率要大于使目标函数上升的候选解概率()随温度的下降接受使目标函数上升的解的概率要逐渐减小()当温度趋于零时只能接受目标函数下降的解。方法具体形式对算法影响不大一般采用min,exp(∆Ct)状态接受函数模拟退火算法关键参数和操作的设计智能算法导论浙江大学收敛性分析通过理论分析可以得到初温的解析式但解决实际问题时难以得到精确的参数初温应充分大实验表明初温越大获得高质量解的机率越大但花费较多的计算时间初温越小易陷入局部最优解。初温模拟退火算法关键参数和操作的设计智能算法导论浙江大学方法()均匀抽样一组状态以各状态目标值得方差为初温()随机产生一组状态确定两两状态间的最大目标值差根据差值利用一定的函数确定初温()利用经验公式。初温模拟退火算法关键参数和操作的设计智能算法导论浙江大学初温如何取模拟退火算法关键参数和操作的设计智能算法导论浙江大学时齐算法的温度下降函数()α越接近温度下降越慢且其大小可以不断变化比较常用()其中t为起始温度K为算法温度下降的总次数。该下降方法易操作但每一步下降长度相同温度更新函数,,kttkktKkKtk模拟退火算法关键参数和操作的设计智能算法导论浙江大学非时齐模拟退火算法每个温度下只产生一个或少量候选解时齐算法常用的Metropolis抽样稳定准则()按一定的步数()抽样检验目标函数的均值是否稳定()连续若干步的目标值变化较小。内循环终止准则模拟退火算法关键参数和操作的设计智能算法导论浙江大学常用方法()设置终止温度的阈值(零度法)()设置外循环迭代次数()算法搜索到的最优值连续若干步保持不变()概率分析方法。外循环终止准则模拟退火算法的改进智能算法导论浙江大学模拟退火算法的优点质量高初值鲁棒性强简单、通用、易实现理论上可实现全局最优解实际上为启发式算法模拟退火算法的缺点由于要求较高的初始温度、较慢的降温速率、较低的终止温度以及各温度下足够多次的抽样因此优化过程较长。模拟退火算法的优缺点模拟退火算法的改进智能算法导论浙江大学改进的可行方案()设计合适的状态产生函数()设计高效的退火历程()避免状态的迂回搜索()采用并行搜索结构()避免陷入局部极小改进对温度的控制方式()选择合适的初始状态()设计合适的算法终止准则。改进内容模拟退火算法的改进智能算法导论浙江大学改进的方式()增加升温或重升温过程避免陷入局部极小()增加记忆功能(记忆“Bestsofar”状态)()增加补充搜索过程(以最优结果为初始解)()对每一当前状态采用多次搜索策略以概率接受区域内的最优状态()结合其它搜索机制的算法()上述各方法的综合。改进内容模拟退火算法的改进智能算法导论浙江大学改进的思路()记录“Bestsofar”状态并即时更新()设置双阈值使得在尽量保持最优性的前提下减少计算量即在各温度下当前状态连续m步保持不变则认为Metropolis抽样稳定若连续m次退温过程中所得最优解不变则认为算法收敛。一种改进的模拟退火算法模拟退火算法的改进智能算法导论浙江大学改进的退火过程()给定初温t随机产生初始状态s令初始最优解s*=s当前状态为s()=si=p=()令t=ti以ts*和s(i)调用改进的抽样过程返回其所得最优解s*’和当前状态s’(k)令当前状态s(i)=s’(k)()判断C(s*)<C(s*’)若是则令p=p否则令s*=s*’p=()退温ti=update(ti)令i=i()判断p>m若是则转第()步否则返回第()步()以最优解s*作为最终解输出停止算法。一种改进的模拟退火算法模拟退火算法的改进智能算法导论浙江大学改进的抽样过程()令k=时的初始当前状态为s’()=s(i)q=()由状态s通过状态产生函数产生新状态s’计算增量∆C’=C(s’)C(s)()若∆C’<则接受s’作为当前解并判断C(s*’)>C(s’)若是则令s*’=s’q=否则令q=q。若∆C’>则以概率exp(∆C’t)接受s’作为下一当前状态()令k=k判断q>m若是则转第()步否则返回第()步()将当前最优解s*’和当前状态s’(k)返回改进退火过程。一种改进的模拟退火算法模拟退火算法的实现与应用智能算法导论浙江大学城市TSP问题(d*=byDBFogel)TSPBenchmark问题模拟退火算法的实现与应用智能算法导论浙江大学算法流程城市TSP问题(d*=byDBFogel)给定算法初始参数由当前状态Si产生新状态Sj结束搜索输出s*算法收敛准则满足否?判断min{,exp(C(sj)C(si))tk}>=random,计算初始温度随机产生初始解令k=Metropolis抽样稳定准则满足否?tk=update(tk)令k=k令Si=Sj并记录当前最优解s*保持当前状态不变YNYNYN模拟退火算法的实现与应用智能算法导论浙江大学初始温度的计算fori=:route=randperm(CityNum)fval(i)=CalDist(dislist,route)endt=(max(fval)min(fval))log()城市TSP问题(d*=byDBFogel)模拟退火算法的实现与应用智能算法导论浙江大学状态产生函数的设计()互换操作随机交换两个城市的顺序()逆序操作两个随机位置间的城市逆序()插入操作随机选择某点插入某随机位置。城市TSP问题(d*=byDBFogel)模拟退火算法的实现与应用智能算法导论浙江大学参数设定截止温度tf=退温系数alpha=内循环次数L=*CityNum城市TSP问题(d*=byDBFogel)模拟退火算法的实现与应用智能算法导论浙江大学运行过程城市TSP问题(d*=byDBFogel)模拟退火算法的实现与应用智能算法导论浙江大学运行过程城市TSP问题(d*=byDBFogel)模拟退火算法的实现与应用智能算法导论浙江大学运行过程城市TSP问题(d*=byDBFogel)模拟退火算法的实现与应用智能算法导论浙江大学运行过程城市TSP问题(d*=byDBFogel)模拟退火算法的实现与应用智能算法导论浙江大学运行过程城市TSP问题(d*=byDBFogel)模拟退火算法的实现与应用智能算法导论浙江大学运行结果城市TSP问题(d*=byDBFogel)模拟退火算法的实现与应用智能算法导论浙江大学换热器模型两级管壳式换热器组成的换热器系统数学模型高度非线性其目标函数通常是多峰(谷)的具有很多局部最优解。模拟退火算法在管壳式换热器优化设计中的应用模拟退火算法的实现与应用智能算法导论浙江大学优化目标以换热器系统的总费用年值最小作为优化设计的目标。其中f(X)是两级换热器的初始投资f(X)是两级换热器年维护费(包括除垢、保养、维修等)f(X)是冷却水资源费以及管程压降能耗费f(X)是壳程压降能耗费。模拟退火算法在管壳式换热器优化设计中的应用)()()()()()()(minXfXfXfiiiXfXfnn模拟退火算法的实现与应用智能算法导论浙江大学优化目标经过分析优化问题的独立变量共个分别是一级换热器煤油出口温度t、冷却水流量G、两个换热器的管内径dd和管间距SS、折流板间距BB、折流板开口角αα、单管长度LL。模拟退火算法在管壳式换热器优化设计中的应用),,,,,,,,,,,()(minLLBBSSddGtfXf模拟退火算法的实现与应用智能算法导论浙江大学应用模拟退火算法解决优化设计状态表示个变量的实数表示初始温度结束温度状态产生函数η为扰动幅度参数ξ为随机扰动变量随机扰动可服从柯西、高斯、均匀分布。降温因子马氏链长度。模拟退火算法在管壳式换热器优化设计中的应用)()(kxkx模拟退火算法的实现与应用智能算法导论浙江大学优化结果优化目标值E+独立变量取值模拟退火算法在管壳式换热器优化设计中的应用t℃GKgsdmmSmmBmα弧度LmdmmSmmBmα弧度Lm第三章结束智能算法导论浙江大学

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

评分:

/10

VIP

意见
反馈

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利