数学建模竞赛SA参考.pptVIP

模擬退火法Simulated Annealing 历 史 模拟退火法（Simulated Annealing；SA） 最早的想法是由N.Metropolis等人于1953年所提出，在当时并没有受到重视。 直到1983年由Kirkpatrick et al.提出蒙地卡罗模拟（MonteCarlo Simulated）概念的随机搜寻技巧，利用此方法来求解的组合优化问题时，才使此算法受到重视。 简介 SA的观念主要来自于固体加热至一定的温度后，固体间的分子结构会被打散瓦解变为液态结构， 接着再对其降温过程加以控制，当完全冷却能使其分子在液态结构转变为固体结构时，重新排列成我们所预期的稳定状态 什么是退火 将工件加热到预定温度，保温一定的时间后缓慢冷却的金属热处理工艺。退火的目的在于：①改善或消除钢铁在铸造、锻压、轧制和焊接过程中所造成的各种组织缺陷以及残余应力，防止工件变形、开裂。②软化工件以便进行切削加工。③细化晶粒，改善组织以提高工件的机械性能。④为最终热处理（淬火、回火）作好准备 退火过程 简介 当目前状况是落于区域的最佳解时，模拟退火法会藉由重新加热的动作，透过随机的过程，以机率性质来接受一个暂劣解使其算法能跳脱目前的区域最佳解，而有机会能达到另一个最佳解 简介 模拟退火法采用Metropolis的 接受法则（Accepting Rule） 并用退火程序（Annealing Schedule）的参数算法的进行 而Metroplis接受法则的概念则在于能使求解时跳脱陷入区域最佳解 而模拟退火法能否成功应用在于退火程序的合理选择 简介 假设在搜寻最佳解的过程中 若令i代表在时间k的现有解，其成本为C(i) 下一个搜寻到的解，其成本为C(j) D E=C(j) - C(i)为两个解之间的成本差，如图所示 简介 当j的成本大于i时，SA会根据一机率决定是否要接受j来取代i成为时间k+1的新解 因此当搜寻到的新解比现有解之成本大时，会有一个机率值来决定是否接受交换。 SA基本上是以Metrolopis接受法则为基础，再配合退火程序，藉由温度逐渐的降低来条整是否接受成本较差新解的机率，当温度越低时，机率值也跟着降低 SA的运作流程 包含了四个基本要素 系统状态（Configuration）：即在某一个温度下，系统产生的初始解，并当作目前的现行解 搜寻法则（Search rule）：在退火的过程中，由目前系统状态经由随机扰动而产生变化跳至另一种状态 一般而言，SA较常用的有梯度搜寻法（Gradient Type） 和迭代改善法（IterativeImprovement） SA的运作流程 包含了四个基本要素 成本函数（Cost Function）：用来衡量某一系统状态下之能量函数 退火程序（Annealing Process）：退火程序中包含的参数有初始温度、降温机制、冷却率和终止温度 在退火的过程中，在温度高的时候，虽然是较差的目标值，但有可能被接受当成目前的目标值，但随着温度慢慢的降低，接受较差目标值的机率逐渐降低 SA 的運作流程 No 退火程序之参数设定 初始温度 为了防止落入区域极小的陷阱，在模拟退火法中初始温度的设定必须使得大部份的转移均可被接受 初始温度的设定可以是一个定值， 如Kirkpatrick等学者( 1983 )将初始温度定为10 Heragu以及Alfa ( 1992 )将初始温度定为999 初始温度亦可由所设定之移转接受机率的门坎值P0来反推求得，如Kouvelis以及Chiang( 1992 )将初始温度定为 退火程序之参数设定 终止条件 终止条件最简单的设定方式是指定一个固定的终止温度，一般是一个接近于零较小的数，或是限制降温次数不超过预定值 其它方式则为检查所求得的解是否有所改善，如在1992年Kouvelis与Chiang设定若经过数次降温后所得的解仍未改善或移转接受比率低于一个定值，则将终止模拟退火法的运算。 退火程序之参数设定 降温时机 降温时机乃指马可夫链长度，亦即在同一温度下所应反复进行Metropolis演算的次数 最直接的方式是设定一个固定长度，但此长度与问题规模有关，如在1992年Kouvelis与Chiang将其设定为邻近解个数之比率。 此外亦可设定降温时机为移转接受次数已达一定值，如Heragu以及Alfa（1992）所使用的方式便是 但此一方式当温度降至很低时，移转接受之机率将会很小，进而导致马可夫链过长，因此必须同时限定马可夫链的长度，以免造成求解时间过长 退火程序之参数设定 温度控制参数 温度控制参数是指在演算过程中，若达到降温时机时，由目前温度减少到次一温度的下降比率 若温度控制参数愈小，则温度下降的差距愈大，那么会造成在次一温度达成均衡所需的马可夫链长度愈长，使得求解时间