《现代优化算法》ppt课件 (2)-文库吧

【正文】

个数， D0是具有最低能量的状态集合： 当温度很高时，每个状态概率基本相同，接近平均值1/|D|； 状态空间存在超过两个不同能量时，具有最低能量状态的概率超出平均值 1/|D| ； 当温度趋于 0时，分子停在最低能量状态概率趋于 1。 模拟退火算法 能量最低状态 非能量最低状态  TkrETZrEEP B)(ex p)(1)}({ 数学表述 44 模拟退火算法及模型 智能优化计算  Metropolis准则（ 1953） —— 以概率接受新状态 物理退火过程 固体在恒定温度下达到热平衡的过程可以用 Monte Carlo方法 （计算机随机模拟方法）加以模拟，虽然该方法简单，但必须大量采样才能得到比较精确的结果，计算量很大。 45 模拟退火算法及模型 智能优化计算 否则，以概率 p=exp[(EjEi)/kBT] 接受 j 为当前状态。 物理退火过程  Metropolis准则（ 1953） —— 以概率接受新状态 若在温度 T，当前状态 i → 新状态 j 若 EjEi，则接受 j 为当前状态； 即： p大于 [0,1)区间的随机数，则仍接受状态 j 为当前状态；否则保留状态 i 为当前状态。 46 模拟退火算法及模型 智能优化计算  Metropolis准则（ 1953） —— 以概率接受新状态 p=exp[(EjEi)/kBT] 物理退火过程  在低温下，只接受与当前状态能量差较小的新状态。  在高温下，可接受与当前状态能量差较大的新状态； 47 组合优化与物理退火的相似性 智能优化计算  相似性比较 组合优化问题 金属物体 解 粒子状态 最优解 能量最低的状态 设定初温 熔解过程 Metropolis抽样过程 等温过程 控制参数的下降 冷却 目标函数 能量 48 SA算法描述 49 案例讲解  已知敌方 100个目标的经度、纬度 我方有一个基地，经度和纬度为（ 70,40）。假设我方飞机的速度为 1000公里 /小时。我方派一架飞机从基地出发，侦察完敌方所有目标，再返回原来的基地。在敌方每一目标点的侦察时间不计，求该架飞机所花费的时间（假设我方飞机巡航时间可以充分长）。 50 问题分析 51 算法描述 (解空间与目标函数 ) 52 算法描述  一次迭代由三步组成 53 算法描述 54 案例讲解 0 10 20 30 40 50 60 700510152025303540S u m = 4 1 2 1 7 . 8 6 455 模拟退火算法及模型 智能优化计算  基本步骤 给定初温 t=t0，随机产生初始状态 s=s0，令 k=0； Repeat Repeat 产生新状态 sj=Gee(s)； if min{1,exp[(C(sj)C(s))/tk]}=randrom[0,1] s=sj。 Until 抽样稳定准则满足； 退温 tk+1=update(tk)并令 k=k+1； Until 算法终止准则满足； 输出算法搜索结果。 模拟退火算法的基本思想和步骤 56 模拟退火算法及模型 智能优化计算  影响优化结果的主要因素 给定初温 t=t0，随机产生初始状态 s=s0，令 k=0； Repeat Repeat 产生新状态 sj=Gee(s)； if min{1,exp[(C(sj)C(s))/tk]}=randrom[0,1] s=sj。 Until 抽样稳定准则满足； 退温 tk+1=update(tk)并令 k=k+1； Until 算法终止准则满足； 输出算法搜索结果。 模拟退火算法的基本思想和步骤 三函数两准则 初始温度 57 模拟退火算法关键参数和操作的设计 智能优化计算 华东理工大学自动化系 2022年  原则 产生的候选解应遍布全部解空间 (保证全局最优解 )  方法 在当前状态的邻域结构内以一定概率方式（均匀分布、正态分布、指数分布等）产生 状态产生函数 58 模拟退火算法关键参数和操作的设计 智能优化计算  原则 (1)在固定温度下，接受使目标函数下降的候选解的概率要大于使目标函数上升的候选解概率； (2)随温度的下降，接受使目标函数上升的解的概率要逐渐减小； (3)当温度趋于零时，只能接受目标函数下降的解。  方法 具体形式对算法影响不大 , 一般采用 min[1,exp(∆C/t)] 状态接受函数 59 模拟退火算法关键参数和操作的设计 智能优化计算  收敛性分析 通过理论分析可以得到初温的解析式，但解决实际问题时难以得到精确的参数； 初温应充分大；  实验表明 初温越大，获得高质量解的机率越大，但花费较多的计算时间； 初温 60 模拟退火算法关键参数和操作的设计 智能优化计算  方法 （ 1）均匀抽样一组状态，以各状态目标值得方差为初温； （ 2）随机产生一组状态，确定两两状态间的最大目标值 差，根据差值，利用一定的函数确定初温； （ 3）利用经验公式。 初温 61 模拟退火算法关键参数和操作的设计 智能优化计算  时齐算法的温度下降函数 （ 1） ， α越接近 1温度下降越慢，且其大小可以不断变化； （ 2） ，其中 t0为起始温度， K为算法温度下降的总次数。 温度更新函数 10 ,0 ,1   ktt kk0tKkKtk 若固定每一温度，算法均计算至平稳分布，然后下降温度，则称为时齐算法；  若无需各温度下算法均达到平稳分布，但温度需按一定速率下降，则称为非时齐算法。 62 模拟退火算法关键参数和操作的设计 智能优化计算  非时齐模拟退火算法 每个温度下只产生一个或少量候选解  时齐算法 —— 常用的 Metropolis抽样稳定准则 （ 1）检验目标函数的均值是否稳定； （ 2）连续若干步的目标值变化较小； （ 3）按一定的步数抽样。 内循环终止准则 63 模拟退火算法关键参数和操作的设计 智能优化计算  常用方法 （ 1）设置终止温度的阈值； （ 2）设置外循环迭代次数； （ 3）算法搜索到的最优值连续若干步保持不变； （ 4）概率分析方法。 外循环终止准则 64 智能优化计算  模拟退火算法的优点 质量高； 初值鲁棒性强； 简单、通用、易实现。  模拟退火算法的缺点 由于要求较高的初始温度、较慢的降温速率、较低的终止温度，以及各温度下足够多次的抽样，因此优化过程较长。 模拟退火算法的优缺点 65 模拟退火算法的实现与应用 智能优化计算 30城市 TSP问题（ d*= by D B Fogel）  TSP Benchmark 问题 41 94。37 84。54 67。25 62。 7 64。2 99。68 58。71 44。54 62。83 69。64 60。18 54。22 60。83 46。91 38。25 38。24 42。58 69。71 71。74 78。87 76。18 40。13 40。82 7。62 32。 58 35。45 21。41 26。44 35。4 50 66 67 智能优化计算  算法流程 给 给 给 给 给 给 给 给给 给 给 给 给 Si给 给 给 给 给 Sj给 给 给 给 给 给 给 s *给 给 给 给 给 给 给 给 给 给给 给m i n { 1 , e x p [ ( C ( sj) C ( si) ) / tk] } = r a n d o m [ 0 , 1 ]给 给 给 给 给 给 给 给 给 给 给 给 给 给 给 给 k = 0M e t r o p o l i s 给 给 给 给 给 给 给 给 给 给tk + 1= u p d a t e ( tk)给 k = k + 1给 S i 给 S j ， 给 给 给 给 给 给 给 给 s *给 给 给 给 给 给给 给YNYNYN68 模拟退火算法的实现与应用 智能优化计算  初始温度的计算 for i=1:100 route=randperm(CityNum)。 fval0(i)=CalDist(dislist,route)。 end t0=(max(fval0)min(fval0))/log()。 30城市 TSP问题（ d*= by D B Fogel） 69 模拟退火算法的实现与应用 智能优化计算  状态产生函数的设计 （ 1）互换操作，随机交换两个城市的顺序； （ 2）逆序操作，两个随机位置间的城市逆序； （ 3）插入操作，随机选择某点插入某随机位置。 30城市 TSP问题（ d*= by D B Fogel） 2 8 3 5 9 1 4 6 7 2 8 3 5 9 1 4 6 7 2 8 3 5 9 1 4 6 7 2 8 1 5 9 3 4 6 7 2 8 3 4 1 9 5 6 7 2 3 5 9 8 1 4 6 7 70 模拟退火算法的实现与应用 智能优化计算  参数设定 截止温度 tf=。 退温系数 alpha=。 内循环次数 L=200*CityNum。 30城市 TSP问题（ d*= by D B Fogel） 71 模拟退火算法的实现与应用 智能优化计算  运行过程 30城市 TSP问题（ d*= by D B Fogel） 72 模拟退火算法的实现与应用 智能优化计算  运行过程 30城市 TSP问题（ d*= by D B Fogel） 73 模拟退火算法的实现与应用 智能优化计算  运行过程 30城市 TSP问题（ d*= by D B Fogel） 74 模拟退火算法的实现与应用 智能优化计算  运行过程 30城市 TSP问题（ d*= by D B Fogel） 75 模拟退火算法的实现与应用 智能优化计算  运行过程 30城市 TSP问题（ d*= by D B Fogel） 76 模拟退火算法的实现与应用 智能优化计算  运行结果 30城市 TSP问题（ d*= by D B Fogel） 77 模拟退火算法的改进 智能优化计算  改进的可行方案 （ 1）设计合适的状态产生函数； （ 2）设计高效的退火历程； （ 3）避免状态的迂回搜索； （ 4）采用并行搜索结构； （ 5）避免陷入