《人工神经网络.07.boltzman》由会员分享，可在线阅读，更多相关《人工神经网络.07.boltzman（68页珍藏版）》请在金锄头文库上搜索。
1、1,人工神经网络 (Artifical Neural Network),张 凯 副教授,武汉科技大学 计算机学院,2,要点简介,1. 研究背景,2. 随机神经网络,3. 模拟退火算法,4. Boltzmann机,随机神经网络,随机神经网络是统计力学思想引入神经网络研究的结果。 统计力学是研究大系统宏观平衡性质的学科，这种大系统的组成元素服从微观机制。统计力学的主要目的是寻找从微观粒子（原子、电子）的运动开始的宏观物体的热力学性质，由于所遇到的自由度数目很大，因此只能使用概率的方法进行研究。,随机神经网络,BP网络是一种“贪心”算法，容易陷入局部最小点。 Hopfield网络很难避免出现伪状态，
2、网络是严格按照能量减小的方向运行的，容易陷入局部极小点，而无法跳出。 所以，在用BP网络和Hopfield网络进行最优化的计算时，由于限定条件的不足，往往会使网络稳定在误差或能量函数的局部最小点，而不是全局最小点，即所得的解不是最优解。,随机神经网络,随机神经网络,网络陷入局部最小点的原因主要有两点： (1)网络结构上存在着输入到输出之间的非线性函数关系，从而使网络误差或能量函数所构成的空间是一个含有多极点的非线性空间。 (2)在算法上，网络的误差或能量函数只能单方向减小，不能有一点上升。,6,随机神经网络,随机神经网络的基本思想： 网络向误差或能量函数减小方向运行的概率大，同时向误差或能量函
3、数增大方向运行的概率存在，这样网络跳出局部极小点的可能性存在，而且向全局最小点收敛的概率最大。,模拟退火算法(Simulated Annealing)来源于固体退火原理，将固体加温至充高，再让其徐徐冷却，加温时，固体内部粒子随温度升高变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。 它由Metropolis算法和退火过程(Annealing Procedure，AP)组成。,模拟退火算法,模拟退火算法的基本思路,首先在高温下进行搜索，此时各状态出现概率相差不大，可以很快进入“热平衡状态”，这时进行的是一种“粗搜索”，也就是大致找到系统
4、的低能区域； 随着温度的逐渐降低，各状态出现概率的差距逐渐被扩大，搜索精度不断提高。这就可以越来越准确的找到网络能量函数的全局最小点。,9,模拟退火算法的基本思路,当使用最速下降法(gradient descent)时，系统可能陷入局部最小值(local minimum),模拟退火算法的基本思路,仿真退火算法 基本概念 改变系统能量 以组合最速下降与随机过程的方式搜寻能量函数的总体最小值 在搜寻的过程中，通常以最速下降法使其解答状态在搜寻空间中往能量函数值较低处移动，但透过随机过程，偶而往能量函数值较高处移动，以跳过局部最小值,模拟退火算法的基本思路,最速下降 模拟退火,模拟退火概念,在模拟退
5、火搜寻过程中，当次一个解的能量函数值比现行解的能量函数值低时，移至此解。 反之，则允许少许机率移动到能量函数值较高的次一个解，此机率通常假设为两个解间能量函数差额的Boltzmann机率分布函数。,模拟退火算法的基本思路,模拟退火的最初目的是寻找代表复杂系统的代价函数的全局最小值。因此，这种方法为解决凹平面最优问题提供了一个强有力的工具，其中心思想在于：在用模拟退火最优化一个复杂系统（如：一个拥有很多自由度的系统）时，误差或能量函数绝大部分的时间在下降，但不是一直下降，即误差或能量函数的总趋势向减小的方向变化，但有时也向增大的方向变化，这样可跳出局部极小点，向全局最小点收敛。,模拟退火与传统迭
6、代最优算法的比较： (1)当系统在非零温度下时，从局部最优中跳出是非常可能的，因此不会陷入局部最优。 (2)系统最终状态的总特征可以在较高温度下看到，而状态的好的细节却在低温下表现，因此，模拟退火是自适应的.。,模拟退火算法的基本思路,1. Metropolis抽样过程,模拟退火算法原理,1. Metropolis抽样过程 假定一随机变量在某一时刻的状态为vi。在另一时刻的状态为vj。假设这种状态的转移满足以下条件： E表示系统从状态vi转移至状态vj所引起的能量差。 如果能量差E为负，这种转移就导致状态能量的降低，这种转移就被接受。接下来，新状态作为算法下一步的起始点。,模拟退火算法原理,模
7、拟退火算法原理,若能量差为正，算法在这一点进行概率操作。首先，选定一个在0,1内服从均匀分布的随机数。如果e-E/T，则接受这种转移。否则，拒绝这种转移；即在算法的下一步中拒绝旧的状态。如此反复，达到系统在此温度下的热平衡。 这个过程称作Metropolis抽样过程。Metropolis抽样过程就是在一确定温度下，使系统达到热平衡的过程。,模拟退火算法原理,2. 退火过程（降温过程） 在Metropolis抽样过程中温度T缓慢的降低。模拟退火过程就是通过T参数的变化使状态收敛于最小能量处。因而，T参数的选择对于算法最后的结果有很大影响。初始温度和终止温度设置的过低或过高都会延长搜索时间。降温步
8、骤太快，往往会漏掉全局最优点，使算法收敛至局部最优点。降温步骤太慢，则会大大延长搜索全局最优点的计算时间，从而难以实际应用。因此，T可以理解为一个控制参数。,模拟退火算法原理,为寻找在有限时间逼近全局最优的模拟退火算法，设置了许多控制算法收敛的参数。在退火过程中指定了有限的退火温度值和在每一温度下的转移数目。Kirlpatrick等人在退火步骤中设定的参数如下： (1)初始温度值：初始温度值T0要选的足够高，保证模拟退火算法中所有可能的转移都能被接受。,2018年12月17日星期一,20,模拟退火算法原理,(2)温度的下降：原先使用指数函数实现温度的下降。但是这种方法使降温幅度过小，从而延长搜
9、索时间。在实际中，通常使用下式： 此处是一小于却接近于1的常数。通常的取值在0.8至0.99之间。在每一温度下，实验足够多的转移次数。,2018年12月17日星期一,21,模拟退火算法原理,(3)终止温度：如果在连续的若干个温度下没有可接受的新状态，系统冻结或退火停止。 模拟退火尤其适合解决组合优化问题，下面以模拟退火算法解决组合优化问题来进一步介绍模拟退火算法的步骤。,2018年12月17日星期一,22,许多工程上和理论上的问题，其目标都是在一个很大的解空间中寻求一个最优解，这些问题统称为组合优化问题。 在许多组合优化问题中，一个解通常是满足一定规则的一些离散对象的排列，所有这些解的集合叫做
10、解空间。通常用一个“代价函数”C(x)来衡量一个解的优劣，目标就是选择一个解使其代价函数C(x)最小，如TSP问题、大规模集成电路布局布线问题等。,2018年12月17日星期一,23,模拟退火求解组合优化问题,2018年12月17日星期一,24,模拟退火求解组合优化问题,设V=V1,V2,Vn为所有可能的组合（或状态）所构成的集合。C()是V的函数，且 ，反映取状态Vi为解的代价，目标是寻找 使 模拟退火算法应用于组合优化问题的基本思想就是把每种组合状态Vi看成某一物质体系的微观状态，C(Vi)可看成该物质体系在Vi下的能量 ，温度T为控制参数。,模拟退火求解组合优化问题,让T从一个足够高的值
11、慢慢下降，对于每个T，对当前状态V作随机扰动产生一个新状态V，计算其增量C=C(V)-C(V)，并以概率e-C/kT接受V作为新的当前状态。根据统计力学的知识，当重复如此随机扰动足够次数后，状态Vi的出现概率如下：,2018年12月17日星期一,26,模拟退火求解组合优化问题,k为Boltzmann常数,第一步：初始化。依据所要解决的组合优化问题，确定代价函数C()的表达式，随机选择初始状态V=V(0)，设定初始温度T0，终止温度Tfinal，概率阈值。 第二步：Metropolis抽样过程 （1）在温度T下依据某一规定的方式，根据当前解所处的状态V，产生一个近邻子集N(V)（可包括V，也可不
12、包括V），在N(V)内随机寻找一个新状态S作为下一个当前解的候选解，计算C=C(V)-C(V)。,2018年12月17日星期一,27,模拟退火求解组合优化问题,模拟退火求解组合优化问题,（2）若C0，则计算概率e-C/T，若其大于给定概率阈值，则取下一状态为V=V，否则，保留这一状态。 （3）按某一给定的收敛算法检查算法在温度T下是否应停止，若符合收敛条件则表示已达到热平衡，转向第三步的退火过程，若不符合收敛条件，则转向（1）继续迭代，直至在此温度下收敛。,2018年12月17日星期一,28,模拟退火求解组合优化问题,第三步：退火过程。 按照一定的降温方法得到一个新的温度T，检查T是否小于给定
13、的温度终止阈值Tfinal。若小于，则退火过程结束，当前状态V即为算法最终输出解。若温度T大于等于给定阈值，则转至Metropolis抽样过程，在新的温度下搜索状态。 注意：在上述退火过程中，模拟退火算法是否能达到能量E的最小值，取决于T0是否足够高，和T下降得是否充分慢，以及对每个T时系统是否稳定。,（1）T0的选择方法： a. 均匀随机抽样Vi，取此时C(Vi)的方差为T0 b. 在所有可能的组合状态中，选两个状态使C 最大，取T0为C的若干倍； c. 按经验给出。,2018年12月17日星期一,30,模拟退火参数控制,模拟退火参数控制,(2) 退火过程中Tfinal 的选取方法： a 依
14、据经验确定 b 检验系统的熵是已否达到最小，若达到最小， 即可认为温度已达到终止温度。 c T下降n次后都没有改善，即可认为能量已降 到最低，没有必要再降温。,2018年12月17日星期一,31,模拟退火参数控制,（3）Metropolis抽样过程的收敛算法： a.检验目标函数C()的均值是否稳定； b.继续若干步，C()变化很小（设定阈值）； c.按一个固定步数抽样。 （4）降温方法的确定： 根据Kirlpatrick的方法令 ，,模拟退火参数控制,模拟退火算法是一种通用的随机搜索算法，它可用于解决众多的优化问题，并已经广泛的应用于其他领域。如VLSL设计、图像识别等。当待解决的问题复杂性较
15、高，而且规模较大时，在对问题的领域知识甚少的情况下，采用模拟退火算法最合适。因为模拟退火算法不像其他确定型启发式算法那样，需要依赖于问题的领域知识来提高算法的性能。,模拟退火参数控制,但是，从另一方面来说，已知有关待解决问题的一些知识后，模拟退火算法却无法充分利用它们，这使得模拟退火算法的优点就成了缺点。如何把传统的启发式搜索方法和模拟退火随机搜索算法结合起来，这是一个有待研究的十分有意义的课题。,2018年12月17日星期一,34,模拟退火参数控制,模拟退火算法具有跳出局部最优陷阱的能力，因此被Ackley、Hinton和Sejnowski用作Boltzmann机学习算法，从而使Boltzm
16、ann机克服了Hopfield网络经常收敛到局部最优点的缺点。在Boltmann机中，即使系统落入局部最优的陷阱，经过一段时间后，它还能重新跳出来，使系统最终将往全局最优点的方向收敛。,2018年12月17日星期一,35,模拟退火参数控制,模拟退火算法在求解规模较大的实际问题时，往往存在以下缺点： (1)收敛速度比较慢。 (2)尽管理论上只要计算时间足够长，模拟退火法就可以保证以概率1收敛于全局最优点。但是在实际算法的实现过程中，由于计算速度和时间的限制，在优化效果和计算时间二者之间存在矛盾，因而难以保证计算结果为全局最优点，优化效果不甚理想。 (3)在每一温度下很难判定是否达到了平衡状态。,模拟退火参数控制,为此，人们对模拟退火算法提出了各种各样的改进，其中包括并行模拟退火算法、快速模拟退火算法和对模拟退火算法中各个函数和参数的重新设计等。,Boltzmann机,20世纪80年代，Ackley, Hinton 和Se
