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

1、现代优化技术现代优化技术第第8 8讲：现代启发式算法之模拟退火算法讲：现代启发式算法之模拟退火算法现代启发式算法之模拟退火算法现代启发式算法之模拟退火算法 别名别名 Meta-solutionMeta-solution Modern heuristicsModern heuristics 含义其一）含义其一） 启发式方法的有机结合启发式方法的有机结合现代启发式算法之模拟退火算法现代启发式算法之模拟退火算法 含义其二）含义其二） 模拟某些现象模拟某些现象 Simulated AnnealingSimulated Annealing法法 ( (退火退火現現象象) ) Tabu Search Tab

2、u Search （大脑的思考过程）（大脑的思考过程） Genetic Algorithm Genetic Algorithm （遺伝遺伝现象）现象） 含义其三）含义其三） 通过改变参数可以得到的各种通过改变参数可以得到的各种“无限运无限运行时间行时间近似算法近似算法any time any time algorithmsalgorithms）现代启发式算法之模拟退火算法现代启发式算法之模拟退火算法现代启发式算法探索机制：现代启发式算法探索机制： 集中化与多样化的对立与统一集中化与多样化的对立与统一 集中化集中化(intensification)：在良解的附近存在良解：在良解的附近存在良解 (

3、proximate optimality property)。基于这一性质，。基于这一性质， 在较好解的周围集中探在较好解的周围集中探索索 多様化多様化(diversification) 避免在悪解的周围滞留及长时间无为探索，强制到迄今为止尚未避免在悪解的周围滞留及长时间无为探索，强制到迄今为止尚未探索的领域进行探索探索的领域进行探索现代启发式算法之模拟退火算法现代启发式算法之模拟退火算法集中化集中化 intensification intensification因为这附近良解比较多因为这附近良解比较多再花点功夫找找看再花点功夫找找看现代启发式算法之模拟退火算法现代启发式算法之模拟退火算法多样

4、化多样化 diversification diversification这附近已经探索得差不多了这附近已经探索得差不多了再到别的地方找找看再到别的地方找找看现代启发式算法之模拟退火算法现代启发式算法之模拟退火算法 集中化与多样化的有机结合集中化与多样化的有机结合多多様様化化集中化集中化现代启发式算法之模拟退火算法现代启发式算法之模拟退火算法 Simulated Annealing Simulated Annealing 法法 （模拟退火法）（模拟退火法） 随机局部探索法随机局部探索法 + + 系统地改变系统温度参数系统地改变系统温度参数 集中化与多样化探索结合的一种模式集中化与多样化探索结合的

5、一种模式现代启发式算法之模拟退火算法现代启发式算法之模拟退火算法 Simulated AnnealingAlgorithm现代启发式算法之模拟退火算法现代启发式算法之模拟退火算法温度高温度高温度温度 T T0 0Simulated Annealing AlgorithmSimulated Annealing Algorithm 模拟金属退火模拟金属退火(annealing)(annealing)现象的逻辑现象的逻辑逐渐冷却逐渐冷却现代启发式算法之模拟退火算法现代启发式算法之模拟退火算法Simulated Annealing AlgorithmSimulated Annealing Algori

6、thm高温期高温期逐渐冷却逐渐冷却低温期低温期现代启发式算法之模拟退火算法现代启发式算法之模拟退火算法 Simulated Simulated AnnealingAnnealingAlgorithmAlgorithm现代启发式算法之模拟退火算法现代启发式算法之模拟退火算法温度与接受概率的关系温度与接受概率的关系0 0=f(y)-f(x)=f(y)-f(x)低温低温高温高温接受概率接受概率1 1现代启发式算法之模拟退火算法现代启发式算法之模拟退火算法 Simulated Annealing Simulated Annealing # # 模拟退火法的参数模拟退火法的参数初始温度初始温度 ：适当的

7、高温区域：适当的高温区域冷却率冷却率 ：冷却温度下降的程序：冷却温度下降的程序终止条件终止条件 ：同一温度下探索的次数等：同一温度下探索的次数等停机规则停机规则 ：停止探索的标准，如最低温度标准、最大：停止探索的标准，如最低温度标准、最大无更新迭代次数等无更新迭代次数等0TtTg,maxtminT现代启发式算法之模拟退火算法现代启发式算法之模拟退火算法 对数冷却对数冷却 (logarithmic cooling) (logarithmic cooling) 几何冷却几何冷却 (geometric cooling) (geometric cooling) 冷却程序冷却程序现代启发式算法之模拟退火算法现代启发式算法之模拟退火算法Simulated AnnealingSimulated Annealing弱点弱点 没有记忆探索后的解的集合的信息没有记忆探索后的解的集合的信息 存在相同解反复探索的可能性存在相同解反复探索的可能性 又被称为又被称为blind searchblind sear