模拟退火算法PPT.ppt

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