很经典模拟退火算法

,单击以编辑母片标题样式,单击以编辑母片,第二层,第三层,第四层,第五层,*,*,单击以编辑母片标题样式,单击以编辑母片,第二层,第三层,第四层,第五层,*,*,Simulated Annealing,（模拟退火法）,报告人,:,1,大纲,简介,攀登算法,模拟退火法,v.s. Hill Climbing,仿真退火法的检测标准与流程,模拟退火法的考虑因素,其他的问题,提高效能与算法的修正,结论,2,简介,仿真退火法是仿真冷却晶体的过程,。,最早是由,Metropolis,、,Rosenbluth,等人,在,1953,年提出,。,1983,年，,Kirkpatrick,等人将其运用在求优化的问,题,、定位及图分割等问题上,，,它是蒙地卡罗算法的推广,。,3,攀登算法,(,Hill Climbing),攀登算法（,Hill-climbingAlgorithm,）是一种迭代增进的算法，它用单一解在解空间作搜寻，并在每一次迭代中，在目前解的邻近解空间选择出一个邻近解。,当邻近解的目标函值比目前解的目标函值的佳时，就以邻近解取代目前解；否则，就重新在目前解的邻近解空间选择一个邻近解。,4,模拟退火法,v.s. Hill Climbing,HillClimbing,是挑选邻近点中最好的点，但这样会有局部最大值的问题。,仿真算法是随机数找寻邻近的点。,若找到的点比立足点好，则取之。,否则依照机率决定是否取之。,5,模拟退火法的程,(1/2),需先设定一些，。接着随机产生一个初始的目前解 ，并计算他的目标函值 。,以目前解为中心对解空间做随机扰动，产生一个扰动解 ，其目标函值为,。,接受，则以该扰动解取代目前解作为该次迭代的解。,6,模拟退火法的检测标准,根据热力学定律，在温度为,t,的情况下，能量差所表现的机率如下：,P(E)=exp(-E / kt),k,是,Boltzmanns Constant,转换到模拟退火法，则变成,P=exp(-c / t)r,c,是评估函数的差,r,是,01,之间的随机数,7,模拟退火法的程,(2/2),假设所求解的问题是目标函最小化问题 ，,，,则透过机函接受 为新解,。,接着判断是否满足温条件，是，则透过却机制温， ， 。,反之，维持目前温。之后判断是否达到终止条件，,如达到设定的迭代次或是续几次迭代目前解再改变时,。,8,模拟退火法的程图,初使化设定,随机产生一个初始解,扰动产生一个新解,是否接受,?,修改目前解,降温,缩减温度,是否达到中止条件,?,最佳解,No,Yes,Yes,Yes,No,No,9,冷却排程,(1/4),初始温度（,Starting Temperature,）,温度要够高才能移动到任何的状态,。,温度不能太高，否则会导致在一段时间内皆用随机数在凑解答,。,如果可以知道检测函数的最大值就可以找到最好的初始温度,。,快速提高温度，然后又快速降温，直到有,60%,的最差解被接受,。,快速提高温度，但慢慢降温，并定出适当比例最差解的接受度,。,10,冷却排程,(2/4),最终温度（,Final Temperature,）,通常是零，但会耗掉许多模拟时间,。,温度趋近于零，其周遭状态几乎是一样的,。,所以寻找一个低到可接受的温度,。,11,冷却排程,(3/4),温度减少（,Temperature Decrement,）,每次降低温度的差距以及在同一温度反复寻找最适解会导致指数般成长的搜寻空间,。,1.,以线性降温来说,Temp=Temp-x,2.,以几何观念来看,Temp=Temp*y,(y,约,0.80.99,为佳,),12,冷却排程（,4/4,）,反复次数（,Iterations at each Temperature,）,一般会定一个常数,。,Lundy,认为只要反复一次，但每次降低的温度差距必须非常小,。,Temp=Temp / (1+a*Temp),a,是非常小的值,低温需要较多反复次数以避免找到局部最大值，但高温则可减少次数,。,13,模拟退火法的程图,初使化设定,随机产生一个初始解,扰动产生一个新解,是否接受,?,修改目前解,降温,缩减温度,是否达到中止条件,?,最佳解,No,Yes,Yes,Yes,No,No,14,扰动方式,(1/2),模拟退火法以扰动的机制产生一个解，我们称此解为扰动解,，,在以机函判断是否接受此扰动解为此次迭代的新解。,被接受，就再以扰动重新产生一个扰动解，并以机函重新判断。每代重复以上的步骤，直到接受为此次迭代的新解为止。,15,扰动方式,(2/2),扰动的作法就是以目前解为中心，对部分或整个解空间随机取样一个解。,16,模拟退火法的程图,初使化设定,随机产生一个初始解,扰动产生一个新解,是否接受,?,修改目前解,降温,缩减温度,是否达到中止条件,?,最佳解,No,Yes,Yes,Yes,No,No,17,机函,(1/3),模拟退火法用机函有机的接受较差的扰动解为新解，使其避免传统梯搜寻法,（,GradientSearch,）往往陷入区域解的缺点，而使模拟退火法有机会跳脱区域解，往全局最佳解收敛。,18,机函,(2/3),一般的机函方程式如下,:,为目前温。当 ， ；当,会是之后随机产生一个介于,0,到,1,间的一个小于,1,大於,0,的值。,随机值,r,与 比較,，若,，,则接收扰动解,；,反之，则接受。,19,机函,(3/3),当 越高或 越小时，则 越大,，,相对的扰动解被接受成新解的机越高。,因此,会随着迭代次的增加而逐渐下，所以较差的扰动解被接受成新解的机会也随着 的下而越越小。,所以当迭代到最后因为温 已到达低点，这时系统只会接受较佳的扰动解为新解。,而扰动解 小于目前解 则一定接受为新解，但是,则接受为新解的机随着 的变大而越小。,20,模拟退火法的程图,初使化设定,随机产生一个初始解,扰动产生一个新解,是否接受,?,修改目前解,降温,缩减温度,是否达到中止条件,?,最佳解,No,Yes,Yes,Yes,No,No,21,其他的问题,(1/4),价值函数（,Cost Function,）,用来评估解的质量,。,Delta Evaluation,求某解与其邻近点的价值,。,Partial Evaluation,不需额外产生的计算结果就可以判断出来解的价值,。,22,其他的问题（,2/4,）,价值函数（,Cost Function,）,Hard Constraints,在不违背合适解的条件下，所提出的强制规定,。,Soft Constraints,无论这种解是否违背条件，都算是合适解,。,HardConstraints,会给一个很大的,weight,SoftConstraints,则是情况给予不同的,weight,23,其他的问题（,3/4,）,邻近点的结构（,Neighborhood Structure,）,有些结构是对称性的，即可以从,A,状态到,B,状态，也可以从,B,状态到,A,状态,。,条件较弱（结构较松散）的有稳定的收敛,。,条件定的好，就可以使得在各种状态之下都可以到达另一种状态,。,24,其他的问题（,4/4,）,所有解的空间（,The Solution Space,）,空间小，可以展开搜寻,。,若允许不合适的解也存在的话就会加大搜寻空间,。,我们想办法取一个适当值，期望能快速搜寻，又可避免在不利的情况下没有好的进展,。,25,提高效能,初始化（,Initialization,）,将原本用随机数取初始值的方式改为尽可能找出一有用的起始点,。,结合（,Combine,）,可将仿真退火法配合其他算法应用于问题上。,26,算法修正,(1/2),可接受的机率（,Acceptance Probability,）,少计算,exponential,会加快速度,建立一个可查询各种值的,table,冷却（,Cooling,）,花一些时间找寻最佳温度（包括最终温度、温差）,27,算法修正（,2/2,）,邻近点（,Neighborhood,）,对于不好的邻近点给予一个惩罚值,。,价值函数（,Cost Function,）,利用其他算法的价值函数来做计算,。,28,结论,模拟退火法已经证明可能收敛出最好解。,要花较多的时间去搜寻各种解。,可将仿真退火法配合其他算法应用于问题上。,已有学者发展出导引模拟退火法，因此可尝试使用新的算法去求解。,29,The End,Thanks for everyone listening,30,