模拟退火算法研究

模拟退火算法研究报告提纲一、模拟退火算法概述二、模拟退火算法特点及改进三、模拟退火算法的主要应用一、模拟退火算法概述1、物理退火2、模拟退火1、物理退火

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

Heheatsthemetal,thenslowlycoolsitashehammersthebladeintoshape.Ifhecoolsthebladetooquicklythemetalwillformpatchesofdifferentcomposition;Ifthemetaliscooledslowlywhileitisshaped,theconstituentmetalswillformauniformalloy.2、模拟退火

模拟退火（SimulatedAnnealing，简称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)若Δt′<0则接受S′作为新的当前解，否则以概率exp(-Δt′/T)接受S′作为新的当前解.(6)如果满足终止条件则输出当前解作为最优解，结束程序。终止条件通常取为连续若干个新解都没有被接受时终止算法。(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(-ΔE/T(i));1)如果c=random[0,1]<p，xbest=xnew;否则xbest=xbest。5)Endfor4)i=i＋1；5)EndDo6)输出当前最优点，计算结束。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问题概述

旅行商问题（TravelingSalesmanProblem，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.4×1015年！模拟退火算法解决TSP问题UINTSACompution(LPVOIDpParam){ while(1) { doubledeltatotaldis=0.0; while(1) { SYRouterSelRouter(ResultRouter.m_CityRouter,NowTemperature,NowExternalIterNumber,NowInnerIterNumber); //从某路径的邻域中随机选择一个新的路径，邻域映射为2-opt deltatotaldis=SelRouter.m_fTotalDistance-ResultRouter.m_fTotalDistance; //计算新路径与当前路径的路程长度差值

if(deltatotaldis<=0.0) ResultRouter=SelRouter; //如果新路径的路程短，则用它替换当前路径

else { doublechgprobability=exp(-(deltatotaldis/NowTemperature)); intrandomnum=rand(); doublerandom=((double)(randomnum%10000))/10000.0; if(chgprobability>random) ResultRouter=SelRouter;//如果新路径长于当前路径，但exp(-Δf/t)>random(0,1)，则仍然替换当前路径

} if(JudgeOverInnerLoop(0)) break; //判断内循环是否结束，结束则跳出当前温度的内循环

else NowInnerIterNumber++; //判断内循环是否结束，不结束则继续内循环

} if(JudgeOverExternalLoop(0)) break; //判断外循环是否结束，结束