《随机神经网络 PPT课件.ppt》由会员分享，可在线阅读，更多相关《随机神经网络 PPT课件.ppt（74页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、随机网络：学习运行引入随机机制随机网络：学习运行引入随机机制1.1.存在的问题：以目标函数的极小值，作为学习或运行的目的存在的问题：以目标函数的极小值，作为学习或运行的目的 BPBP算法算法-误差函数，梯度下降误差函数，梯度下降 HopHop算法算法-HebbHebb规则规则-能量函数能量函数E E 容易陷入局部极小点。容易陷入局部极小点。无法避免，从无法避免，从入手：将入手：将“总是沿梯总是沿梯度下降方向演变度下降方向演变”改为改为”大部分沿梯度下大部分沿梯度下降方向演变，但允许少数情况沿上升方向降方向演变，但允许少数情况沿上升方向演变。演变。”目录v引言引言v模拟退火算法的模型模拟退火算法
2、的模型v模拟退火算法的简单应用模拟退火算法的简单应用v模拟退火算法的参数控制问题模拟退火算法的参数控制问题vBoltzmann机机4.1 引言引言v模拟退火模拟退火(Simulated Annealing,SA)(Simulated Annealing,SA)算法是算法是近年来特别引入注目的一种适用于解大型组近年来特别引入注目的一种适用于解大型组合优化问题的优化方法合优化问题的优化方法,算法来源于固体退火算法来源于固体退火原理原理,其核心在于其核心在于模仿热力学中液体的冻结与结晶或金属熔液的冷模仿热力学中液体的冻结与结晶或金属熔液的冷却与退火过程却与退火过程-物理退火过程和物理退火过程和Met
3、ropolisMetropolis准则准则.v 下面分别介绍下面分别介绍SASA原理原理SASA全局优化的直观解释全局优化的直观解释4.1.1 4.1.1 模拟退火模拟退火原理原理v简单而言简单而言,在固体退火时在固体退火时,先将固体加热使其先将固体加热使其温度充分高温度充分高,再让其徐徐冷却再让其徐徐冷却,其物理退火过其物理退火过程由以下三部分组成：程由以下三部分组成：加温过程加温过程等温过程等温过程冷却过程冷却过程4.1.1 4.1.1 模拟退火模拟退火原理原理加温过程加温过程v在固体退火时在固体退火时,先将固体加热使其温度充分高先将固体加热使其温度充分高,其目的是增强粒子的热运动其目的是
4、增强粒子的热运动,使其偏离平衡位使其偏离平衡位置置.v当温度足够高时当温度足够高时,固体将溶解为液体固体将溶解为液体,固体内固体内部粒子随温升变为无序状部粒子随温升变为无序状,彼此之间可以自彼此之间可以自由移动由移动,从而消除系统原先可能存在的非均匀从而消除系统原先可能存在的非均匀态态,使随后进行的冷却过程以某一平衡态为起使随后进行的冷却过程以某一平衡态为起点点.v熔解过程熔解过程(加热固体至高温液态加热固体至高温液态)与系统的熵与系统的熵增过程联系增过程联系,系统内部能量也随温度的升高而系统内部能量也随温度的升高而增大增大.4.1.1 4.1.1 模拟退火模拟退火原理原理等温过程等温过程v物
5、理学的知识告诉我们物理学的知识告诉我们,对于与周围环境交换热量而对于与周围环境交换热量而温度不变的封闭系统温度不变的封闭系统,系统状态的自发变化总是朝自系统状态的自发变化总是朝自由能减少的方向进行由能减少的方向进行,当自由能达到最小时当自由能达到最小时,系统达系统达到平衡态到平衡态.冷却过程冷却过程v目的是使粒子的热运动减弱并渐趋有序目的是使粒子的热运动减弱并渐趋有序,系统能量逐系统能量逐渐下降渐下降,从而得到低能的晶体结构从而得到低能的晶体结构.v徐徐冷却时粒子就会丧失由干温度而引起的流动性徐徐冷却时粒子就会丧失由干温度而引起的流动性,渐趋有序渐趋有序,这时原子就会自己排列起来而形成一种纯这
6、时原子就会自己排列起来而形成一种纯晶体晶体,它们依次地朝各个方向排列成几十亿倍于单个它们依次地朝各个方向排列成几十亿倍于单个原子大小的距离原子大小的距离,这个纯晶体状态就是该系统的平衡这个纯晶体状态就是该系统的平衡态态,亦为最小能量状态亦为最小能量状态.4.1.1 4.1.1 模拟退火模拟退火原理原理v有趣的是有趣的是:对一个徐徐冷却的系统对一个徐徐冷却的系统,当这些原子在逐渐失去当这些原子在逐渐失去活力的同时活力的同时,它们自己就同时地排列而形成一个它们自己就同时地排列而形成一个纯晶体纯晶体,使这个系统的能量达到其最小值使这个系统的能量达到其最小值.这里引起特别关注的是这里引起特别关注的是,
7、在这个物理系统的冷却在这个物理系统的冷却过程中过程中,这些原子是这些原子是“同时地同时地”把它们自己排列把它们自己排列成一个纯晶体的成一个纯晶体的.如果一种金属熔液是被快速冷却或泼水使其冷却如果一种金属熔液是被快速冷却或泼水使其冷却的的,则它不能达到纯晶体状态则它不能达到纯晶体状态,而是变成一种多晶而是变成一种多晶体或非晶体状态体或非晶体状态,系统处在这种状态时具有较高系统处在这种状态时具有较高的能量的能量.4.1.1 4.1.1 模拟退火模拟退火原理原理vSASA算法就是模仿上述物理系统徐徐退火过程的一种算法就是模仿上述物理系统徐徐退火过程的一种通用随机搜索技术通用随机搜索技术,人们可用马尔
8、柯夫链的遍历理论人们可用马尔柯夫链的遍历理论来给它以数学上的描述来给它以数学上的描述.在搜索最优解的过程中在搜索最优解的过程中,SA,SA算法除了可以接受优算法除了可以接受优化解外化解外,还基于随机接受准则还基于随机接受准则(Metropolis(Metropolis准则准则)有限度地接受有限度地接受恶化解恶化解,并且接受恶化解的概率慢并且接受恶化解的概率慢慢趋向于慢趋向于0.0.v这使得算法有可能从局部最优中跳出这使得算法有可能从局部最优中跳出,尽可能找到全尽可能找到全局最优解局最优解,并保证了算法的收敛并保证了算法的收敛.SASA的思想最早是由的思想最早是由MetropolisMetrop
9、olis等等(1953)(1953)提出的提出的.vMetropolisMetropolis等提出了重要性采样法等提出了重要性采样法,即以概率接受新即以概率接受新状态状态.对于某一给定温度，系统若达到热平衡状态对于某一给定温度，系统若达到热平衡状态(循环若干次循环若干次)，则该状态下的能量服从，则该状态下的能量服从BottzmannBottzmann分布分布.4.1.1 4.1.1 模拟退火模拟退火原理原理4.1.1 4.1.1 模拟退火模拟退火原理原理v具体而言,在温度t,由当前状态i产生新状态j,两者的能量分别为Ei和Ej,若EjEi则接受新状态j为当前状态；否则,若概率 大于0,1)区间
10、内的随机数则仍旧接受新状态j为当前状态,若不成立则保留i为当前状态,其中k为Boltzmann常数.v这种重要性采样过程在高温下可接受与当前状态能量差较大的新状态,而在低温下基本只接受与当前能量差较小的新状态,而且当温度趋于零时,就不能接受比当前状态能量高的新状态.这种接受准则通常称为Metropolis准则.4.1.1 4.1.1 模拟退火模拟退火原理原理19831983年年KirkpatrickKirkpatrick等人意识到组合优化与物理退火的相等人意识到组合优化与物理退火的相似性似性,并受到并受到MetropolisMetropolis准则的启迪准则的启迪,首次把固体的退火首次把固体的
11、退火过程与组合极小化联系在一起过程与组合极小化联系在一起,他们分别用目标函数和组他们分别用目标函数和组合极小化问题的解替代物理系统的能量和状态合极小化问题的解替代物理系统的能量和状态,从而物理从而物理系统内粒子的摄动等价于组合极小化问题的试探系统内粒子的摄动等价于组合极小化问题的试探.vSASA是基于是基于Monte CarloMonte Carlo迭代求解策略的一种随机寻优迭代求解策略的一种随机寻优算法算法.v极小化过程就是极小化过程就是:首先在一个高温首先在一个高温(温度现在就成为一个控制参数温度现在就成为一个控制参数)状态下状态下,利用具有概率突跳特性的利用具有概率突跳特性的Metrop
12、olisMetropolis抽抽样策略在解空间中进行随机搜索样策略在解空间中进行随机搜索,伴随温度的不伴随温度的不断下降断下降,重复抽样过程重复抽样过程,将有效地将有效地“溶化溶化”解空间解空间;然后慢慢地降低温度直到系统然后慢慢地降低温度直到系统“结晶结晶”到一个稳到一个稳定解定解,最终得到问题的全局最优解最终得到问题的全局最优解.4.1.1 4.1.1 模拟退火模拟退火原理原理SASA算法在组合最优化中的成功应用掀起了算法在组合最优化中的成功应用掀起了SASA算法算法研究与应用的高潮研究与应用的高潮.v19911991年年DekkersDekkers和和AartsAarts探讨将探讨将SA
13、SA算法应用于算法应用于求解连续优化问题求解连续优化问题.v2020世纪世纪9090年代以来年代以来,SA,SA算法在算法在NNNN、GAGA、进化算、进化算法等优化、学习领域得到极大的应用法等优化、学习领域得到极大的应用.4.1.1 4.1.1 模拟退火模拟退火原理原理vSASA算法的主要精髓是基于算法的主要精髓是基于MetropolisMetropolis准则可准则可接受求解过程的恶化解接受求解过程的恶化解.Metropolis.Metropolis准则为准则为:粒子在温度粒子在温度T T时趋于平衡的概率为时趋于平衡的概率为其中其中E E为温度为温度T T时的内能时的内能,E E为其改变量
14、为其改变量,k k为为BoltzmannBoltzmann常数常数.4.1.1 4.1.1 模拟退火模拟退火原理原理利用上述固体退火原理来模拟求解组合优化问题利用上述固体退火原理来模拟求解组合优化问题时时,v将内能将内能E E模拟为目标函数值模拟为目标函数值f f,温度温度T T演化成控演化成控制参数制参数t t,v并以并以MetropolisMetropolis准则的概率准则的概率接受恶化解接受恶化解,按照上述方法即得到解组合优化问题的按照上述方法即得到解组合优化问题的SASA算算法法.4.1.1 4.1.1 模拟退火模拟退火原理原理SASA算法的思想为算法的思想为:v由初始解由初始解i i
15、和控制参数初值和控制参数初值t t开始开始,对当前解重复对当前解重复产生新解产生新解 计算目标函数差计算目标函数差 接受或舍弃接受或舍弃的迭代的迭代,v并逐步衰减并逐步衰减t t值值,v算法终止时的当前解即为所得近似最优解算法终止时的当前解即为所得近似最优解,v这是基于蒙特卡罗迭代求解法的一种启发式随机搜这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程索过程.4.1.1 4.1.1 模拟退火模拟退火原理原理退火过程由冷却进度表退火过程由冷却进度表(Cooling(Cooling Schedule)Schedule)控制控制,包括控制参数的初值包括控制参数的初值t t及其及其衰减因子衰减因子
16、t t、每个每个t t值时的迭代次数值时的迭代次数L L和停和停止条件止条件S S.4.1.2 SA4.1.2 SA全局优化的直观解释全局优化的直观解释vSASA算法最重要的贡献在于其能以较大的概率算法最重要的贡献在于其能以较大的概率求取复杂优化问题的全局解求取复杂优化问题的全局解.下面通过连续函数优化的几何直观解释来说明下面通过连续函数优化的几何直观解释来说明SASA算法如何能以较大概率求得全局最优解算法如何能以较大概率求得全局最优解.考虑如下图所示的全局优化问题考虑如下图所示的全局优化问题.4.1.2 SA4.1.2 SA全局优化的直观解释全局优化的直观解释startingpointdes
17、cenddirectionlocal minimaglobal minimabarrier to local search4.1.2 SA4.1.2 SA全局优化的直观解释全局优化的直观解释v所谓所谓SASA优化算法优化算法,其实质上相当于对该函数在其实质上相当于对该函数在水平方向上施以振动水平方向上施以振动.若需逃离极值若需逃离极值,则则v逃离出局部极值比全局极值需要更小的能量逃离出局部极值比全局极值需要更小的能量,即振动即振动的幅度更小的幅度更小.4.1.2 SA4.1.2 SA全局优化的直观解释全局优化的直观解释local minimaglobal minimabarrier to lo
18、cal searchEnergy for escapeEnergy for escape4.1.2 SA4.1.2 SA全局优化的直观解释全局优化的直观解释v但实际上相反但实际上相反,SA,SA的策略为函数值大的策略为函数值大,其能量大其能量大,即振即振动的幅度大动的幅度大.local minimaglobal minimabarrier to local search函数值大能量大振动幅度大逃出极值可能性大4.1.2 SA4.1.2 SA全局优化的直观解释全局优化的直观解释因此因此,SA,SA算法使得局部极值更容易被逃逸算法使得局部极值更容易被逃逸,全局全局极值更稳定极值更稳定.v故求得全局
19、极值的概率较大故求得全局极值的概率较大.v从上述直观解释从上述直观解释,可以得出可以得出SASA算法的全局优化算法的全局优化的原理：的原理：由于优化过程中由于优化过程中,拒绝恶化解的概率与函数值拒绝恶化解的概率与函数值(能量能量)大小成正指数关系大小成正指数关系,v而且局部极值本身更容易被逃逸而且局部极值本身更容易被逃逸,v因此迭代变量落入函数值大的局部极值比落入函数因此迭代变量落入函数值大的局部极值比落入函数值最小值最小(能量最小能量最小)的全局极值更有可能产生逃逸的全局极值更有可能产生逃逸.4.2 SA4.2 SA算法的模型算法的模型vSASA算法可以分解为解空间、目标函数和初始算法可以分
20、解为解空间、目标函数和初始解三部分解三部分.vSA的基本思想的基本思想:Step 1 初始化:初始温度T(充分大),初始解状态S(是算法迭代的起点),每个T值的迭代次数LStep 2 对k=1,L做第(3)至第6步:Step 3 产生新解SStep 4 计算增量t=C(S)-C(S),其中C(S)为评价函数4.2 SA4.2 SA算法的模型算法的模型Step 5 若t0则接受S作为新的当前解,否则以概率exp(-t/T)接受S作为新的当前解.Step 6 如果满足终止条件则输出当前解作为最优解,结束程序.v终止条件通常取为连续若干个新解都没有被接受时终止算法.Step 7 T逐渐减少,且T0,
21、然后转第2步.v算法对应流程图如下所示.4.2 SA4.2 SA算法的模型算法的模型4.2 SA4.2 SA算法的模型算法的模型vSASA算法新解的产生和接受可分为如下四个步算法新解的产生和接受可分为如下四个步骤骤:第一步第一步是由一个产生函数从当前解产生一个位于是由一个产生函数从当前解产生一个位于解空间的新解解空间的新解第二步第二步是计算与新解所对应的目标函数差是计算与新解所对应的目标函数差第三步第三步是判断新解是否被接受是判断新解是否被接受,判断的依据是一判断的依据是一个接受准则个接受准则第四步第四步是当新解被确定接受时是当新解被确定接受时,用新解代替当前用新解代替当前解解.4.2 SA4
22、.2 SA算法的模型算法的模型第一步第一步是由一个产生函数从当前解产生一个位于是由一个产生函数从当前解产生一个位于解空间的新解解空间的新解.v为便于后续的计算和接受为便于后续的计算和接受,减少算法耗时减少算法耗时,通常选择通常选择由当前新解经过简单地变换即可产生新解的方法由当前新解经过简单地变换即可产生新解的方法,v如对构成新解的全部或部分元素进行置换、互换等如对构成新解的全部或部分元素进行置换、互换等,注意到产生新解的变换方法决定了当前新解的邻域注意到产生新解的变换方法决定了当前新解的邻域结构结构,因而对冷却进度表的选取有一定的影响因而对冷却进度表的选取有一定的影响.4.2 SA4.2 SA
23、算法的模型算法的模型第二步第二步是计算与新解所对应的目标函数差.第三步第三步是判断新解是否被接受,判断的依据是一个接受准则.v最常用的接受准则是Metropo1is准则:若ta，则接受x为新状态，否则仍停留来原状态X）.4.2 SA4.2 SA算法的模型算法的模型第四步第四步是当新解被确定接受时是当新解被确定接受时,用新解代替当前用新解代替当前解解.v这只需将当前解中对应于产生新解时的变换部分予这只需将当前解中对应于产生新解时的变换部分予以实现以实现,同时修正目标函数值即可同时修正目标函数值即可.v此时此时,当前解实现了一次迭代当前解实现了一次迭代.可在此基础上开始下可在此基础上开始下一轮试验
24、一轮试验.v而当新解被判定为舍弃时而当新解被判定为舍弃时,则在原当前解的基础上继则在原当前解的基础上继续下一轮试验续下一轮试验.4.2 SA4.2 SA算法的模型算法的模型v从算法流程上看从算法流程上看,模拟退火算法包括三过程模拟退火算法包括三过程(函数函数)两两准则准则,即即状态产生过程、状态产生过程、状态接受过程、状态接受过程、温度更新过程、温度更新过程、内循环终止准则和内循环终止准则和外循环终止准则外循环终止准则,这些环节的设计将决定这些环节的设计将决定SASA算法的优化性能算法的优化性能.其中状态产生过程和外循环终止准则根据其中状态产生过程和外循环终止准则根据SASA算法应用于算法应用
25、于不同的领域的不同优化问题不同的领域的不同优化问题,其具体过程不同其具体过程不同.其它过程和准则则是其它过程和准则则是SASA算法的基本要素算法的基本要素,基本不变基本不变.4.2 SA4.2 SA算法的模型算法的模型A.A.状态产生函数状态产生函数设计状态产生函数设计状态产生函数(邻域函数邻域函数)的出发点应该是尽的出发点应该是尽可能保证产生的候选解遍布全部的解空间可能保证产生的候选解遍布全部的解空间.通常通常,状态产生函数由两部分组成状态产生函数由两部分组成,即产生候选解即产生候选解的方式和候选解产生的概率分布的方式和候选解产生的概率分布.B.B.状态接受函数状态接受函数状状态态接接受受函
26、函数数一一般般以以概概率率的的方方式式给给出出,不不同同接接受受函数的差别主要在于接受概率的形式不同函数的差别主要在于接受概率的形式不同.设计状态接受概率设计状态接受概率,应该遵循以下原则：应该遵循以下原则：在固定温度下在固定温度下,接受使目标函数值下降的候选解的概接受使目标函数值下降的候选解的概率要大于使目标值上升的候选解的概率；率要大于使目标值上升的候选解的概率；4.2 SA4.2 SA算法的模型算法的模型 随温度的下降,接受使目标函数值上升的解的概率要逐渐减小；当温度趋于零时,只能接受目标函数值下降的解.状态接受函数的引入是SA算法实现全局搜索的最关键的因素.C.温度更新函数温度更新函数
27、,即温度的下降方式,用于在外循环中修改温度值.目前,最常用的温度更新函数为指数退温函数,当然还有其它不同的降温策略.4.2 SA4.2 SA算法的模型算法的模型4.2 SA4.2 SA算法的模型算法的模型D.D.内循环终止准则内循环终止准则内循环终止准则内循环终止准则,或称或称MetropolisMetropolis抽样稳定准则抽样稳定准则,用于决定在各温度下产生候选解的数目用于决定在各温度下产生候选解的数目.常用的抽样准则包括：常用的抽样准则包括：检验目标函数的均值是否稳定；检验目标函数的均值是否稳定；连续若干步的目标值变化较小；连续若干步的目标值变化较小；按一定的步数抽样按一定的步数抽样.
28、4.2 SA4.2 SA算法的模型算法的模型E.E.外循环终止准则外循环终止准则外循环终止准则外循环终止准则,即算法终止准则即算法终止准则,用于决定算法用于决定算法何时结束何时结束.设置温度终值是一种简单的方法设置温度终值是一种简单的方法.SASA算法的收敛性理论中要求温度终值趋于零算法的收敛性理论中要求温度终值趋于零,这这显然不合实际显然不合实际.通常的做法是：通常的做法是：设置终止温度的阈值；设置终止温度的阈值；设置外循环迭代次数；设置外循环迭代次数；算法收敛到的最优值连续若干步保持不变；算法收敛到的最优值连续若干步保持不变；检验系统熵是否稳定检验系统熵是否稳定.4.3 SA4.3 SA算
29、法的简单应用算法的简单应用v作为SA算法应用,讨论货郎担问题(TSP):设有n个城市,用数码1,n代表.城市i和城市j之间的距离为d(i,j),i,j=1,nTSP问题是要找遍访每个域市恰好一次的一条回路,且其路径总长度为最短.4.3 SA4.3 SA算法的简单应用算法的简单应用v求解TSP的SA算法模型可描述如下:解空间解空间 v解空间S是遍访每个城市恰好一次的所有回路,是1,n的所有循环排列的集合,vS中的成员记为(w1,w2,wn),v并记wn+1=w1.初始解可选为(1,n)目标函数目标函数 v此时的目标函数即为访问所有城市的路径总长度或称为代价函数:f(w1,w2,wn)=sum(d
30、(wj,wj+1)v我们要求此代价函数的最小值.4.3 SA4.3 SA算法的简单应用算法的简单应用新解的产生新解的产生v随机产生1和n之间的两相异数k和m,若km,则将(w1,w2,wk,wk+1,wm,wn)变为:(wm,wm-1,w1,wm+1,wk-1,wn,wn-1,wk).v上述变换方法可简单说成是“逆转中间或者逆转两端”.4.3 SA4.3 SA算法的简单应用算法的简单应用v也可以采用其他的变换方法,有些变换有独特的优越性,有时也将它们交替使用,得到一种更好方法.代价函数差代价函数差v设将(w1,w2,wn)变换为(u1,u2,un),则代价函数差为4.3 SA4.3 SA算法的
31、简单应用算法的简单应用根据上述分析,可写出用SA算法求解TSP问题的伪程序:Procedure TSPSA:begininit-of-T;T为初始温度S=1,n;S为初始值termination=false;while termination=falsebeginfor i=1 to L dobegingenerate(S from S);从当前回路S产生新回 路S4.3 SA4.3 SA算法的简单应用算法的简单应用t:=f(S)-f(S);f(S)为路径总长IF(tRandom-of-0,1)S=S;IF the-halt-condition-is-TRUE THENtermination=
32、true;End;T_lower;End;End4.3 SA4.3 SA算法的简单应用算法的简单应用vSASA算法的应用很广泛算法的应用很广泛,可以以较高的效率可以以较高的效率求解最大截问题求解最大截问题(Max Cut Problem)(Max Cut Problem)、0-10-1背包问题背包问题(Zero One Knapsack Problem)(Zero One Knapsack Problem)、图着色问题图着色问题(Graph(Graph ColouringColouring Problem)Problem)、调度问题调度问题(Scheduling Problem)(Schedu
33、ling Problem)等等等等.4.4 SA4.4 SA算法的参数控制问题算法的参数控制问题vSASA算法是一种非常良好的算法是一种非常良好的,具有普适性的迭代具有普适性的迭代优化算法优化算法.其主要性质有：其主要性质有：与初始值无关与初始值无关,算法求得的解与初始解状态算法求得的解与初始解状态S(S(是是算法迭代的起点算法迭代的起点)无关无关;SASA算法具有渐近收敛性算法具有渐近收敛性,已在理论上被证明是一已在理论上被证明是一种以概率种以概率1 1收敛于全局最优解的全局优化算法收敛于全局最优解的全局优化算法;SASA算法具有并行性算法具有并行性.4.4 SA4.4 SA算法的参数控制问
34、题算法的参数控制问题vSASA算法的应用很广泛算法的应用很广泛,可以求解可以求解NPNP完全问题完全问题,但其参数难以控制但其参数难以控制,其主要问题有以下三点其主要问题有以下三点:温度温度T T的初始值设置问题的初始值设置问题.退火速度问题退火速度问题温度管理问题温度管理问题.4.4 SA4.4 SA算法的参数控制问题算法的参数控制问题A.A.温度温度T T的初始值设置问题的初始值设置问题.初始温度、温度更新函数、内循环终止准则和外初始温度、温度更新函数、内循环终止准则和外循环终止准则通常被称为退火历程循环终止准则通常被称为退火历程(annealing(annealing schedule)
35、.schedule).实验表明实验表明,初温越大初温越大,获得高质量解的几率越大获得高质量解的几率越大,但花费的计算时间将增加但花费的计算时间将增加.v初始温度高初始温度高,则搜索到全局最优解的可能性大则搜索到全局最优解的可能性大,但因此但因此要花费大量的计算时间要花费大量的计算时间;反之反之,则可节约计算时间则可节约计算时间,但全局搜索性能可能受但全局搜索性能可能受到影响到影响.4.4 SA4.4 SA算法的参数控制问题算法的参数控制问题v因此因此,初温的确定是影响初温的确定是影响SASA算法全局搜索性能的重要算法全局搜索性能的重要因素之一因素之一,应折衷考虑优化质量和优化效率应折衷考虑优化
36、质量和优化效率,实际应用过程中实际应用过程中,初始温度一般需要依据实验结初始温度一般需要依据实验结果进行若干次调整果进行若干次调整.4.4 SA4.4 SA算法的参数控制问题算法的参数控制问题B.退火速度问题退火速度问题.SA算法的全局搜索性能也与退火速度密切相关.一般来说,同一温度下的“充分”搜索(退火)是相当必要的,但这需要计算时间.实际应用中,要针对具体问题的性质和特征设置合理的退火平衡条件.C.温度管理问题温度管理问题.温度管理问题也是SA算法难以处理的问题之一.实际应用中,由于必须考虑计算复杂度的切实可行性等问题,常采用如下所示的降温方式:T(t+1)kT(t)式中k为正的略小于1.
37、00的常数,t为降温的次数.4.5 Boltzmann4.5 Boltzmann机机v前面介绍的前面介绍的NNNN模型都为确定性的模型都为确定性的NN,NN,组成它们组成它们的神经元进行信息处理时均为确定的的神经元进行信息处理时均为确定的.但在生物神经元中但在生物神经元中,由于有各种各样的干扰由于有各种各样的干扰,以及以及神经元本身所具有的一定程度的不确定性神经元本身所具有的一定程度的不确定性.同时基于硬件实现的同时基于硬件实现的ANNANN本身也会受到各种扰动本身也会受到各种扰动,其特性也呈现一定的不确定性其特性也呈现一定的不确定性.因此因此,研究具有不确定性特征、随机特征的研究具有不确定性
38、特征、随机特征的ANNANN是是非常必要的非常必要的.BoltzmannBoltzmann机是基于退火原理来决定神经元状态演机是基于退火原理来决定神经元状态演变的变的,正是具有随机性特征的互联型网络正是具有随机性特征的互联型网络.4.5 Boltzmann4.5 Boltzmann机机vBoltzmannBoltzmann机是由机是由HintonHinton等人于等人于19841984年提出的年提出的,其一般拓扑结构为具有输入层、隐单元层、输其一般拓扑结构为具有输入层、隐单元层、输出层的出层的3 3层前向层前向NN.NN.下面将主要介绍下面将主要介绍BoltzmannBoltzmann机的机的
39、v网络结构网络结构v网络能量网络能量vBoltzmannBoltzmann机网络状态变化规则机网络状态变化规则4.5.1 4.5.1 网络结构网络结构vBoltzmann机是一种有反馈的互联型网络.假定网络由n个节点构成,任意一个节点i的输出为:vi(t)0,1.节点之间的连接权植矩阵是对称的,即:wij=wji,wii=0.当节点i的输入:发生变化时,将引起输出vi(t+1)的更新.这种更新在各节点之间是以异步方式进行的,并且以概率Pi值来决定vi(t+1).4.5.1 4.5.1 网络结构网络结构v在此规定vi(t+1)为1的概率Pi为：由上式可得到：(4.1)4.5.1 4.5.1 网络
40、结构网络结构图图4.2 4.2 节点的输出受温度节点的输出受温度T T的影响的影响4.5.1 4.5.1 网络结构网络结构v由以上分析可知，任意节点i当被选择状态更新时，下一状态为1的概率为：(4.2)T为网络的温度参数，ui为i节点的激活函数。则下一状态为0的概率为4.5.1 4.5.1 网络结构网络结构v一般情况下，当激活函数ui0时，下一状态为1的概率pi(1)将大于下一状态为0的概率pi(0)，且随着ui值的增加，pi(1)也越大。同理，当uipi(1),且随着ui值的减小，pi(0)也越大。T趋于0时，概率分布曲线近似于单位阶跃函数(等价于离散HNN网络，只是描述网络单元状态“思想”
41、的出发点不同)。T趋于无穷大时，概率分布曲线近似于一条直线。4.5.2 4.5.2 网络能量网络能量网络的能量函数定义为：网络的能量函数定义为：根据式根据式(4.1)给定的概率给定的概率,考查考查vi(t+1)更新更新为为1时时,网络能量的变化为：网络能量的变化为：4.5.2 4.5.2 网络能量网络能量v由上式可知,当ui(t)0时,网络能量将减少或不变,且ui(t)0时,概率Pi大；相反,ui(t)0时,网络的能量增加或不变,且ui(t)0时,概率Pi小.4.5.2 4.5.2 网络能量网络能量v稳定性分析由于有v若ui0，pi(1)0.5，即有较大的概率取vi=1，若原来vi=1，则vi
42、=0，Ei=0；若原来vi=0，则vi0，所以Ei0。v若ui0，pi(1)0.5，即有较大的概率取vi=0，若原来vi=0，则vi=0，Ei=0；若原来vi=1，则vi0，所以Ei0。4.5.2 4.5.2 网络能量网络能量v可见，随着系统状态的演变，从概率意义上，可见，随着系统状态的演变，从概率意义上，系统的能量总是朝小的方向变化，所以系统系统的能量总是朝小的方向变化，所以系统最后总能稳定到能量的极小点附近。但由于最后总能稳定到能量的极小点附近。但由于是随机网络，在能量极小点附近，系统也不是随机网络，在能量极小点附近，系统也不会停止在某一个固定的状态。会停止在某一个固定的状态。总之总之,B
43、oltzmann,Boltzmann机允许网络状态以小的概率往能机允许网络状态以小的概率往能量大的方向迁移量大的方向迁移,这样做的目的是使网络能量函这样做的目的是使网络能量函数能够收敛于全局最小点数能够收敛于全局最小点.4.5.3 Boltzmann4.5.3 Boltzmann机网络状态变化规则机网络状态变化规则vBoltzmann机网络状态变化规则Step 1 从n个节点中随机地选取节点i；Step 2 计算节点i(1in)的输入ui(t)Step 3 以概率Pi来决定i的输出vi(t+1)：4.5.3 Boltzmann4.5.3 Boltzmann机网络状态变化规则机网络状态变化规则S
44、tep 4 其它节点不变化；Step 5 返回返回Step 1Step 14.5.3 Boltzmann4.5.3 Boltzmann机网络状态变化规则机网络状态变化规则例例4.14.1：假设一个假设一个3 3节点的节点的BoltzmannBoltzmann机。机。设网络参数为设网络参数为4.5.3 Boltzmann4.5.3 Boltzmann机网络状态变化规则机网络状态变化规则试确定温度T=0.5和T=1时的网络状态转移函数。首先计算某一状态下各节点单元的激活函数值。以状态v1v2v3=(111)为例：应用状态转移公式，依次计算温度T=0.5和T=1时各个状态相应各节点的状态更新概率，如
45、表4.1。这样就可以计算出各个状态的转移概率。4.5.3 Boltzmann4.5.3 Boltzmann机网络状态变化规则机网络状态变化规则表4.1 3节点BoltzmannBoltzmann机各个状态的节点的激发概率机各个状态的节点的激发概率网络状态节点T=1.0T=0.5p(1)p(0)p(1)p(0)S0(000)1230.710.550.430.290.450.570.860.600.350.140.400.65S1(001)1230.550.650.430.450.350.570.600.770.350.400.230.65S2(010)1230.730.550.520.270.4
46、50.480.880.600.550.120.400.45S3(011)1230.570.650.520.430.350.480.650.770.550.350.230.45S4(100)1230.710.570.270.290.430.730.860.650.120.140.350.88S5(101)1230.550.670.270.450.330.730.600.800.120.400.200.88S6(110)1230.730.570.350.270.430.650.880.650.230.120.350.77S7(111)1230.570.670.350.430.330.650.650
47、.800.230.350.200.774.5.3 Boltzmann4.5.3 Boltzmann机网络状态变化规则机网络状态变化规则状态转移概率可用一个统一式子表达为：应用上面两个公式，可以方便的确定在不同温度下，各状态转移到其他状态的概率。状态转移情况可以和HNN的情况进行比较后，可以得出结论：温度的引入，使原有HNN中的状态转移概率分布发生了一定的变化，不仅可以向低能转移，而且有机会由低能向高能态转移。当温度较高时，转移到其它状态的概率分别接近1/n。状态保持不变的概率可按下式求得：4.5.3 Boltzmann4.5.3 Boltzmann机网络状态变化规则机网络状态变化规则用图示的方
48、法来描述状态转移关系是复杂的，不实用的，我们可以用随机过程中的马尔可夫链的一些知识清晰的表达这一关系。马尔可夫链是时间和状态都离散的马尔可夫过程。考虑给定一组状态S0,-Sm-1，这些状态以已知转移概率pij（表示在状态Si后出现Sj的概率）一个接一个的出现。该系统的状态变化可用pij构成的m*m 矩阵表示。其中，4.5.3 Boltzmann4.5.3 Boltzmann机网络状态变化规则机网络状态变化规则例4.1中3节点Boltzmann机在T=1.0时的状态转移图可用下表表示：T=1.0S0(t+1)(000)S1(t+1)(001)S2(t+1)(010)S3(t+1)(011)S4(
49、t+1)(100)S5(t+1)(101)S6(t+1)(110)S7(t+1)(111)S0(t)(000)0.440.140.180.000.240.000.000.00S1(t)(001)0.190.410.000.220.000.180.000.00S2(t)(010)0.150.000.440.170.000.000.240.00S3(t)(011)0.000.120.160.530.000.000.000.19S4(t)(100)0.110.000.000.000.620.090.190.00S5(t)(101)0.000.150.000.000.240.390.000.22S6(
50、t)(110)0.000.000.090.000.140.000.650.12S7(t)(111)0.000.000.000.140.000.110.220.534.5.3 Boltzmann4.5.3 Boltzmann机网络状态变化规则机网络状态变化规则假设在t时刻出现Si的概率为Pi(t)，那么在t+1时刻状态为Sj的概率Pj(t+1)可以由所有进入该状态的概率求和得到，即4.5.3 Boltzmann4.5.3 Boltzmann机网络状态变化规则机网络状态变化规则例4.2 对于例4.1所给的系统，假设在t=0时刻处，任何状态的概率均为0.125，试确定下时刻状态S2的概率。同理，可计