模拟退火算法演示幻灯片

模拟退火算法（SimulationAnnealing）及其改进,1,2,目录,2,2020/5/5,搜索问题,最小最优解的搜索,局部最优,全局最优,除对当前的位置外，对环境无任何感知。,3,2020/5/5,搜索算法,盲目搜索与启发式搜索按照预定的控制策略实行搜索，在搜索过程中获取的中间信息不用来改进控制策略，称之为盲目搜索，反之，称为启发式搜索。盲目搜索深度优先、广度优先、代价优先、向前、向后、双向等启发式搜索爬山法、模拟退火算法、遗传算法、蚁群算法、粒子蚁群算法等等,4,2020/5/5,贪心算法,222,5,2020/5/5,模拟退火算法的起源,物理退火过程加温过程等温过程冷却（退火过程）1953年，由Metropolis最早提出模拟退火算法的思想1983年，由kirkpatrick等将模拟退火的思想成功引入组合优化领域。目前，模拟退火算法已经应用到各门学科中以解决非线性系统的优化问题。理论上已证明，模拟退火算法是一个全局最优算法，而且以概率1接近最优值。,6,2020/5/5,Metropolis接受准则,Metropolis准则（1953）即以概率接受新状态准则。若在温度时，从状态变化到状态若，则接受j为新状态否则，若概率=exp大于0,1区间的随机数，则接受状态为当前状态，否则仍保留为当前状态。对于概率=exp。在高温下，可接受与当前状态能量差距较大的状态；在低温下，只接受与当前能量差较小的状态。,Metropolis,7,2020/5/5,模拟退火算法与物理退火的关系,8,2020/5/5,模拟退火算法的基本流程,9,2020/5/5,流程图及伪代码,10,2020/5/5,模拟退火算法的关键要素,11,2020/5/5,模拟退火算法的关键要素,4、初始温度T0实验表明，初温越大，获得高质量解的概率越大，同时花费的时间增加。因此初温的选择要综合考虑优化质量和优化效率。常用方法有：1).均匀抽样一组状态，以各状态目标值的方差作为初温；2).随机产生一组状态，确定最大目标值差，然后根据差值利用一定函数确定初温，如：0=/3).经验公式5、内循环终止准则可称为Metropolis抽样稳定准则，用于决定在各温度下产生候选解的数目。可通过限定步数，限定变化值，判断均值稳定性来实现。6、外循环终止准则即算法终止准则，常用的有：设置终止温度；设置外循环迭代次数；算法检索到最优值时若干步保持不变；检验系统熵是否稳定。,12,2020/5/5,模拟退火算法的改进,算法本身的改进，以提高算法的搜索效率1).设计合适的状态产生函数,使其根据搜索过程的需要表现出状态的全空间分散性和局部区域性；2).设计高效的退火策略，改进对温度的控制方式；3).避免状态的迂回搜索；4).采用并行搜索结构；5).选择合适的初始状态与算法终止准则。增加某些环节1).增加升温或重升温过程。在算法进程的适当时期，调整温度。2).增加记忆功能。存储算法过程中的较优状态，避免最优解遗失。3).增加补充搜索过程。即以最优解为初始解在此执行退火过程。4).结合其他搜索机制的算法，如遗传算法，粒子蚁群算法等。5).综合以上各个方法的应用。,13,2020/5/5,算法的实现和应用,TSP问题求解旅行商问题（TSP，TravelingSalesmanProblem)：有N个城市，要求从其中某个城市出发，一次走遍所有城市，最终返回出发的城市，求最短路线。TSP问题属于NP难问题，精确解决的方法只能通过穷举所有路径组合。使用模拟退火算法可以比较快的求出TSP的一条近似最优路径。,几个城市间的最短路线问题,14,2020/5/5,TSP问题解决思路,1.选择一组初始路径P(i)，并计算L(P(i).2.产生一条新的遍历路径P(i+1)的长度，计算路径P(i+1)的长度L(p(i+1)；3.若L(P(i+1)L(P(i),则接受P(i+1)为新的路径，否则以Metropolis准则接受P(i+1),然后降温。4.重复2,3直到满足退出条件。产生新路径的方法有如下几种：1).随机选择2个节点，叫唤路径中的这2点的顺序。2).随机选择2个节点，将路径中2个节点间的节点顺序逆转；3).随机选择3个节点m,n,k,然后将节点m与n间的节点移位到节点k后面。,15,2020/5/5,算法运行结果（20个地点）,初始旅行商路线,最终求得旅行商路线,每次迭代求得的旅行距离,16,2020/5/5,其它应用,工业方面：再制造车间布局优化问题1;系统可靠性4;交通方面：运输网络的优化2；供应链优化3;材料科学：自旋玻璃模型优化5；图像带宽系统最优化问题6;地球物理：物体重力研究7；大气辐射方程求解问题9;医学方面：放射治疗中放束角优化问题8;其他方面：最优解的求解；电解过程优化10；家具下料问题；贷款问题优化方案11.,17,2020/5/5,外文文献讲解2,文献题目：Simulatedannealingapproachfortransportationproblemofcross-dockingnetworkdesign译名：使用模拟退火方法解决运输问题中的直接转运网的设计2014年，Uludag大学，第二届世界商业经济管理大会研究背景：在产品供应链管理中，运输效率是一个重要因素，高效的运输既满足了顾客的需求，也降低了成本。直接转运策略降低了储存成本加速了产品流通，而直接转运网的设计与优化是一个研究热点。研究目的：设计二维的直接转运网络，设计卡车载运计划与货物的流通路径来实现最低的运输费用。,18,2020/5/5,文献讲解问题描述,如图，为一个二维运输网，由供应商，直接转运设施与用户组成，本文做出以下相关假设，约束条件方便建模。,19,2020/5/5,文献讲解算法应用,退火算法流程所示如图求新解的方法1.改变货物的顺序2.改变进入车的顺序3.改变出去车的顺序,20,2020/5/5,文献讲解计算与结论,通过设置不同的参数（S/C/D/Fmax）文中设置了两个例子分析：单产品，单卡车模型与多产品多卡车模型。SA算法可以在短时间内高效的获得有效解或最优解，优化结果是有效的。,21,2020/5/5,参考文献,1李聪波等,面向不确定性的再制造车间设施动态布局方法.计算机集成制造系统,2015(11):第2901-2911页.2Kkolu,İ.andN.ztrk,SimulatedAnnealingApproachforTransportationProblemofCross-dockingNetworkDesign.Procedia-SocialandBehavioralSciences,2014.109:p.1180-1184.3Zaretalab,A.,etal.,Aknowledge-basedarchivemulti-objectivesimulatedannealingalgorithmtooptimizeseriesparallelsystemwithchoiceofredundancystrategies.Computers&IndustrialEngineering,2015.80:p.33-44.4Zaretalab,A.,etal.,Aknowledge-basedarchivemulti-objectivesimulatedannealingalgorithmtooptimizeseriesparallelsystemwithchoiceofredundancystrategies.Computers&IndustrialEngineering,2015.80:p.33-44.5Yamaguchi,C.,Proposalofacheckingparameterinthesimulatedannealingmethodappliedtothespinglassmodel.ComputerPhysicsCommunications,2016.199:p.47-52.6Torres-Jimenez,J.,etal.,Adualrepresentationsimulatedannealingalgorithmforthebandwidthminimizationproblemongraphs.InformationSciences,2015.303:p.33-49.7Biswas,A.,Interpretationofresidualgravityanomalycausedbysimpleshapedbodiesusingveryfastsimulatedannealingglobaloptimization.GeoscienceFrontiers,2015.6(6):p.875-893.8Dias,J.,etal.,SimulatedannealingappliedtoIMRTbeamangleoptimization:Acomputationalstudy.PhysicaMedica,2015.31(7):p.747-756.9Buras-Schnell,R.,F.SchnellandA.Buras,GORRAM:Introducingaccurateoperational-spee