随机神经网络及模拟退火算法

133第6章随机神经网络及模拟退火算法前面介绍了两种典型的神经网络：多层前向网络—BP网络和反馈神经网络—Hopfield网络。从网络结构上来看：BP网络含有输入层、隐层和输出层，层内神经元无连接；而Hopfield网络无输入层、隐层和输出层，是一个单层神经网络，层内神经元是全互联的。从学习算法上来看：BP网络按误差减小的最大梯度方向调整网络权值，是一种“贪心”算法，容易陷入局部极小点；而Hopfield网络是按照其用途来设计或训练网络的权值，很难避免出现伪状态，对于有用的吸引子，其吸引力的强弱、吸引域的大小也不同，而且网络是严格按照能量减小的方向运行的，这就容易陷入局部极小点，而无法跳出。在用BP网络和Hopfield网络进行最优化计算时，由于限定条件的不足，往往会使网络稳定在误差或能量函数的局部极小点，而不是全局最小点，即所得的结果不是最优解。网络陷入局部极小点的原因主要有两点：（1）网络结构上存在着输入到输出之间的非线性函数关系，从而使网络误差或能量函数所构成的空间是一个含有多极点的非线性空间。（2）在算法上，网络的误差或能量函数只能单方向减小，不能有一点上升。对于第（1）点，是为了保证网络具有非线性映射能力而必不可少的。那么要提高网络的性能，只能从第（2）点入手，即网络运行向误差或能量函数减小方向运行的概率大，向误差或能量函数增大方向运行的概率存在，这样网络跳出局部极小点的可能性存在，而且向全局最小点收敛的概率最大。这就是随机神经网络算法的基本思想。随机神经网络是统计力学思想引入神经网络研究的结果。统计力学是研究大系统宏观平衡性质的学科，这种大系统的组成元素服从微观机制。统计力学的主要目的是寻找从微观粒子（原子、电子）的运动开始的宏观物体的热力学性质（LandauandLifshitz,1980;Parisi,1988），由于所遇到的自由度数目很大，因此只能使用概率的方法进行研究。上世纪80年代，Ackley,Hinton和Sejnowski等人以模拟退火思想为基础，对Hopfield模型引入了随机机制，提出了Boltzmann机。Boltzmann机是第一个受统计力学启发的多层学习机，它是一类典型的随机神经网络。其命名来源于Boltzmann在统计热力学中的早期工作和网络本身的动态分布行为（其平衡状态服从Boltzmann分布）。Boltzmann机的运行机制服从模拟退火算法。本章首先介绍Boltzmann机的结构，并结合Boltzmann机的结构讨论Boltzmann机的运行机制以及学习算法。由于Boltzmann机学习过程中存在着计算时间过长和对统计错误敏感的缺点，在6.2节讨论了确定性Boltzmann机和Sigmoid置信度网络。6.3节讨论了模拟退火算法以及它在组合优化问题上的应用。最后给出仿真实例。6.1Boltzmann机Boltzmann机结合BP网络和Hopfield网络在网络结构、学习算法和动态运行机制的优点，具有多层网络含义的网络结构、简易而高效的学习算法以及依概率方式工作的动态运行机134制。6.1.1Boltzmann机的网络结构Boltzmann机考虑到多层网络的优点，采用具有多层网络含义的网络结构，其网络结构如图6.1所示。Boltzmann机由输入部、输出部和中间部构成。输入部和输出部神经元通称作显见神经元，是网络与外部环境进行信息交换的媒介，中间部的神经元称为隐见神经元，它们通过显见神经元与外界进行信息交换，但Boltzmann机网络没有明显的层次。另外，Boltzmann机考虑到Hopfield网络的动态特性，其神经元是互联的，网络状态按照概率分布进行变化。输入部输出部显见神经元隐见神经元中间部图6.1Boltzmann机的网络结构与Hopfield网络一样，网络中每一对神经元之间的信息传递是双向对称的，即wij=wji，而且自身无反馈，即wii=0。学习期间，显见神经元将被外部环境“约束”在某一特定的状态，而中间部隐见神经元则不受外部环境约束。Boltzmann机中每个神经元的兴奋或抑制具有随机性，其概率取决于神经元的输入。Boltzmann机中单个随机神经元的形式化描述如图6.2所示。1v2vjvnv1iw2iwijwinwiuibiiviP图6.2Boltzmann机神经元的形式化描述神经元i的全部输入信号的总和为ui，由式（6.1）给出。式中bi是该神经元的阈值。可以将bi归并到总的加权和中去，即得到式（6.2）：135injjijibvwu（6.1）或njjijivwu（6.2）神经元i的输出vi依概率取1或0：vi取1的概率：)1/(1)1(/TuiievP（6.3）vi取0的概率：)1()1(1)0(/iTuiivPevPvPi（6.4）显然，ui越大，则vi取1的概率越大，而取0的概率越小。参数T称为“温度”，对vi取1或0的概率有影响。在不同的温度下vi取1的概率P随ui的变化如图6.3所示。图6.3P～u关系曲线从图6.3可见，T越高时，曲线越平滑，因此，即使ui有很大变动，也不会对vi取1的概率变化造成很大的影响；反之，T越低时，曲线越陡峭，当ui有稍许变动时就会使概率有很大差异。当T→0时，每个神经元不再具有随机特性，而具有确定的特性，激励函数变为阶跃函数，这时Boltzmann机趋向于Hopfield网络。从这个意义上来说，Hopfield网络是Boltzmann机的特例。6.1.2Boltzmann机的工作原理Boltzmann机采用式（6.5）所示的能量函数作为描述其状态的函数。将Boltzmann机视为一动力系统，利用式（6.5）可以证明能量函数的极小值对应系统的稳定平衡点，由于能量函数有界，当网络温度T以某种方式逐渐下降到某一特定值时，系统必趋于稳定状态。将需要求解的优化问题的目标函数与网络的能量函数相对应，神经网络的稳定状态就对应优化目标的极小值。Boltzmann机的运行过程就是逐步降低其能量函数的过程。136jijiijvvwE,21（6.5）Boltzmann机在运行时，假设每次只改变一个神经元的状态，如第i个神经元，设vi取0和取1时系统的能量函数分别为0和jjijvw，它们的差值为ΔEi：jjijvvivwEEEii10（6.6）ΔEi0即0jjijvw时，网络在vi＝1状态的能量小于vi=0状态时的能量，在这种情况下，根据式（6.2）、式（6.3）和式（6.4），可知：P(vi＝1)P(vi=0)，即神经元i的状态取1的可能性比取0的可能性大，亦即网络状态取能量低的可能性大；反之，当ΔEi0即0jjijvw时，vi=0状态时的能量小于vi＝1时的能量，根据式（6.2）、式（6.3）和式（6.4），可知：P(vi=1)P(vi=0)，即神经元i取0状态的可能性比取1的可能性大，亦即网络状态取能量低的可能性大。因此，网络运行过程中总的趋势是朝能量下降的方向运动，但也存在能量上升的可能性。从概率的角度来看，如果ΔEi越是一个大正数，vi取1的概率加大；如果ΔEi越是一个小负数，vi取0的概率加大。对照式(6.2)，(6.3)和(6.6)，可得：vi取1的概率：)1/(1/TEiieP（6.7）每次调整一个神经元的状态，被调整的神经元取1还是0，则根据其输入由（6.7）式决定。每次调整后，系统总能量下降的概率总是大于上升的概率，所以系统的总能量呈下降趋势。图6.4描述了Boltzmann机能量函数随状态的变化。其中点A和C是局部极小点，点B是全局极小点。在最优化计算时希望使搜索的结果停留在全局极小点而不是局部极小点，即求得最优解而不是次优解。通过前面的分析可知，Boltzmann机状态的演化过程中达到B点状态的概率最大。ABC图6.4能量函数曲线图示137假定Boltzmann机中有V1和V2两种状态：在V1状态下神经元i的输出vi=1，V2状态下神经元i的输出vi=0，而所有其他神经元在这两种状态下的取值都是一致的，另外假设两种状态出现的概率分别是1vP和2vP：1221)1/()1()1/(///vviTETEivTEivEEEekePkPkekPkPiii为常数（6.8）对于网络中任意两个状态V1和V2的出现概率1vP和2vP，它们之间的关系为：TEETEvvvvieePP/)(/2121/1（6.9）即符合Boltzmann分布。这也是这种网络模型之所以称为Boltzmann机的原因所在。从式（6.9）可见Boltzmann机处于某一状态的概率取决于该网络在此状态下的能量。21212121212111/)(/)(vvTEEvvvvTEEvvPPeEEPPeEEvvvv（6.10）（6.10）式说明能量低的状态出现的概率大，能量高的状态出现的概率小。另一方面，Boltzmann机处于某一状态的概率也取决于温度参数T：（1）T很高时，各状态出现的概率差异大大减小，也就是说网络停留在全局最小点的概率，并不比局部最小点的概率甚至非局部最小点高很多。也即网络不会陷在某个极小点中拔不出来，网络在搜索过程中能够“很快”的穿行于各极小点之间，但落于全局最小点的概率还是最大的。这一点保证网络状态落入全局最小点的可能性大。（2）T很低时，情况正好相反。概率差距被加大，一旦网络陷于某个极小点之后，虽然还有可能跳出该极小点，但是所需的搜索次数将是非常多的。这一点保证网络状态一旦达到全局最小点，跳出的可能性小。（3）T→0（Hopfield网络）差距被无限扩展，跳出局部最小点的概率趋于无穷小。这一点保证网络状态稳定在全局最小点。在Hopfield网络中，每一种约束相当于一种初始条件，不同的约束所造成的不同初始条件将把网络引入不同的的局部最小点；Boltzmann机的思路与Hopfield网络相类似，但Boltzmann机进行的是概率式的搜索，相比较它具有两个特点：一是低能量状态比高能量状态发生的概率大；二是随着温度T的降低，概率集中于一个低能量状态的子集。6.1.3Boltzmann机的运行步骤设一个Boltzmann机具有n个随机神经元（p个显见神经元，q个隐见神经元），第i个神经元与第j个神经元的连接权值为wij，i，j＝1,2,…,n。T0为初始温度，m＝1,2,…,M为迭138代次数。Boltzmann机的运行步骤为：第一步：对网络进行初始化。设定初始温度T0、终止温度Tfinal和阈值ξ，以及网络各神经元的连接权值wij。第二步：在温度Tm条件下（初始温度为T0）随机选取网络中的一个神经元i，计算神经元i的输入信号总和ui：injijjijibvwu1第三步：若ui0，即能量差ΔEi0，取vi=1为神经元i的下一状态值。若ui0，计算概率：)1/(1/miTuiep若Pi大于等于一事先给定的阈值ξ，则取vi=1为神经元i的下一状态，否则保持神经元i的状态不变。在此过程中，网络中其它神经元的状态保持不变。第四步：判断网络在温度Tm下是否达到稳定，若未达到稳定，则继续在网络中随机选取另一神经元j，令j＝i，转至第二步重复计算，直至网络在Tm下达到稳定。若网络在Tm下已达到稳定则转至第五步计算。第五步：以一定规律降低温度，使Tm+1Tm，判断Tm+1是否小于Tfinal，若Tm+1大于等于Tfinal，则Tm=Tm＋1，转至第二步重复计算；若Tm+1小于Tfinal，则运行结束。此时在Tm下所求得的网络稳定状态，即为网络的输出。对于上述的Boltzmann机的运行步骤需要注意以下几点：（1）初始温度T0的选择方法。初始温度T0的选取主要有以下方法：随机选取网络中k个神经元，选取这k个神经元能量的方差作为T0；在初始网络中选取使ΔE最大的两个神经元，取T0为ΔEmax的若干倍；按经验值给出T0等。（2）确定终止温度阈值Tfinal的方法。主要根据经验选取，若在连