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