随机神经网络.ppt

随机网络：学习运行引入随机机制 1.存在的问题：以目标函数的极小值，作为学习或运行的目的 BP算法-误差函数，梯度下降 Hop算法-Hebb规则-能量函数E 容易陷入局部极小点。,无法避免，从入手：将“总是沿梯度下降方向演变”改为”大部分沿梯度下降方向演变，但允许少数情况沿上升方向演变。”,目录,引言 模拟退火算法的模型 模拟退火算法的简单应用 模拟退火算法的参数控制问题 Boltzmann机,4.1 引言,模拟退火(Simulated Annealing, SA)算法是近年来特别引入注目的一种适用于解大型组合优化问题的优化方法,算法来源于固体退火原理,其核心在于 模仿热力学中液体的冻结与结晶或金属熔液的冷却与退火过程-物理退火过程和Metropolis准则. 下面分别介绍 SA原理 SA全局优化的直观解释,4.1.1 模拟退火原理,简单而言,在固体退火时,先将固体加热使其温度充分高,再让其徐徐冷却,其物理退火过程由以下三部分组成： 加温过程 等温过程 冷却过程,4.1.1 模拟退火原理,加温过程 在固体退火时,先将固体加热使其温度充分高,其目的是增强粒子的热运动,使其偏离平衡位置. 当温度足够高时,固体将溶解为液体,固体内部粒子随温升变为无序状, 彼此之间可以自由移动,从而消除系统原先可能存在的非均匀态,使随后进行的冷却过程以某一平衡态为起点. 熔解过程(加热固体至高温液态)与系统的熵增过程联系,系统内部能量也随温度的升高而增大.,4.1.1 模拟退火原理,等温过程 物理学的知识告诉我们,对于与周围环境交换热量而温度不变的封闭系统,系统状态的自发变化总是朝自由能减少的方向进行,当自由能达到最小时,系统达到平衡态. 冷却过程 目的是使粒子的热运动减弱并渐趋有序,系统能量逐渐下降,从而得到低能的晶体结构. 徐徐冷却时粒子就会丧失由干温度而引起的流动性,渐趋有序,这时原子就会自己排列起来而形成一种纯晶体,它们依次地朝各个方向排列成几十亿倍于单个原子大小的距离,这个纯晶体状态就是该系统的平衡态,亦为最小能量状态.,4.1.1 模拟退火原理,有趣的是: 对一个徐徐冷却的系统,当这些原子在逐渐失去活力的同时,它们自己就同时地排列而形成一个纯晶体,使这个系统的能量达到其最小值. 这里引起特别关注的是,在这个物理系统的冷却过程中,这些原子是“同时地”把它们自己排列成一个纯晶体的. 如果一种金属熔液是被快速冷却或泼水使其冷却的,则它不能达到纯晶体状态,而是变成一种多晶体或非晶体状态,系统处在这种状态时具有较高的能量.,4.1.1 模拟退火原理,SA算法就是模仿上述物理系统徐徐退火过程的一种通用随机搜索技术,人们可用马尔柯夫链的遍历理论来给它以数学上的描述. 在搜索最优解的过程中,SA算法除了可以接受优化解外,还基于随机接受准则(Metropolis准则)有限度地接受恶化解,并且接受恶化解的概率慢慢趋向于0. 这使得算法有可能从局部最优中跳出,尽可能找到全局最优解,并保证了算法的收敛. SA的思想最早是由Metropolis等(1953)提出的. Metropolis等提出了重要性采样法,即以概率接受新状态.,对于某一给定温度，系统若达到热平衡状态(循环若干次)，则该状态下的能量服从Bottzmann分布.,4.1.1 模拟退火原理,4.1.1 模拟退火原理,具体而言,在温度t,由当前状态i产生新状态j,两者的能量分别为Ei和Ej,若EjEi则接受新状态j为当前状态；否则,若概率,大于0,1)区间内的随机数则仍旧接受新状态j为当前状态,若不成立则保留i为当前状态,其中k为Boltzmann常数. 这种重要性采样过程在高温下可接受与当前状态能量差较大的新状态,而在低温下基本只接受与当前能量差较小的新状态,而且当温度趋于零时,就不能接受比当前状态能量高的新状态. 这种接受准则通常称为Metropolis准则.,4.1.1 模拟退火原理,1983年Kirkpatrick等人意识到组合优化与物理退火的相似性,并受到Metropolis准则的启迪,首次把固体的退火过程与组合极小化联系在一起,他们分别用目标函数和组合极小化问题的解替代物理系统的能量和状态,从而物理系统内粒子的摄动等价于组合极小化问题的试探. SA是基于Monte Carlo迭代求解策略的一种随机寻优算法. 极小化过程就是: 首先在一个高温(温度现在就成为一个控制参数)状态下,利用具有概率突跳特性的Metropolis抽样策略在解空间中进行随机搜索,伴随温度的不断下降,重复抽样过程,将有效地“溶化”解空间; 然后慢慢地降低温度直到系统“结晶”到一个稳定解,最终得到问题的全局最优解.,4.1.1 模拟退火原理,SA算法在组合最优化中的成功应用掀起了SA算法研究与应用的高潮. 1991年Dekkers和Aarts探讨将SA算法应用于求解连续优化问题. 20世纪90年代以来,SA算法在NN、GA、进化算法等优化、学习领域得到极大的应用.,4.1.1 模拟退火原理,SA算法的主要精髓是基于Metropolis准则可接受求解过程的恶化解. Metropolis准则为: 粒子在温度T时趋于平衡的概率为,其中E为温度T时的内能, E为其改变量, k为Boltzmann常数.,4.1.1 模拟退火原理,利用上述固体退火原理来模拟求解组合优化问题时, 将内能E模拟为目标函数值f,温度T演化成控制参数t, 并以Metropolis准则的概率,接受恶化解, 按照上述方法即得到解组合优化问题的SA算法.,4.1.1 模拟退火原理,SA算法的思想为: 由初始解i和控制参数初值t开始,对当前解重复 产生新解 计算目标函数差 接受或舍弃 的迭代, 并逐步衰减t值, 算法终止时的当前解即为所得近似最优解, 这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程.,4.1.1 模拟退火原理,退火过程由冷却进度表(Cooling Schedule)控制,包括控制参数的初值t及其衰减因子t、每个t值时的迭代次数L和停止条件S.,4.1.2 SA全局优化的直观解释,SA算法最重要的贡献在于其能以较大的概率求取复杂优化问题的全局解. 下面通过连续函数优化的几何直观解释来说明SA算法如何能以较大概率求得全局最优解. 考虑如下图所示的全局优化问题.,4.1.2 SA全局优化的直观解释,4.1.2 SA全局优化的直观解释,所谓SA优化算法,其实质上相当于对该函数在水平方向上施以振动. 若需逃离极值,则 逃离出局部极值比全局极值需要更小的能量,即振动的幅度更小.,4.1.2 SA全局优化的直观解释,4.1.2 SA全局优化的直观解释,但实际上相反,SA的策略为函数值大,其能量大,即振动的幅度大.,4.1.2 SA全局优化的直观解释,因此,SA算法使得局部极值更容易被逃逸,全局极值更稳定. 故求得全局极值的概率较大. 从上述直观解释,可以得出SA算法的全局优化的原理： 由于优化过程中,拒绝恶化解的概率与函数值(能量)大小成正指数关系, 而且局部极值本身更容易被逃逸, 因此迭代变量落入函数值大的局部极值比落入函数值最小(能量最小)的全局极值更有可能产生逃逸.,4.2 SA算法的模型,SA算法可以分解为解空间、目标函数和初始解三部分. SA的基本思想: Step 1 初始化:初始温度T(充分大),初始解状态S(是算法迭代的起点),每个T值的迭代次数L Step 2 对k=1,L做第(3)至第6步: Step 3 产生新解S Step 4 计算增量t=C(S)-C(S),其中C(S)为评价函数,4.2 SA算法的模型,Step 5 若t0则接受S作为新的当前解,否则以概率exp(-t/T)接受S作为新的当前解. Step 6 如果满足终止条件则输出当前解作为最优解,结束程序. 终止条件通常取为连续若干个新解都没有被接受时终止算法. Step 7 T逐渐减少,且T0,然后转第2步. 算法对应流程图如下所示.,4.2 SA算法的模型,4.2 SA算法的模型,SA算法新解的产生和接受可分为如下四个步骤: 第一步是由一个产生函数从当前解产生一个位于解空间的新解 第二步是计算与新解所对应的目标函数差 第三步是判断新解是否被接受,判断的依据是一个接受准则 第四步是当新解被确定接受时,用新解代替当前解.,4.2 SA算法的模型,第一步是由一个产生函数从当前解产生一个位于解空间的新解. 为便于后续的计算和接受,减少算法耗时,通常选择由当前新解经过简单地变换即可产生新解的方法, 如对构成新解的全部或部分元素进行置换、互换等,注意到产生新解的变换方法决定了当前新解的邻域结构,因而对冷却进度表的选取有一定的影响.,4.2 SA算法的模型,第二步是计算与新解所对应的目标函数差. 第三步是判断新解是否被接受,判断的依据是一个接受准则. 最常用的接受准则是Metropo1is准则: 若ta，则接受x为新状态，否则仍停留来原状态X）.,4.2 SA算法的模型,第四步是当新解被确定接受时,用新解代替当前解. 这只需将当前解中对应于产生新解时的变换部分予以实现,同时修正目标函数值即可. 此时,当前解实现了一次迭代.可在此基础上开始下一轮试验. 而当新解被判定为舍弃时,则在原当前解的基础上继续下一轮试验.,4.2 SA算法的模型,从算法流程上看,模拟退火算法包括三过程(函数)两准则,即 状态产生过程、 状态接受过程、 温度更新过程、 内循环终止准则和 外循环终止准则, 这些环节的设计将决定SA算法的优化性能. 其中状态产生过程和外循环终止准则根据SA算法应用于不同的领域的不同优化问题,其具体过程不同. 其它过程和准则则是SA算法的基本要素,基本不变.,4.2 SA算法的模型,A. 状态产生函数 设计状态产生函数(邻域函数)的出发点应该是尽可能保证产生的候选解遍布全部的解空间. 通常,状态产生函数由两部分组成,即产生候选解的方式和候选解产生的概率分布. B. 状态接受函数 状态接受函数一般以概率的方式给出,不同接受函数的差别主要在于接受概率的形式不同. 设计状态接受概率,应该遵循以下原则： 在固定温度下,接受使目标函数值下降的候选解的概率要大于使目标值上升的候选解的概率；,4.2 SA算法的模型, 随温度的下降,接受使目标函数值上升的解的概率要逐渐减小； 当温度趋于零时,只能接受目标函数值下降的解. 状态接受函数的引入是SA算法实现全局搜索的最关键的因素.,C. 温度更新函数 温度更新函数,即温度的下降方式,用于在外循环中修改温度值. 目前,最常用的温度更新函数为指数退温函数,当然还有其它不同的降温策略.,4.2 SA算法的模型,4.2 SA算法的模型,D. 内循环终止准则 内循环终止准则,或称Metropolis抽样稳定准则,用于决定在各温度下产生候选解的数目. 常用的抽样准则包括： 检验目标函数的均值是否稳定； 连续若干步的目标值变化较小； 按一定的步数抽样.,4.2 SA算法的模型,E. 外循环终止准则 外循环终止准则,即算法终止准则,用于决定算法何时结束.设置温度终值是一种简单的方法. SA算法的收敛性理论中要求温度终值趋于零,这显然不合实际.通常的做法是： 设置终止温度的阈值； 设置外循环迭代次数； 算法收敛到的最优值连续若干步保持不变； 检验系统熵是否稳定.,4.3 SA算法的简单应用,作为SA算法应用,讨论货郎担问题(TSP): 设有n个城市,用数码1,n代表. 城市i和城市j之间的距离为d(i,j), i, j=1,n TSP问题是要找遍访每个域市恰好一次的一条回路,且其路径总长度为最短.,4.3 SA算法的简单应用,求解TSP的SA算法模型可描述如下: 解空间 解空间S是遍访每个城市恰好一次的所有回路,是1,n的所有循环排列的集合, S中的成员记为(w1,w2 ,wn), 并记wn+1= w1.初始解可选为(1,n) 目标函数 此时的目标函数即为访问所有城市的路径总长度或称为代价函数: f(w1, w2 ,wn)=sum(d(wj, wj+1) 我们要求此代价函数的最小值.,4.3 SA算法的简单应用,新解的产生 随机产生1和n之间的两相异数k和m,若km,则将 (w1, w2 ,wk , wk+1 ,wm ,wn) 变为: (wm, wm-1 ,w1 , wm+1 ,wk-1 ,wn , wn-1 ,wk). 上述变换方法可简单说成是“逆转中间或者逆转两端”.,4.3 SA算法的简单应用,也可以采用其他的变换方法,有些变换有独特的优越性,有时也将它们交替使用,得到一种更好方法. 代价函数差 设将(w1, w2 ,wn)变换为(u1, u2 ,un), 则代价函数差为,4.3 SA算法的简单应用,根据上述分析,可写出用SA算法求解TSP问题的伪程序: Procedure TSPSA: begin init-of-T; T为初始温度 S=1,n; S为初始值 termination=false; while termination=false begin for i=1 to L do begin generate(S from S); 从当前回路S产生新回 路S,4.3 SA算法的简单应用,t:=f(S)-f(S);f(S)为路径总长 IF(tRandom-of-0,1) S=S; IF the-halt-condition-is-TRUE THEN termination=true; End; T_lower; End; End,4.3 SA算法的简单应用,SA算法的应用很广泛,可以以较高的效率 求解最大截问题(Max Cut Problem)、 0-1背包问题(Zero One Knapsack Problem)、 图着色问题(Graph Colouring Problem)、 调度问题(Scheduling Problem)等等.,4.4 SA算法的参数控制问题,SA算法是一种非常良好的,具有普适性的迭代优化算法.其主要性质有： 与初始值无关,算法求得的解与初始解状态S(是算法迭代的起点)无关; SA算法具有渐近收敛性,已在理论上被证明是一种以概率1收敛于全局最优解的全局优化算法; SA算法具有并行性.,4.4 SA算法的参数控制问题,SA算法的应用很广泛,可以求解NP完全问题,但其参数难以控制,其主要问题有以下三点: 温度T的初始值设置问题. 退火速度问题 温度管理问题.,4.4 SA算法的参数控制问题,A. 温度T的初始值设置问题. 初始温度、温度更新函数、内循环终止准则和外循环终止准则通常被称为退火历程(annealing schedule). 实验表明,初温越大,获得高质量解的几率越大,但花费的计算时间将增加. 初始温度高,则搜索到全局最优解的可能性大,但因此要花费大量的计算时间; 反之,则可节约计算时间,但全局搜索性能可能受到影响.,4.4 SA算法的参数控制问题,因此,初温的确定是影响SA算法全局搜索性能的重要因素之一,应折衷考虑优化质量和优化效率, 实际应用过程中,初始温度一般需要依据实验结果进行若干次调整.,4.4 SA算法的参数控制问题,B. 退火速度问题. SA算法的全局搜索性能也与退火速度密切相关. 一般来说,同一温度下的“充分”搜索(退火)是相当必要的,但这需要计算时间. 实际应用中,要针对具体问题的性质和特征设置合理的退火平衡条件. C. 温度管理问题. 温度管理问题也是SA算法难以处理的问题之一. 实际应用中,由于必须考虑计算复杂度的切实可行性等问题,常采用如下所示的降温方式: T(t+1)kT(t) 式中k为正的略小于1.00的常数,t为降温的次数.,4.5 Boltzmann机,前面介绍的NN模型都为确定性的NN,组成它们的神经元进行信息处理时均为确定的. 但在生物神经元中,由于有各种各样的干扰,以及神经元本身所具有的一定程度的不确定性. 同时基于硬件实现的ANN本身也会受到各种扰动,其特性也呈现一定的不确定性. 因此,研究具有不确定性特征、随机特征的ANN是非常必要的. Boltzmann机是基于退火原理来决定神经元状态演变的,正是具有随机性特征的互联型网络.,4.5 Boltzmann机,Boltzmann机是由Hinton等人于1984年提出的,其一般拓扑结构为具有输入层、隐单元层、输出层的3层前向NN. 下面将主要介绍Boltzmann机的 网络结构 网络能量 Boltzmann机网络状态变化规则,4.5.1 网络结构,Boltzmann机是一种有反馈的互联型网络.假定 网络由n个节点构成,任意一个节点i的输出为:vi(t)0,1. 节点之间的连接权植矩阵是对称的,即:wij=wji ,wii=0. 当节点i的输入:,发生变化时,将引起输出vi(t+1)的更新. 这种更新在各节点之间是以异步方式进行的,并且以概率Pi值来决定vi(t+1).,4.5.1 网络结构,在此规定vi(t+1)为1的概率Pi为：,由上式可得到： (4.1),4.5.1 网络结构,图4.2 节点的输出受温度T的影响,4.5.1 网络结构,由以上分析可知，任意节点i当被选择状态更新时，下一状态为1的概率为： (4.2),T为网络的温度参数，ui为i节点的激活函数。,则下一状态为0的概率为,4.5.1 网络结构,一般情况下，当激活函数ui0时，下一状态为1的概率pi(1)将大于下一状态为0的概率pi(0)，且随着ui值的增加， pi(1)也越大。同理，当uipi(1), 且随着ui值的减小， pi(0)也越大。,T趋于0时，概率分布曲线近似于单位阶跃函数(等价于离散HNN网络，只是描述网络单元状态“思想”的出发点不同)。 T趋于无穷大时，概率分布曲线近似于一条直线。,4.5.2 网络能量,网络的能量函数定义为：,根据式(4.1)给定的概率,考查vi(t+1)更新为1时,网络能量的变化为：,4.5.2 网络能量,由上式可知,当ui(t)0时,网络能量将减少或不变,且ui(t)0时,概率Pi大； 相反,ui(t)0时,网络的能量增加或不变,且ui(t)0时,概率Pi小.,4.5.2 网络能量,稳定性分析 由于有,若ui0，pi(1)0.5，即有较大的概率取vi=1，若原来vi=1，则vi=0， Ei=0；若原来vi=0，则vi0，所以Ei0。 若ui0， pi(1)0.5，即有较大的概率取vi=0，若原来vi=0，则vi=0， Ei=0；若原来vi=1，则vi0，所以Ei0。,4.5.2 网络能量,可见，随着系统状态的演变，从概率意义上，系统的能量总是朝小的方向变化，所以系统最后总能稳定到能量的极小点附近。但由于是随机网络，在能量极小点附近，系统也不会停止在某一个固定的状态。 总之,Boltzmann机允许网络状态以小的概率往能量大的方向迁移,这样做的目的是使网络能量函数能够收敛于全局最小点.,4.5.3 Boltzmann机网络状态变化规则,Boltzmann机网络状态变化规则 Step 1 从n个节点中随机地选取节点i； Step 2 计算节点i(1in)的输入ui(t),Step 3 以概率Pi来决定i的输出vi(t+1) ：,4.5.3 Boltzmann机网络状态变化规则,Step 4 其它节点不变化；,Step 5 返回Step 1,4.5.3 Boltzmann机网络状态变化规则,例4.1： 假设一个3节点的Boltzmann机。 设网络参数为,4.5.3 Boltzmann机网络状态变化规则,试确定温度T=0.5和T=1时的网络状态转移函数。 首先计算某一状态下各节点单元的激活函数值。以状态v1v2v3=(111)为例：,应用状态转移公式，依次计算温度T=0.5和T=1时各个状态相应各节点的状态更新概率，如表4.1。这样就可以计算出各个状态的转移概率。,4.5.3 Boltzmann机网络状态变化规则,表4.1 3节点Boltzmann机各个状态的节点的激发概率,4.5.3 Boltzmann机网络状态变化规则,状态转移概率可用一个统一式子表达为：,应用上面两个公式，可以方便的确定在不同温度下，各状态转移到其他状态的概率。状态转移情况可以和HNN的情况进行比较后，可以得出结论：温度的引入，使原有HNN中的状态转移概率分布发生了一定的变化，不仅可以向低能转移，而且有机会由低能向高能态转移。当温度较高时，转移到其它状态的概率分别接近1/n。,状态保持不变的概率可按下式求得：,4.5.3 Boltzmann机网络状态变化规则,用图示的方法来描述状态转移关系是复杂的，不实用的，我们可以用随机过程中的马尔可夫链的一些知识清晰的表达这一关系。 马尔可夫链是时间和状态都离散的马尔可夫过程。考虑给定一组状态S0,-Sm-1，这些状态以已知转移概率pij（表示在状态Si后出现Sj的概率）一个接一个的出现。该系统的状态变化可用pij构成的m*m 矩阵表示。,其中，,4.5.3 Boltzmann机网络状态变化规则,例4.1中3节点Boltzmann机在T=1.0时的状态转移图可用下表表示：,4.5.3 Boltzmann机网络状态变化规则,假设在t时刻出现Si的概率为Pi(t)，那么在t+1时刻状态为Sj的概率Pj(t+1