模拟退火算法研究.ppt
模拟退火算法原理与应用,报告提纲,一、模拟退火算法概述 二、模拟退火算法特点及改进三、模拟退火算法的主要应用,一、模拟退火算法概述,1、物理退火2、模拟退火,1、物理退火,退火是将工件加热到预定温度，保温一定的时间后缓慢冷却的金属热处理工艺。退火的目的在于：改善或消除钢铁在铸造、锻压、轧制和焊接过程中所造成的各种组织缺陷以及残余应力，防止工件变形、开裂。软化工件以便进行切削加工。细化晶粒，改善组织以提高工件的机械性能。为最终热处理（淬火、回火）作好组织准备。,物理退火,He heats the metal,thenslowly cools it as hehammers the blade intoshape.If he cools the blade tooquickly the metal will formpatches of differentcomposition;If the metal is cooled slowlywhile it is shaped,theconstituent metals will forma uniform alloy.,2、模拟退火,模拟退火（Simulated Annealing，简称SA）是一种通用概率算法，用来在一个大的搜寻空间内找寻命题的最优解。“模拟退火”的原理和金属退火的原理近似。,模拟退火,模拟退火,物理退火 模拟退火,二、模拟退火算法原理及改进,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)若t0，然后转第2步。,模拟退火算法原理,1)随机产生一个初始解x0，令xbest x0，并计算目标函数值E(x0);2)设置初始温度T(0)=To，迭代次数i=1;3)Do while T(i)Tmin1)for j=1k2)对当前最优解xbest按照某一邻域函数，产生一新的解xnew。计算新的目标函数值E(xnew)，并计算目标函数值的增量E=E(xnew)-E(xbest)。3)如果E 0，则xbest=xnew；4)如果E 0，则p=exp(-E/T(i);1)如果c=random0,1 p，xbest=xnew;否则xbest=xbest。5)End for4)i=i 1；5)End Do6)输出当前最优点，计算结束。,2、模拟退火算法要素,1、状态空间与状态产生函数（邻域函数）2、状态转移概率（接受概率）p3、冷却进度表T(t)4、初始温度T(0)5、内循环终止准则6、外循环终止准则,3、模拟退火算法特点及改进,算法设计要素：编码策略（“个体表示”与“问题解”的映射关系）初始解的产生（从什么位置开始搜索）邻域函数的设计（下一个解的产生概率与当前解之 间距离包括方向和步长的关系）新解产生策略（随机，确定）接受策略（贪心算法）,模拟退火算法特点及改进,特点：快速收敛于局部最优解 遇到flat无所适从,模拟退火算法特点及改进,快速收敛于局部最优,模拟退火算法特点及改进,遇到flat则无所适从,模拟退火算法特点及改进,改进：(1)设计合适的状态产生函数，使其根据搜索进程的需要表现出状态的全空间分散性或局部区域性。(2)设计高效的退火策略。(3)避免状态的迂回搜索。(4)采用并行搜索结构。(5)为避免陷入局部极小，改进对温度的控制方式(6)选择合适的初始状态。(7)设计合适的算法终止准则。,模拟退火算法特点及改进,也可通过增加某些环节而实现对模拟退火算法的改进。主要的改进方式包括：(1)增加升温或重升温过程。(2)增加记忆功能。(3)增加补充搜索过程。(4)对每一当前状态，采用多次搜索策略，以概率接受区域内的最优状态，而非标准SA的单次比较方式。(5)结合其他搜索机制的算法，如遗传算法、混沌搜索等。(6)上述各方法的综合应用。,三、模拟退火算法的主要应用,1、TSP问题概述 2、模拟退火算法解决TSP问题,1、TSP问题概述,旅行商问题（Traveling Salesman Problem，TSP）又译为旅行推销员问题、货郎担问题，简称为TSP问题，是最基本的路线问题，该问题是在寻求单一旅行者由起点出发，通过所有给定的需求点之后，最后再回到原点的最小路径成本。最早的旅行商问题的数学规划是由Dantzig（1959）等人提出。,TSP问题概述,解决办法：1、遍历法2、模拟退火算法3、其他优化算法,TSP问题概述,遍历法：TSP问题即在n 个顶点的完全图中找一条最小Hamilton 回路,当图为对称图时,要从(n-1)!/2个可能解中找出最优者,需进行(n-1)!/2-1次比较,若用每秒运算一亿次的计算机,n=10时只需0.0018秒,n=20时就需19年,n=30时则猛增为1.41015 年！,2、模拟退火算法解决TSP问题,模拟退火算法：,模拟退火算法解决TSP问题,UINT SACompution(LPVOID pParam)while(1)double deltatotaldis=0.0;while(1)SYRouter SelRouter(ResultRouter.m_CityRouter,NowTemperature,NowExternalIterNumber,NowInnerIterNumber);/从某路径的邻域中随机选择一个新的路径，邻域映射为2-optdeltatotaldis=SelRouter.m_fTotalDistance-ResultRouter.m_fTotalDistance;/计算新路径与当前路径的路程长度差值if(deltatotaldis random)ResultRouter=SelRouter;/如果新路径长于当前路径，但exp(-f/t)random(0,1)，则仍然替换当前路径if(JudgeOverInnerLoop(0)break;/判断内循环是否结束，结束则跳出当前温度的内循环elseNowInnerIterNumber+;/判断内循环是否结束，不结束则继续内循环if(JudgeOverExternalLoop(0)break;/判断外循环是否结束，结束则结束模拟退火计算elseNowTemperature=CountDownTemperature(NowTemperature,0);NowExternalIterNumber+;NowInnerIterNumber=0;/判断外循环是否结束，不结束则计算出下降后的温度，并继续循环,模拟退火算法解决TSP问题,
