模拟退火算法

模拟退火算法是什么？是怎样提出来的？模拟退火算法（SimulatedAnnealing，SA）是一种模拟物理退火的过程而设计的优化算法。它的基本思想最早在1953年就被Metropolis提出，但直到1983年Kirkpatrick等人才设计出真正意义上的模拟退火算法并进行应用。模拟退火算法的基本思想是怎样的？模拟退火算法采用类似于物理退火的过程，先在一个高温状态下（相当于算法随机搜索），然后逐渐退火，在每个温度下（相当于算法的每一次状态转移）徐徐冷却（相当于算法局部搜索），最终达到物理基态（相当于算法找到最优解）。第一页，共113页。

简介模拟退火算法的来源是根据复杂组合优化问题与固体的退火过程之间的相似之处。该算法在系统向着能量减小的趋势变化过程中，偶尔允许系统跳到能量较高的状态，以避开局部最小，最终稳定在全局最小。第二页，共113页。简介SAA属于随机模拟算法模拟统计物理学中物体加热后冷却这一退火过程而建立的随机优化算法，意图是避免陷入局部极小解，早期用于组合优化，后来发展成一种通用的优化算法。第三页，共113页。基本思想SAA是基于MenteCarlo迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。另一方面，结合爬山法和随机行走。SAA在某一初温下，伴随温度参数的不断下降，结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部优解能概率性地跳出并最终趋于全局最优。

模拟退火算法是一种通用的优化算法，目前已在工程中得到了广泛应用。第四页，共113页。基本思路首先在高温下进行搜索，此时各状态出现概率相差不大，可以很快进入“热平衡状态”，这时进行的是一种“粗搜索”，也就是大致找到系统的低能区域；随着温度的逐渐降低，各状态出现概率的差距逐渐被扩大，搜索精度不断提高。这就可以越来越准确的找到网络能量函数的全局最小点。第五页，共113页。一、模拟退火算法概述二、模拟退火算法的马氏链描述及收敛性三、模拟退火算法关键参数和操作设计四、模拟退火算法的改进及其并行性五、模拟退火算法的实现及应用第六页，共113页。固体退火过程Metropolis准则组合优化与物理退火的相似性模拟退火算法的步骤第一节模拟退火算法概述第七页，共113页。

1模拟退火算法概述

算法的提出

模拟退火算法最早的思想由Metropolis等（1953）提出，1983年Kirkpatrick等将其应用于组合优化。

—Optimizationbysimulatedannealing,IBMResearchReport算法的目的

解决NP复杂性问题提供有效近似算法；克服优化过程陷入局部极小；克服初值依赖性。1.1固体退火过程第八页，共113页。1、源于对固体退火过程的模拟；2、采用Metropolis接受准则；3、用冷却进度表控制算法进程，使算法在多项式时间里给出一个近似解。固体退火过程的物理图像和统计性质是SAA的物理背景；Metropolis接受准则使算法跳离局部最优“险井”；而冷却进度表的合理选择是算法应用的前提。

1模拟退火算法概述

1.1固体退火过程算法的基础第九页，共113页。

1模拟退火算法概述

固体退火过程

什么是退火：

退火是指将固体加热到足够高的温度，使分子呈随机排列状态，然后逐步降温使之冷却，最后分子以低能状态排列，固体达到某种稳定状态。

1.1固体退火过程第十页，共113页。固体退火是将固体加热至融化，再徐徐冷却使之凝固成规整晶体的热力学过程，属于热力学与统计物理研究的范畴。由以下三部分组成：加温过程等温过程冷却过程固体在恒定温度下达到热平衡的过程！第十一页，共113页。

1模拟退火算法概述

固体退火过程

加温过程——增强粒子的热运动，使其偏离平衡位置，目的是消除系统原先可能存在的非均匀态；

等温过程——退火过程中要让温度慢慢降低，在每一个温度下要达到热平衡状态，对于与环境换热而温度不变的封闭系统满足自由能较少定律，系统状态的自发变化总是朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡态；

冷却过程——使粒子热运动减弱并渐趋有序，系统能量逐渐下降，从而得到低能的晶体结构。当液体凝固为固体的晶态时退火过程完成。

1.1固体退火过程第十二页，共113页。

1模拟退火算法概述

数学表述

在温度T，分子停留在状态r满足Boltzmann概率分布

温度低时能量低的微观状态概率大，温度趋于零时，固体几乎处于概率最大能量最小的基态。

1.1固体退火过程第十三页，共113页。

1模拟退火算法概述

数学表述

在同一个温度T，选定两个能量E1<E2，有

在同一个温度，分子停留在能量小的状态的概率比停留在能量大的状态的概率要大。

1.1固体退火过程<1>0第十四页，共113页。

1模拟退火算法概述数学表述

若|D|为状态空间D中状态的个数，D0是具有最低能量的状态集合：

(1)当温度很高时，每个状态概率基本相同，接近平均值1/|D|；

(2)状态空间存在超过两个不同能量时，具有最低能量状态的概率超出平均值1/|D|；(3)当温度趋于0时，分子停留在最低能量状态的概率趋于1。

1.1固体退火过程能量最低状态非能量最低状态第十五页，共113页。

1模拟退火算法概述

Metropolis准则（1953）——以概率接受新状态

固体在恒定温度下达到热平衡的过程可以用MonteCarlo方法（计算机随机模拟方法）加以模拟，虽然该方法简单，但必须大量采样才能得到比较精确的结果，计算量很大。

1.2

Metropolis准则第十六页，共113页。MonteCarlo模拟退火过程蒙特卡罗(MonteCarlo)方法，或称计算机随机模拟方法，是一种基于“随机数”的计算方法。这一方法源于美国在第一次世界大战中研制原子弹的“曼哈顿计划”。该计划的主持人之一、数学家冯·诺伊曼用驰名世界的赌城—摩纳哥的MonteCarlo—来命名这种方法，为它蒙上了一层神秘色彩。第十七页，共113页。MonteCarlo方法MonteCarlo方法的基本思想很早以前就被人们所发现和利用。早在17世纪，人们就知道用事件发生的“频率”来决定事件的“概率”。Buffon试验：19世纪人们用投针试验的方法来求解圆周率π。本世纪40年代电子计算机的出现，特别是近年来高速电子计算机的出现，使得用数学方法在计算机上大量、快速地模拟这样的试验成为可能。第十八页，共113页。MonteCarlo方法用民意测验来作一个不严格的比喻。民意测验的人不是征询每一个登记选民的意见，而是通过对选民进行小规模的抽样调查来确定可能的优胜者。其基本思想是一样的。它需要一个良好的随机数源。这种方法往往包含一些误差，但是随着随机抽取样本数量的增加，结果也会越来越精确。第十九页，共113页。

1模拟退火算法概述

Metropolis准则（1953）——以概率接受新状态

若在温度T，当前状态i→新状态j若Ej<Ei，则接受j为当前状态；否则，若概率

p=exp[-(Ej-Ei)/kBT]

大于[0,1)区间的随机数，则仍接受状态j为当前状态；若不成立则保留状态i为当前状态。

1.2

Metropolis准则第二十页，共113页。1953年提出重要性采样法----以概率接受新状态.设固体的初态为，其状态能量为，然后用一扰动装置随机选取某个微粒的微小变化，得到一新状态，其能量为:(1)当，则该新状态为“重要状态”，并接受它；(2)当，该状态是否为“重要状态”，要依据固体处于该状态的概率来判断。记固体处于状态和状态的概率比值为，则在[0,1)之间随机产生一随机数。若，则新状态作为重要状态，并接受它；否则舍弃新状态。Metropolis准则第二十一页，共113页。若，则接受j，否则接受i。随机数在温度t，初始状态i，该状态的能量为,随机选取某个粒子的位移随机地产生一微小变化，得到一个新状态j，新状态的能量为则接受新状态j则考虑到热运动的影响Metropolis准则第二十二页，共113页。由的定义可知，高温下可接受与当前状态能差较大的状态为重要状态，而在低温下只能接受与当前状态能差较小的新状态为重要状态。在温度趋于零时，就不再接受的新状态了。

如此反复，达到系统在此温度下的热平衡。这个过程称作Metropolis抽样过程。

Metropolis抽样过程就是在一确定温度下，使系统达到热平衡的过程。第二十三页，共113页。退火过程（降温过程）

在Metropolis抽样过程中温度T缓慢的降低。模拟退火过程就是通过T参数的变化使状态收敛于最小能量处。因而，T参数的选择对于算法最后的结果有很大影响。初始温度和终止温度设置的过低或过高都会延长搜索时间。降温步骤太快，往往会漏掉全局最优点，使算法收敛至局部最优点。降温步骤太慢，则会大大延长搜索全局最优点的计算时间，从而难以实际应用。因此，T可以理解为一个控制参数。第二十四页，共113页。为寻找在有限时间逼近全局最优的模拟退火算法，设置了许多控制算法收敛的参数。在退火过程中指定了有限的退火温度值和在每一温度下的转移数目。Kirlpatrick等人在退火步骤中设定的参数如下：

（1）初始温度值：初始温度值T0要选的足够高，保证模拟退火算法中所有可能的转移都能被接受。第二十五页，共113页。

（2）温度的下降：原先使用指数函数实现温度的下降。但是这种方法使降温幅度过小，从而延长搜索时间。在实际中，通常使用下式：此处λ是一小于却接近于1的常数。λ通常的取值在0.8至0.99之间。在每一温度下，实验足够多的转移次数。

（3）终止温度：如果在连续的若干个温度下没有可接受的新状态，系统冻结或退火停止。第二十六页，共113页。SAA提出依据固体模拟退火与组合优化问题的相似性退火过程的状态组合优化问题的解能量目标值能量的取舍目标值的取舍能量的最小值目标值的最小值根据这种相似性，并依据Metropolis准则进行迭代就形成了模拟退火算法第二十七页，共113页。

1模拟退火算法概述

相似性比较

1.3组合优化与固体退火的相似性组合优化问题金属物体退火解粒子状态最优解能量最低的状态设定初温熔解过程Metropolis抽样过程等温过程控制参数的下降冷却目标函数能量第二十八页，共113页。物理退火过程物体内部的状态状态的能量温度熔解过程退火冷却过程状态的转移能量最低状态模拟退火算法问题的解空间解的质量控制参数设定初始温度控制参数的修改解在邻域中的变化最优解物理退火过程模拟退火算法类比关系第二十九页，共113页。SAA机理优化问题的解视为固体的状态；随机给定优化问题的初始解；给定初始温度；根据当前的解产生新的解；依据Metropolis准则对两个解进行取舍；重复以上两步直到达到热平衡；降低温度继续上述过程直到温度降到最低，最后的状态就认为是问题的解。第三十页，共113页。

1模拟退火算法概述

基本步骤

给定初温t=t0，随机产生初始状态s=s0，令k=0；

RepeatRepeat

产生新状态sj=Genete(s)；

ifmin{1,exp[-(C(sj)-C(s))/tk]}>=randrom[0,1]s=sj;Until抽样稳定准则满足；退温tk+1=update(tk)并令k=k+1；

Until算法终止准则满足；输出算法搜索结果。

1.4模拟退火算法的步骤第三十一页，共113页。

1模拟退火算法概述

影响优化结果的主要因素

给定初温t=t0，随机产生初始状态s=s0，令k=0；

RepeatRepeat

产生新状态sj=Genete(s)；

ifmin{1,exp[-(C(sj)-C(s))/tk]}>=randrom[0,1]s=sj;Until抽样稳定准则满足；退温tk+1=update(tk)并令k=k+1；

Until算法终止准则满足；输出算法搜索结果。

1.4模拟退火算法的步骤三函数两准则初始温度第三十二页，共113页。三函数两准则状态产生函数状态接受函数退温函数抽样稳定准则退火结束准则第三十三页，共113页。SAA流程确定初温随机给定初始解收敛准则满足否？输出结果Y抽样稳定准则满足否？由当前状态产生新状态接受函数成立否？替换当前状态YYNNN退温保持当前状态不变

关键环节1初温、初始解2状态产生函数3状态接受函数4退温函数5抽样稳定准则6收敛准则第三十四页，共113页。第三十五页，共113页。SAA特点可以保证全局最优特别适合组合优化问题可以随机选择初始解对问题本身没有特别要求，不会因为问题实例的改变影响性能简单易行，通用性好第三十六页，共113页。马氏链描述收敛性时齐算法收敛性非时齐算法收敛性渐近性态第二节SAA的马氏链描述及收敛性第三十七页，共113页。模拟退火算法(SAA)是将物理退火过程与组合优化相结合的一种随机迭代寻优算法。数学模型描述为由某一较高初始温度开始，在给定的邻域结构中，模拟退火过程，利用概率特性与抽样策略在解空间中随机搜索，随着温度不断下降重复抽样，用来优化问题的解。引言第三十八页，共113页。设为所有状态构成的解空间，为k时刻状态变量的取值。随机序列称为马氏链,若满足简记（记忆遗忘功能）

2

SAA的马氏链描述及收敛性

2.1

马尔可夫（Markov）链第三十九页，共113页。一步转移概率n步转移概率有限状态马氏链若解空间有限。时齐马氏链第四十页，共113页。模拟退火算法(SAA)的搜索进程：算法从某一个初始状态开始后，每一步状态转移均是在当前状态的邻域中随机产生新状态，然后以一定概率进行接受的。接受概率仅依赖于新状态和当前状态，并由温度加以控制。因此，SAA对应一个马氏链。第四十一页，共113页。若固定每一温度，算法均计算马氏链的变化直至平稳分布，然后下降温度。时齐算法非时齐算法若无需各温度下算法均达到平稳分布，但温度需按照一定的速率下降。或称非平稳马氏链算法。第四十二页，共113页。SAA基础理论马氏链模型第四十三页，共113页。SAA要实现全局收敛必须满足下列条件：状态可达性初值鲁棒性极限分布存在性收敛到最优解温度不变，M链极限分布存在温度渐近0，M链极限分布存在对应马氏链的状态图是强连通的对算法的最终结果不依赖于初值第四十四页，共113页。定义1状态i可达状态j:定义2平稳分布:称

为马氏链的平稳分布,若一步转移概率满足等式2.2.1时齐算法的收敛性

2

SAA的马氏链描述及收敛性

2.2

收敛性分析第四十五页，共113页。时齐模拟退火算法的收敛性结论：结论1

时齐模拟退火算法对应的有限状态马氏链存在平稳分布。结论2

当温度趋于0时，马氏链以概率1收敛到最优状态集，而收敛到非最优状态的概率为0。实现途径：通过各温度下各状态序列无限长得以实现！第四十六页，共113页。2.2.2非时齐算法的收敛性收敛定理第四十七页，共113页。对退温函数加以严格控制，可使得SA算法以概率1收敛到全局最优解。可设计退温函数为其中，则当时，SA算法以概率1收敛到全局最优解。第四十八页，共113页。2.2.3SA算法渐近性能的逼近收敛可以保证，但是时间性能不好收敛速度有待研究第四十九页，共113页。第三节模拟退火算法关键参数和操作的设计三函数两准则状态产生函数状态接受函数退温函数抽样稳定准则退火结束准则从算法流程看，SA算法包括三函数两准则初温第五十页，共113页。1状态产生函数（邻域函数）设计的出发点：尽可能保证产生的候选解遍布全部解空间。产生候选解的方式候选解产生的概率分布两部分第五十一页，共113页。前者决定由当前解产生候选解的方式，后者决定在当前解产生的候选解中选择不同状态的概率。候选解的产生方式由问题的性质决定，通常在当前状态的邻域结构内以一定概率方式产生，而邻域函数和概率方式可以多样化设计，其中概率分布可以是均匀分布、正态分布、指数分布、柯西分布等。第五十二页，共113页。2状态接受函数目的：尽可能接受优化解状态接受函数一般以概率的方式给出，不同接受函数的差别主要在于接受概率的形式不同。第五十三页，共113页。固定温度下，接受使目标函数值下降的候选解的概率要大于使目标函数值上升的候选解的概率。随温度的下降，接受使目标函数值上升的解的概率要逐渐减小。当温度趋于零时，只能接受目标函数值下降的解。设计状态接受概率，应遵循的原则：第五十四页，共113页。3初温实验表明：初温值只要选择充分大，获得高质量解的概率就大！但花费计算时间增加。初温的选择要足够高。初温的确定应折衷考虑优化质量和优化效率。第五十五页，共113页。均匀抽样一组状态，选各状态目标值的方差利用经验公式随机产生一组状态，确定两两状态间的最大目标值差，然后依据差值，利用一定的函数确定初温。例如，第五十六页，共113页。初始温度温度更新函数内循环终止准则外循环终止准则退火历程(annealingschedule)第五十七页，共113页。4温度更新函数衰减量“以小为宜”实验表明降温速度越慢，获得高质量解的几率越大，但花费的计算时间将同时增加。温度高时下降的慢些，温度低时下降的快些。即温度的下降方式，用于在外循环中修改温度值。第五十八页，共113页。Nahar及Skiscim等人把划分成K个小区间，温度更新函数为Kirkpatrick首先提出被Johnson,Bonomi及Lutton采用取0.5至0.99之间第五十九页，共113页。5内循环终止准则检验目标函数值的均值是否稳定连续若干步目标函数值的变化较小按一定的步数抽样链长（Metropolis抽样稳定准则）用于决定在各温度下产生候选解的数目。时齐算法——常用Metropolis抽样稳定准则包括：非时齐SAA：每个温度下只产生一个或少量候选解。第六十页，共113页。具体应与问题规模成比例。实验表明高温时迭代次数越多越好，低温时迭代次数可以适当减少。第六十一页，共113页。6外循环终止准则理论上要求温度终值趋于零设置终止温度的阀值设置外循环迭代次数(6-50)算法搜索到的最优值连续若干步保持不变（算法终止准则）用于决定算法何时结束。通常的做法包括：检验系统熵是否稳定第六十二页，共113页。三个参数、和值均有显著影响。总结过大的值、值和值均能导致过长的CPU时间。因而在最终解的质量有待较大值和值予以保证的前提下，选取较小的值可以抑制CPU时间上升的态势。第六十三页，共113页。模拟退火算法基本要素和设定方法第六十四页，共113页。模拟退火算法是一种通用的随机搜索算法，它可用于解决众多的优化问题，并已经广泛的应用于其他领域。如VLSL设计、图像识别等。当待解决的问题复杂性较高，而且规模较大时，在对问题的领域知识甚少的情况下，采用模拟退火算法最合适。因为模拟退火算法不像其他确定型启发式算法那样，需要依赖于问题的领域知识来提高算法的性能。第六十五页，共113页。但是，从另一方面来说，已知有关待解决问题的一些知识后，模拟退火算法却无法充分利用它们，这使得模拟退火算法的优点就成了缺点。如何把传统的启发式搜索方法和模拟退火随机搜索算法结合起来，这是一个有待研究的十分有意义的课题。第六十六页，共113页。模拟退火算法在求解规模较大的实际问题时，往往存在以下缺点：（1）收敛速度比较慢。（2）尽管理论上只要计算时间足够长，模拟退火法就可以保证以概率1收敛于全局最优点。但是在实际算法的实现过程中，由于计算速度和时间的限制，在优化效果和计算时间二者之间存在矛盾，因而难以保证计算结果为全局最优点，优化效果不甚理想。（3）在每一温度下很难判定是否达到了平衡状态。第六十七页，共113页。为此，人们对模拟退火算法提出了各种各样的改进，其中包括并行模拟退火算法、快速模拟退火算法（Cauchy机）和对模拟退火算法中各个函数和参数的重新设计等。第六十八页，共113页。SA算法直接简单模拟固体退火。特点：思路清晰、原理简单、使用灵活、应用广泛同时，由于其直接性和简单化，也存在不足与弊病，使其应用及性能受到一定影响。第四节模拟退火算法的改进及并行性第六十九页，共113页。不同p值对CHN144实例测得值第七十页，共113页。

4模拟退火算法的改进及并行性模拟退火算法的优点

质量高；初值鲁棒性强；简单、通用、易实现。模拟退火算法的缺点

由于要求较高的初始温度、较慢的降温速率、较低的终止温度，以及各温度下足够多次的抽样，因此优化过程较长。

4.1模拟退火算法的优缺点第七十一页，共113页。

4模拟退火算法的改进及并行性改进的可行方案（1）设计合适的状态产生函数；（2）设计高效的退火历程；（3）避免状态的迂回搜索；（4）采用并行搜索结构；（5）避免陷入局部极小，改进对温度的控制方式；（6）选择合适的初始状态；（7）设计合适的算法终止准则。

4.2改进内容第七十二页，共113页。

4模拟退火算法的改进及并行性改进的方式：增加某些新的环节（1）增加升温或重升温过程，避免陷入局部极小；（2）增加记忆功能（记忆“Bestsofar”状态）；（3）增加补充搜索过程（以最优结果为初始解）；（4）对每一当前状态，采用多次搜索策略，以概率接受区域内的最优状态；（5）结合其它搜索机制的算法；（6）上述各方法的综合。

4.2改进内容第七十三页，共113页。

4模拟退火算法的改进及并行性改进的思路

（1）记录“Bestsofar”状态，并即时更新；（2）设置双阈值，使得在尽量保持最优性的前提下减少计算量，即在各温度下当前状态连续m1步保持不变则认为Metropolis抽样稳定，若连续m2次退温过程中所得最优解不变则认为算法收敛。

4.3一种改进的模拟退火算法第七十四页，共113页。

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*)<C(s*’)?若是，则令p=p+1；否则，令s*=s*’，p=0；（4）退温ti+1=update(ti)，令i=i+1；（5）判断p>m2?若是，则转第(6)步；否则，返回第(2)步；（6）以最优解s*作为最终解输出，停止算法。

4.3一种改进的模拟退火算法第七十五页，共113页。

4模拟退火算法的改进及并行性改进的抽样过程

（1）令k=0时的初始当前状态为s’(0)=s(i)，q=0；（2）由状态s通过状态产生函数产生新状态s’，计算增量∆C’=C(s’)-C(s)；（3）若∆C’<0，则接受s’作为当前解，并判断C(s*’)>C(s’)?若是，则令s*’=s’，q=0；否则，令q=q+1。若∆C’>0，则以概率exp(-∆C’/t)接受s’作为下一当前状态；（4）令k=k+1，判断q>m1?若是，则转第(5)步；否则，返回第(2)步；（5）将当前最优解s*’和当前状态s’(k)返回改进退火过程。

4.3一种改进的模拟退火算法第七十六页，共113页。TINATime-invariantnoisealgorithm状态产生函数中扰动强度不随时间改变，而是和能量大小相关，能量大的扰动大，能量小的扰动小，能量为零，扰动也为零，算法停止。第七十七页，共113页。MTRSA单调升温(Monotonictemperaturerising)SA在算法退火后期，温度很低且陷入局部极小解的时，算法很难跳出。因此，可以适当重新提高温度，促使算法跳出。第七十八页，共113页。SAMG记忆指导SA(SimulatedAnnealingwithMemmoryGuidance,简记为SAMG)增加一个记忆装置，存储算法计算过程产生的最好的解，以这个解为最终解。第七十九页，共113页。自适应SA自适应SA算法,根据邻域搜索进展的反馈信息,自适应确定温度变化和邻域搜索强度特点：1)退火过程中温度参数变化符合幅值递减的下降总趋势,但不排除局部升温的可能,以保证寻求到合适的温度序列,避免陷入局部最优;2)算法的终止条件依据退火温度和邻域搜索进展状态设计;3)每一温度下算法的迭代次数随温度下降而递增,邻域搜索强度依其对目标函数的贡献动态分配;4)温度变化、邻域搜索和终止条件的控制机制由算法过程自动触发。第八十页，共113页。

4模拟退火算法的改进及并行性

4.4

并行性1、操作并行性：各个环节同时处理；2、进程并行性：同时多个算法运行；3、空间并行性：解空间分解分别处理，最终组合。全过程并行性子进程并行性第八十一页，共113页。第五节算法的实现与应用第八十二页，共113页。引言SAA应用的一般形式：从选定的初始解开始，在借助于控制参数t递减时产生的一系列Markov链中，利用一个新解产生装置和接受准则，重复进行包括“产生新解----计算目标函数差-----判断是否接受新解------接受(或舍弃)新解”这四个任务的实验，不断对当前解迭代，从而达到使目标函数最优的执行过程。第八十三页，共113页。SAA实现通用框架确定问题编码方案设计初始温度、终止温度和温度下降策略（退温函数）设计能量函数设定稳定准则设计产生新解的方式（状态产生函数）设计Metropolis接受准则（状态接受函数）生成初始状态第八十四页，共113页。1、数学模型对问题的简明描述。解空间目标函数初始解所有可能解的集合，它限定了初始解选取和新解产生的范围对问题的优化目标的数学描述，易计算，对应关系明确算法开始迭代的起点，它的选取使算法能导出较好的最终解

5模拟退火算法的实现与应用

5.1应用的一般要求第八十五页，共113页。2、新解的产生和接受机制产生新解由产生装置从当前解的解空间中产生。计算目标函数值之差最快的方法是按增量计算。判断新解是否被接受准则Metropolis新解代替当前解代替变换部分，修正目标函数值。第八十六页，共113页。3、温度更新函数关键参数：初温、温度降低函数、马氏链长度、停止准则。综合应用，达到最佳效果！第八十七页，共113页。SAA求解TSP关键问题如何由旧的解产生新的解方式很多相邻两位置对换——变动最小任意两位置对换单点位置移动子排列位置移动子排列反序子排列位置移动且反序——变动最大理论已经证明上述所有方式都收敛实际验证收敛性能差异很大第八十八页，共113页。1、组合优化问题的求解数学模型一个商人欲到个城市推销商品，每两个城市和之间的距离为，如何选择一条道路使得商人每个城市走一遍后回到起点且所走路经最短。

5模拟退火算法的实现与应用

5.2

算法的实现

第八十九页，共113页。解空间目标函数初始解选为第九十页，共113页。新解的产生1、互换操作(SWAP)随机交换两个不同城市的位置。2、逆序操作(INV)两个不同随机位置的城市逆序。3、插入操作(INS)随机选择某个城市插入到不同随机位置。第九十一页，共113页。衰减函数初值马氏链长停止准则设计终止温度的阀值设计外循环迭代次数算法搜索到的最优值连续若干步保持不变第九十二页，共113页。

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第九十三页，共113页。5模拟退火算法的实现与应用算法流程

例130城市TSP问题（d*=423.741byDBFogel）

第九十四页，共113页。5模拟退火算法的实现与应用初始温度的计算

fori=1:100route=randperm(CityNum);fval0(i)=CalDist(dislist,route);endt0=-(max(fval0)-min(fval0))/log(0.9);

例130城市TSP问题（d*=423.741byDBFogel）

第九十五页，共113页。5模拟退火算法的实现与应用状态产生函数的设计

（1）互换操作，随机交换两个城市的顺序；（2）逆序操作，两个随机位置间的城市逆序；（3）插入操作，随机选择某点插入某随机位置。例130城市TSP问题（d*=423.741byDBFogel）

281593467283419567235981467283591467283591467283591467第九十六页，共113页。5模拟退火算法的实现与应用参数设定

截止温度tf=0.01;

退温系数alpha=0.90;

内循环次数L=200*CityNum;例130城市TSP问题（d*=423.741byDBFogel）

第九十七页，共113页。5模拟退火算法的实现与应用运行过程

例130城市TSP问题（d*=423.741byDBFogel）

第九十八页，共113页。5模拟退火算法的实现与应用运行过程

例130城市TSP