CH4 模拟退火算法.ppt

模拟退火算法Simulated Annealing 简介 模拟退火法（ Simulated Annealing；SA） 最早的想法是由 N.Metropolis 等人于1953 年所提出，在当时并沒有受到重视 直到1983 年由Kirkpatrick et al. 提出Monte Carlo（MonteCarlo Simulated）概念的随机有哪些信誉好的足球投注网站技巧，利用此方法来求解的组合最佳化问题时，才使此算法受到重视。 简介 SA的概念主要来自于固体加热至一定的温度后，固体间的分子结构会被打散瓦解变为液态结构 接着再对其降温过程加以控制，当完全冷却能使其分子在液态结构转变为固体结构时，重新排列成我们所预期的稳定状态 简介 当目前状况是落于区域的最佳解时，模拟退火法会由重新加热的动作，透过随机的过程，以概率性质来接受一个暂劣解使其算法能跳脱目前的区域最佳解（即局部最优），而有机会能达到另一个最佳解. 简介 模拟退火法组成 接受法则（Accepting Rule） 并用退火程序（Annealing Schedule）的参数演算法进行 而Metroplis接受法则的概念则在于能使求解时跳脱陷入区域最佳解 而模拟退火法能否成功应用在于退火程序的合理选择 简介 假设在搜寻最佳解的过程中 若令i 代表在时间k 的现有解，其成本为C(i) 下一个搜寻到的解，其成本为C(j) D E = C(j) - C(i)为两个解之间的成本差，如图所示 简介 当j 的成本C(j) 大于i的成本C(i)时，SA 会根据一概率决定是否要接受j來取代i 成为时间k+1 的新解： 因此当搜寻到的新解比现有解之成本大时，会有一个概率值来决定是否接受交换。 SA 基本上是以Metrolopis 接受法则为基础，再配合退火程序，由温度逐渐的降低来调整是否接受成本较差新解的概率，当温度越低时，概率值也跟着降低. b即为Boltzmann常数 SA 的基理分析 四个基本要素 系统状态（Configuration）：即在某一个温度下，系统产生的初始解，并当作目前的现行解 搜寻法则（Search rule）：在退火的过程中，由目前系统状态经由随机扰动而产生变化跳至另一种状态 一般而言，SA 较常用的有梯度搜寻法（Gradient Type） 和叠代改善法（ Iterative Improvement） 四个基本要素 成本函数（Cost Function）：用来衡量某一系统状态下之能量函数 退火程序（Annealing Process）：退火程序中包含的参数有初始温度、降温机制、冷却率和终止温度 在退火的过程中，在温度高的时候，虽然是较差的目标值，也有可能被接受成目前的目标值，但随着温度慢慢的降低，接受较差目标值的概率逐渐降低. SA的基本步骤 No 退火程序的参数设定 初始温度 为了防止落入局部最小的陷阱，在模拟退火法中初始温度的设定必须使得大部份的转移均可被接受 初始温度的设定可以是一个定值 如Kirkpatrick等学者 ( 1983 ) 将初始温度定为10 Heragu 以及 Alfa ( 1992 )将初始温度定为999 初始温度也可由所设定的转移接受概率的门槛值P0来反推求得，如Kouvelis 以及 Chiang( 1992 )将初始温度定为