大连海事大学《现代优化技术》第8讲：现代启发式算法之模拟退火算法.ppt

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