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

,*,書式設定,書式設定,第,2,第,3,第,4,第,5,第,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,法,温度高,温度,T,0,Simulated Annealing,法,模拟金属退火,(annealing),现象的逻辑,逐渐,冷却,Simulated Annealing,法,高温期,逐渐,冷却,低温期,Simulated Annealing法,温度,与接受概率的关系,0,=f(y)-f(x),低温,高温,接受概率,1,目标函数值的,変化量,Simulated Annealing 法,#,模拟退火法的参数,初始温度 ：适当的高温区域,冷却率 ：冷却（温度下降）的程序,终止条件 ：同一温度下探索的次数等,停机规则 ：停止探索的标准，如最低温度标准、最大无更新迭代次数等,#,其它共性问题：,1）初始解的产生方式,2）邻域的定义,3）邻域解的选择,对数,冷却,(logarithmic cooling),几何,冷却,(geometric cooling),冷却,程序,Simulated Annealing,法,的,弱点,没有记忆,探索,后,的解的集合的信息,存在相同解反复探索的可能性,又被称为,blind search,因其依赖于随机探索,，,存在着从局部最优解不能脱出的情况,向最优解收敛速度较慢,(,特别是在探索的后期空探索较多,）,Simulated Annealing,法,的应用,参见第,8,讲（,2,）,