资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,模拟退火算法,汇报人:许炯楼,2014xxxxxx,李娜,2014200909,冒亚婷,2014200922,李园园,2014200923,模拟退火算法汇报人:许炯楼2014xxxxxx,1,模拟退火算法及模型,1,模拟退火算法及模型1,2,1.1,模拟退火算法的来源及基本原理,算法的提出,模拟退火算法最早的思想由,Metropolis,等(,1953,)提出,,1983,年,Kirkpatrick,等将其应用于组合优化。,算法的目的,解决,NP,复杂性,问题;,克服优化过程陷入局部极小;,克服初值依赖性。,1.1 模拟退火算法的来源及基本原理算法的提出,3,1.1,模拟退火算法的来源及基本原理,物理退火过程:,退火是指将固体加热到足够高的温度,使分子呈随机排列状态,,然后逐步降温使之冷却,最后分子以低能状态排列,固体达到某,种稳定状态。,加温过程,增强粒子的热运动,消除系统原先可能存在的非均匀态;,等温过程,对于与环境换热而温度不变的封闭系统,系统状态的自发变化总是,朝自由能减少的方向进行,当自由能达到最小时,系统达到平衡态;,冷却过程,使粒子热运动减弱并渐趋有序,系统能量逐渐下降,从而得到低能的,晶体结构。,1.1 模拟退火算法的来源及基本原理物理退火过程:加温过程,4,1.1,模拟退火算法的来源及基本原理,模仿自然界退火現象而得,利用了物理中固体物质的,退火过程,与一般,优化,问题的相似性;,从某一初始,温度,开始,伴随温度的不断下降,结合,概率突跳,特性在解空间中,随机,寻找,全局最优解。,1.1 模拟退火算法的来源及基本原理模仿自然界退火現象而得,,5,1.1,模拟退火算法的来源及基本原理,数学表述,在温度,T,,分子停留在状态,r,满足,Boltzmann,概率分布,1.1 模拟退火算法的来源及基本原理数学表述,6,1.1,模拟退火算法的来源及基本思想,数学表述,在,同一个温度,T,,选定两个能量,E,1,0,1,1.1 模拟退火算法的来源及基本思想数学表述模拟退火算法基本,7,1.1,模拟退火算法的来源及基本思想,Boltzman,概率分布,告诉我们:,(,1,)在同一个温度,分子停留在能量小状态的概率大于停留在能量大状态的概率,(,2,)温度越高,不同能量状态对应的概率相差越小;温度足够高时,各状态对应概率基本相同。,(,3,)随着温度的下降,能量最低状态对应概率越来越大;温度趋于,0,时,其状态趋于,1,1.1 模拟退火算法的来源及基本思想Boltzman概率分布,8,1.1,模拟退火算法的来源及基本原理,数学表述,若,|,D,|,为状态空间,D,中状态的个数,,D,0,是具有最低能量的状态集合:,当温度很高时,每个状态概率基本相同,接近平均值,1/|,D,|,;,状态空间存在超过两个不同能量时,具有最低能量状态的概率超出平均值,1/|,D,|,;,当温度趋于,0,时,分子停留在最低能量状态的概率趋于,1,。,能量最低状态 非能量最低状态,1.1 模拟退火算法的来源及基本原理数学表述能量最低状态,9,1.1,模拟退火算法的来源及基本原理,Metropolis,准则(,1953,),以概率接受新状态,固体在恒定温度下达到热平衡的过程可以用,Monte Carlo,方法(计算机随机模拟方法)加以模拟,虽然该方法简单,但必须大量采样才能得到比较精确的结果,计算量很大。,若在温度,T,,当前状态,i,新状态,j;,若,E,j,=randrom0,1,s,=,s,j,;,Until,抽样稳定准则满足;,退温,t,k,+1,=update(,t,k,),并令,k,=,k,+1,;,Until,算法终止准则满足;,输出算法搜索结果。,基本步骤,1.1模拟退火算法的基本思想和步骤 给定初温t=t0,,11,1.1,模拟退火算法的基本思想和步骤,给定初温,t,=,t,0,,随机产生初始状态,s,=,s,0,,令,k,=0,;,Repeat,Repeat,产生新状态,s,j,=Genete(,s,),;,if min1,exp-(,C,(,s,j,)-,C,(,s,)/,t,k,=randrom0,1,s,=,s,j,;,Until,抽样稳定准则满足;,退温,t,k,+1,=update(,t,k,),并令,k,=,k,+1,;,Until,算法终止准则满足;,输出算法搜索结果。,影响优化结果的主要因素,三函数两准则,初始温度,1.1模拟退火算法的基本思想和步骤 给定初温t=t0,随机产,12,1.1,模拟退火算法的基本思想和步骤,模拟退火算法的步骤,Step1,设定初始温度,t=tmax,任选初始解,r=r0,Step2,内循环,Step2.1,从,r,的邻域中随机选一个解,rt,计算,r,和,rt,对应目标函 数值,如,rt,对,应目标函数值较小,则令,r=rt;,否则若,exp(E(rt)E(r)/t)random(0,1),则令,r=rt.,Step2.2,不满足内循环停止条件时,重复,Step2.1,Step3,外循环,Step3.1,降温,t=decrease(t),Step3.2,如不满足外循环停止条件,则转,Step2,;否则算法结束,1.,达到终止温度,2.,达到迭代次数,3.,最优值连续若干步,保持不变,1.,目标函数均值稳定,2.,连续若干步的目标值变化较小,3.,固定的抽样步数,1.1模拟退火算法的基本思想和步骤模拟退火算法的步骤Step,13,模拟退火算法的马氏链描述,2,模拟退火算法的马氏链描述2,14,2.1,马尔科夫链,定义,一步转移概率:,n,步转移概率:,若解空间有限,称马尔可夫链为,有限状态,;,若 ,称马尔可夫链为,时齐的,。,2.1马尔科夫链定义一步转移概率:n步转移概率:若解空间有限,15,2.2,模拟退火算法与马尔科夫链,模拟退火算法对应了一个马尔可夫链,模拟退火算法:新状态接受概率仅依赖于新状态和当前状态,,并由温度加以控制。,若固定每一温度,算法均计算马氏链的变化直至平稳分布,然,后下降温度,则称为,时齐算法,;,若无需各温度下算法均达到平稳分布,但温度需按一定速率下,降,则称为,非时齐算法,。,分析收敛性,2.2 模拟退火算法与马尔科夫链模拟退火算法对应了一个马尔可,16,模拟退火算法关键参数和操作的设计,3,模拟退火算法关键参数和操作的设计3,17,*,3,模拟退火算法关键参数和操作的设计,原则,产生的候选解应遍布全部解空间,方法,在当前状态的邻域结构内以一定概率方式(均匀分布、正态分布、指数分布等)产生,状态产生函数,状态接受函数,原则,(1),在固定温度下,接受使目标函数下降的候选解的概率要大于使目标函数上升的候选解概率;,(2),随温度的下降,接受使目标函数上升的解的概率要逐渐减小;,(3),当温度趋于零时,只能接受目标函数下降的解。,方法,具体形式对算法影响不大,一般采用,min1,exp(-C/t),*3 模拟退火算法关键参数和操作的设计原则 状态产生函数,18,*,3,模拟退火算法关键参数和操作的设计,收敛性分析,通过理论分析可以得到初温的解析式,但解决实际问题时难以得到精确的参数;,初温应充分大;,实验表明,初温越大,获得高质量解的机率越大,但花费较多的计算时间;,方法,(,1,)均匀抽样一组状态,以各状态目标值得方差为初温;,(,2,)随机产生一组状态,确定两两状态间的最大目标值差,根据差值,利用一定的函数确定初温;,(,3,)利用经验公式。,初温,*3 模拟退火算法关键参数和操作的设计收敛性分析,19,*,3,模拟退火算法关键参数和操作的设计,时齐算法的温度下降函数,(,1,),,越接近,1,温度下降越慢,且其大小可以不断变化;,(,2,),其中,t,0,为起始温度,,K,为算法温度下降的总次数。,温度更新函数,*3 模拟退火算法关键参数和操作的设计时齐算法的温度下降函,20,*,3,模拟退火算法关键参数和操作的设计,非时齐模拟退火算法,每个温度下只产生一个或少量候选解,时齐算法,常用的,Metropolis,抽样稳定准则,(,1,)检验目标函数的均值是否稳定;,(,2,)连续若干步的目标值变化较小;,(,3,)按一定的步数抽样。,内循环终止准则,外循环终止准则,常用方法,(,1,)设置终止温度的阈值;,(,2,)设置外循环迭代次数;,(,3,)算法搜索到的最优值连续若干步保持不变;,(,4,)概率分析方法。,*3 模拟退火算法关键参数和操作的设计非时齐模拟退火算法,21,实例计算,4,成都市三环线-绕城高速西北区域公交路线的设计,实例计算4成都市三环线-绕城高速西北区域公交,22,*,4,.1,问题描述,发展成都市经济文化的发展导致三环路以外居民不断普及,绕城高速区聚集了越来越多的企业、学校和商业网点。,1,2,3,经济的发展凸显了公共交通网络的不完善,成都市现有的公交线路覆盖范围主要涉及主城区,但郊区的公交线路和数量都很少,无法满足人们的出行要求。鉴于此,对未开通公交车的地区进行线路的优化是十分有必要的。,优化目标:明确选择成都三环线绕城高速的西北区域范围(必须包括大丰镇、安靖镇、犀浦镇和高新西区等重点区域),利用数学模型,在考虑人口密度、交通路况等基础上,对该区域的公交路线进行合理的规划设计,以满足居民在该区域内或区域外工作和生活的需要;,*4.1 问题描述发展成都市经济文化的发展导致三环路以外居,23,*,4.,2 调查分析,在成都三环线绕城高速的西北区域范围(包括大丰镇、安靖镇、犀浦镇和高新西区等重点区域)内:,一共收集到了通过该区域的公交车辆,38,辆(线路,76,条,往返线路可以不一致),在该区域范围内的公交站点,以及每条公交线路的总长、在区域范围内的实际长度和空间直线长度,同时也刻画了公交站点在区域范围内的相对位置。,注:在进行线路优化时,总的公交线路条数是不变的(76条),不添,加额外的公交线路。,*4.2 调查分析 在成都三环线绕城高速的西北区域范,24,时间代价矩阵,*,4.,3 模型建立,(1)数据准备,客流矩阵OD,距离矩阵,公交网络矩阵,2,1,路况矩阵,3,4,5,(2)公交空间网络解空间M的建立,记原来区域内的路线组成的交通网络为S,0,,根据S,0,的每一条线路在区域上的起,讫点,运用 前n条最短路算法,确定,S,0,的每一条路线的n条备用路线,建立区域内公交网络解空间M。记原来区域内的路线组成的交通网络为,S,0,,显然,S,0,属于M,所设计的新公交路线便从M中选取。(生成代码见附录2),时间代价矩阵*4.3 模型建立(1)数据准备客流矩,25,其中:,*,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 模型建立(3)目标函数的确定对于每一个交通,26,*,4.,3 模型建立,:第m条需换乘公交线路上相邻站点k与k+1之间的距离;,:第m条需换乘公交线路上换乘的次数。,转化为解空间的表达,客户评价内容,S,:解空间产生的一个公交路线网络,M,:公交路线网络解空间,P,ih,:第i条路线的原起始点,l,i,:解空间中第i条线路的一条备选路线,P,it,:第i条路线的原始终点,D,i,:第i条路的原始距离,Cover1,:交通网络的1级覆盖率,Cover2,:交通网络的2级覆盖率,*4.3 模型建立 :第m条需换乘公交线路,27,*,4 利用算法求解,第一步 确定
展开阅读全文