模拟退火算法研究.ppt
模拟退火算法原理与应用模拟退火算法原理与应用报告提纲报告提纲一、模拟退火算法概述一、模拟退火算法概述 二、模拟退火算法特点及改进二、模拟退火算法特点及改进三、模拟退火算法的主要应用三、模拟退火算法的主要应用一、模拟退火算法概述1 1、物理退火物理退火2 2、模拟退火模拟退火1 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 1、模拟退火算法原理、模拟退火算法原理、模拟退火算法原理、模拟退火算法原理 2 2、模拟退火算法要素、模拟退火算法要素、模拟退火算法要素、模拟退火算法要素3 3、模拟退火算法特点及改进、模拟退火算法特点及改进、模拟退火算法特点及改进、模拟退火算法特点及改进1、模拟退火算法原理、模拟退火算法原理模拟退火算法可以分解为解空间、目标函数和初始解三部分。模拟退火算法可以分解为解空间、目标函数和初始解三部分。模拟退火算法可以分解为解空间、目标函数和初始解三部分。模拟退火算法可以分解为解空间、目标函数和初始解三部分。模拟退火的基本思想模拟退火的基本思想模拟退火的基本思想模拟退火的基本思想:(1)(1)初始化：初始温度初始化：初始温度初始化：初始温度初始化：初始温度T(T(充分大充分大充分大充分大)，初始解状态，初始解状态，初始解状态，初始解状态S(S(是算法迭代的起点是算法迭代的起点是算法迭代的起点是算法迭代的起点)，每个每个每个每个T T值的值的值的值的迭代次数迭代次数迭代次数迭代次数L L(2)(2)对对对对k=1k=1，L L做第做第做第做第(3)(3)至第至第至第至第6 6步：步：步：步：(3)(3)产生新解产生新解产生新解产生新解SS。(4)(4)计算增量计算增量计算增量计算增量t=C(S)-C(S)t=C(S)-C(S)，其中，其中，其中，其中C(S)C(S)为评价函数为评价函数为评价函数为评价函数 (5)(5)若若若若t0t0T-0，然后转第，然后转第，然后转第，然后转第2 2步。步。步。步。模拟退火算法原理模拟退火算法原理1)1)随机产生一个初始解随机产生一个初始解随机产生一个初始解随机产生一个初始解x0 x0，令，令，令，令xbestxbest x0 x0，并计算目标函数值，并计算目标函数值，并计算目标函数值，并计算目标函数值E(x0);E(x0);2)2)设置初始温度设置初始温度设置初始温度设置初始温度T(0)=ToT(0)=To，迭代次数，迭代次数，迭代次数，迭代次数i=1;i=1;3)Do while T(i)Tmin3)Do while T(i)Tmin1)for j=1k1)for j=1k2)2)对当前最优解对当前最优解对当前最优解对当前最优解xbestxbest按照某一邻域函数，产生一新的解按照某一邻域函数，产生一新的解按照某一邻域函数，产生一新的解按照某一邻域函数，产生一新的解xnewxnew。计算新的目。计算新的目。计算新的目。计算新的目标函数值标函数值标函数值标函数值E(xnew)E(xnew)，并计算目标函数值的增量，并计算目标函数值的增量，并计算目标函数值的增量，并计算目标函数值的增量E=E(xnew)-E(xbest)E=E(xnew)-E(xbest)。3)3)如果如果如果如果E E 0 0，则，则，则，则xbest=xnewxbest=xnew；4)4)如果如果如果如果E E 0 0，则，则，则，则p=exp(-E/T(i);p=exp(-E/T(i);1)1)如果如果如果如果c=random0,1 pc=random0,1 p，xbest=xnew;xbest=xnew;否则否则否则否则xbest=xbestxbest=xbest。5)End for5)End for4)i=i 4)i=i 1 1；5)End Do5)End Do6)6)输出当前最优点，计算结束。输出当前最优点，计算结束。输出当前最优点，计算结束。输出当前最优点，计算结束。2、模拟退火算法要素、模拟退火算法要素1、状态空间与状态产生函数（邻域函数）2、状态转移概率（接受概率）p3、冷却进度表T(t)4、初始温度T(0)5、内循环终止准则6、外循环终止准则3、模拟退火算法特点及改进、模拟退火算法特点及改进 算法设计要素：算法设计要素：算法设计要素：算法设计要素：编码策略（编码策略（编码策略（编码策略（“个体表示个体表示个体表示个体表示”与与与与“问题解问题解问题解问题解”的映射关系）的映射关系）的映射关系）的映射关系）初始解的产生（从什么位置开始搜索）初始解的产生（从什么位置开始搜索）初始解的产生（从什么位置开始搜索）初始解的产生（从什么位置开始搜索）邻域函数的设计（下一个解的产生概率与当前解之邻域函数的设计（下一个解的产生概率与当前解之邻域函数的设计（下一个解的产生概率与当前解之邻域函数的设计（下一个解的产生概率与当前解之 间距离间距离间距离间距离 包括方向和步长包括方向和步长包括方向和步长包括方向和步长 的关系）的关系）的关系）的关系）新解产生策略（随机，确定）新解产生策略（随机，确定）新解产生策略（随机，确定）新解产生策略（随机，确定）接受策略（贪心算法）接受策略（贪心算法）接受策略（贪心算法）接受策略（贪心算法）模拟退火算法特点及改进模拟退火算法特点及改进特点：特点：快速收敛于局部最优解快速收敛于局部最优解 遇到遇到flat无所适从无所适从模拟退火算法特点及改进模拟退火算法特点及改进快速收敛于局部最优快速收敛于局部最优模拟退火算法特点及改进模拟退火算法特点及改进遇到遇到遇到遇到flatflat则无所适从则无所适从则无所适从则无所适从模拟退火算法特点及改进模拟退火算法特点及改进改进：改进：改进：改进：(1)(1)设计合适的状态产生函数，使其根据搜索进程的需要设计合适的状态产生函数，使其根据搜索进程的需要表现出状态的全空间分散性或局部区域性。表现出状态的全空间分散性或局部区域性。(2)(2)设计高效的退火策略。设计高效的退火策略。(3)(3)避免状态的迂回搜索。避免状态的迂回搜索。(4)(4)采用并行搜索结构。采用并行搜索结构。(5)(5)为避免陷入局部极小，改进对温度的控制方式为避免陷入局部极小，改进对温度的控制方式(6)(6)选择合适的初始状态。选择合适的初始状态。(7)(7)设计合适的算法终止准则。设计合适的算法终止准则。模拟退火算法特点及改进模拟退火算法特点及改进也可通过增加某些环节而实现对模拟退火算法的改进。主要的改也可通过增加某些环节而实现对模拟退火算法的改进。主要的改进方式包括：进方式包括：(1)(1)增加升温或重升温过程。增加升温或重升温过程。(2)(2)增加记忆功能。增加记忆功能。(3)(3)增加补充搜索过程。增加补充搜索过程。(4)(4)对每一当前状态，采用多次搜索策略，以概率接受区域内的最优对每一当前状态，采用多次搜索策略，以概率接受区域内的最优状态，而非标准状态，而非标准SASA的单次比较方式。的单次比较方式。(5)(5)结合其他搜索机制的算法，如遗传算法、混沌搜索等。结合其他搜索机制的算法，如遗传算法、混沌搜索等。(6)(6)上述各方法的综合应用。上述各方法的综合应用。三、模拟退火算法的主要应用三、模拟退火算法的主要应用 1 1、TSPTSP问题概述问题概述问题概述问题概述 2 2、模拟退火算法解决、模拟退火算法解决、模拟退火算法解决、模拟退火算法解决TSPTSP问题问题问题问题1、TSP问题概述问题概述 旅行商问题（旅行商问题（旅行商问题（旅行商问题（Traveling Salesman ProblemTraveling Salesman Problem，TSPTSP）又译为旅行推销员问题、货郎担问题，简）又译为旅行推销员问题、货郎担问题，简）又译为旅行推销员问题、货郎担问题，简）又译为旅行推销员问题、货郎担问题，简称为称为称为称为TSPTSP问题，是最基本的路线问题，该问题是问题，是最基本的路线问题，该问题是问题，是最基本的路线问题，该问题是问题，是最基本的路线问题，该问题是在寻求单一旅行者由起点出发，通过所有给定的在寻求单一旅行者由起点出发，通过所有给定的在寻求单一旅行者由起点出发，通过所有给定的在寻求单一旅行者由起点出发，通过所有给定的需求点之后，最后再回到原点的最小路径成本。需求点之后，最后再回到原点的最小路径成本。需求点之后，最后再回到原点的最小路径成本。需求点之后，最后再回到原点的最小路径成本。最早的旅行商问题的数学规划是由最早的旅行商问题的数学规划是由最早的旅行商问题的数学规划是由最早的旅行商问题的数学规划是由DantzigDantzig（19591959）等人提出。）等人提出。）等人提出。）等人提出。TSP问题概述问题概述解决办法：解决办法：1、遍历法、遍历法2、模拟退火算法、模拟退火算法3、其他优化算法、其他优化算法TSP问题概述问题概述 遍历法：遍历法：遍历法：遍历法：TSPTSP问题即在问题即在问题即在问题即在n n 个顶点的完全图中找一条最个顶点的完全图中找一条最个顶点的完全图中找一条最个顶点的完全图中找一条最小小小小Hamilton Hamilton 回路回路回路回路,当图为对称图时当图为对称图时当图为对称图时当图为对称图时,要从要从要从要从(n-1)!(n-1)!/2/2个可能解中找出最优者个可能解中找出最优者个可能解中找出最优者个可能解中找出最优者,需进行需进行需进行需进行(n-1)!/2-1(n-1)!/2-1次比较次比较次比较次比较,若用每秒运算一亿次的计算机若用每秒运算一亿次的计算机若用每秒运算一亿次的计算机若用每秒运算一亿次的计算机,n=10,n=10时时时时只需只需只需只需0.00180.0018秒秒秒秒,n=20,n=20时就需时就需时就需时就需1919年年年年,n=30,n=30时则猛时则猛时则猛时则猛增为增为增为增为1.41015 1.41015 年！年！年！年！2、模拟退火算法解决、模拟退火算法解决TSP问题问题 模拟退火算法：模拟退火算法：模拟退火算法：模拟退火算法：模拟退火算法解决模拟退火算法解决TSP问题问题UINT SACompution(LPVOID pParam)UINT SACompution(LPVOID pParam)while(1)while(1)double deltatotaldis=0.0;double deltatotaldis=0.0;while(1)while(1)SYRouter SelRouter(ResultRouter.m_CityRouter,NowTemperature,NowExternalIterNumber,NowInnerIterNumber);SYRouter SelRouter(ResultRouter.m_CityRouter,NowTemperature,NowExternalIterNumber,NowInnerIterNumber);/从某路径的邻域中随机选择一个新的路径，邻域映射为从某路径的邻域中随机选择一个新的路径，邻域映射为从某路径的邻域中随机选择一个新的路径，邻域映射为从某路径的邻域中随机选择一个新的路径，邻域映射为2-opt2-optdeltatotaldis=SelRouter.m_fTotalDistance-ResultRouter.m_fTotalDistance;deltatotaldis=SelRouter.m_fTotalDistance-ResultRouter.m_fTotalDistance;/计算新路径与当前路径的路程长度差值计算新路径与当前路径的路程长度差值计算新路径与当前路径的路程长度差值计算新路径与当前路径的路程长度差值if(deltatotaldis=0.0)if(deltatotaldis random)if(chgprobability random)ResultRouter=SelRouter;/ResultRouter=SelRouter;/如果新路径长于当前路径，但如果新路径长于当前路径，但如果新路径长于当前路径，但如果新路径长于当前路径，但exp(-f/t)random(0,1)exp(-f/t)random(0,1)，则仍然替换当前路径，则仍然替换当前路径，则仍然替换当前路径，则仍然替换当前路径 if(JudgeOverInnerLoop(0)if(JudgeOverInnerLoop(0)break;break;/判断内循环是否结束，结束则跳出当前温度的内循环判断内循环是否结束，结束则跳出当前温度的内循环判断内循环是否结束，结束则跳出当前温度的内循环判断内循环是否结束，结束则跳出当前温度的内循环elseelseNowInnerIterNumber+;NowInnerIterNumber+;/判断内循环是否结束，不结束则继续内循环判断内循环是否结束，不结束则继续内循环判断内循环是否结束，不结束则继续内循环判断内循环是否结束，不结束则继续内循环 if(JudgeOverExternalLoop(0)if(JudgeOverExternalLoop(0)break;break;/判断外循环是否结束，结束则结束模拟退火计算判断外循环是否结束，结束则结束模拟退火计算判断外循环是否结束，结束则结束模拟退火计算判断外循环是否结束，结束则结束模拟退火计算elseelse NowTemperature=CountDownTemperature(NowTemperature,0);NowTemperature=CountDownTemperature(NowTemperature,0);NowExternalIterNumber+;NowExternalIterNumber+;NowInnerIterNumber=0;/NowInnerIterNumber=0;/判断外循环是否结束，不结束则计算出下降后的温度，并继续循环判断外循环是否结束，不结束则计算出下降后的温度，并继续循环判断外循环是否结束，不结束则计算出下降后的温度，并继续循环判断外循环是否结束，不结束则计算出下降后的温度，并继续循环 模拟退火算法解决模拟退火算法解决TSP问题问题
