模拟退火算法

模拟退火算法,SimulatedAnnealingAlgorithmSAA,模拟退火算法是什么？是怎样提出来的？,模拟退火算法（SimulatedAnnealing，SA）是一种模拟物理退火的过程而设计的优化算法。它的基本思想最早在1953年就被Metropolis提出，但直到1983年Kirkpatrick等人才设计出真正意义上的模拟退火算法并进行应用。,模拟退火算法的基本思想是怎样的？,模拟退火算法采用类似于物理退火的过程，先在一个高温状态下（相当于算法随机搜索），然后逐渐退火，在每个温度下（相当于算法的每一次状态转移）徐徐冷却（相当于算法局部搜索），最终达到物理基态（相当于算法找到最优解）。,简介,模拟退火算法的来源是根据复杂组合优化问题与固体的退火过程之间的相似之处。该算法在系统向着能量减小的趋势变化过程中，偶尔允许系统跳到能量较高的状态，以避开局部最小，最终稳定在全局最小。,简介,SAA属于随机模拟算法模拟统计物理学中物体加热后冷却这一退火过程而建立的随机优化算法，意图是避免陷入局部极小解，早期用于组合优化，后来发展成一种通用的优化算法。,基本思想,SAA是基于MenteCarlo迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。另一方面，结合爬山法和随机行走。,SAA在某一初温下，伴随温度参数的不断下降，结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部优解能概率性地跳出并最终趋于全局最优。模拟退火算法是一种通用的优化算法，目前已在工程中得到了广泛应用。,基本思路,首先在高温下进行搜索，此时各状态出现概率相差不大，可以很快进入“热平衡状态”，这时进行的是一种“粗搜索”，也就是大致找到系统的低能区域；随着温度的逐渐降低，各状态出现概率的差距逐渐被扩大，搜索精度不断提高。这就可以越来越准确的找到网络能量函数的全局最小点。,一、模拟退火算法概述,二、模拟退火算法的马氏链描述及收敛性,三、模拟退火算法关键参数和操作设计,四、模拟退火算法的改进及其并行性,五、模拟退火算法的实现及应用,固体退火过程,Metropolis准则,组合优化与物理退火的相似性,模拟退火算法的步骤,第一节模拟退火算法概述,1模拟退火算法概述,算法的提出模拟退火算法最早的思想由Metropolis等（1953）提出，1983年Kirkpatrick等将其应用于组合优化。Optimizationbysimulatedannealing,IBMResearchReport算法的目的解决NP复杂性问题提供有效近似算法；克服优化过程陷入局部极小；克服初值依赖性。,1.1固体退火过程,1、源于对固体退火过程的模拟；,2、采用Metropolis接受准则；,3、用冷却进度表控制算法进程，使算法在多项式时间里给出一个近似解。,固体退火过程的物理图像和统计性质是SAA的物理背景；Metropolis接受准则使算法跳离局部最优“险井”；而冷却进度表的合理选择是算法应用的前提。,1模拟退火算法概述,1.1固体退火过程,算法的基础,1模拟退火算法概述,固体退火过程什么是退火：退火是指将固体加热到足够高的温度，使分子呈随机排列状态，然后逐步降温使之冷却，最后分子以低能状态排列，固体达到某种稳定状态。,1.1固体退火过程,固体退火是将固体加热至融化，再徐徐冷却使之凝固成规整晶体的热力学过程，属于热力学与统计物理研究的范畴。,由以下三部分组成：,加温过程,等温过程,冷却过程,固体在恒定温度下达到热平衡的过程！,1模拟退火算法概述,固体退火过程加温过程增强粒子的热运动，使其偏离平衡位置，目的是消除系统原先可能存在的非均匀态；等温过程退火过程中要让温度慢慢降低，在每一个温度下要达到热平衡状态，对于与环境换热而温度不变的封闭系统满足自由能较少定律，系统状态的自发变化总是朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡态；冷却过程使粒子热运动减弱并渐趋有序，系统能量逐渐下降，从而得到低能的晶体结构。当液体凝固为固体的晶态时退火过程完成。,1.1固体退火过程,1模拟退火算法概述,数学表述在温度T，分子停留在状态r满足Boltzmann概率分布温度低时能量低的微观状态概率大，温度趋于零时，固体几乎处于概率最大能量最小的基态。,1.1固体退火过程,1模拟退火算法概述,数学表述在同一个温度T，选定两个能量E1=randrom0,1s=sj;Until抽样稳定准则满足；退温tk+1=update(tk)并令k=k+1；Until算法终止准则满足；输出算法搜索结果。,1.4模拟退火算法的步骤,三函数两准则初始温度,三函数两准则,状态产生函数,状态接受函数,退温函数,抽样稳定准则,退火结束准则,SAA流程,关键环节1初温、初始解2状态产生函数3状态接受函数4退温函数5抽样稳定准则6收敛准则,SAA特点,可以保证全局最优特别适合组合优化问题可以随机选择初始解对问题本身没有特别要求，不会因为问题实例的改变影响性能简单易行，通用性好,马氏链描述,收敛性,时齐算法收敛性,非时齐算法收敛性,渐近性态,第二节SAA的马氏链描述及收敛性,模拟退火算法(SAA)是将物理退火过程与组合优化相结合的一种随机迭代寻优算法。,数学模型描述为,由某一较高初始温度开始，在给定的邻域结构中，模拟退火过程，利用概率特性与抽样策略在解空间中随机搜索，随着温度不断下降重复抽样，用来优化问题的解。,引言,设为所有状态构成的解空间，,为k时刻状态变量的取值。,随机序列称为马氏链,若,满足,简记,（记忆遗忘功能）,2SAA的马氏链描述及收敛性,2.1马尔可夫（Markov）链,一步转移概率,n步转移概率,有限状态马氏链,若解空间有限。,时齐马氏链,模拟退火算法(SAA)的搜索进程：,算法从某一个初始状态开始后，每一步状态转移均是在当前状态的邻域中随机产生新状态，然后以一定概率进行接受的。接受概率仅依赖于新状态和当前状态，并由温度加以控制。因此，SAA对应一个马氏链。,若固定每一温度，算法均计算马氏链的变化直至平稳分布，然后下降温度。,时齐算法,非时齐算法,若无需各温度下算法均达到平稳分布，但温度需按照一定的速率下降。或称非平稳马氏链算法。,SAA基础理论,马氏链模型,SAA要实现全局收敛必须满足下列条件：,状态可达性,初值鲁棒性,极限分布存在性,收敛到最优解,温度不变，M链极限分布存在,温度渐近0，M链极限分布存在,对应马氏链的状态图是强连通的,对算法的最终结果不依赖于初值,定义1,状态i可达状态j:,定义2,平稳分布:,称为马氏链的平稳分布,若一步转移概率满足等式,2.2.1时齐算法的收敛性,2SAA的马氏链描述及收敛性,2.2收敛性分析,时齐模拟退火算法的收敛性结论：,结论1时齐模拟退火算法对应的有限状态马氏链存在平稳分布。,结论2当温度趋于0时，马氏链以概率1收敛到最优状态集，而收敛到非最优状态的概率为0。,实现途径：,通过各温度下各状态序列无限长得以实现！,2.2.2非时齐算法的收敛性,收敛定理,对退温函数加以严格控制，可使得SA算法以概率1收敛到全局最优解。可设计退温函数为,其中，则当时，SA算法以概率1收敛到全局最优解。,2.2.3SA算法渐近性能的逼近,收敛可以保证，但是时间性能不好收敛速度有待研究,第三节模拟退火算法关键参数和操作的设计,三函数两准则,状态产生函数,状态接受函数,退温函数,抽样稳定准则,退火结束准则,从算法流程看，SA算法包括三函数两准则,初温,1状态产生函数（邻域函数）,设计的出发点：,尽可能保证产生的候选解遍布全部解空间。,产生候选解的方式,候选解产生的概率分布,两部分,前者决定由当前解产生候选解的方式，后者决定在当前解产生的候选解中选择不同状态的概率。候选解的产生方式由问题的性质决定，通常在当前状态的邻域结构内以一定概率方式产生，而邻域函数和概率方式可以多样化设计，其中概率分布可以是均匀分布、正态分布、指数分布、柯西分布等。,2状态接受函数,目的：,尽可能接受优化解,状态接受函数一般以概率的方式给出，不同接受函数的差别主要在于接受概率的形式不同。,固定温度下，接受使目标函数值下降的候选解的概率要大于使目标函数值上升的候选解的概率。,随温度的下降，接受使目标函数值上升的解的概率要逐渐减小。,当温度趋于零时，只能接受目标函数值下降的解。,设计状态接受概率，应遵循的原则：,3初温,实验表明：初温值只要选择充分大，获得高质量解的概率就大！但花费计算时间增加。,初温的选择要足够高。初温的确定应折衷考虑优化质量和优化效率。,均匀抽样一组状态，选各状态目标值的方差,利用经验公式,随机产生一组状态，确定两两状态间的最大目标值差，然后依据差值，利用一定的函数确定初温。例如，,初始温度温度更新函数内循环终止准则外循环终止准则,退火历程(annealingschedule),4温度更新函数,衰减量“以小为宜”,实验表明降温速度越慢，获得高质量解的几率越大，但花费的计算时间将同时增加。温度高时下降的慢些，温度低时下降的快些。,即温度的下降方式，用于在外循环中修改温度值。,Nahar及Skiscim等人把划分成K个小区间，温度更新函数为,取0.5至0.99之间,5内循环终止准则,检验目标函数值的均值是否稳定,连续若干步目标函数值的变化较小,按一定的步数抽样,链长,（Metropolis抽样稳定准则）,用于决定在各温度下产生候选解的数目。,时齐算法常用Metropolis抽样稳定准则包括：,非时齐SAA：每个温度下只产生一个或少量候选解。,具体应与问题规模成比例。实验表明高温时迭代次数越多越好，低温时迭代次数可以适当减少。,6外循环终止准则,理论上要求温度终值趋于零,设置终止温度的阀值,设置外循环迭代次数(6-50),算法搜索到的最优值连续若干步保持不变,（算法终止准则）,用于决定算法何时结束。,通常的做法包括：,检验系统熵是否稳定,三个参数、和值均有显著影响。,总结,过大的值、值和值均能导致过长的CPU时间。因而在最终解的质量有待较大值和值予以保证的前提下，选取较小的值可以抑制CPU时间上升的态势。,模拟退火算法基本要素和设定方法,模拟退火算法是一种通用的随机搜索算法，它可用于解决众多的优化问题，并已经广泛的应用于其他领域。如VLSL设计、图像识别等。当待解决的问题复杂性较高，而且规模较大时，在对问题的领域知识甚少的情况下，采用模拟退火算法最合适。因为模拟退火算法不像其他确定型启发式算法那样，需要依赖于问题的领域知识来提高算法的性能。,但是，从另一方面来说，已知有关待解决问题的一些知识后，模拟退火算法却无法充分利用它们，这使得模拟退火算法的优点就成了缺点。如何把传统的启发式搜索方法和模拟退火随机搜索算法结合起来，这是一个有待研究的十分有意义的课题。,模拟退火算法在求解规模较大的实际问题时，往往存在以下缺点：（1）收敛速度比较慢。（2）尽管理论上只要计算时间足够长，模拟退火法就可以保证以概率1收敛于全局最优点。但是在实际算法的实现过程中，由于计算速度和时间的限制，在优化效果和计算时间二者之间存在矛盾，因而难以保证计算结果为全局最优点，优化效果不甚理想。（3）在每一温度下很难判定是否达到了平衡状态。,为此，人们对模拟退火算法提出了各种各样的改进，其中包括并行模拟退火算法、快速模拟退火算法（Cauchy机）和对模拟退火算法中各个函数和参数的重新设计等。,SA算法直接简单模拟固体退火。,特点：,思路清晰、原理简单、使用灵活、应用广泛,同时，由于其直接性和简单化，也存在不足与弊病，使其应用及性能受到一定影响。,第四节模拟退火算法的改进及并行性,不同p值对CHN144实例测得值,4模拟退火算法的改进及并行性,模拟退火算法的优点质量高；初值鲁棒性强；简单、通用、易实现。模拟退火算法的缺点由于要求较高的初始温度、较慢的降温速率、较低的终止温度，以及各温度下足够多次的抽样，因此优化过程较长。,4.1模拟退火算法的优缺点,4模拟退火算法的改进及并行性,改进的可行方案（1）设计合适的状态产生函数；（2）设计高效的退火历程；（3）避免状态的迂回搜索；（4）采用并行搜索结构；（5）避免陷入局部极小，改进对温度的控制方式；（6）选择合适的初始状态；（7）设计合适的算法终止准则。,4.2改进内容,4模拟退火算法的改进及并行性,改进的方式：增加某些新的环节（1）增加升温或重升温过程，避免陷入局部极小；（2）增加记忆功能（记忆“Bestsofar”状态）；（3）增加补充搜索过程（以最优结果为初始解）；（4）对每一当前状态，采用多次搜索策略，以概率接受区域内的最优状态；（5）结合其它搜索机制的算法；（6）上述各方法的综合。,4.2改进内容,4模拟退火算法的改进及并行性,改进的思路（1）记录“Bestsofar”状态，并即时更新；（2）设置双阈值，使得在尽量保持最优性的前提下减少计算量，即在各温度下当前状态连续m1步保持不变则认为Metropolis抽样稳定，若连续m2次退温过程中所得最优解不变则认为算法收敛。,4.3一种改进的模拟退火算法,4模拟退火算法的改进及并行性,改进的退火过程（1）给定初温t0，随机产生初始状态s，令初始最优解s*=s，当前状态为s(0)=s，i=p=0；（2）令t=ti，以t，s*和s(i)调用改进的抽样过程，返回其所得最优解s*和当前状态s(k)，令当前状态s(i)=s(k)；（3）判断C(s*)m2?若是，则转第(6)步；否则，返回第(2)步；（6）以最优解s*作为最终解输出，停止算法。,4.3一种改进的模拟退火算法,4模拟退火算法的改进及并行性,改进的抽样过程（1）令k=0时的初始当前状态为s(0)=s(i)，q=0；（2）由状态s通过状态产生函数产生新状态s，计算增量C=C(s)-C(s)；（3）若CC(s)?若是，则令s*=s，q=0；否则，令q=q+1。若C0，则以概率exp(-C/t)接受s作为下一当前状态；（4）令k=k+1，判断qm1?若是，则转第(5)步；否则，返回第(2)步；（5）将当前最优解s*和当前状态s(k)返回改进退火过程。,4.3一种改进的模拟退火算法,TINA,Time-invariantnoisealgorithm状态产生函数中扰动强度不随时间改变，而是和能量大小相关，能量大的扰动大，能量小的扰动小，能量为零，扰动也为零，算法停止。,MTRSA,单调升温(Monotonictemperaturerising)SA在算法退火后期，温度很低且陷入局部极小解的时，算法很难跳出。因此，可以适当重新提高温度，促使算法跳出。,SAMG,记忆指导SA(SimulatedAnnealingwithMemmoryGuidance,简记为SAMG)增加一个记忆装置，存储算法计算过程产生的最好的解，以这个解为最终解。,自适应SA,自适应SA算法,根据邻域搜索进展的反馈信息,自适应确定温度变化和邻域搜索强度特点：1)退火过程中温度参数变化符合幅值递减的下降总趋势,但不排除局部升温的可能,以保证寻求到合适的温度序列,避免陷入局部最优;2)算法的终止条件依据退火温度和邻域搜索进展状态设计;3)每一温度下算法的迭代次数随温度下降而递增,邻域搜索强度依其对目标函数的贡献动态分配;4)温度变化、邻域搜索和终止条件的控制机制由算法过程自动触发。,4模拟退火算法的改进及并行性,4.4并行性,1、操作并行性：各个环节同时处理；,2、进程并行性：同时多个算法运行；,3、空间并行性：解空间分解分别处理，最终组合。,全过程并行性,子进程并行性,第五节算法的实现与应用,引言,SAA应用的一般形式：从选定的初始解开始，在借助于控制参数t递减时产生的一系列Markov链中，利用一个新解产生装置和接受准则，重复进行包括“产生新解-计算目标函数差-判断是否接受新解-接受(或舍弃)新解”这四个任务的实验，不断对当前解迭代，从而达到使目标函数最优的执行过程。,SAA实现,通用框架确定问题编码方案设计初始温度、终止温度和温度下降策略（退温函数）设计能量函数设定稳定准则设计产生新解的方式（状态产生函数）设计Metropolis接受准则（状态接受函数）生成初始状态,1、数学模型,对问题的简明描述。,解空间,目标函数,初始解,所有可能解的集合，它限定了初始解选取和新解产生的范围,对问题的优化目标的数学描述，易计算，对应关系明确,算法开始迭代的起点，它的选取使算法能导出较好的最终解,5模拟退火算法的实现与应用,5.1应用的一般要求,2、新解的产生和接受机制,产生新解,由产生装置从当前解的解空间中产生。,计算目标函数值之差,最快的方法是按增量计算。,判断新解是否被接受,准则Metropolis,新解代替当前解,代替变换部分，修正目标函数值。,3、温度更新函数,关键参数：初温、温度降低函数、马氏链长度、停止准则。,综合应用，达到最佳效果！,SAA求解TSP,关键问题如何由旧的解产生新的解方式很多相邻两位置对换变动最小任意两位置对换单点位置移动子排列位置移动子排列反序子排列位置移动且反序变动最大理论已经证明上述所有方式都收敛实际验证收敛性能差异很大,1、组合优化问题的求解,数学模型,一个商人欲到个城市推销商品，每两个城市和之间的距离为，如何选择一条道路使得商人每个城市走一遍后回到起点且所走路经最短。,5模拟退火算法的实现与应用,5.2算法的实现,解空间,目标函数,初始解,选为,新解的产生,1、互换操作(SWAP),随机交换两个不同城市的位置。,2、逆序操作(INV),两个不同随机位置的城市逆序。,3、插入操作(INS),随机选择某个城市插入到不同随机位置。,衰减函数,初值,马氏链长,5模拟退火算法的实现与应用,例130城市TSP问题（d*=423.741byDBFogel）,TSPBenchmark问题4194;3784;5467;2562;764;299;6858;7144;5462;8369;6460;1854;2260;8346;9138;2538;2442;5869;7171;7478;8776;1840;1340;827;6232;5835;4521;4126;4435;450,5模拟退火算法的实现与应用,算法流程,例130城市TSP问题（d*=423.741byDBFogel）,5模拟退火算法的实现与应用,初始温度的计算fori=1:100route=randperm(CityNum);fval0(i)=CalDist(dislist,route);endt0=-(max(fval0)-min(fval0)/log(0.9);,例130城市TSP问题（d*=423.741byDBFogel）,5模拟退火算法的实现与应用,状态产生函数的设计（1）互换操作，随机交换两个城市的顺序；（2）逆序操作，两个随机位置间的城市逆序；（3）插入操作，随机选择某点插入某随机位置。,例130城市TSP问题（d*=423.741byDBFogel）,2,8,3,5,9,1,4,6,7,2,8,3,5,9,1,4,6,7,2,8,3,5,9,1,4,6,7,5模拟退火算法的实现与应用,参数设定截止温度tf=0.01;退温系数alpha=0.90;内循环次数L=200*CityNum;,例130城市TSP问题（d*=423.741byDBFogel）,5模拟退火算法的实现与应用,运行过程,例130城市TSP问题（d*=423.741byDBFogel）,5模拟退火算法的实现与应用,运行过程,例130城市TSP问题（d*=423.741byDBFogel）,5模拟退火算法的实现与应用,运行过程,例130城市TSP问题（d*=423.741byDBFogel）,5模拟退火算法的实现与应用,运行过程,例130城市TSP问题（d*=423.741byDBFogel）,5模拟退火算法的