搜索
用Hopfield网络实现联想记忆1．问题描述设有n个城市记为D={d1,d2,d3。。。,dn},用dxy表示dx和dy之间的距离。一个旅行商从某一城市出发，访问各个城市一次且仅一次，再回到原出发城市，且要求总路径最短。2．算法理论用神经网络解决组合优化问题是神经网络应用的一个重要方面。所谓组合优化问题，就是在给定约束条件下，使目标函数极小（或极大）的变量组合问题。将Hopfield网络应用于求解组合优化问题，把目标函数转化为网络的能量函数，把问题的变量对应到网络的状态。这样，当网络的能量函数收敛于极小值时，问题的最优解也随之求出。由于神经网络是并行计算的，其计算量不随维数的增加而发生指数性“爆炸”，因而对于优化问题的高速计算特别有效。利用连续的Hopfield网络求解TSP问题。Hopfield神经网络主要是模拟生物神经网络的记忆机理，是一种全连接型的神经网络，对于每个神经元来说，自己输出的信号通过其他神经元又反馈到自身，所以Hopfield神经网络是一种反馈型神经网络。连续的Hopfield神经网络状态的演变过程是一个非线性动力学系统，可以用一组非线性微分方程来描述。系统的稳定性可用所谓的下“能量函数”（即李雅普诺夫或哈密顿函数）进行分析。在满足一定条件下，某种“能量函数”的能量在网络运行过程中不断地减小，最后趋于稳定的平衡状态。反馈网络达稳定状态时可以使系统的能量达极小，因而可用于一些最优化问题的计算，如何把实际问题的目标函数表达成下述二次型的能量函数是一个关键问题。3．求解步骤可设计一个矩阵描述旅行路线，假设只有5个目的地。城市|次序12345C100010C210000C300100C401000C500001则路线为：C2—C4—C3—C1—C51）满足矩阵每行不多于一个“1”，即每个城市只能访问一次；E1=（1/2）*A*∑∑∑Vxi*Vyi;2）满足矩阵每列不多于一个”1”，即一次只能访问一个城市；E2=（1/2）*B*∑∑∑Vxi*Vyi;3）元素为“1”的个数为n，即共有n个城市；E3=（1/2）*C*(∑∑Vxi-N)²;4）保证路线最短E4=（1/2）*D*∑∑∑Dxy*[(Vxi,Vy,i+1)+(Vxi,Vy,i-1)];综上所述，可得TSP问题的能量函数如下：E=E1+E2+E3+E4;使E其达到极小值即为最佳路径。4．运行结果程序运行结果：routeLen=2.8394最小路径变化过程5．结果分析Hopfield网络很快得出十个城市的最佳路径。通过实验前后的对比，我们发现Hopfield联想记忆网络处理该问题有很好的效果，运行效率也高，值得借鉴。6．源程序%Hopfield_neuro_net.m主程序：clear;CityNum=10;[dislist,Clist]=tsp(CityNum);A=500;B=500;C=200;D=500;arf=1;miu0=0.02;lan=0.00001;EndNum=1000;y=zeros(CityNum,CityNum);fori=1:CityNumy(i,i)=1;endz=-miu0/2*log(9)*ones(CityNum,CityNum);delu=0.1*miu0*rand(CityNum,CityNum);figure(1);fork=1:EndNumz=z+lan*delu;foru=1:CityNumfori=1:CityNumy(u,i)=1/(1+exp(-2*z(u,i)/miu0));endendforu=1:CityNumfori=1:CityNumA1=0;B1=0;foraa=1:CityNumA1=A1+y(u,aa);B1=B1+y(aa,i);endA1=A1-y(u,i);B1=B1-y(u,i);C1=0;foraa=1:CityNumforbb=1:CityNumC1=C1+y(aa,bb);endendC1=C1-CityNum;D1=0;forx=1:CityNumifx~=uifi==1D1=D1+dislist(u,x)*(y(x,2)+y(x,CityNum));elseifi==CityNumD1=D1+dislist(u,x)*(y(x,1)+y(x,CityNum-1));elseD1=D1+dislist(u,x)*(y(x,i+1)+y(x,i-1));endendenddelu(u,i)=-z(u,i)*arf-A*A1-B*B1-C*C1-D*D1;endendfori=1:CityNum[xn]=max(y(:,i));S(i)=n;endfori=1:CityNum-1forj=i+1:CityNumifS(i)~=S(j)ff=1;elseff=0;break;endifff==0break;endendifff==0break;endendifff==1bsf=CalDist(dislist,S);elsebsf=4;endArrbsf(k)=bsf;drawTSP(Clist,S,bsf,k,0);%pause;endfigure(2);plot(Arrbsf,'r');holdon;title('搜索过程');legend('最优解');%tsp.m城市位置function[DLn,cityn]=tsp(n)ifn==10city10=[0.40.4439;0.24390.1463;0.17070.2293;0.22930.761;0.51710.9414;0.87320.6536;0.68780.5219;0.84880.3609;0.66830.2536;0.61950.2634];fori=1:10forj=1:10DL10(i,j)=((city10(i,1)-city10(j,1))^2+(city10(i,2)-city10(j,2))^2)^0.5;endendDLn=DL10;cityn=city10;end%Caldist.m建立函数脚本functionF=CalDist(dislist,s)DistanV=0;n=size(s,2);fori=1:(n-1)DistanV=DistanV+dislist(s(i),s(i+1));endDistanV=DistanV+dislist(s(n),s(1));F=DistanV;%drawTSP.m画图functionm=drawTSP(Clist,BSF,bsf,p,f)CityNum=size(Clist,1);fori=1:CityNum-1plot([Clist(BSF(i),1),Clist(BSF(i+1),1)],[Clist(BSF(i),2),Clist(BSF(i+1),2)],'ms-','LineWidth',2,'MarkerEdgeColor','k','MarkerFaceColor','g');holdon;endplot([Clist(BSF(CityNum),1),Clist(BSF(1),1)],[Clist(BSF(CityNum),2),Clist(BSF(1),2)],'ms-','LineWidth',2,'MarkerEdgeColor','k','MarkerFaceColor','g');title([num2str(CityNum),'城市TSP']);iff==0text(0,1,['第',int2str(p),'步','最短距离为',num2str(bsf)]);elsetext(0,1,['最终搜索结果：最短距离',num2str(bsf)]);endholdoff;pause(0.05);用SOFM网络对输入样本进行分类1．问题描述利用SOFM网络实现对0-9数字及26个小写英文字母的分类。用SOFM实现分类，将数字和小写字母由5*7黑白点矩阵表示，黑点为1，白点为0，输入层神经元为36个，形成35*36的输入矩阵。采用matlab工具箱中的SOFM神经网络对应函数newsom,将输入向量分为25类。2．算法理论SOFM的主要算法是一种无教师示范的聚类方法，能将任意输入模式在输出层映射成一维或二维离散图形，并保持其拓扑结构不变，即在无教师示范的情况下，通过对输入模式的自组织学习，在竞争层将分类结果表示出来。此外，网络通过对输入模式的反复学习，可以使连接权矢量空间分布密度和输入模式的概率分布趋于一致，即连接权矢量空间分布能反映输入模式的统计特征。总之，SOFM神经网络能够将高维模式映射到一平面上，而保持其拓扑结构不变，亦即距离相近的模式点，其映射点的距离也相近。SOFM网络的几个基本参数为：1）输入模式矢量其中，M为输入训练矢量的个数；K为网络输入节点数，即输入模式矢量的维数；W为网络连接权矢量，,N为输出神经元的个数；2）α(t)为网络学习速率，通常0α(t)1,且随时间单调下降；3)NEj(t)（j=1,2,...,N）为输出层神经元j的邻域,它与其所包含的节点数有关，随着t的增加逐步减小；所谓邻域NEj(t)，是指以确定的获胜神经元节点j为中心，包含若干神经元的区域范围。这个区域可以是任何形状，但一般是均匀对称的，典型的是正方形或圆形区域。可将SOFM算法描述如下[2,4,5]：①初始化；a)设置初始权值。一般将k个输入层神经元到N个输出层神经元之间的权值设置一些较小的非零随机数。b)定义学习速率函数α(t)，并设置其初始值α(0)c)定义输出层神经元的邻域NEj(t)，并设置其初始值NEj(0)。NEj(t)的值表示在第t次学习过程中邻域中所包含的神经元的个数。②对网络输入训练矢量并进行归一化处理③对连接权值wj进行归一化处理，计算输入模式xi与每个输出神经元节点连接权矢量wj的欧氏距离dj。设xi(t)是t时刻输入层第I个神经元的输出，wij(t)是输入神元i到输出层神经元j之间的连接权。则jd的计算公式为：④选择具有最小距离的输出节点j作为获胜节点，即⑤调整与神经元j*及其邻域内所有神经元节点的连接权矢量⑥入训练矢量集的下一个输入矢量，回到步骤③，反复进行，直到k个学习模式全部提供给网络⑦新学习速率α(t)及邻域NEj(t)。；；α(0)为初始学习速率，t为学习次数,T为总的学习次数。；INT(x)为取整符号，NEj(0)为NEj(t)的初值⑧令t=t+1,返回步骤②，直至t=T，达到足够的学习次数或满足规定的终止条件为止。3．运行结果4．结果分析近年来，SOFM网络算法越来越受到人们的重视，尽管到目前为止，SOFM理论还未形成一个体系,但其应用发展得很快，已经成为继BP网络之后得到研究最多、应用最广泛的一种神经网络模型。利用Matlab先进行仿真和试验，确定出想要分类的模式，对于实际的应用有很好的指导作用。SOFM的很多特性都是在实践中发现的，如它有拓扑保持和概率分布保持的优良特性，但在越来越多的实践研究中发现，SOFM中预定的网络拓扑结构隐含了对结果应设的限制，通常只有在训练结束之后才发现不同的网络拓扑结构也许能得到更好的结果，而这种定结构的SOFM带来了诸如神经元欠利用、网络映射欠准确以及边缘效应等问题。大多数情况下，并没有先验知识能让我们事先去选择一个合适的网络规模，所以这些因素严重影响了SOFM的应用，有待于进一步的研究和实践。5．源程序形成输入矩阵程序：%prodat.m文件给小写字母和数字赋初值function[alphabet]=prodat()%Returns:%ALPHABET-35x36matrixof5x7bitmapsforeachletter.Lettera=[00100010101000110001100010101100101]';Letterb=[10000100001000011110100011000111110]';Letterc=[01110100011000010000100001000101110]';Letterd=[0000000001000010111