离散系统神经网络

1、人工神经网络1.离散系统神经网络离散系统神经网络的输出值一般有如下关系： 其中式中，如采用符号函数的反馈神经网络，其关系为：记 在离散动力系统中，可以用输出值的特性定义平衡点。 则称为离散系统的平衡状态。在离散系统的神经网络中，当采用符号激活函数时，建立的能量函数（5.30）变为：其中， ，为符号函数，为和神经元的权数，为第个神经元的接受值，为外部输入值。 由（5.43），得到能量函数（5.44）对应的一个动力系统为：（5.45）的动力系统方程转化为：其中如（5.42）的符号函数。异步算法是指每次只调整一个神经元，可表达为：它的含义是：在一步迭代中，只有第个神经元发生变化，而其他神经元保持不变

2、。每次被调整的神经元随机选定。同步算法指同一时刻对所有神经元同时调整，表达式为：例5.6：三个神经元的反馈网络的权数为： 在时刻，一组输出，每个神经元的阈值都为3。在第时刻，同步算法使得每个神经元接受到的值为： 同步算法在时刻的输出为： 异步算法的计算为：当步迭代选择第一个神经元时，它的接受值为：若步迭代选择第二个神经元变化时，所以 ， 若步迭代选择第三个神经元变化时，所以 ， 虽说异步算法采用上面例中相邻的三次迭代达到同步算法对三个神经元进行的计算，但输出结果（0，0，0）与同步算法输出结果（0，1，0）的差别是显而易见的。 定理5.3：若（5.44）中的权数是正定矩阵，采用符号函数的同步算

3、法的平衡点是系统（5.45）的稳定点。 离散系统的异步算法有别于连续系统的神经网络，我们在此专门讨论。在以下的讨论中，特假定下列条件满足：1.是对称的阶方阵，且；2. ；3.符号函数为： 此处的符号函数有别于前面的函数定义，它把的点赋予值1。 定理5.4：若能量函数（5.44）有下界，则对任意的初始状态，满足上面假设的异步算法，最终收敛到一个平衡状态。 定义5.5：的邻域为，其中，表示第个分量为1其他分量为0的维向量， 若能量函数在满足：则称为邻域的能量极小点，简称能量极小点。 定理5.5：若时，定义，则每个能量极小点为平衡点。证明： 若为平衡点，则结论成立。当某一个神经元不平衡时，记神经元的

4、能量变化为，则由（5.48）有 按定理5.4证明中讨论的三种情况和时，定义，不平衡的可能有：CASE1:时，则，由的条件，推出，进而推出： 于是，与不平衡矛盾。CASE2：时，则，进而推出： 于是，与不平衡矛盾。综合CASE1 和CASE2的讨论，得到是一个平衡点。定理5.6：若离散系统神经网络的权矩阵对角线还满足，则网络的所有平衡点为能量函数极小点。证明：记平衡点，从的邻域中任选一点，不妨设为第 个神经元变化，则由（5.48）能量变化为：当时，由平衡点性质，知。由此得到。当时，由平衡点性质，知。由此得到。综合上面两点，平衡点为能量函数极小点。 神经网络异步算法的基本步骤为： STEP1：任意

5、选取一个初始状态； STEP2：随机选取一个神经元，按（5.46）更新状态； STEP3：检验是否为网络的平衡点，若是，转STEP4；否则，转STEP2； STEP4：输出。2.变形算法在中的应用 假设的个城市位置为，其中为空间的维数。在这个空间中我们给以个临界点，。我们期望将临时点同城市位置匹配使得：每个城市仅同一个临界点匹配且这些临时点形成的闭路满足尽量小，其中。若当城市同临时点匹配，则定义一个变量，否则。于是可以给出下列的能量函数 （5.49）的第一项的功能是匹配，需要满足。当已经匹配且渐进零的时候，（5.49）的第二项功能是使得这些临界点的闭路尽量小且点的分布尽量均匀。由于和是变量和求

6、解的难度，用另外一个效能函数：使其达到最小。 在（5.50）中，从右边的第一项看出，当每一个都有一个临界点与其匹配时， 其中，表示同匹配的临时点集合，为同匹配的临时点个数。此时，当趋向零时，（5.50）右端第一项的值接近零。当存在一个，没有一个临界点与其匹配时，由推出（5.50）右端第一项随着的趋向零而增加，因此需要继续优化。（5.50）右端的第二项要求个临时点形成的闭路尽量小和尽可能在闭路上均匀分布。（5.50）中只有为决策变量。能量函数的梯度为： 其中 对变量的下降梯度为：，是不小于零的参数。的弹性算法如下： STEP1：给定实例个城市的坐标； STEP2：选一个比大得多的临时点数； ST

7、EP3：选择合适的参数、初始温度和初始步长参数； STEP4：求初始坐标的重心；随即将，均匀地分布在以重心为圆心的一个小圆周上； STEP5：在算法没有达到停止条件前，重复以下计算：.更新临时坐标为，其中由（5.52）计算。.，。3.局部搜索算法组合最优化问题：其中为目标函数，为约束方程，为定义域。局部搜索算法 STEP1：选定一个初始可行解；记录当前最优解=，令； STEP2：当=时，或满足其他停止运算准则时，输出计算结果，停止运算；否则，从中选一集合，得到中的最优解；若，则，；否则，；重复STEP2。 在局部搜索算法中，STEP1的初始可行解选择可以采用随机的方法，也可用一些经验的方法或是

8、其他算法所得到的解。STEP2中的集合选取可以大到是 本身，也可以小到只有一个元素，如果用随机的方法在中选一点。从直观可以看出，选取得小将使每一步的计算量减少，但可比较的范围很小；的选取大时每一步计算时间增加，比较的范围自然增加，这两种情况的应用效果依赖于实际问题，在STEP2中，其他停止准则是除STEP2的其他准则。这写准则的给出往往取决于人们对算法的计算时间，计算结果的要求。通过下面的例子来理解局部搜索算法。 例2.1 五个城市的对称数据如图2.1，其对应的距离矩阵为 初始解=(),=45。在本例中，邻域映射定义为对换两个城市的。选定城市为起点，我们用两种情况解释缉捕搜索算法。 情况1 全

9、邻域搜索，即 第一循环：=,相对应的目标函数值为：，。 第二循环：=，相对应的目标函数值为：，。 此时，为空集，于是所得解为，目标值为43。情况2一步随机搜索：，第一循环：由于采用中的一步随机搜索，可以不再计算中每一点的值。若从中随机选一点，如。因，所以，。 第二循环：若从中又随机选一点，最后得到的解为。 局部搜索算法的优点是简单易行，容易理解，但其缺点是无法保证全局最优性。例2.2 四个城市非对称如图2.2，距离矩阵为： 若初始解为并且假设城市为起始点，。邻域中，其局部最优解是。读者可以按例2.1局部搜索讨论的两种情况进行验证，该算法终止时的解是局部最优解。而全局最优解是，。改变局部搜索中只按下降规则转移状态的一个