模拟退火算法研究.ppt

《模拟退火算法研究.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、模拟退火算法原理与应用报告提纲一、模拟退火算法概述二、模拟退火算法特点及改进三、模拟退火算法的主要应用一、模拟退火算法概述1、物理退火2、模拟退火1、物理退火退火是将工件加热到预定温度，保温一定的时间后缓慢冷却的金属热处理工艺。退火的目的在于：①改善或消除钢铁在铸造、锻压、轧制和焊接过程中所造成的各种组织缺陷以及残余应力，防止工件变形、开裂。②软化工件以便进行切削加工。③细化晶粒，改善组织以提高工件的机械性能。④为最终热处理（淬火、回火）作好组织准备。物理退火Heheatsthemetal,thenslowlycoolsitashehammersthebladein

2、toshape.?Ifhecoolsthebladetooquicklythemetalwillformpatchesofdifferentcomposition;?Ifthemetaliscooledslowlywhileitisshaped,theconstituentmetalswillformauniformalloy.2、模拟退火模拟退火（SimulatedAnnealing，简称SA）是一种通用概率算法，用来在一个大的搜寻空间内找寻命题的最优解。“模拟退火”的原理和金属退火的原理近似。模拟退火模拟退火粒子状态解能量最低态问题最优解熔解过程设定初温等温过程

3、采样过程冷却控制参数下降能量目标函数物理退火模拟退火二、模拟退火算法原理及改进1、模拟退火算法原理2、模拟退火算法要素3、模拟退火算法特点及改进1、模拟退火算法原理模拟退火算法可以分解为解空间、目标函数和初始解三部分。模拟退火的基本思想:(1)初始化：初始温度T(充分大)，初始解状态S(是算法迭代的起点)，每个T值的迭代次数L(2)对k=1，……，L做第(3)至第6步：(3)产生新解S′。(4)计算增量Δt′=C(S′)-C(S)，其中C(S)为评价函数(5)若Δt′<0则接受S′作为新的当前解，否则以概率exp(-Δt′/T)接受S′作为新的当前解.(6)如果满足

4、终止条件则输出当前解作为最优解，结束程序。终止条件通常取为连续若干个新解都没有被接受时终止算法。(7)T逐渐减少，且T->0，然后转第2步。模拟退火算法原理1)随机产生一个初始解x0，令xbest＝x0，并计算目标函数值E(x0);2)设置初始温度T(0)=To，迭代次数i=1;3)DowhileT(i)>Tmin1)forj=1~k2)对当前最优解xbest按照某一邻域函数，产生一新的解xnew。计算新的目标函数值E(xnew)，并计算目标函数值的增量ΔE=E(xnew)-E(xbest)。3)如果ΔE＜0，则xbest=xnew；4)如果ΔE＞0，则p=exp(

5、-ΔE/T(i));1)如果c=random[0,1]

6、）接受策略（贪心算法）模拟退火算法特点及改进特点：快速收敛于局部最优解遇到flat无所适从模拟退火算法特点及改进快速收敛于局部最优模拟退火算法特点及改进遇到flat则无所适从模拟退火算法特点及改进改进：(1)设计合适的状态产生函数，使其根据搜索进程的需要表现出状态的全空间分散性或局部区域性。(2)设计高效的退火策略。(3)避免状态的迂回搜索。(4)采用并行搜索结构。(5)为避免陷入局部极小，改进对温度的控制方式(6)选择合适的初始状态。(7)设计合适的算法终止准则。模拟退火算法特点及改进也可通过增加某些环节而实现对模拟退火算法的改进。主要的改进方式包括：(1)增加升

7、温或重升温过程。(2)增加记忆功能。(3)增加补充搜索过程。(4)对每一当前状态，采用多次搜索策略，以概率接受区域内的最优状态，而非标准SA的单次比较方式。(5)结合其他搜索机制的算法，如遗传算法、混沌搜索等。(6)上述各方法的综合应用。三、模拟退火算法的主要应用1、TSP问题概述2、模拟退火算法解决TSP问题1、TSP问题概述旅行商问题（TravelingSalesmanProblem，TSP）又译为旅行推销员问题、货郎担问题，简称为TSP问题，是最基本的路线问题，该问题是在寻求单一旅行者由起点出发，通过所有给定的需求点之后，最后再回到原点的最小路径成本。最早