模拟退火算法算法精选文档.ppt

模拟退火算法算法本讲稿第一页，共一百一十四页模拟退火算法是什么？是怎样提出来的？模拟退火算法是什么？是怎样提出来的？模拟退火算法（模拟退火算法（Simulated Annealing，SA）是一种模拟物理退火的过程而设计的优化算法。是一种模拟物理退火的过程而设计的优化算法。它的基本思想最早在它的基本思想最早在1953年就被年就被Metropolis提出，提出，但直到但直到1983年年Kirkpatrick等人才设计出真正等人才设计出真正意义上的模拟退火算法并进行应用。意义上的模拟退火算法并进行应用。模拟退火算法的基本思想是怎样的？模拟退火算法的基本思想是怎样的？模拟退火算法采用类似于物理退火的过程，模拟退火算法采用类似于物理退火的过程，先在一个高温状态下（相当于算法先在一个高温状态下（相当于算法随机搜索随机搜索），然后逐渐退火，），然后逐渐退火，在每个温度下（相当于算法的每一次在每个温度下（相当于算法的每一次状态转移状态转移）徐徐冷却）徐徐冷却（相当于算法（相当于算法局部搜索局部搜索），最终达到物理基态），最终达到物理基态（相当于算法找到（相当于算法找到最优解最优解）。）。本讲稿第二页，共一百一十四页 简介简介l模模拟拟退退火火算算法法的的来来源源是是根根据据复复杂杂组组合合优优化化问问题题与与固体的退火过程之间的相似之处。固体的退火过程之间的相似之处。l该该算算法法在在系系统统向向着着能能量量减减小小的的趋趋势势变变化化过过程程中中，偶偶尔尔允允许许系系统统跳跳到到能能量量较较高高的的状状态态，以以避避开开局局部部最最小小，最终稳定在全局最小。最终稳定在全局最小。本讲稿第三页，共一百一十四页简介简介lSAA属于随机模拟算法属于随机模拟算法l模拟统计物理学中物体加热后冷却这一退火模拟统计物理学中物体加热后冷却这一退火过程而建立的过程而建立的随机优化算法随机优化算法，意图是避免陷，意图是避免陷入局部极小解，早期用于组合优化，后来发入局部极小解，早期用于组合优化，后来发展成一种通用的优化算法。展成一种通用的优化算法。本讲稿第四页，共一百一十四页基本思想基本思想lSAA是是基基于于Mente Carlo迭迭代代求求解解策策略略的的一一种种随随机机寻寻优优算算法法，其其出出发发点点是是基基于于物物理理中中固固体体物物质质的的退退火火过过程程与与一一般般组组合合优优化化问问题题之之间间的的相相似似性。另一方面，性。另一方面，结合结合爬山法和随机行走爬山法和随机行走。lSAA在在某某一一初初温温下下，伴伴随随温温度度参参数数的的不不断断下下降降，结结合合概概率率突突跳跳特特性性在在解解空空间间中中随随机机寻寻找找目目标标函函数数的的全全局局最最优优解解，即即在在局局部部优优解解能能概概率率性性地地跳跳出出并并最最终终趋趋于于全全局最优。局最优。模模拟拟退退火火算算法法是是一一种种通通用用的的优优化化算算法法，目目前前已已在在工工程中得到了广泛应用。程中得到了广泛应用。本讲稿第五页，共一百一十四页基本思路基本思路l首先在高温下进行搜索，此时各状态出现概率相差不首先在高温下进行搜索，此时各状态出现概率相差不大，可以很快进入大，可以很快进入“热平衡状态热平衡状态”，这时进行的是一，这时进行的是一种种“粗搜索粗搜索”，也就是大致找到系统的低能区域；，也就是大致找到系统的低能区域；l随着温度的逐渐降低，各状态出现概率的差距逐渐被扩随着温度的逐渐降低，各状态出现概率的差距逐渐被扩大，搜索精度不断提高。这就可以越来越准确的找到网大，搜索精度不断提高。这就可以越来越准确的找到网络能量函数的络能量函数的全局最小点全局最小点。本讲稿第六页，共一百一十四页一、模拟退火算法概述一、模拟退火算法概述二、模拟退火算法的马氏链描述及收敛性二、模拟退火算法的马氏链描述及收敛性三、模拟退火算法关键参数和操作设计三、模拟退火算法关键参数和操作设计四、模拟退火算法的改进及其并行性四、模拟退火算法的改进及其并行性五、模拟退火算法的实现及应用五、模拟退火算法的实现及应用本讲稿第七页，共一百一十四页固体退火过程固体退火过程Metropolis准则准则组合优化与物理退火的相似性组合优化与物理退火的相似性模拟退火算法的步骤模拟退火算法的步骤第一节第一节 模拟退火算法概述模拟退火算法概述本讲稿第八页，共一百一十四页 1 模拟退火算法概述模拟退火算法概述 l算法的提出算法的提出 模拟退火算法最早的思想由模拟退火算法最早的思想由Metropolis等（等（1953）提出，）提出，1983年年Kirkpatrick等将其应用于组合优化。等将其应用于组合优化。Optimization by simulated annealing,IBM Research Reportl算法的目的算法的目的 解决解决NP复杂性复杂性问题提供有效近似算法；问题提供有效近似算法；克服优化过程陷入局部极小；克服优化过程陷入局部极小；克服初值依赖性。克服初值依赖性。1.1 固体退火过程固体退火过程本讲稿第九页，共一百一十四页1、源于对固体退火过程的模拟；、源于对固体退火过程的模拟；2、采用、采用Metropolis接受准则；接受准则；3、用冷却进度表控制算法进程，使算法在多项、用冷却进度表控制算法进程，使算法在多项式时间里给出一个近似解。式时间里给出一个近似解。固体退火过程的物理图像和统计性质是固体退火过程的物理图像和统计性质是SAA的的物理物理背景背景；Metropolis接受准则使算法接受准则使算法跳离局部跳离局部最优最优“险险井井”；而冷却进度表的合理选择是算法应用的；而冷却进度表的合理选择是算法应用的前提前提。1 模拟退火算法概述模拟退火算法概述 1.1 固体退火过程固体退火过程l算法的基础算法的基础本讲稿第十页，共一百一十四页 1 模拟退火算法概述模拟退火算法概述 l固体退火过程固体退火过程 什么是退火：什么是退火：退火退火是指将固体加热到是指将固体加热到足够高的温度，使分子呈随机足够高的温度，使分子呈随机排列状态排列状态，然后逐步降温使之冷却，最后分子以，然后逐步降温使之冷却，最后分子以低低能状态排列能状态排列，固体达到某种，固体达到某种稳定状态。稳定状态。1.1 固体退火过程固体退火过程本讲稿第十一页，共一百一十四页 固体退火是将固体加热至融化，再徐徐固体退火是将固体加热至融化，再徐徐冷却使之凝固成规整晶体的热力学过程，属冷却使之凝固成规整晶体的热力学过程，属于于热力学与统计物理热力学与统计物理研究的范畴。研究的范畴。由以下三部分组成：由以下三部分组成：加温过程加温过程等温过程等温过程冷却过程冷却过程固体在恒定温度下达到固体在恒定温度下达到热平衡的过程！热平衡的过程！本讲稿第十二页，共一百一十四页 1 模拟退火算法概述模拟退火算法概述 l固体退火过程固体退火过程 加温过程加温过程增强粒子的热运动，使其偏离平衡位置，目的是消增强粒子的热运动，使其偏离平衡位置，目的是消除系统原先可能存在的非均匀态；除系统原先可能存在的非均匀态；等温过程等温过程退火过程中要让温度慢慢降低，在每一个温度退火过程中要让温度慢慢降低，在每一个温度下要达到热平衡状态，下要达到热平衡状态，对于与环境换热而温度不变的封闭系统对于与环境换热而温度不变的封闭系统满足自由能较少定律，系统状态的自发变化总是朝自由能减少的满足自由能较少定律，系统状态的自发变化总是朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡态；方向进行，当自由能达到最小时，系统达到平衡态；冷却过程冷却过程使粒子热运动减弱并渐趋有序，系统能量逐渐下使粒子热运动减弱并渐趋有序，系统能量逐渐下降，从而得到低能的晶体结构降，从而得到低能的晶体结构。当液体凝固为固体的晶态时退火。当液体凝固为固体的晶态时退火过程完成。过程完成。1.1 固体退火过程固体退火过程本讲稿第十三页，共一百一十四页 1 模拟退火算法概述模拟退火算法概述 l数学表述数学表述 在温度在温度T，分子停留在状态，分子停留在状态r满足满足Boltzmann概率分布概率分布 温度低时能量低的微观状态概率大，温度趋于零时，温度低时能量低的微观状态概率大，温度趋于零时，固体几乎处于概率最大能量最小的基态。固体几乎处于概率最大能量最小的基态。1.1 固体退火过程固体退火过程本讲稿第十四页，共一百一十四页 1 模拟退火算法概述模拟退火算法概述 l数学表述数学表述 在在同一个温度同一个温度T，选定两个能量，选定两个能量E1E2，有，有 在同一个温度，分子停留在能量小的状态的概率比在同一个温度，分子停留在能量小的状态的概率比停留在能量大的状态的概率要大。停留在能量大的状态的概率要大。1.1 固体退火过程固体退火过程0本讲稿第十五页，共一百一十四页 1 模拟退火算法概述模拟退火算法概述l数学表述数学表述 若若|D|为状态空间为状态空间D中状态的个数，中状态的个数，D0是具是具有最低能量的状态集合：有最低能量的状态集合：(1)当温度很高时，每个状态概率基本相同，当温度很高时，每个状态概率基本相同，接近接近平均值平均值1/|D|；(2)状态空间存在超过两个不同能量时，具有状态空间存在超过两个不同能量时，具有最低能量状态的概率超出平均值最低能量状态的概率超出平均值1/|D|；(3)当温度趋于当温度趋于0时，分子停留在最低能时，分子停留在最低能量状态的概率趋于量状态的概率趋于1。1.1 固体退火过程固体退火过程能量最低状态能量最低状态非能量最低状态非能量最低状态本讲稿第十六页，共一百一十四页 1 模拟退火算法概述模拟退火算法概述 lMetropolis准则（准则（1953）以概率接受新状态以概率接受新状态 固体在恒定温度下达到热平衡的过程可以用固体在恒定温度下达到热平衡的过程可以用Monte Carlo方法方法（计算机随机模拟方法）加以模拟，虽然（计算机随机模拟方法）加以模拟，虽然该方法简单，但必须大量采样才能得到比较精确的该方法简单，但必须大量采样才能得到比较精确的结果，计算量很大。结果，计算量很大。1.2 Metropolis准则准则本讲稿第十七页，共一百一十四页lMonte Carlo模拟退火过程模拟退火过程l蒙蒙特特卡卡罗罗(Monte Carlo)方方法法，或或称称计计算算机机随随机机模模拟拟方方法法，是是一一种种基基于于“随随机机数数”的的计计算算方方法法。这这一一方方法法源源于于美美国国在在第第一一次次世世界界大大战战中中研研制制原原子子弹弹的的“曼曼哈哈顿顿计计划划”。该该计计划划的的主主持持人人之之一一、数数学学家家冯冯诺诺伊伊曼曼用用驰驰名名世世界界的的赌赌城城摩摩纳纳哥哥的的Monte Carlo来来命命名名这这种种方方法法，为为它它蒙蒙上上了一层神秘色彩。了一层神秘色彩。本讲稿第十八页，共一百一十四页lMonte Carlo方法方法lMonte Carlo方方法法的的基基本本思思想想很很早早以以前前就就被被人人们所发现和利用。们所发现和利用。l早早在在17世世纪纪，人人们们就就知知道道用用事事件件发发生生的的“频频率率”来决定事件的来决定事件的“概率概率”。lBuffon试试验验：19世世纪纪人人们们用用投投针针试试验验的的方方法法来来求解圆周率求解圆周率。l本本世世纪纪40年年代代电电子子计计算算机机的的出出现现，特特别别是是近近年年来来高高速速电电子子计计算算机机的的出出现现，使使得得用用数数学学方方法法在在计计算算机机上上大大量量、快快速速地地模模拟拟这这样样的的试试验验成成为为可可能。能。本讲稿第十九页，共一百一十四页lMonte Carlo方法方法l用用民民意意测测验验来来作作一一个个不不严严格格的的比比喻喻。民民意意测测验验的的人人不不是是征征询询每每一一个个登登记记选选民民的的意意见见，而而是是通通过过对对选选民民进进行行小小规规模模的的抽抽样样调调查查来来确确定定可可能能的的优胜者。其基本思想是一样的。优胜者。其基本思想是一样的。l它它需需要要一一个个良良好好的的随随机机数数源源。这这种种方方法法往往往往包包含含一一些些误误差差，但但是是随随着着随随机机抽抽取取样样本本数数量量的的增增加，结果也会越来越精确。加，结果也会越来越精确。本讲稿第二十页，共一百一十四页 1 模拟退火算法概述模拟退火算法概述 lMetropolis准则（准则（1953）以概率接受新状态以概率接受新状态 若在温度若在温度T，当前状态，当前状态i 新状态新状态j 若若Ej=randrom0,1 s=sj;Until 抽样稳定准则满足；抽样稳定准则满足；退温退温tk+1=update(tk)并令并令k=k+1；Until 算法终止准则满足；算法终止准则满足；输出算法搜索结果。输出算法搜索结果。1.4 模拟退火算法的步骤模拟退火算法的步骤本讲稿第三十二页，共一百一十四页 1 模拟退火算法概述模拟退火算法概述 l影响优化结果的主要因素影响优化结果的主要因素 给定初温给定初温t=t0，随机产生初始状态，随机产生初始状态s=s0，令，令k=0；Repeat Repeat 产生新状态产生新状态sj=Genete(s)；if min1,exp-(C(sj)-C(s)/tk=randrom0,1 s=sj;Until 抽样稳定准则满足；抽样稳定准则满足；退温退温tk+1=update(tk)并令并令k=k+1；Until 算法终止准则满足；算法终止准则满足；输出算法搜索结果。输出算法搜索结果。1.4 模拟退火算法的步骤模拟退火算法的步骤三函数两准则三函数两准则初始温度初始温度本讲稿第三十三页，共一百一十四页三函数两准则三函数两准则状态产生函数状态产生函数状态接受函数状态接受函数退温函数退温函数抽样稳定准则抽样稳定准则退火结束准则退火结束准则本讲稿第三十四页，共一百一十四页SAA流程流程确定确定初温初温随机给定随机给定初始解初始解收敛准则收敛准则满足否？满足否？输出结果输出结果Y抽样稳定准则抽样稳定准则满足否？满足否？由当前由当前状态产生状态产生新状态新状态接受函数接受函数成立否？成立否？替换当前状态替换当前状态YYNNN退温退温保持当前状态不变保持当前状态不变 关键环节关键环节1 1 初温、初始解初温、初始解2 2 状态产生函数状态产生函数3 3 状态接受函数状态接受函数4 4 退温函数退温函数5 5 抽样稳定准则抽样稳定准则6 6 收敛准则收敛准则本讲稿第三十五页，共一百一十四页本讲稿第三十六页，共一百一十四页SAA特点特点l可以保证全局最优可以保证全局最优l特别适合组合优化问题特别适合组合优化问题l可以随机选择初始解可以随机选择初始解l对问题本身没有特别要求，不会因为问题对问题本身没有特别要求，不会因为问题实例的改变影响性能实例的改变影响性能l简单易行，通用性好简单易行，通用性好本讲稿第三十七页，共一百一十四页马氏链描述马氏链描述收敛性收敛性时齐算法收敛性时齐算法收敛性非时齐算法收敛性非时齐算法收敛性渐近性态渐近性态第二节第二节 SAA的马氏链描述及收敛性的马氏链描述及收敛性本讲稿第三十八页，共一百一十四页 模拟退火算法模拟退火算法(SAA)是将物理退火过程与组是将物理退火过程与组合优化相结合的一种随机迭代寻优算法。合优化相结合的一种随机迭代寻优算法。数学模型描述为数学模型描述为 由某一较高初始温度开始，在给定的邻域由某一较高初始温度开始，在给定的邻域结构中，模拟退火过程，利用概率特性与抽样结构中，模拟退火过程，利用概率特性与抽样策略在解空间中随机搜索，随着温度不断下降策略在解空间中随机搜索，随着温度不断下降重复抽样，用来优化问题的解。重复抽样，用来优化问题的解。引言引言本讲稿第三十九页，共一百一十四页设设 为所有状态构成的解空间，为所有状态构成的解空间，为为k时刻状态变量的取值。时刻状态变量的取值。随机序列随机序列 称为称为马氏链马氏链,若若满足满足简简记记（记忆遗忘功能）（记忆遗忘功能）2 SAA的的马氏链描述及收敛性马氏链描述及收敛性 2.1 马尔马尔可夫（可夫（Markov）链）链本讲稿第四十页，共一百一十四页一步转移概率一步转移概率n步转移概率步转移概率有限状态马氏链有限状态马氏链若解空间有限。若解空间有限。时齐马氏链时齐马氏链本讲稿第四十一页，共一百一十四页模拟退火算法模拟退火算法(SAA)的搜索进程：的搜索进程：算法从某一个初始状态开始后，每一步状算法从某一个初始状态开始后，每一步状态转移均是在当前状态的邻域中随机产生新状态转移均是在当前状态的邻域中随机产生新状态，然后以一定概率进行接受的。态，然后以一定概率进行接受的。接受概率仅依赖于新状态和当前状态，并由温接受概率仅依赖于新状态和当前状态，并由温度加以控制。因此，度加以控制。因此，SAA对应一个马氏链。对应一个马氏链。本讲稿第四十二页，共一百一十四页若固定每一温度，算法均计算若固定每一温度，算法均计算马氏链的变化直至平稳分布，马氏链的变化直至平稳分布，然后下降温度。然后下降温度。时齐算法时齐算法非时齐算法非时齐算法若无需各温度下算法均达到平若无需各温度下算法均达到平稳分布，但温度需按照一定的稳分布，但温度需按照一定的速率下降。或称非平稳马氏链速率下降。或称非平稳马氏链算法。算法。本讲稿第四十三页，共一百一十四页SAA基础理论基础理论马氏链模型马氏链模型本讲稿第四十四页，共一百一十四页SAA要实现全局收敛必须满足下列条件：要实现全局收敛必须满足下列条件：状态可达性状态可达性初值鲁棒性初值鲁棒性极限分布存在性极限分布存在性收敛到最优解收敛到最优解温度不变，温度不变，M链极限分布存在链极限分布存在温度渐近温度渐近0，M链极限分布存在链极限分布存在对应马氏链的状态图是强连通的对应马氏链的状态图是强连通的对算法的最终结果不依赖于初值对算法的最终结果不依赖于初值本讲稿第四十五页，共一百一十四页定义定义1状态状态i可达状态可达状态j:定义定义2平稳分布平稳分布:称称 为马氏链的平稳分布为马氏链的平稳分布,若一步转移概率满足等式若一步转移概率满足等式2.2.1 时齐算法的收敛性时齐算法的收敛性 2 SAA的的马氏链描述及收敛性马氏链描述及收敛性 2.2 收敛性分析收敛性分析本讲稿第四十六页，共一百一十四页时齐模拟退火算法的收敛性时齐模拟退火算法的收敛性结论结论：结论结论1 时齐模拟退火算法对应的有限状态马氏链存时齐模拟退火算法对应的有限状态马氏链存在平稳分布。在平稳分布。结论结论2 当温度趋于当温度趋于0时，马氏链以概率时，马氏链以概率1收敛到收敛到最优状态集，而收敛到非最优状态的概率为最优状态集，而收敛到非最优状态的概率为0。实现途径：实现途径：通过各温度下各状态序列无限长得通过各温度下各状态序列无限长得以实现！以实现！本讲稿第四十七页，共一百一十四页2.2.2 非时齐算法的收敛性非时齐算法的收敛性收敛定理收敛定理本讲稿第四十八页，共一百一十四页 对退温函数加以严格控制，可使得对退温函数加以严格控制，可使得SA算法以算法以概率概率1收敛到全局最优解。收敛到全局最优解。可设计退温函数为可设计退温函数为其中其中 ，则当，则当 时，时，SA算法算法以概率以概率1收敛到全局最优解。收敛到全局最优解。本讲稿第四十九页，共一百一十四页2.2.3 SA算法渐近性能的逼近算法渐近性能的逼近 收敛可以保证，但是时间性能不好收敛可以保证，但是时间性能不好 收敛速度有待研究收敛速度有待研究本讲稿第五十页，共一百一十四页第三节第三节 模拟退火算法关键参数和操作的设计模拟退火算法关键参数和操作的设计三函数两准则三函数两准则状态产生函数状态产生函数状态接受函数状态接受函数退温函数退温函数抽样稳定准则抽样稳定准则退火结束准则退火结束准则从算法流程看从算法流程看，SA算法包括三函数两准则算法包括三函数两准则初温初温本讲稿第五十一页，共一百一十四页1 状态产生函数（邻域函数）状态产生函数（邻域函数）设计的出发点：设计的出发点：尽可能保证产生的候选解遍布全部解空间。尽可能保证产生的候选解遍布全部解空间。产生候选解的方式产生候选解的方式候选解产生的概率分布候选解产生的概率分布两部分两部分本讲稿第五十二页，共一百一十四页l前者决定由当前解产生候选解的方式，后者决定前者决定由当前解产生候选解的方式，后者决定在当前解产生的候选解中选择不同状态的概率。在当前解产生的候选解中选择不同状态的概率。l候选解的产生方式由问题的性质决定，通常在当前状态候选解的产生方式由问题的性质决定，通常在当前状态的邻域结构内以一定概率方式产生，的邻域结构内以一定概率方式产生，l而邻域函数和概率方式可以多样化设计，其中概率分布而邻域函数和概率方式可以多样化设计，其中概率分布可以是均匀分布、正态分布、指数分布、柯西分布等。可以是均匀分布、正态分布、指数分布、柯西分布等。本讲稿第五十三页，共一百一十四页2 状态接受函数状态接受函数目的：目的：尽可能接受优化解尽可能接受优化解 状态接受函数一般以概率的方式给出，状态接受函数一般以概率的方式给出，不同接受函数的差别主要在于不同接受函数的差别主要在于接受概率接受概率的形的形式不同。式不同。本讲稿第五十四页，共一百一十四页固定温度下，接受使目标函数值下降的候选解的概率固定温度下，接受使目标函数值下降的候选解的概率要大于使目标函数值上升的候选解的概率。要大于使目标函数值上升的候选解的概率。随温度的下降，接受使目标函数值上升的解的概率随温度的下降，接受使目标函数值上升的解的概率要逐渐减小。要逐渐减小。当温度趋于零时，只能接受目标函数值下降的解。当温度趋于零时，只能接受目标函数值下降的解。设计状态接受概率，应遵循的原则：设计状态接受概率，应遵循的原则：本讲稿第五十五页，共一百一十四页3 初温初温实验表明：实验表明：初温值只要选择充分大，获得高质量初温值只要选择充分大，获得高质量解的概率就大！但花费计算时间增加。解的概率就大！但花费计算时间增加。初温的选择要足够高。初温的选择要足够高。初温的确定应折衷考虑优化质量和优化效率。初温的确定应折衷考虑优化质量和优化效率。本讲稿第五十六页，共一百一十四页均匀抽样一组状态，选各状态目标值的方差均匀抽样一组状态，选各状态目标值的方差利用经验公式利用经验公式随机产生一组状态，确定两随机产生一组状态，确定两两状态间的最大目标值差，两状态间的最大目标值差，然后依据差值，利用一定的然后依据差值，利用一定的函数确定初温。例如，函数确定初温。例如，本讲稿第五十七页，共一百一十四页初始温度初始温度温度更新函数温度更新函数内循环终止准则内循环终止准则外循环终止准则外循环终止准则退火历程退火历程(annealing schedule)本讲稿第五十八页，共一百一十四页4 温度更新函数温度更新函数衰减量衰减量“以小为宜以小为宜”实验表明降温速度越慢，获得高质量解的几率越大，实验表明降温速度越慢，获得高质量解的几率越大，但花费的计算时间将同时增加。但花费的计算时间将同时增加。温度高时下降的慢些，温度低时下降的快些。温度高时下降的慢些，温度低时下降的快些。即温度的下降方式，用于在外循环中修改温度值。即温度的下降方式，用于在外循环中修改温度值。本讲稿第五十九页，共一百一十四页Nahar及及Skiscim等人把等人把 划分成划分成K个个小区间，温度更新函数为小区间，温度更新函数为Kirkpatrick首先提出首先提出被被Johnson,Bonomi及及Lutton采用采用取取0.5至至0.99之间之间本讲稿第六十页，共一百一十四页5 内循环终止准则内循环终止准则检验目标函数值的均值是否稳定检验目标函数值的均值是否稳定连续若干步目标函数值的变化较小连续若干步目标函数值的变化较小按一定的步数抽样按一定的步数抽样链长链长（Metropolis抽样稳定准则）抽样稳定准则）用于决定在各温度下产生候选解的数目。用于决定在各温度下产生候选解的数目。时齐算法时齐算法常用常用Metropolis抽样稳定准则包括：抽样稳定准则包括：非时齐非时齐SAA：每个温度下只产生一个或少量候选解。每个温度下只产生一个或少量候选解。本讲稿第六十一页，共一百一十四页l具体应与问题规模成比例。具体应与问题规模成比例。l实验表明高温时迭代次数越多越好，低温实验表明高温时迭代次数越多越好，低温时迭代次数可以适当减少。时迭代次数可以适当减少。本讲稿第六十二页，共一百一十四页6 外循环终止准则外循环终止准则理论上理论上要求温度终值趋于零要求温度终值趋于零设置终止温度的阀值设置终止温度的阀值设置外循环迭代次数设置外循环迭代次数(6-50)算法搜索到的最优值连续若干步保持不变算法搜索到的最优值连续若干步保持不变（算法终止准则）（算法终止准则）用于决定算法何时结束。用于决定算法何时结束。通常的做法包括：通常的做法包括：检验系统熵是否稳定检验系统熵是否稳定本讲稿第六十三页，共一百一十四页三个参数三个参数 、和和 值均有显著影响。值均有显著影响。总结总结过大的过大的 值、值、值和值和 值均能导致过长的值均能导致过长的CPU时间。因而在最终解的质量有待较大时间。因而在最终解的质量有待较大 值和值和 值予以保证的前提下，选取较小值予以保证的前提下，选取较小的的 值可以抑制值可以抑制CPU时间上升的态势。时间上升的态势。本讲稿第六十四页，共一百一十四页模拟退火算法基本要素和设定方法模拟退火算法基本要素和设定方法本讲稿第六十五页，共一百一十四页l模拟退火算法是一种通用的随机搜索算法，它可用模拟退火算法是一种通用的随机搜索算法，它可用于解决众多的优化问题，并已经广泛的应用于其他于解决众多的优化问题，并已经广泛的应用于其他领域。如领域。如VLSL设计、图像识别等。当待解决的问设计、图像识别等。当待解决的问题复杂性较高，而且规模较大时，在对问题的领题复杂性较高，而且规模较大时，在对问题的领域知识甚少的情况下，采用模拟退火算法最合适。域知识甚少的情况下，采用模拟退火算法最合适。因为模拟退火算法不像其他确定型启发式算法那因为模拟退火算法不像其他确定型启发式算法那样，需要依赖于问题的领域知识来提高算法的性样，需要依赖于问题的领域知识来提高算法的性能。能。本讲稿第六十六页，共一百一十四页l但是，从另一方面来说，已知有关待解决问题的一些但是，从另一方面来说，已知有关待解决问题的一些知识后，模拟退火算法却无法充分利用它们，这使得知识后，模拟退火算法却无法充分利用它们，这使得模拟退火算法的优点就成了缺点。如何把传统的启发模拟退火算法的优点就成了缺点。如何把传统的启发式搜索方法和模拟退火随机搜索算法结合起来，这是式搜索方法和模拟退火随机搜索算法结合起来，这是一个有待研究的十分有意义的课题。一个有待研究的十分有意义的课题。本讲稿第六十七页，共一百一十四页l模模拟拟退退火火算算法法在在求求解解规规模模较较大大的的实实际际问问题题时时，往往往往存在以下缺点：存在以下缺点：（1）收敛速度比较慢。）收敛速度比较慢。（2）尽管理论上只要计算时间足够长，模拟退火法就可以）尽管理论上只要计算时间足够长，模拟退火法就可以保证以概率保证以概率1收敛于全局最优点。但是在实际算法的实现收敛于全局最优点。但是在实际算法的实现过程中，由于计算速度和时间的限制，在优化效果和计过程中，由于计算速度和时间的限制，在优化效果和计算时间二者之间存在矛盾，因而难以保证计算结果为全算时间二者之间存在矛盾，因而难以保证计算结果为全局最优点，优化效果不甚理想。局最优点，优化效果不甚理想。（3）在每一温度下很难判定是否达到了平衡状态。）在每一温度下很难判定是否达到了平衡状态。本讲稿第六十八页，共一百一十四页l为此，人们对模拟退火算法提出了各种各样的改为此，人们对模拟退火算法提出了各种各样的改进，其中包括并行模拟退火算法、快速模拟退火进，其中包括并行模拟退火算法、快速模拟退火算法（算法（Cauchy机）和对模拟退火算法中各个函数和参机）和对模拟退火算法中各个函数和参数的重新设计等。数的重新设计等。本讲稿第六十九页，共一百一十四页SA算法直接简单模拟固体退火。算法直接简单模拟固体退火。特点：特点：思路清晰、原理简单、使用灵活、应用广泛思路清晰、原理简单、使用灵活、应用广泛同时，由于其直接性和简单化，也存在不足与同时，由于其直接性和简单化，也存在不足与弊病，使其应用及性能受到一定影响。弊病，使其应用及性能受到一定影响。第四节第四节 模拟退火算法的改进及并行性模拟退火算法的改进及并行性本讲稿第七十页，共一百一十四页不同不同p值对值对CHN144实例测得实例测得 值值本讲稿第七十一页，共一百一十四页 4 模拟退火算法的改进及并行性模拟退火算法的改进及并行性l模拟退火算法的优点模拟退火算法的优点 质量高；质量高；初值鲁棒性强；初值鲁棒性强；简单、通用、易实现。简单、通用、易实现。l模拟退火算法的缺点模拟退火算法的缺点 由于要求较高的初始温度、较慢的降温速率、较由于要求较高的初始温度、较慢的降温速率、较低的终止温度，以及各温度下足够多次的抽样，低的终止温度，以及各温度下足够多次的抽样，因此优化过程较长。因此优化过程较长。4.1 模拟退火算法的优缺点模拟退火算法的优缺点本讲稿第七十二页，共一百一十四页 4 模拟退火算法的改进及并行性模拟退火算法的改进及并行性l改进的可行方案改进的可行方案 （1）设计合适的状态产生函数；）设计合适的状态产生函数；（2）设计高效的退火历程；）设计高效的退火历程；（3）避免状态的迂回搜索；）避免状态的迂回搜索；（4）采用并行搜索结构；）采用并行搜索结构；（5）避免陷入局部极小，改进对温度的控制方式；）避免陷入局部极小，改进对温度的控制方式；（6）选择合适的初始状态；）选择合适的初始状态；（7）设计合适的算法终止准则。）设计合适的算法终止准则。4.2 改进内容改进内容本讲稿第七十三页，共一百一十四页 4 模拟退火算法的改进及并行性模拟退火算法的改进及并行性l改进的方式：增加某些新的环节改进的方式：增加某些新的环节 （1）增加升温或重升温过程，避免陷入局部极小；）增加升温或重升温过程，避免陷入局部极小；（2）增加记忆功能（记忆）增加记忆功能（记忆“Best so far”状态）；状态）；（3）增加补充搜索过程（以最优结果为初始解）；）增加补充搜索过程（以最优结果为初始解）；（4）对每一当前状态，采用多次搜索策略，以概率接受区域内的最）对每一当前状态，采用多次搜索策略，以概率接受区域内的最优状态；优状态；（5）结合其它搜索机制的算法；）结合其它搜索机制的算法；（6）上述各方法的综合。）上述各方法的综合。4.2 改进内容改进内容本讲稿第七十四页，共一百一十四页 4 模拟退火算法的改进及并行性模拟退火算法的改进及并行性l改进的思路改进的思路 （1）记录）记录“Best so far”状态，并即时更新；状态，并即时更新；（2）设置双阈值，使得在尽量保持最优性的前提）设置双阈值，使得在尽量保持最优性的前提下减少计算量，即在各温度下当前状态连续下减少计算量，即在各温度下当前状态连续 m1 步步保持不变则认为保持不变则认为Metropolis抽样稳定，若连续抽样稳定，若连续 m2 次次退温过程中所得最优解不变则认为算法收敛。退温过程中所得最优解不变则认为算法收敛。4.3 一种改进的模拟退火算法一种改进的模拟退火算法本讲稿第七十五页，共一百一十四页 4 模拟退火算法的改进及并行性模拟退火算法的改进及并行性l改进的退火过程改进的退火过程 （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 模拟退火算法的改进及并行性模拟退火算法的改进及并行性l改进的抽样过程改进的抽样过程 （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 lTime-invariant noise algorithml状态产生函数中扰动强度不随时间改变，而是和能量大小相关，能量大的扰动大，能量小的扰动小，能量为零，扰动也为零，算法停止。本讲稿第七十八页，共一百一十四页MTRSAl单调升温(Monotonic temperature rising)SAl在算法退火后期，温度很低且陷入局部极小解的时，算法很难跳出。因此，可以适当重新提高温度，促使算法跳出。本讲稿第七十九页，共一百一十四页SAMGl记忆指导SA(Simulated Annealing with Memmory Guidance,简记为SAMG)l增加一个记忆装置，存储算法计算过程产生的最好的解，以这个解为最终解。本讲稿第八十页，共一百一十四页自适应SAl自适应自适应SA算法算法,l根据邻域搜索进展的反馈信息根据邻域搜索进展的反馈信息,自适应确定温度变化和邻域自适应确定温度变化和邻域搜索强度搜索强度l特点：特点：l1)退火过程中温度参数变化符合幅值递减的下降总趋势退火过程中温度参数变化符合幅值递减的下降总趋势,但不但不排除局部升温的可能排除局部升温的可能,以保证寻求到合适的温度序列以保证寻求到合适的温度序列,避免陷避免陷入局部最优入局部最优;l2)算法的终止条件依据退火温度和邻域搜索进展状态设算法的终止条件依据退火温度和邻域搜索进展状态设计计;l3)每一温度下算法的迭代次数随温度下降而递增每一温度下算法的迭代次数随温度下降而递增,邻域邻域搜索强度依其对目标函数的贡献动态分配搜索强度依其对目标函数的贡献动态分配;l4)温度变化、邻域搜索和终止条件的控制机制由算法过程自动温度变化、邻域搜索和终止条件的控制机制由算法过程自动触发。触发。本讲稿第八十一页，共一百一十四页 4 模拟退火算法的改进及并行性模拟退火算法的改进及并行性 4.4 并行性并行性1、操作并行性操作并行性：各个：各个环节环节同同时处时处理；理；2、进进程并行性程并行性：同：同时时多个算法运行；多个算法运行；3、空空间间并行性并行性：解空：解空间间分解分分解分别处别处理，最理，最终组终组合。合。全过程并行性全过程并行性子进程并行性子进程并行性本讲稿第八十二页，共一百一十四页第五节第五节 算法的实现与应用算法的实现与应用本讲稿第八十三页，共一百一十四页引言引言SAA应用的一般形式：应用的一般形式：从选定的初始解开始，在借助于控制参数从选定的初始解开始，在借助于控制参数t递减时产生的一系列递减时产生的一系列Markov链中，利用一个新链中，利用一个新解产生装置和接受准则，重复进行包括解产生装置和接受准则，重复进行包括“产生新产生新解解-计算目标函数差计算目标函数差-判断是否接受新解判断是否接受新解-接受接受(或舍弃或舍弃)新解新解”这四个任务的实验，不断对这四个任务的实验，不断对当前解迭代，从而达到使目标函数当前解迭代，从而达到使目标函数最优最优的执行过的执行过程。程。本讲稿第八