模拟退火算法 第一节ppt课件

.,模拟退火(simulatedannealing)算法是局部搜索算法的扩展它源于对固体退火过程的模拟;采用Metropolis接受准则；并用一组称为冷却进度表的参数控制算法进程，使算法在多项式时间里给出一个近似最优解,模拟退火算法最早的思想由Metropolis在1953年提出，Kirkpatrick在1983年成功地应用在组合最优化问题中,第2章模拟退火算法,.,一固体退火过程,退火是一种物理过程，固体退火是先将固体加热至熔化，再徐徐冷却使之凝固成规整晶体的热力学过程,退火过程中，系统在每一温度下达到平衡态，系统状态的分布满足一定的概率分布，即在温度T，系统达到平衡态后，分子停留在状态r满足波兹曼(Boltzmann)概率分布,2.1模拟退火算法及模型,.,其中，E(r)为状态r的能量，kB0为波兹曼常数，,为分子能量的一个随机变量，,称为波兹曼因子Z(T)为概率分布的标准化因子，,先研究由(2.1)确定的函数随T变化的趋势选定两个能量E1，则新状态j作为重要状态，否则舍去若新状态j是重要状态，就以j取代i成为当前状态，否则仍以i为当前状态，再重复以上新状态产生过程在大量固体状态的变换后，系统趋于能量较低的平衡状态，固体状态的概率分布趋于(2.1)式的Boltzmann概率分布,.,由()式可知，高温下可接受与当前状态能差较大的新状态为重要状态而在低温下只能接受与当前状态能差较小的新状态为重要状态.这与不同温度下热运动的影响完全一致在温度趋与零时，就不能接受任一EjEi的新状态j了,上述接受新状态的准则称为Metropolis准则，相应的算法称为Metropolis算法这种算法的计算量显著减少,.,三模拟退火算法,对固体退火过程的研究给人们以新的启示1982年，Kirkpatrick等首先意识到固体退火过程与组合优化问题之间存在的类似性，Metropolis等对固体在恒定温度下达到热平衡的模拟也给他们以启迪：应该把Metropolis准则引入到过程中来最终他们得到一种对Metropolis算法进行迭代的组合优化算法，这种算法模拟固体退火过程，称之为模拟退火算法,.,我们可以将组合优化问题同金属物体退火进行类比：,组合优化问题,金属物体,假设算法用以解决如下组合优化问题：,解,费用(目标)函数,最优解,状态,能量,能量最低的状态,.,模拟退火算法,Step1任选一个初始解x0；xi:=x0；k:=0；,Step2若在该温度达到内循环条件，则到step3;,Step3tk+1:=d(tk)；k:=k+1；若满足停止条件，终,t0:=tmax；(初始温度)；,否则，从邻域N(xi)中随机选一xj，计算,fij=f(xj)f(xi)；若fij0，则xi:=xj；否则若exp(fij/tk)random(0,1)时，则xi:=xj；重复step2；,止计算；否则，回到step2,产生一个0与1之间的一个随机数,.,(1)随算法进程递减其值的控制参数t担当固体退火过程中的温度T的角色,(2)对t的每一取值，算法持续进行“产生新解判断接受舍弃”的迭代过程就对应着固体在某一恒定温度下趋于热平衡的过程也就是执行了一次Metropolis算法模拟退火算法从某个初始解出发，经过大量解的变换后，可以求得给定控制参数值时组合优化问题的相对最优解然后减小t的值，重复执行Metropolis算法，就可以在t趋于零时，最终求得整体最优解,(3)由于退火必须“徐徐”降温，t也必须缓慢衰减，才能确保模拟退火算法最终趋于组合优化问题的整体最优解集,.,(4)模拟退火算法依据Metropolis准则接受新解，因此除接受优化解外，还在一个限定范围内接受恶化解，这正是模拟退火算法与局部搜索算法的本质区别所在开始时t值大，可能接受较差的恶化解；随着t的减小，只能接受较好的恶化解；最后在t值趋于零时，就不再接受任何恶化解了这就使算法既可以从局部最优的陷阱中跳出，更有可能求得组合优化问题的整体最优解；又不失简单性和通用性因此对大多数组合优化问题而言，模拟退火算法要优于局部搜索算法,.,模拟退火算法的数学模型可以描述为：在给定邻域结构后，模拟退火过程是从一个状态到另一个状态不断地随机游动我们可用马尔可夫链描述这一过程当温度t为一确定值时，两个状态的转移概率定义为：,Gij(t)称为从i到j的产生概率，Gij(t)表示在状态i时，j状态被选取的概率比较容易理解的是j是i的邻居，如果在邻域中等概率选取，则j被,.,选中的概率为,Aij(t)称为接受概率，Aij(t)表示在状态i产生j后，接受j的概率，如在模拟退火算法中接受的概率是,.,(2.5),(2.6),(2.7)为模拟退火算法的主要模型模拟退火算法主要可以分为两类第一类为齐次算法，在(2.5)中对每一个固定的t，计算对应的马尔可夫链变化，直至达到一个稳定状态，然后再使温度下降第二类是非齐次算法，由一个马尔可夫链组成，要求在两个相邻的转移中，温度t是下降的,.,描述模拟退火算法过程的马尔可夫链应满足下列条件：,(1)可达性无论起点如何，任何一