模拟退火算法ppt课件.ppt

,模拟退火算法,汇报人：许炯楼2014xxxxxx 李娜2014200909冒亚婷2014200922李园园2014200923,模拟退火算法及模型,1,1.1 模拟退火算法的来源及基本原理,算法的提出 模拟退火算法最早的思想由Metropolis等（1953）提出，1983年Kirkpatrick等将其应用于组合优化。算法的目的 解决NP复杂性问题；克服优化过程陷入局部极小；克服初值依赖性。,1.1 模拟退火算法的来源及基本原理,物理退火过程：退火是指将固体加热到足够高的温度，使分子呈随机排列状态，然后逐步降温使之冷却，最后分子以低能状态排列，固体达到某种稳定状态。,加温过程增强粒子的热运动，消除系统原先可能存在的非均匀态；等温过程对于与环境换热而温度不变的封闭系统，系统状态的自发变化总是 朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡态；冷却过程使粒子热运动减弱并渐趋有序，系统能量逐渐下降，从而得到低能的 晶体结构。,1.1 模拟退火算法的来源及基本原理,模仿自然界退火現象而得，利用了物理中固体物质的退火过程与一般优化问题的相似性；从某一初始温度开始，伴随温度的不断下降，结合概率突跳特性在解空间中随机寻找全局最优解。,1.1 模拟退火算法的来源及基本原理,数学表述 在温度T，分子停留在状态r满足Boltzmann概率分布,1.1 模拟退火算法的来源及基本思想,数学表述 在同一个温度T，选定两个能量E1E2，有,模拟退火算法基本思想：在一定温度下，搜索从一个状态随机地变化到另一个状态；随着温度的不断下降直到最低温度，搜索过程以概率1停留在最优解,0,1,1.1 模拟退火算法的来源及基本思想,Boltzman概率分布告诉我们：（1）在同一个温度，分子停留在能量小状态的概率大于停留在能量大状态的概率（2）温度越高，不同能量状态对应的概率相差越小；温度足够高时，各状态对应概率基本相同。（3）随着温度的下降，能量最低状态对应概率越来越大；温度趋于0时，其状态趋于1,1.1 模拟退火算法的来源及基本原理,数学表述 若|D|为状态空间D中状态的个数，D0是具有最低能量的状态集合：当温度很高时，每个状态概率基本相同，接近平均值1/|D|；状态空间存在超过两个不同能量时，具有最低能量状态的概率超出平均值1/|D|；当温度趋于0时，分子停留在最低能量状态的概率趋于1。,能量最低状态 非能量最低状态,1.1 模拟退火算法的来源及基本原理,Metropolis准则（1953）以概率接受新状态 固体在恒定温度下达到热平衡的过程可以用Monte Carlo方法（计算机随机模拟方法）加以模拟，虽然该方法简单，但必须大量采样才能得到比较精确的结果，计算量很大。若在温度T，当前状态i 新状态j;若EjEi，则接受 j 为当前状态；否则，若概率 p=exp-(Ej-Ei)/kBT 大于0,1)区间的随机数，则仍接受状态 j 为当前状态；若不成立则保留状态 i 为当前状态。p=exp-(Ej-Ei)/kBT 在高温下，可接受与当前状态能量差较大的新状态；在低温下，只接受与当前状态能量差较小的新状态。,1.1模拟退火算法的基本思想和步骤,给定初温t=t0，随机产生初始状态s=s0，令k=0；Repeat Repeat 产生新状态sj=Genete(s)；if min1,exp-(C(sj)-C(s)/tk=randrom0,1 s=sj;Until 抽样稳定准则满足；退温tk+1=update(tk)并令k=k+1；Until 算法终止准则满足；输出算法搜索结果。,基本步骤,1.1模拟退火算法的基本思想和步骤,给定初温t=t0，随机产生初始状态s=s0，令k=0；Repeat Repeat 产生新状态sj=Genete(s)；if min1,exp-(C(sj)-C(s)/tk=randrom0,1 s=sj;Until 抽样稳定准则满足；退温tk+1=update(tk)并令k=k+1；Until 算法终止准则满足；输出算法搜索结果。,影响优化结果的主要因素,三函数两准则初始温度,1.1模拟退火算法的基本思想和步骤,模拟退火算法的步骤,Step1 设定初始温度t=tmax,任选初始解r=r0Step2 内循环 Step2.1 从r的邻域中随机选一个解rt,计算r和rt对应目标函 数值,如rt对 应目标函数值较小，则令r=rt;否则若 exp(E(rt)E(r)/t)random(0,1),则令r=rt.Step2.2 不满足内循环停止条件时，重复Step2.1Step3 外循环 Step3.1 降温t=decrease(t)Step3.2 如不满足外循环停止条件，则转Step2；否则算法结束,1.达到终止温度2.达到迭代次数3.最优值连续若干步 保持不变,1.目标函数均值稳定2.连续若干步的目标值变化较小3.固定的抽样步数,模拟退火算法的马氏链描述,2,2.1马尔科夫链,定义,一步转移概率：,n步转移概率：,若解空间有限，称马尔可夫链为有限状态；,若，称马尔可夫链为时齐的。,2.2 模拟退火算法与马尔科夫链,模拟退火算法对应了一个马尔可夫链 模拟退火算法：新状态接受概率仅依赖于新状态和当前状态，并由温度加以控制。若固定每一温度，算法均计算马氏链的变化直至平稳分布，然后下降温度，则称为时齐算法；若无需各温度下算法均达到平稳分布，但温度需按一定速率下降，则称为非时齐算法。分析收敛性,模拟退火算法关键参数和操作的设计,3,*,3 模拟退火算法关键参数和操作的设计,原则 产生的候选解应遍布全部解空间方法 在当前状态的邻域结构内以一定概率方式（均匀分布、正态分布、指数分布等）产生,状态产生函数,状态接受函数,原则(1)在固定温度下，接受使目标函数下降的候选解的概率要大于使目标函数上升的候选解概率；(2)随温度的下降，接受使目标函数上升的解的概率要逐渐减小；(3)当温度趋于零时，只能接受目标函数下降的解。方法 具体形式对算法影响不大 一般采用min1,exp(-C/t),*,3 模拟退火算法关键参数和操作的设计,收敛性分析 通过理论分析可以得到初温的解析式，但解决实际问题时难以得到精确的参数；初温应充分大；实验表明 初温越大，获得高质量解的机率越大，但花费较多的计算时间；方法（1）均匀抽样一组状态，以各状态目标值得方差为初温；（2）随机产生一组状态，确定两两状态间的最大目标值差，根据差值，利用一定的函数确定初温；（3）利用经验公式。,初温,*,3 模拟退火算法关键参数和操作的设计,时齐算法的温度下降函数（1），越接近1温度下降越慢，且其大小可以不断变化；（2），其中t0为起始温度，K为算法温度下降的总次数。,温度更新函数,*,3 模拟退火算法关键参数和操作的设计,非时齐模拟退火算法 每个温度下只产生一个或少量候选解时齐算法常用的Metropolis抽样稳定准则（1）检验目标函数的均值是否稳定；（2）连续若干步的目标值变化较小；（3）按一定的步数抽样。,内循环终止准则,外循环终止准则,常用方法（1）设置终止温度的阈值；（2）设置外循环迭代次数；（3）算法搜索到的最优值连续若干步保持不变；（4）概率分析方法。,实例计算,4,成都市三环线-绕城高速西北区域公交路线的设计,*,4.1 问题描述,发展成都市经济文化的发展导致三环路以外居民不断普及，绕城高速区聚集了越来越多的企业、学校和商业网点。,1,2,3,经济的发展凸显了公共交通网络的不完善，成都市现有的公交线路覆盖范围主要涉及主城区，但郊区的公交线路和数量都很少，无法满足人们的出行要求。鉴于此，对未开通公交车的地区进行线路的优化是十分有必要的。,优化目标：明确选择成都三环线绕城高速的西北区域范围（必须包括大丰镇、安靖镇、犀浦镇和高新西区等重点区域），利用数学模型，在考虑人口密度、交通路况等基础上，对该区域的公交路线进行合理的规划设计，以满足居民在该区域内或区域外工作和生活的需要；,*,4.2 调查分析,在成都三环线绕城高速的西北区域范围（包括大丰镇、安靖镇、犀浦镇和高新西区等重点区域）内：,一共收集到了通过该区域的公交车辆38辆（线路76条，往返线路可以不一致），在该区域范围内的公交站点，以及每条公交线路的总长、在区域范围内的实际长度和空间直线长度，同时也刻画了公交站点在区域范围内的相对位置。,注：在进行线路优化时，总的公交线路条数是不变的（76条），不添 加额外的公交线路。,时间代价矩阵,*,4.3 模型建立,（1）数据准备,客流矩阵OD,距离矩阵,公交网络矩阵,2,1,路况矩阵,3,4,5,（2）公交空间网络解空间M的建立,记原来区域内的路线组成的交通网络为S0，根据S0的每一条线路在区域上的起讫点，运用 前n条最短路算法，确定S0的每一条路线的n条备用路线，建立区域内公交网络解空间M。记原来区域内的路线组成的交通网络为S0，显然 S0 属于M，所设计的新公交路线便从M中选取。（生成代码见附录2）,其中：,*,4.3 模型建立,（3）目标函数的确定,对于每一个交通网络 根据相应的数据库得出的数据所确定时间成本函数，我们的目标即在解空间内找到最优解S使得 最小，即求：,表示从站点i到j站点的第m条直达公交线路上的人流量；表示从站点i到j站点的第m条需换乘公交线路上的人流量；表示第m条直达公交线路上从站点i到站点j所需行车时间；表示第m条需换乘公交线路上从站点i到站点j所需行车时间。,：第m条公交线路上相邻站点k与k+1之间的平均速度；：第m条公交线路上相邻站点k与k+1之间的距离；,*,4.3 模型建立,：第m条需换乘公交线路上相邻站点k与k+1之间的距离；：第m条需换乘公交线路上换乘的次数。,转化为解空间的表达,客户评价内容,*,4 利用算法求解,第一步 确定目标函数,第二步 利用模拟退火算法进行最优解计算,根据路况矩阵，以及od矩阵和相关参数确定目标函数T(S),第三步 列出所得最优解，进行合理性测试。,*,4.4 算法程序,function S,L3new=tuihuoNew(Sc,OD,condition,L,L3,L4)%L3 原始解 L4 解空间S=Sc;S2=Sc;k=0;T=100;k_max=21T_min=20;r=0.95;while TT_min end,模拟退火算法,function A=buildA(S)%UNTITLED2 Summary of this function goes here%Detailed explanation goes here%到了第三问这里有buildA for count version two.A=zeros(244,244);for i=1:244for j=1:244if length(Si,j)=1 temp=(Si,j);aaa=mean(temp,1);A(i,j)=aaa(2);endendendfor i=1:244 for j=1:244 if A(i,j)=0 end endend,代价矩阵A代码,*,4.4 算法程序,function pathaim,dist=dijkstra2(D,s,aim)%Dijkstra最短路算法Matlab程序用于求从起始点s到其它各点的最短路%D为赋权邻接矩阵%d为s到其它各点最短路径的长度%DD记载了最短路径生成树tic;m,n=size(D);d=inf.*ones(1,m);d(1,s)=0;dd=zeros(1,m);dd(1,s)=1;y=s;for iii=1:m pathiii,1(1)=iii;endwhile length(find(dd=1)m for i=1:m if dd(i)=0 d(i)=min(d(i),d(y)+D(y,i);if d(i)=d(y)+D(y,i)pathi=pathy;pathi(length(pathy,1)+1)=i;end end end ddd=inf;,Dijstras最短路代码,for i=1:m if dd(i)=0endToc,*,4 算法程序,function finalcost=timeCost(S,OD)%计算代价矩阵 包括换乘的代价附加值 换乘一次附加5 换乘两次附加10%包含了直接用S计算 和 考虑od矩阵的计算的timeCost 最终用于退火算法的判断函数tic;test=buildA(S);m=size(test,1);cost=floydnew(test);t1=zeros(m,m);for i=1:m for j=1:m if test(i,j)=0 end endend,temp=t1+t2;for i=1:m for j=1:m if temp(i,j)=0 end endendtocend,T（n）最小时间代价代码,*,4.5 求解结果,结果评价：计算时间新公交路线的时间代价为，原矩阵的时间代价为4898202，新矩阵的代价为4342931，模拟算法使得公交网络路线的重新规划的时间成本代价下降11.34%，以综合检测解得的合理系数为0.03720.05。可以认为重新规划的交通网络既科学合理，又较好的优化了原有交通系统的服务能力。,感谢大家请对不足之处提宝贵意见！,