我的人工神经网络-10 非确定方法

第10章非确定方法

10.1基本的非确定学习算法

10.2模拟退火算法

10.3Cauchy学习

10.4相关的几个问题

第10章非确定方法确定的方法前几章所给方法的共同特征非确定的方法生物神经网络按照概率运行别称统计方法（StatisticalMethod）。既可以用于学习，又可以用于运行

10.1基本的非确定学习算法

基本思想从所给的网络中“随机地选取一个联接权”，对该联接权提出一个“伪随机调整量”，当用此调整量对所选的联接权进行修改后，如果“被认为”修改改进了网络的性能，则保留此调整；否则放弃本次调整。

10.1基本的非确定学习算法基本数据结构样本集：S={(X1,Y1),(X2,Y2),…,(Xs,Ys)}输入向量：X=(x1，x2，…，xn)理想输出向量：Y=(y1，y2，…，ym)L层：W(1)，W(2)，…，W(L)

10.1基本的非确定学习算法拓扑结构

x1o1输出层隐藏层输入层x2o2omxn…………………W(1)

W(L)W(2)算法10-1

基本统计学习算法

1从样本集S中取一样本（X,Y）；2将X输入到网络中，计算出实际输出O；3求出网络关于Y，O的误差测度E；4随机地从W(1)，W(2)，…，W(L)中选择一个联接权wij(p)；5生成一个小随机数Δwij(p)；6用Δwij(p)修改wij(p)；算法10-1

基本统计学习算法7用修改后的W(1)，W(2)，…，W(L)重新计算X对应的实际输出O′；8求出网络关于Y，O′的误差测度E′；9如果E′<E，则保留本次对W(1)，W(2)，…，W(L)的修改，否则，根据概率判断本次修改是否有用，如果认为有用，则保留本次对W(1)，W(2)，…，W(L)的修改，如果认为本次修改无用，则放弃它；10重复上述过程，直到网络满足要求。算法10-1

基本统计学习算法目标函数（ObjectiveFunction）误差测度函数：实际输出与理想输出方差和

计算量从W(1)，W(2)，…，W(L)中随机地选择wij

共有n×H1+H1×H2+H2×H3+…+HM-1×m个“变量”可供选择伪随机数伪随机数发生器来产生Δwij(p)；按照所谓的“能量”函数的分布去计算它算法10-1

基本统计学习算法局部极小点当E′<E不成立时，考虑使网络从局部极小点中逃离出来，必须允许目标函数暂时变坏

循环控制判断标准用一个样本对网络的某一个联接权进行修改后，是随机地抽取另一个联接权进行重复，还是再选择下一个样本进行重复对一个选定的样本，每次是否可以选取若干个联接权进行修改？如果可以，还应做什么工作？

逃离局部极小点

联接权修改量

太小：落到A点后很难逃离

太大：导致在A、B两点来回抖动

解决办法

控制联接权修改量的大小：权修改量由大变小

允许暂时变坏

修改量的大小和网络的“能量”相关

模拟退火

ABD逃离局部极小点DBA10.1模拟退火算法及模型

算法的提出

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

解决NP复杂性问题；克服优化过程陷入局部极小；克服初值依赖性。10.1.1物理退火过程10.1模拟退火算法及模型

物理退火过程

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

10.1.1物理退火过程10.1模拟退火算法及模型

物理学方面的模拟退火概念

固体物理中，金属结构的稳定程度对应着一个能量函数。

当温度高时，原子的运动不稳定，能量函数较高。

如果用淬火的方式骤然降温，能量函数就会进入一个局部极小。

10.1.1物理退火过程10.1模拟退火算法及模型

物理学方面的模拟退火概念

所谓退火，是近似一种双极限过程：极限一：当温度有改变时，经过无穷大时间后，系统可以进入稳态；极限二：温度以无穷小的速度趋进于绝对零度；

10.1.1物理退火过程10.1模拟退火算法及模型

物理学方面的模拟退火概念

在以上两个极限的退火作用下，能量函数以概率收敛到全局极小。

所谓模拟退火算法，也就是近似构造这种双极限过程，从而获得全局优化的算法．

10.1.1物理退火过程10.1模拟退火算法及模型

物理退火过程

加温过程——增强粒子的热运动，消除系统原先可能存在的非均匀态；等温过程——对于与环境换热而温度不变的封闭系统，系统状态的自发变化总是朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡态；冷却过程——使粒子热运动减弱并渐趋有序，系统能量逐渐下降，从而得到低能的晶体结构。

10.1.1物理退火过程10.1模拟退火算法及模型

数学表述

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

10.1.1物理退火过程10.1模拟退火算法及模型

数学表述

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

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

10.1.1物理退火过程<1>010.1模拟退火算法及模型

数学表述

若|D|为状态空间D中状态的个数，D0是具有最低能量的状态集合：当温度很高时，每个状态概率基本相同，接近平均值1/|D|；状态空间存在超过两个不同能量时，具有最低能量状态的概率超出平均值1/|D|；当温度趋于0时，分子停留在最低能量状态的概率趋于1。能量最低状态10.1模拟退火算法及模型

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

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

10.1.1物理退火过程10.1模拟退火算法及模型

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

若在温度T，当前状态i→新状态j若Ej<Ei，则接受j为当前状态；否则，若概率p=exp[-(Ej-Ei)/kBT]大于[0,1)区间的随机数，则仍接受状态j为当前状态；若不成立则保留状态i为当前状态。

10.1.1物理退火过程10.1模拟退火算法及模型

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

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

在高温下，可接受与当前状态能量差较大的新状态；在低温下，只接受与当前状态能量差较小的新状态。

10.1.1物理退火过程10.1模拟退火算法及模型

相似性比较

10.1.2组合优化与物理退火的相似性10.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算法终止准则满足；输出算法搜索结果。

10.1.3模拟退火算法的基本思想和步骤10.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算法终止准则满足；输出算法搜索结果。

10.1.3模拟退火算法的基本思想和步骤三函数两准则初始温度10.1模拟退火算法及模型

定义马尔科夫性（无后效性）：由时刻t0系统或过程所处的状态，可以决定系统或过程在时刻t>0所处的状态，而无需借助于t0以前系统或过程所处状态的历史资料。马尔科夫性过程分布函数的描述：X(tn-1)=xn-1,即：P{X(tn)<=xn|x(t1=x1),X(t2)=x2,......,X(tn-1)=xn-1}=P{X(tn)<=xn|X(tn-1)<=xn-1},xn€R.

10.2.1马尔科夫链10.2模拟退火算法的马氏链描述

定义

10.2.1马尔科夫链10.2模拟退火算法的马氏链描述

定义

一步转移概率：

n步转移概率：若解空间有限，称马尔可夫链为有限状态；若，称马尔可夫链为时齐的。

10.2.1马尔科夫链10.2模拟退火算法的马氏链描述

模拟退火算法对应了一个马尔可夫链

模拟退火算法：新状态接受概率仅依赖于新状态和当前状态，并由温度加以控制。若固定每一温度，算法均计算马氏链的变化直至平稳分布，然后下降温度，则称为时齐算法；若无需各温度下算法均达到平稳分布，但温度需按一定速率下降，则称为非时齐算法。分析收敛性

10.2.2模拟退火算法与马尔科夫链10.3模拟退火算法关键参数和操作的设计原则

产生的候选解应遍布全部解空间方法

在当前状态的邻域结构内以一定概率方式（均匀分布、正态分布、指数分布等）产生

10.10.1状态产生函数10.3模拟退火算法关键参数和操作的设计原则

(1)在固定温度下，接受使目标函数下降的候选解的概率要大于使目标函数上升的候选解概率；(2)随温度的下降，接受使目标函数上升的解的概率要逐渐减小；(3)当温度趋于零时，只能接受目标函数下降的解。方法

具体形式对算法影响不大一般采用min[1,exp(-∆C/t)]

10.10.2状态接受函数10.3模拟退火算法关键参数和操作的设计收敛性分析

通过理论分析可以得到初温的解析式，但解决实际问题时难以得到精确的参数；初温应充分大；实验表明

初温越大，获得高质量解的机率越大，但花费较多的计算时间；

10.10.3初温10.3模拟退火算法关键参数和操作的设计方法

（1）均匀抽样一组状态，以各状态目标值得方差为初温；（2）随机产生一组状态，确定两两状态间的最大目标值差，根据差值，利用一定的函数确定初温；（3）利用经验公式。

10.10.3初温10.3模拟退火算法关键参数和操作的设计时齐算法的温度下降函数

（1），α越接近1温度下降越慢，且其大小可以不断变化；（2），其中t0为起始温度，K为算法温度下降的总次数。

10.10.4温度更新函数10.3模拟退火算法关键参数和操作的设计

时齐算法——常用的Metropolis抽样稳定准则

（1）检验目标函数的均值是否稳定；（2）连续若干步的目标值变化较小；（3）按一定的步数抽样。

10.10.5内循环终止准则10.3模拟退火算法关键参数和操作的设计常用方法

（1）设置终止温度的阈值；（2）设置外循环迭代次数；（3）算法搜索到的最优值连续若干步保持不变；（4）概率分析方法。

10.10.6外循环终止准则模拟退火组合优化法

目标函数——能量函数人工温度T——一个初值较大的数依据网络的能量和温度来决定联接权的调整量（称为步长）。与金属的退火过程（Annealing）非常相似模拟退火组合优化法基本思想随机地为系统选择一个初始状态{wij(p)}，在此初始状态下，给系统一个小的随机扰动Δwij(p)，计算系统的能量变化ΔE=E({wij(p)+Δwij(p)})-E({wij(p)})

若ΔE<0则接受若ΔE≥0则依据概率判断是否被接受若接受，则系统从状态{wij(p)}变换到状态{wij(p)+Δwij(p)}；否则，系统保持不变

模拟退火组合优化法在这个过程中，逐渐地降低温度T。所得的系统状态序列{wij(p)