现代启发式算法-模拟退火算法.ppt

第8讲：现代启发式算法-模拟退火算法 现代启发式算法 别名 Meta-solution Modern heuristics 含义（其一） 启发性方法的有机结合 现代启发式算法 含义（其二） 模拟某些现象 Simulated Annealing法 (退火現象) Tabu Search （大脑的思考过程） Genetic Algorithm （遺伝现象） 含义（其三） 通过改变参数可以得到的各种“无限运行时间”近似算法（any time algorithms） 现代启发式算法探索机制： 集中化与多样化的对立与统一 集中化(intensification)：在良解的附近存在良解 (proximate optimality property)。基于这一性质， 在较好解的周围集中探索． 多様化(diversification) 避免在悪解的周围滞留及长时间无为探索，强制到迄今为止尚未探索的领域进行探索． 集中化 intensification 多样化 diversification 集中化与多样化的有机结合 Simulated Annealing 法 （模拟退火法） 随机局部探索法 + 系统地改变系统温度参数 集中化与多样化探索结合的一种模式 Simulated Annealing 法 Simulated Annealing 法  模拟金属退火(annealing)现象的逻辑 Simulated Annealing法 Simulated Annealing法 温度与接受概率的关系 Simulated Annealing 法 # 模拟退火法的参数 初始温度 ：适当的高温区域 冷却率 ：冷却（温度下降）的程序 终止条件 ：同一温度下探索的次数等 停机规则 ：停止探索的标准，如最低温度标准、最大无更新迭代次数等 冷却程序 对数冷却 (logarithmic cooling) 几何冷却 (geometric cooling) Simulated Annealing法的弱点 没有记忆探索后的解的集合的信息 存在相同解反复探索的可能性 又被称为blind search． 因其依赖于随机探索，存在着从局部最优解不能脱出的情况． 向最优解收敛速度较慢．(特别是在探索的后期空探索较多） Simulated Annealing法的应用 参见第8讲（2） * 跳离局部最优的两难选择 因为这附近良解比较多 再花点功夫找找看 这附近已经探索得差不多了 再到别的地方找找看 φ 多様化 集中化 现代启发式算法的核心问题 温度Ｔ高 温度 T＝0 逐渐冷却 高温期 逐渐冷却 低温期 0 Δ=f(y)-f(x) 低温 高温 接受概率 1 目标函数值的変化量 # 其它共性问题： 1）初始解的产生方式 2）邻域的定义 3）邻域解的选择 * * * * *