第五章--模拟退火算法-(新).ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1,第五章模拟退火,2,第五章 模拟退火,一,.,导言,二,.,退火过程和,Bolzman,方程,三,.SA,的算法构造及步骤,四,.,计算举例,五,.SA,的收敛性分析,六,.SA,的应用举例,3,模拟退火的产生,(SA),1953,年,Metropolis,提出原始的,SA,算法，未引,起反响,1982,年,Kirkpatrick,提出现代的,SA,算法，得到广泛的应用,一,.,导言,（,1,）,4,基本思想,模拟热力学当中的退火过程,退火过程：,物体：高温低温,高能状态低能状态,一,.,导言,（,2,）,缓慢下降,5,淬火：,快速冷却，使金属处于高能状态，较硬易断,退火：,缓慢冷却，使金属处于低能状态，较为柔韧,一,.,导言,（,3,）,6,模拟退火在,SA,中的应用,在,SA,中将目标函数作为能量函数,模拟：,初始高温 温度缓慢下降 终止在低温,这时能量函数达到极小，目标函数最小,一,.,导言,（,4,）,7,热力学中的退火过程,变温物体缓慢降温从而达到分子之间能量最,低的状态,二,.,退火过程和,Bolzman,方程,（,1,）,8,二,.,退火过程和,Bolzman,方程,（,2,）,9,Bolzman,方程,二,.,退火过程和,Bolzman,方程,（,3,）,10,温度 对 的影响,当 很大时，,，各状态的概率几乎相等,SA,开始做广域搜索，随着温度的下降 差别,扩大,二,.,退火过程和,Bolzman,方程,（,4,）,11,当 时，,与 的小差别带来 和 的巨大差别,例如：,=90,，,=100,，,二,.,退火过程和,Bolzman,方程,（,5,）,12,当,=100,时,二,.,退火过程和,Bolzman,方程,（,6,）,13,当,=1,时,此时,结论,:,时，以概率,1,趋于最小能量状态,二,.,退火过程和,Bolzman,方程,（,7,）,14,SA,的模拟要求,初始温度足够高,降温过程足够慢,终止温度足够低,三,.SA,的算法构造及步骤,（,1,）,15,问题的描述及要素,三,.SA,的算法构造及步骤,（,2,）,16,SA,的计算步骤,初始化,任选初始解,给定初始温度 ，终止温度 ，令迭代指标 。,注：选择 时，要足够高，使,随机产生一个邻域解，计算目标值增量,三,.SA,的算法构造及步骤,（,3,）,17,若 转步,(j,比,i,好无条件转移,),；否则产生,(j,比,i,好，有条件转移,),。,注：高时，广域搜索；低时，局域搜索,若达到热平衡,(,内循环次数大于,),转步,，否则转步。,三,.SA,的算法构造及步骤,（,4,）,18,降低 ，若 停止，否则转步。,注：降低 的方法有以下两种,流程框图见下页,三,.SA,的算法构造及步骤,（,5,）,19,内循环,产生,开始,停止,Y,N,Y,N,，降温,外循环,设定,产生,计算,Y,Y,N,N,20,问题的提出,单机极小化总流水时间的排序问题,四个工作：，求,的最优顺序。,四,.,计算举例,（,1,）,21,预备知识：按,SPT,准则，最优顺序为,3-1-4-2,四,.,计算举例,（,2,）,22,用,SA,求解这个问题,状态表达：顺序编码,邻域定义：两两换位定义为邻域移动,解：,设,降温过程定义为,初始解：,i=1-4-2-3,四,.,计算举例,（,3,）,23,注释：,无条件转移；,为有条件转移；,在中，虽然目标值变坏，但搜索范围变大；,是随机产生的,四,.,计算举例,（,4,）,24,注释：,有条件转移；,为无条件转移；,在中，停在,4-3-1-2,状态，目标值仍为,109,；,四,.,计算举例,（,5,）,25,注释：,无条件转移；,在中，停在,3-1-4-2,状态，目标值仍为,92,；,SA,没有历史最优，不会终止在最优解，故算法一,定要保持历史最优。,四,.,计算举例,（,6,）,26,SA,终止在最优解上的条件：,初始温度足够高,热平衡时间足够长,终止温度足够低,降温过程足够慢,以上条件实际中很难满足，所以只能记录历,史最优解。,四,.,计算举例,（,7,）,27,SA,特点：编程最容易，理论最完善。下面基于,Markov,过程分析收敛性。,四,.,计算举例,（,8,）,28,Markov,过程的基本概念,举例说明：盲人一维游走、醉汉或青蛙在,3,块石,头上随机跳动，这,3,中状况可用来说明这个问,题，他们行动的共同特点是无记忆性。,五,.SA,的收敛性分析,（,1,）,29,基本概念,状态：,处于系统中的一种特定状态表达。,状态转移概率：,从状态,i,转移到状态,j,的可能性。,无后效应：,到一个状态后，决策只与本状态有关，与以,前的历史状态无关。,五,.SA,的收敛性分析,（,2,）,30,以青蛙跳动为例说明状态转移概率,用石头唯一的表达青蛙所处的状态，假设青蛙,跳动具有无后效应的特点。,五,.SA,的收敛性分析,（,3,）,1/3,1/3,1/4,1/4,1/2,1/2,青蛙跳动图示,状态转移概率矩阵：,1/3,1/4,1/4,31,t,时刻处在各状态的概率向量,是行向量，假设系统在,t+1,时达到稳态，则,五,.SA,的收敛性分析,（,4,）,32,解方程组：,可得结果：,可见青蛙是跳到第三块石头上的机会多一些,五,.SA,的收敛性分析,（,5,）,33,SA,的收敛性分析,问题：,将状态按目标值进行升序编号，,即,五,.SA,的收敛性分析,（,6,）,34,状态间的转移概率,设 为,i,选,j,为邻域点时，,i j,的转移概率,五,.SA,的收敛性分析,（,7,）,35,设是系统处于状态,i,时选择,j,为邻域移动点,的概率，为状态,i,的邻域点的个数，则,则状态,i,到状态,j,的转移概率为,五,.SA,的收敛性分析,（,8,）,36,当,T,k,很大时，则状态转移矩阵为：,分两种情况讨论：,五,.SA,的收敛性分析,（,9,）,37,当,五,.SA,的收敛性分析,（,10,）,38,当,状态,1,是“捕捉的”（任何状态到,1,状态后都无法,转出）即青蛙跳到石头,1,上无法跳出。,五,.SA,的收敛性分析,（,11,）,39,推理证明：,证毕,即,SA,将以概率,1,停在状态（石头）,1,上。,五,.SA,的收敛性分析,（,12,）,40,定理：当,P,对称时，当达到热平衡时，对所有,有：,定理证明见下页。,五,.SA,的收敛性分析,（,13,）,41,定理证明：,当达到热平衡时有,五,.SA,的收敛性分析,（,14,）,42,问题：成组技术中加工中心的组成问题,设有,m,台机器，要组成若干个加工中心，每个,加工中心可有最多,q,台、最少,p,台机器，有,n,种,加工工作要在这些机器上加工。,如何组织加工中心，可使总的各中心的机器相,似性最好。,六,.SA,的应用举例,（,1,）,43,六,.SA,的应用举例,（,2,）,44,六,.SA,的应用举例,（,3,）,45,六,.SA,的应用举例,（,4,）,46,所有相似的机器放在同一个中心，极大化成组相似性,指定唯一性，一个机器只能放一个中心,每一个中心的机器数小于,q,台,每一个中心的机器数至少有,p,台,六,.SA,的应用举例,（,5,）,47,用,SA,求解,六,.SA,的应用举例,（,6,）,48,六,.SA,的应用举例,（,7,）,不够时的惩罚,多了时的惩罚,49,六,.SA,的应用举例,（,8,）,控制参数,50,编程最容易,大时，广域搜索性能好,小时，局域搜索性能好,理论上停止在最优解上，但实际上很难做到,SA,是达优性较差的算法,七,.,学习,SA,的几点体会,（,1,）,