《随机神经网络精品文稿.ppt》由会员分享，可在线阅读，更多相关《随机神经网络精品文稿.ppt（75页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、随机神经网络第1 页，本讲稿共75 页随机网络：学习运行引入随机机制1.存在的问题：以目标函数的极小值，作为学习或运行的目的 BP算法-误差函数，梯度下降 Hop算法-Hebb规则-能量函数E 容易陷入局部极小点。第2 页，本讲稿共75 页 无法避免，从入手：将“总是沿梯度下降方向演变”改为”大部分沿梯度下降方向演变，但允许少数情况沿上升方向演变。”第3 页，本讲稿共75 页目录v 引言v 模拟退火算法的模型v 模拟退火算法的简单应用v 模拟退火算法的参数控制问题v Boltzmann机第4 页，本讲稿共75 页4.1 引言v 模拟退火(Simulated Annealing,SA)算法是近年
2、来特别引入注目的一种适用于解大型组合优化问题的优化方法,算法来源于固体退火原理,其核心在于模仿热力学中液体的冻结与结晶或金属熔液的冷却与退火过程-物理退火过程和Metropolis准则.v 下面分别介绍SA原理SA全局优化的直观解释第5 页，本讲稿共75 页4.1.1 模拟退火原理v 简单而言,在固体退火时,先将固体加热使其温度充分高,再让其徐徐冷却,其物理退火过程由以下三部分组成：加温过程等温过程冷却过程第6 页，本讲稿共75 页4.1.1 模拟退火原理加温过程v 在固体退火时,先将固体加热使其温度充分高,其目的是增强粒子的热运动,使其偏离平衡位置.v 当温度足够高时,固体将溶解为液体,固体
3、内部粒子随温升变为无序状,彼此之间可以自由移动,从而消除系统原先可能存在的非均匀态,使随后进行的冷却过程以某一平衡态为起点.v 熔解过程(加热固体至高温液态)与系统的熵增过程联系,系统内部能量也随温度的升高而增大.第7 页，本讲稿共75 页4.1.1 模拟退火原理等温过程v 物理学的知识告诉我们,对于与周围环境交换热量而温度不变的封闭系统,系统状态的自发变化总是朝自由能减少的方向进行,当自由能达到最小时,系统达到平衡态.冷却过程v 目的是使粒子的热运动减弱并渐趋有序,系统能量逐渐下降,从而得到低能的晶体结构.v 徐徐冷却时粒子就会丧失由干温度而引起的流动性,渐趋有序,这时原子就会自己排列起来而
4、形成一种纯晶体,它们依次地朝各个方向排列成几十亿倍于单个原子大小的距离,这个纯晶体状态就是该系统的平衡态,亦为最小能量状态.第8 页，本讲稿共75 页4.1.1 模拟退火原理v 有趣的是:对一个徐徐冷却的系统,当这些原子在逐渐失去活力的同时,它们自己就同时地排列而形成一个纯晶体,使这个系统的能量达到其最小值.这里引起特别关注的是,在这个物理系统的冷却过程中,这些原子是“同时地”把它们自己排列成一个纯晶体的.如果一种金属熔液是被快速冷却或泼水使其冷却的,则它不能达到纯晶体状态,而是变成一种多晶体或非晶体状态,系统处在这种状态时具有较高的能量.第9 页，本讲稿共75 页4.1.1 模拟退火原理v
5、SA算法就是模仿上述物理系统徐徐退火过程的一种通用随机搜索技术,人们可用马尔柯夫链的遍历理论来给它以数学上的描述.在搜索最优解的过程中,SA算法除了可以接受优化解外,还基于随机接受准则(Metropolis准则)有限度地接受恶化解,并且接受恶化解的概率慢慢趋向于0.v 这使得算法有可能从局部最优中跳出,尽可能找到全局最优解,并保证了算法的收敛.SA的思想最早是由Metropolis等(1953)提出的.v Metropolis等提出了重要性采样法,即以概率接受新状态.第10 页，本讲稿共75 页 对于某一给定温度，系统若达到热平衡状态(循环若干次)，则该状态下的能量服从Bottzmann分布.
6、4.1.1 模拟退火原理第11 页，本讲稿共75 页4.1.1 模拟退火原理v 具体而言,在温度t,由当前状态i 产生新状态j,两者的能量分别为Ei和Ej,若EjEi则接受新状态j 为当前状态；否则,若概率 大于0,1)区间内的随机数则仍旧接受新状态j 为当前状态,若不成立则保留i 为当前状态,其中k为Boltzmann 常数.v 这种重要性采样过程在高温下可接受与当前状态能量差较大的新状态,而在低温下基本只接受与当前能量差较小的新状态,而且当温度趋于零时,就不能接受比当前状态能量高的新状态.这种接受准则通常称为Metropolis 准则.第12 页，本讲稿共75 页4.1.1 模拟退火原理
7、1983年Kirkpatrick等人意识到组合优化与物理退火的相似性,并受到Metropolis准则的启迪,首次把固体的退火过程与组合极小化联系在一起,他们分别用目标函数和组合极小化问题的解替代物理系统的能量和状态,从而物理系统内粒子的摄动等价于组合极小化问题的试探.v SA是基于Monte Carlo迭代求解策略的一种随机寻优算法.v 极小化过程就是:首先在一个高温(温度现在就成为一个控制参数)状态下,利用具有概率突跳特性的Metropolis抽样策略在解空间中进行随机搜索,伴随温度的不断下降,重复抽样过程,将有效地“溶化”解空间;然后慢慢地降低温度直到系统“结晶”到一个稳定解,最终得到问题
8、的全局最优解.第13 页，本讲稿共75 页4.1.1 模拟退火原理SA算法在组合最优化中的成功应用掀起了SA算法研究与应用的高潮.v 1991年Dekkers和Aarts探讨将SA算法应用于求解连续优化问题.v 20世纪90年代以来,SA算法在NN、GA、进化算法等优化、学习领域得到极大的应用.第14 页，本讲稿共75 页4.1.1 模拟退火原理v SA算法的主要精髓是基于Metropolis准则可接受求解过程的恶化解.Metropolis准则为:粒子在温度T时趋于平衡的概率为其中E为温度T时的内能,E为其改变量,k为Boltzmann常数.第15 页，本讲稿共75 页4.1.1 模拟退火原理
9、利用上述固体退火原理来模拟求解组合优化问题时,v 将内能E模拟为目标函数值f,温度T演化成控制参数t,v 并以Metropolis准则的概率接受恶化解,按照上述方法即得到解组合优化问题的SA算法.第16 页，本讲稿共75 页4.1.1 模拟退火原理SA算法的思想为:v 由初始解i和控制参数初值t开始,对当前解重复产生新解 计算目标函数差 接受或舍弃的迭代,v 并逐步衰减t值,v 算法终止时的当前解即为所得近似最优解,v 这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程.第17 页，本讲稿共75 页4.1.1 模拟退火原理退火过程由冷却进度表(Cooling Schedule)控制,包括控制参
10、数的初值t及其衰减因子 t、每个t值时的迭代次数L和停止条件 S.第18 页，本讲稿共75 页4.1.2 SA全局优化的直观解释v SA算法最重要的贡献在于其能以较大的概率求取复杂优化问题的全局解.下面通过连续函数优化的几何直观解释来说明SA算法如何能以较大概率求得全局最优解.考虑如下图所示的全局优化问题.第19 页，本讲稿共75 页4.1.2 SA全局优化的直观解释startingpointdescenddirectionlocal minimaglobal minimabarrier to local search第20 页，本讲稿共75 页4.1.2 SA全局优化的直观解释v 所谓SA优
11、化算法,其实质上相当于对该函数在水平方向上施以振动.若需逃离极值,则v 逃离出局部极值比全局极值需要更小的能量,即振动的幅度更小.第21 页，本讲稿共75 页4.1.2 SA全局优化的直观解释local minimaglobal minimabarrier to local searchEnergy for escapeEnergy for escape第22 页，本讲稿共75 页4.1.2 SA全局优化的直观解释v 但实际上相反,SA的策略为函数值大,其能量大,即振动的幅度大.local minimaglobal minimabarrier to local search函数值大能量大振动幅
12、度大逃出极值可能性大第23 页，本讲稿共75 页4.1.2 SA全局优化的直观解释因此,SA算法使得局部极值更容易被逃逸,全局极值更稳定.v 故求得全局极值的概率较大.v 从上述直观解释,可以得出SA算法的全局优化的原理：由于优化过程中,拒绝恶化解的概率与函数值(能量)大小成正指数关系,v 而且局部极值本身更容易被逃逸,v 因此迭代变量落入函数值大的局部极值比落入函数值最小(能量最小)的全局极值更有可能产生逃逸.第24 页，本讲稿共75 页4.2 SA算法的模型v SA算法可以分解为解空间、目标函数和初始解三部分.v SA的基本思想:Step 1 初始化:初始温度T(充分大),初始解状 态S(
13、是算法迭代的起点),每个T 值的迭代次数LStep 2 对k=1,L 做第(3)至第6 步:Step 3 产生新解SStep 4 计算增量t=C(S)-C(S),其中C(S)为评价函数第25 页，本讲稿共75 页4.2 SA算法的模型Step 5 若t0 则接受S 作为新的当前解,否则以概率exp(-t/T)接受S 作为新的当前解.Step 6 如果满足终止条件则输出当前解作为最优解,结束程序.v 终止条件通常取为连续若干个新解都没有被接受时终止算法.Step 7 T 逐渐减少,且T 0,然后转第2 步.v 算法对应流程图如下所示.第26 页，本讲稿共75 页4.2 SA算法的模型第27 页，
14、本讲稿共75 页4.2 SA算法的模型v SA算法新解的产生和接受可分为如下四个步骤:第一步是由一个产生函数从当前解产生一个位于解空间的新解第二步是计算与新解所对应的目标函数差第三步是判断新解是否被接受,判断的依据是一个接受准则第四步是当新解被确定接受时,用新解代替当前解.第28 页，本讲稿共75 页4.2 SA算法的模型第一步是由一个产生函数从当前解产生一个位于解空间的新解.v 为便于后续的计算和接受,减少算法耗时,通常选择由当前新解经过简单地变换即可产生新解的方法,v 如对构成新解的全部或部分元素进行置换、互换等,注意到产生新解的变换方法决定了当前新解的邻域结构,因而对冷却进度表的选取有一
15、定的影响.第29 页，本讲稿共75 页4.2 SA算法的模型第二步是计算与新解所对应的目标函数差.第三步是判断新解是否被接受,判断的依据是一个接受准则.v 最常用的接受准则是Metropo1is 准则:若ta，则接受x 为新状态，否则仍停留来原状态X）.第30 页，本讲稿共75 页4.2 SA算法的模型第四步是当新解被确定接受时,用新解代替当前解.v 这只需将当前解中对应于产生新解时的变换部分予以实现,同时修正目标函数值即可.v 此时,当前解实现了一次迭代.可在此基础上开始下一轮试验.v 而当新解被判定为舍弃时,则在原当前解的基础上继续下一轮试验.第31 页，本讲稿共75 页4.2 SA算法的
16、模型v 从算法流程上看,模拟退火算法包括三过程(函数)两准则,即 状态产生过程、状态接受过程、温度更新过程、内循环终止准则和 外循环终止准则,这些环节的设计将决定SA算法的优化性能.其中状态产生过程和外循环终止准则根据SA算法应用于不同的领域的不同优化问题,其具体过程不同.其它过程和准则则是SA算法的基本要素,基本不变.第32 页，本讲稿共75 页4.2 SA算法的模型A.状态产生函数设计状态产生函数(邻域函数)的出发点应该是尽可能保证产生的候选解遍布全部的解空间.通常,状态产生函数由两部分组成,即产生候选解的方式和候选解产生的概率分布.B.状态接受函数状态接受函数一般以概率的方式给出,不同接
17、受函数的差别主要在于接受概率的形式不同.设计状态接受概率,应该遵循以下原则：在固定温度下,接受使目标函数值下降的候选解的概率要大于使目标值上升的候选解的概率；第33 页，本讲稿共75 页4.2 SA算法的模型 随 温 度 的 下 降,接 受 使 目 标 函 数 值 上 升 的 解 的 概 率 要逐渐减小；当温度趋于零时,只能接受目标函数值下降的解.状态接受函数的引入是SA 算法实现全局搜索的最关键的因素.第34 页，本讲稿共75 页C.温度更新函数 温 度 更 新 函 数,即 温 度 的 下 降 方 式,用 于 在 外 循 环中修改温度值.目前,最常用的温度更新函数为指数退温函数,当然还有其它
18、不同的降温策略.4.2 SA算法的模型第35 页，本讲稿共75 页4.2 SA算法的模型D.内循环终止准则内循环终止准则,或称Metropolis抽样稳定准则,用于决定在各温度下产生候选解的数目.常用的抽样准则包括：检验目标函数的均值是否稳定；连续若干步的目标值变化较小；按一定的步数抽样.第36 页，本讲稿共75 页4.2 SA算法的模型E.外循环终止准则外循环终止准则,即算法终止准则,用于决定算法何时结束.设置温度终值是一种简单的方法.SA算法的收敛性理论中要求温度终值趋于零,这显然不合实际.通常的做法是：设置终止温度的阈值；设置外循环迭代次数；算法收敛到的最优值连续若干步保持不变；检验系统
19、熵是否稳定.第37 页，本讲稿共75 页4.3 SA算法的简单应用v 作为SA 算法应用,讨论货郎担问题(TSP):设有n 个城市,用数码1,n 代表.城市i 和城市j 之间的距离为d(i,j),i,j=1,n TSP 问题是要找遍访每个域市恰好一次的一条回路,且其路径总长度为最短.第38 页，本讲稿共75 页4.3 SA算法的简单应用v 求解TSP 的SA 算法模型可描述如下:解空间 v 解空间S 是遍访每个城市恰好一次的所有回路,是1,n 的所有循环排列的集合,v S 中的成员记为(w1,w2,wn),v 并记wn+1=w1.初始解可选为(1,n)目标函数 v 此时的目标函数即为访问所有城
20、市的路径总长度或称为代价函数:f(w1,w2,wn)=sum(d(wj,wj+1)v 我们要求此代价函数的最小值.第39 页，本讲稿共75 页4.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 上述变换方法可简单说成是“逆转中间或者逆转两端”.第40 页，本讲稿共75 页4.3 SA算法的简单应用v 也可以采用其他的变换方法,有些变换有独特的优越性,有时也将它们交替使用,得到一种更好方法.代价函数差v 设将(w1,w2,wn)变换为(u
21、1,u2,un),则代价函数差为第41 页，本讲稿共75 页4.3 SA算法的简单应用 根据上述分析,可写出用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 产生新回 路S第42 页，本讲稿共75 页4.3 SA算法的简单应用t:=f(S)-f(S);f(S)为路径 总长IF(tRandom-of-0,1)S=S;IF the
22、-halt-condition-is-TRUE THENtermination=true;End;T_lower;End;End第43 页，本讲稿共75 页4.3 SA算法的简单应用v SA算法的应用很广泛,可以以较高的效率求解最大截问题(Max Cut Problem)、0-1背包问题(Zero One Knapsack Problem)、图着色问题(Graph Colouring Problem)、调度问题(Scheduling Problem)等等.第44 页，本讲稿共75 页4.4 SA算法的参数控制问题v SA算法是一种非常良好的,具有普适性的迭代优化算法.其主要性质有：与初始值无关
23、,算法求得的解与初始解状态S(是算法迭代的起点)无关;SA算法具有渐近收敛性,已在理论上被证明是一种以概率1收敛于全局最优解的全局优化算法;SA算法具有并行性.第45 页，本讲稿共75 页4.4 SA算法的参数控制问题v SA算法的应用很广泛,可以求解NP完全问题,但其参数难以控制,其主要问题有以下三点:温度T的初始值设置问题.退火速度问题温度管理问题.第46 页，本讲稿共75 页4.4 SA算法的参数控制问题A.温度T的初始值设置问题.初始温度、温度更新函数、内循环终止准则和外循环终止准则通常被称为退火历程(annealing schedule).实验表明,初温越大,获得高质量解的几率越大,
24、但花费的计算时间将增加.v 初始温度高,则搜索到全局最优解的可能性大,但因此要花费大量的计算时间;反之,则可节约计算时间,但全局搜索性能可能受到影响.第47 页，本讲稿共75 页4.4 SA算法的参数控制问题v 因此,初温的确定是影响SA算法全局搜索性能的重要因素之一,应折衷考虑优化质量和优化效率,实际应用过程中,初始温度一般需要依据实验结果进行若干次调整.第48 页，本讲稿共75 页4.4 SA算法的参数控制问题B.退火速度问题.SA 算法的全局搜索性能也与退火速度密切相关.一般来说,同一温度下的“充分”搜索(退火)是相当必要的,但这需要计算时间.实际应用中,要针对具体问题的性质和特征设置合
25、理的退火平衡条件.C.温度管理问题.温度管理问题也是SA 算法难以处理的问题之一.实际应用中,由于必须考虑计算复杂度的切实可行性等问题,常采用如下所示的降温方式:T(t+1)kT(t)式中k为正的略小于1.00 的常数,t 为降温的次数.第49 页，本讲稿共75 页4.5 Boltzmann机v前面介绍的NN模型都为确定性的NN,组成它们的神经元进行信息处理时均为确定的.但在生物神经元中,由于有各种各样的干扰,以及神经元本身所具有的一定程度的不确定性.同时基于硬件实现的ANN本身也会受到各种扰动,其特性也呈现一定的不确定性.因此,研究具有不确定性特征、随机特征的ANN是非常必要的.Boltzm
26、ann机是基于退火原理来决定神经元状态演变的,正是具有随机性特征的互联型网络.第50 页，本讲稿共75 页4.5 Boltzmann机vBoltzmann机是由Hinton等人于1984年提出的,其一般拓扑结构为具有输入层、隐单元层、输出层的3层前向NN.下面将主要介绍Boltzmann机的v网络结构v网络能量vBoltzmann机网络状态变化规则第51 页，本讲稿共75 页4.5.1 网络结构v Boltzmann 机是一种有反馈的互联型网络.假定 网络由n 个节点构成,任意一个节点i 的输出为:vi(t)0,1.节点之间的连接权植矩阵是对称的,即:wij=wji,wii=0.当节点i 的输
27、入:发生变化时,将引起输出vi(t+1)的更新.这种更新在各节点之间是以异步方式进行的,并且以概率Pi值来决定vi(t+1).第52 页，本讲稿共75 页4.5.1 网络结构v 在此规定vi(t+1)为1 的概率Pi为：由上式可得到：(4.1)第53 页，本讲稿共75 页4.5.1 网络结构图4.2 节点的输出受温度T的影响第54 页，本讲稿共75 页4.5.1 网络结构v 由以上分析可知，任意节点i 当被选择状态更新时，下一状态为1 的概率为：(4.2)T 为网络的温度参数，ui为i 节点的激活函数。则下一状态为0的概率为第55 页，本讲稿共75 页4.5.1 网络结构v 一般情况下，当激活
28、函数ui0 时，下一状态为1 的概率pi(1)将大于下一状态为0 的概率pi(0)，且随着ui值的增加，pi(1)也越大。同理，当uipi(1),且随着ui值的减小，pi(0)也越大。T 趋于0时，概率分布曲线近似于单位阶跃函数(等价于离散HNN 网络，只是描述网络单元状态“思想”的出发点不同)。T 趋于无穷大时，概率分布曲线近似于一条直线。第56 页，本讲稿共75 页4.5.2 网络能量网络的能量函数定义为：根据式(4.1)给定的概率,考查vi(t+1)更新为1时,网络能量的变化为：第57 页，本讲稿共75 页4.5.2 网络能量v 由上式可知,当ui(t)0 时,网络能量将减少或不变,且u
29、i(t)0 时,概率Pi大；相反,ui(t)0时,网络的能量增加或不变,且ui(t)0时,概率Pi小.第58 页，本讲稿共75 页4.5.2 网络能量v 稳定性分析由于有v 若ui0，pi(1)0.5，即有较大的概率取vi=1，若原来vi=1，则vi=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。第59 页，本讲稿共75 页4.5.2 网络能量v可见，随着系统状态的演变，从概率意义上，系统的能量总是朝小的方向变化，所以系统最后总能稳定到能量的极小点附近。但
30、由于是随机网络，在能量极小点附近，系统也不会停止在某一个固定的状态。总之,Boltzmann机允许网络状态以小的概率往能量大的方向迁移,这样做的目的是使网络能量函数能够收敛于全局最小点.第60 页，本讲稿共75 页4.5.3 Boltzmann机网络状态变化规则v Boltzmann 机网络状态变化规则Step 1 从n 个节点中随机地选取节点i；Step 2 计算节点i(1in)的输入ui(t)Step 3 以概率Pi来决定i 的输出vi(t+1)：第61 页，本讲稿共75 页4.5.3 Boltzmann机网络状态变化规则Step 4 其它节点不变化；Step 5 返回 返回Step 1
31、Step 1第62 页，本讲稿共75 页4.5.3 Boltzmann机网络状态变化规则例4.1：假设一个3节点的Boltzmann机。设网络参数为第63 页，本讲稿共75 页4.5.3 Boltzmann机网络状态变化规则试确定温度T=0.5 和T=1 时的网络状态转移函数。首 先 计 算 某 一 状 态 下 各 节 点 单 元 的 激 活 函 数 值。以状态v1v2v3=(111)为例：应 用 状 态 转 移 公 式，依 次 计 算 温 度T=0.5 和T=1时 各 个 状 态 相 应 各 节 点 的 状 态 更 新 概 率，如 表4.1。这样就可以计算出各个状态的转移概率。第64 页，本
32、讲稿共75 页4.5.3 Boltzmann机网络状态变化规则表4.1 3 节点Boltzmann机各个状态的节点的激发概率网络状态 节点T=1.0 T=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.450.480.880.600.550.120.400.45S3(011)1230.570.650.520.430.35
33、0.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.800.230.350.200.77第65 页，本讲稿共75 页4.5.3 Boltzmann机网络状态变化规则状态
34、转移概率可用一个统一式子表达为：应 用 上 面 两 个 公 式，可 以 方 便 的 确 定 在 不 同 温 度 下，各 状 态 转 移 到 其他 状 态 的 概 率。状 态 转 移 情 况 可 以 和HNN 的 情 况 进 行 比 较 后，可以 得 出 结 论：温 度 的 引 入，使 原 有HNN 中 的 状 态 转 移 概 率 分 布发 生 了 一 定 的 变 化，不 仅 可 以 向 低 能 转 移，而 且 有 机 会 由 低 能 向高能态转移。当温度较高时，转移到其它状态的概率分别接近1/n。状态保持不变的概率可按下式求得：第66 页，本讲稿共75 页4.5.3 Boltzmann机网络状
35、态变化规则用 图 示 的 方 法 来 描 述 状 态 转 移 关 系 是 复 杂 的，不 实 用 的，我 们 可 以 用随机过程中的马尔可夫链的一些知识清晰的表达这一关系。马 尔 可 夫 链 是 时 间 和 状 态 都 离 散 的 马 尔 可 夫 过 程。考 虑 给 定 一 组 状态S0,-Sm-1，这 些 状 态 以 已 知 转 移 概 率pij（表 示 在 状 态Si后 出现Sj 的 概 率）一 个 接 一 个 的 出 现。该 系 统 的 状 态 变 化 可 用pij构 成的m*m 矩阵表示。其中，第67 页，本讲稿共75 页4.5.3 Boltzmann机网络状态变化规则例4.1 中3
36、节点Boltzmann 机在T=1.0 时的状态转移图可用下表表示：T=1.0S0(t+1)(000)S1(t+1)(001)S2(t+1)(010)S3(t+1)(011)S4(t+1)(100)S5(t+1)(101)S6(t+1)(110)S7(t+1)(111)S0(t)(000)0.44 0.14 0.18 0.00 0.24 0.00 0.00 0.00S1(t)(001)0.19 0.41 0.00 0.22 0.00 0.18 0.00 0.00S2(t)(010)0.15 0.00 0.44 0.17 0.00 0.00 0.24 0.00S3(t)(011)0.00 0.1
37、2 0.16 0.53 0.00 0.00 0.00 0.19S4(t)(100)0.11 0.00 0.00 0.00 0.62 0.09 0.19 0.00S5(t)(101)0.00 0.15 0.00 0.00 0.24 0.39 0.00 0.22S6(t)(110)0.00 0.00 0.09 0.00 0.14 0.00 0.65 0.12S7(t)(111)0.00 0.00 0.00 0.14 0.00 0.11 0.22 0.53第68 页，本讲稿共75 页4.5.3 Boltzmann机网络状态变化规则假 设 在t 时 刻 出 现Si的 概 率 为Pi(t)，那 么 在t
38、+1 时 刻 状 态 为Sj的 概率Pj(t+1)可以由所有进入该状态的概率求和得到，即第69 页，本讲稿共75 页4.5.3 Boltzmann机网络状态变化规则例4.2 对 于 例4.1 所 给 的 系 统，假 设 在t=0 时 刻 处，任 何 状 态 的 概率均为0.125，试确定下时刻状态S2的概率。同理，可计算出到达其它各个状态的概率，如表4.2 所示。温度T 时间t P0(t)P1(t)P2(t)P3(t)P4(t)P5(t)P6(t)P7(t)1.0 0 0.125 0.125 0.125 0.125 0.125 0.125 0.125 0.1251.0 1 0.110 0.10
39、3 0.109 0.133 0.155 0.096 0.163 0.133随 着 时 间t 的 增 加，在 给 定 的 温 度 下，到 达 各 个 状 态 的 概 率 将 趋 于一个平衡状态。第70 页，本讲稿共75 页4.5.3 Boltzmann机网络状态变化规则利 用 马 尔 可 夫 链 预 测 将 来 某 一 时 刻 的 状 态 概 率 分 布，是 随机NN 中非常有用的一个技术。例4.3 分 析 例4.1 所 示Boltzmann 机，当 温 度 由1.0 按0.005 的 速率降到0.01 时，状态概率的分布变化如下表所示。第71 页，本讲稿共75 页4.5.3 Boltzmann
40、机网络状态变化规则温度T 时间t P0(t)P1(t)P2(t)P3(t)P4(t)P5(t)P6(t)P7(t)1.0001.0001.0001.0001.0001.0001.0001.0000123456130.1250.1100.1000.0930.0880.0860.0840.0800.1250.1030.0880.0780.0720.0680.0650.0590.1250.1090.1030.1010.1000.0990.0990.0970.1250.1330.1300.1250.1200.1160.1130.1050.1250.1550.1680.1750.1790.1820.18
41、40.1890.1250.0960.0850.0790.0760.0740.0730.0710.1250.1630.1900.2100.2250.2350.2420.2570.1250.1330.1360.1380.1400.1400.1410.1410.5000.5002012040.0400.0390.0220.0220.0590.0590.0710.0700.2320.2300.0330.0330.4150.4190.1280.128 0.060 463 0 0 0 0 0.001 0 0.999 00.055 464 0 0 0 0 0.001 0 0.999 00.050 465 0
42、 0 0 0 0 0 1 0 0.010 473 0 0 0 0 0 0 1 0第72 页，本讲稿共75 页4.5.3 Boltzmann机网络状态变化规则假 定 系 统 初 始 时 刻t 0 时 处 于 任 意 一 个 状 态 的 概 率Pi(0)为0.125，起 始 温 度T0=1。利 用 马 尔 可 夫 链 的 一 步 转 移 概 率 矩 阵 所 建立 的 马 尔 可 夫 链，可 以 计 算 出 当t=13 时 刻 状 态 分 布 概 率 不 再发 生 变 化，我 们 称 此 状 态 为 网 络 的 一 个 热 平 衡 态，如 上 表 所 示。此 时，若 将 温 度 降 到0.995，则
43、 打 破 了T=1.0 时 的 热 平 衡，状态 转 移 概 率 重 新 分 布。利 用 新 建 立 的 马 尔 可 夫 链，可 以 计 算 出下 一 时 刻 的 状 态 概 率 分 布，当t=15 时 系 统 达 到 一 个 新 的 热 平 衡。同 理，若 将 温 度 再 降 到0.01 时，则 当t=473 时，系 统 便 可 进 入全局最小能量的稳态S6。第73 页，本讲稿共75 页4.5.3 Boltzmann机网络状态变化规则事实上，S 对应的各个状态的能量如下表示：状态S0(000)S1(001)S2(010)S3(011)S4(100)S5(101)S6(110)S7(111)能
44、量 0.0 0.3-0.2-0.3-0.9 0.1-1.2-0.6第74 页，本讲稿共75 页参考文献1 Kirkpatrick,S,Gelatt,C.D.,Vecchi,M.P.1983.Optimization by Simulated Annealing.Science,vol 220,No.4598,pp 671-680 2 P.J.M.van Laarhoven,E.H.L.Aarts,Simulated Annealing:Theory and Applications,Kluwer Academic Publisher,1987.3 A.A.Zhigljavsky,Theory of Global Random Search,Kluwer Academic Publishers,1991.第75 页，本讲稿共75 页