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

1、大连海事大学现代优化技术第8讲：现代启发式算法之模拟退火算法,1,现代优化技术,第8讲：现代启发式算法之模拟退火算法,大连海事大学现代优化技术第8讲：现代启发式算法之模拟退火算法,2,现代启发式算法之模拟退火算法,别名 Meta-solution Modern heuristics 含义（其一） 启发式方法的有机结合,大连海事大学现代优化技术第8讲：现代启发式算法之模拟退火算法,3,现代启发式算法之模拟退火算法,含义（其二） 模拟某些现象 Simulated Annealing法 (退火現象) Tabu Search （大脑的思考过程） Genetic Algorithm （遺伝现象） 含义（

2、其三） 通过改变参数可以得到的各种“无限运行时间”近似算法（any time algorithms）,大连海事大学现代优化技术第8讲：现代启发式算法之模拟退火算法,4,现代启发式算法之模拟退火算法,现代启发式算法探索机制： 集中化与多样化的对立与统一,集中化(intensification)：在良解的附近存在良解 (proximate optimality property)。基于这一性质， 在较好解的周围集中探索 多様化(diversification) 避免在悪解的周围滞留及长时间无为探索，强制到迄今为止尚未探索的领域进行探索,逃离局部最优的两难选择,大连海事大学现代优化技术第8讲：现代启

3、发式算法之模拟退火算法,5,现代启发式算法之模拟退火算法,集中化 intensification,大连海事大学现代优化技术第8讲：现代启发式算法之模拟退火算法,6,现代启发式算法之模拟退火算法,多样化 diversification,大连海事大学现代优化技术第8讲：现代启发式算法之模拟退火算法,7,现代启发式算法之模拟退火算法,集中化与多样化的有机结合,现代启发式算法的核心问题,大连海事大学现代优化技术第8讲：现代启发式算法之模拟退火算法,8,现代启发式算法之模拟退火算法,Simulated Annealing 法 （模拟退火法）,随机局部探索法 + 系统地改变系统温度参数 集中化与多样化探索

4、结合的一种模式,大连海事大学现代优化技术第8讲：现代启发式算法之模拟退火算法,9,现代启发式算法之模拟退火算法,Simulated Annealing Algorithm,大连海事大学现代优化技术第8讲：现代启发式算法之模拟退火算法,10,现代启发式算法之模拟退火算法,Simulated Annealing Algorithm,模拟金属退火(annealing)现象的逻辑,大连海事大学现代优化技术第8讲：现代启发式算法之模拟退火算法,11,现代启发式算法之模拟退火算法,Simulated Annealing Algorithm,大连海事大学现代优化技术第8讲：现代启发式算法之模拟退火算法,12

5、,现代启发式算法之模拟退火算法,Simulated Annealing Algorithm,大连海事大学现代优化技术第8讲：现代启发式算法之模拟退火算法,13,现代启发式算法之模拟退火算法,温度与接受概率的关系,0,=f(y)-f(x),低温,高温,接受概率,1,目标函数值的変化量,大连海事大学现代优化技术第8讲：现代启发式算法之模拟退火算法,14,现代启发式算法之模拟退火算法,Simulated Annealing,# 模拟退火法的参数 初始温度 ：适当的高温区域 冷却率 ：冷却（温度下降）的程序 终止条件 ：同一温度下探索的次数等 停机规则 ：停止探索的标准，如最低温度标准、最大无更新迭代次数等,# 其它共性问题： 1）初始解的产生方式 2）邻域的定义 3）邻域解的选择,大连海事大学现代优化技术第8讲：现代启发式算法之模拟退火算法,15,现代启发式算法之模拟退火算法,对数冷却 (logarithmic cooling) 几何冷却 (geometric cooling),冷却程序,大连海事大学现代优化技术第8讲：现代启发式算法之模拟退火算法,16,现代启发式算法之模拟退火算法,Simulated Annealing弱点,没有记忆探索后的解的集合的信息 存在相同解反复探索的可能性 又被称为blind search 因