离散系统神经网络

人工神经网络1.离散系统神经网络离散系统神经网络的输出值一般有如下关系：(1)((),),YtgYtt其中0{|,}tiiti为整数式中，12()((),(),())TnYtytytyt，如采用符号函数的反馈神经网络，其关系为：1(1)sgn(()),1,2,niijjijytwytin记1(1)(),1,2,niijjijztwytin在离散动力系统中，可以用输出值Y的特性定义平衡点。(,),eeYgYttI则称eY为离散系统的平衡状态。在离散系统的神经网络中，当采用符号激活函数时，Hopfield建立的能量函数（5.30）变为：1111()2nnnijijiiijiEywyyy其中，()iiiyfz，if为符号函数，ijjiww为i和j神经元的权数，iz为第i个神经元的接受值，iI为外部输入值。由（5.43），得到能量函数（5.44）对应的一个动力系统为：1(1)()()()()1,2,niiiijjijiiiztztztwytyfzin（5.45）的动力系统方程转化为：1(1)(()),1,2,niijjijytfwytin人工神经网络其中f如（5.42）的符号函数。异步算法是指每次只调整一个神经元，可表达为：1(1)sgn(())(1)(),niijjijjjytwytytytji它的含义是：在一步迭代中，只有第i个神经元发生变化，而其他神经元保持不变。每次被调整的神经元i随机选定。同步算法指同一时刻对所有神经元同时调整，表达式为：1(1)sgn(()),1,2,niijjijytwytin例5.6：三个神经元的反馈网络的权数为：012103230W在t时刻，一组输出()(1,0,1)TYt，每个神经元的阈值都为3。在第1t时刻，同步算法使得每个神经元接受到的值为：(1)()(2,4,2)(3,3,3)TTZtWYt同步算法在1t时刻的输出为：(1)((1))(0,1,0)TYtfZt异步算法的计算为：当1t步迭代选择第一个神经元时，它的接受值为：11(1)(0,1,2)()ztYt若1t步迭代选择第二个神经元变化时，220(1)(1,0,3)(1)(1,0,3)0301ztYt所以123(2)0,(2)0,(2)1ytytyt，(2)(0,0,1)TYt人工神经网络若3t步迭代选择第三个神经元变化时，230(3)(2,3,0)(2)(2,3,0)0331ztYt所以123(3)0,(3)0,(3)0ytytyt，(3)(0,0,0)TYt虽说异步算法采用上面例中相邻的三次迭代达到同步算法对三个神经元进行的计算，但输出结果（0，0，0）与同步算法输出结果（0，1，0）的差别是显而易见的。定理5.3：若（5.44）中的权数W是正定矩阵，采用符号函数的同步算法的平衡点是系统（5.45）的稳定点。离散系统的异步算法有别于连续系统的神经网络，我们在此专门讨论。在以下的讨论中，特假定下列条件满足：1.W是对称的n阶方阵，且0iiw；2.(){0,1}iyt；3.符号函数为：1,0sgn()0,xx其他此处的符号函数有别于前面的函数定义，它把0x的点赋予值1。定理5.4：若能量函数（5.44）有下界，则对任意的初始状态，满足上面假设的异步Hopfield算法，最终收敛到一个平衡状态。定义5.5：{0,1}nY的邻域为(){|1,2,}iiNYYein，其中，ie表示第i个分量为1其他分量为0的n维向量，1,11,0iiiyy当当若能量函数在*Y满足：**()(),(),EYEYYNY则称*Y为邻域*()NY的能量极人工神经网络小点，简称能量极小点。定理5.5：若(1)0izt时，定义(1)()iiytyt，则每个能量极小点为平衡点。证明：*****1,(2)(),(2)niijjiiiiiijzwyyfzyyy若为平衡点，则结论成立。当某一个神经元i不平衡时，记神经元的能量变化为iE，则由（5.48）有****111[][]22niiijjiiiiiiijijEywywyzw按定理5.4证明中讨论的三种情况和(1)0izt时，定义(1)()iiytyt，不平衡的可能有：CASE1:1i时，*0jy，则*102iiizw，由0iiw的条件，推出*0iz，进而推出：****0,0(2)()0iiiiizyfzyz当，当于是*(2)iiyy，与不平衡矛盾。CASE2：1i时，*1jy，则**110,022iiiiiiizwzw，进而推出：****1,0(2)()0iiiiizyfzyz当，当于是*(2)iiyy，与不平衡矛盾。综合CASE1和CASE2的讨论，得到*Y是一个平衡点。定理5.6：若离散系统神经网络的权矩阵对角线还满足()(0,0,0)diagW，则网络的所有平衡点为能量函数极小点。人工神经网络证明：记平衡点****12(,,)TnYyyy，从*Y的邻域中任选一点，不妨设为第i个神经元变化，则由（5.48）能量变化为：**1[]2iiiiiiiiEzwz当1i时，*0iy，由平衡点性质*(2)()0iiyfz，知*0iz。由此得到0iE。当1i时，*1iy，由平衡点性质*(2)()1iiyfz，知*0iz。由此得到0iE。综合上面两点，平衡点为能量函数极小点。Hopfield神经网络异步算法的基本步骤为：STEP1：任意选取一个初始状态(0){0,1}nY；STEP2：随机选取一个神经元，按（5.46）更新状态；STEP3：检验()Yt是否为网络的平衡点，若是，转STEP4；否则，转STEP2；STEP4：输出()Yt。2.变形算法在TSP中的应用假设TSP的n个城市位置为12(,,)TiiiimXxxx，1,2,in，其中m为空间的维数。在这个空间中我们给以Nn个临界点12(,,)TaaaamYyyy，1,2,aN。我们期望将临时点同城市位置匹配使得：每个城市仅同一个临界点匹配且这些临时点形成的闭路满足1aaaYY尽量小，其中11NYY。若当城市i同临时点a匹配，则定义一个变量1ias，否则0ias。于是可以给出下列的能量函数2211(,)22iaaiaiaaaiaaEsYsXXYYT（5.49）的第一项的功能是匹配，需要满足iaiasn。当已经匹配且T渐进零的时候，（5.49）的第二项功能是使得这些临界点的闭路尽量小且点的分布尽量均人工神经网络匀。由于aY和ias是变量和ias求解的难度，用另外一个效能函数：2222101()log()2iaXXTeffaaaiaaEYTeYY使其达到最小。在（5.50）中，从右边的第一项看出，当每一个iX都有一个临界点与其匹配时，222222222,0iaiaiaXXXXXXTTTaaMaMeeekT其中，M表示同iX匹配的临时点集合，k为同iX匹配的临时点个数。此时，当T趋向零时，（5.50）右端第一项的值接近零。当存在一个iX，没有一个临界点与其匹配时，由2220,0iaXXTaeT推出（5.50）右端第一项随着T的趋向零而增加，因此需要继续优化。（5.50）右端的第二项要求N个临时点形成的闭路尽量小和尽可能在闭路上均匀分布。（5.50）中只有aY为决策变量。能量函数的梯度为：11()()(2)iaiaeffaiaaaavXYEYYYYYT其中2222exp()2exp()2iaiaibbXYTvXYT()effaEY对变量aY的下降梯度为：()effaaaEYYY，是不小于零的参数。TSP的弹性算法如下：STEP1：给定TSP实例n个城市的坐标{|1,2,}iXin；STEP2：选一个比n大得多的临时点数N；STEP3：选择合适的参数、初始温度0T和初始步长参数0；STEP4：求初始坐标{|1,2,}iXin的重心；随即将12(,,)TaaaamYyyy，人工神经网络1,2,aN均匀地分布在以重心为圆心的一个小圆周上；STEP5：在算法没有达到停止条件前，重复以下计算：a.更新临时坐标aY为11()()()alalalYTYTYT，其中1()alYT由（5.52）计算。b.1ll，1llTT01。3.局部搜索算法组合最优化问题：min().()0fxstgxxD其中()fx为目标函数，()gx为约束方程，D为定义域。局部搜索算法STEP1：选定一个初始可行解0x；记录当前最优解bestx=0x，令()bestPNx；STEP2：当P=时，或满足其他停止运算准则时，输出计算结果，停止运算；否则，从()bestNx中选一集合S，得到S中的最优解nowx；若()()nowbestfxfx，则bestnowxx，()bestPNx；否则，PPS；重复STEP2。在局部搜索算法中，STEP1的初始可行解选择可以采用随机的方法，也可用一些经验的方法或是其他算法所得到的解。STEP2中的集合S选取可以大到是()bestNx本身，也可以小到只有一个元素，如果用随机的方法在()bestNx中选一点。从直观可以看出，S选取得小将使每一步的计算量减少，但可比较的范围很小；S的选取大时每一步计算时间增加，比较的范围自然增加，这两种情况的应用效果依赖于实际问题，在STEP2中，其他停止准则是除STEP2的P其他准则。这写准则的给出往往取决于人们对算法的计算时间，计算结果的要求。通过下面的例子来理解局部搜索算法。人工神经网络例2.1五个城市的对称数据如图2.1，其对应的距离矩阵为01015621008139()158020156132005291550ijDd初始解bestx=(ABCDE),()bestfx=45。在本例中，邻域映射定义为对换两个城市的2opt。选定A城市为起点，我们用两种情况解释缉捕搜索算法。情况1全邻域搜索，即()bestSNx第一循环：()bestNx={(),(),(),ABCDEACBDEADCBE(),()AECDBABDCE,(),()}ABEDCABCED,相对应的目标函数值为：(){45,43,45,60,60,59,44}fx，()bestnowxxACBDE。第二循环：()bestNx={(),(),(),(),(),ACBDEABCDEADBCEAEBDCACDBE(),()}ACEDBACBED，相对应的目标函数值为：(){43,45,44,59,59,58,43}fx，()bestnowxxACBDE。此时，()bestPNxS为空集，于是所得解为()ADCBE，目标值为43。情况2一步随机搜索：bestx()ABCDE，()45bestfx第一循环：由于采用()bestNx中的一步随机搜索，可以不再计算()bestNx中每一点的值。若从中随机选一点，如()nowxACBDE。因()4345nowfx，所以，()bestxACBDE。第二循环：若从()bestNx中又随机选一点()nowxADBCE，()4443nowfx，(){}bestnowPNxx，最后得到的解为()ACBDE。局部搜索算法的优点是简单易行，容易理解，但其缺点是无法保证全局最优人工神经网络性。