智能计算结课大作业

1、 用Hopfield网络实现联想记忆1问题描述设有n个城市记为D=d1,d2,d3。,dn,用dxy表示 dx和dy之间的距离。一个旅行商从某一城市出发，访问各个城市一次且仅一次，再回到原出发城市，且要求总路径最短。2算法理论用神经网络解决组合优化问题是神经网络应用的一个重要方面。所谓组合优化问题，就是在给定约束条件下，使目标函数极小（或极大）的变量组合问题。将Hopfield网络应用于求解组合优化问题，把目标函数转化为网络的能量函数，把问题的变量对应到网络的状态。这样，当网络的能量函数收敛于极小值时，问题的最优解也随之求出。由于神经网络是并行计算的，其计算量不随维数的增加而发生指数性“爆炸”

2、，因而对于优化问题的高速计算特别有效。利用连续的Hopfield网络求解TSP问题。Hopfield神经网络主要是模拟生物神经网络的记忆机理，是一种全连接型的神经网络，对于每个神经元来说，自己输出的信号通过其他神经元又反馈到自身，所以Hopfield神经网络是一种反馈型神经网络。连续的Hopfield神经网络状态的演变过程是一个非线性动力学系统，可以用一组非线性微分方程来描述。系统的稳定性可用所谓的下“能量函数”（即李雅普诺夫或哈密顿函数）进行分析。在满足一定条件下，某种“能量函数”的能量在网络运行过程中不断地减小，最后趋于稳定的平衡状态。反馈网络达稳定状态时可以使系统的能量达极小，因而可用于

3、一些最优化问题的计算，如何把实际问题的目标函数表达成下述二次型的能量函数是一个关键问题。3求解步骤可设计一个矩阵描述旅行路线，假设只有5个目的地。城市 | 次序12345C100010C210000C300100C401000C500001则路线为：C2C4C3C1C51） 满足矩阵每行不多于一个“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

4、*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=

5、500;C=200;D=500;arf=1;miu0=0.02;lan=0.00001;EndNum=1000; y=zeros(CityNum,CityNum);for i=1:CityNum y(i,i)=1;endz=-miu0/2*log(9)*ones(CityNum,CityNum);delu=0.1*miu0*rand(CityNum,CityNum); figure(1);for k=1:EndNum z=z+lan*delu; for u=1:CityNum for i=1:CityNum y(u,i)=1/(1+exp(-2*z(u,i)/miu0); end end fo

6、r u=1:CityNum for i=1:CityNum A1=0; B1=0; for aa=1:CityNum A1=A1+y(u,aa); B1=B1+y(aa,i); end A1=A1-y(u,i); B1=B1-y(u,i); C1=0; for aa=1:CityNum for bb=1:CityNum C1=C1+y(aa,bb); end end C1=C1-CityNum; D1=0; for x=1:CityNum if x=u if i=1 D1=D1+dislist(u,x)*(y(x,2)+y(x,CityNum); elseif i=CityNum D1=D1+

7、dislist(u,x)*(y(x,1)+y(x,CityNum-1); else D1=D1+dislist(u,x)*(y(x,i+1)+y(x,i-1); end end end delu(u,i)=-z(u,i)*arf-A*A1-B*B1-C*C1-D*D1; end end for i=1:CityNum x n=max(y(:,i); S(i)=n; end for i=1:CityNum-1 for j=i+1:CityNum if S(i)=S(j) ff=1; else ff=0; break; end if ff=0 break; end end if ff=0 brea

8、k; end end if ff=1 bsf=CalDist(dislist,S); else bsf=4; end Arrbsf(k)=bsf; drawTSP(Clist,S,bsf,k,0); %pause;endfigure(2);plot(Arrbsf,r); hold on;title(搜索过程);legend(最优解);%tsp.m城市位置function DLn,cityn=tsp(n) if n=10 city10=0.4 0.4439;0.2439 0.1463;0.1707 0.2293;0.2293 0.761;0.5171 0.9414; 0.8732 0.6536;

9、0.6878 0.5219;0.8488 0.3609;0.6683 0.2536;0.6195 0.2634; for i=1:10 for j=1:10 DL10(i,j)=(city10(i,1)-city10(j,1)2+(city10(i,2)-city10(j,2)2)0.5; end end DLn=DL10; cityn=city10;end%Caldist.m建立函数脚本function F=CalDist(dislist,s) DistanV=0;n=size(s,2);for i=1:(n-1) DistanV=DistanV+dislist(s(i),s(i+1);en

10、dDistanV=DistanV+dislist(s(n),s(1);F=DistanV;%drawTSP.m画图function m=drawTSP(Clist,BSF,bsf,p,f)CityNum=size(Clist,1);for i=1:CityNum-1 plot(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); hold on;endplot(Clist(BSF(CityNum),1),C

11、list(BSF(1),1),Clist(BSF(CityNum),2),Clist(BSF(1),2),ms-,LineWidth,2,MarkerEdgeColor,k,MarkerFaceColor,g);title(num2str(CityNum),城市TSP);if f=0 text(0,1,第 ,int2str(p), 步, 最短距离为 ,num2str(bsf);else text(0,1,最终搜索结果：最短距离 ,num2str(bsf);endhold off;pause(0.05);用SOFM网络对输入样本进行分类1问题描述利用SOFM网络实现对0-9数字及26个小写英文字

12、母的分类。用SOFM实现分类，将数字和小写字母由5*7黑白点矩阵表示，黑点为1，白点为0，输入层神经元为36个，形成35*36的输入矩阵。采用matlab工具箱中的SOFM神经网络对应函数newsom,将输入向量分为25类。2算法理论SOFM 的主要算法是一种无教师示范的聚类方法，能将任意输入模式在输出层映射成一维或二维离散图形，并保持其拓扑结构不变，即在无教师示范的情况下，通过对输入模式的自组织学习，在竞争层将分类结果表示出来。此外，网络通过对输入模式的反复学习，可以使连接权矢量空间分布密度和输入模式的概率分布趋于一致，即连接权矢量空间分布能反映输入模式的统计特征。总之，SOFM 神经网络能

13、够将高维模式映射到一平面上，而保持其拓扑结构不变，亦即距离相近的模式点，其映射点的距离也相近。SOFM 网络的几个基本参数为：1）输入模式矢量 其中，M 为输入训练矢量的个数；K 为网络输入节点数，即输入模式矢量的维数； W 为网络连接权矢量， ,N为输出神经元的个数；2）(t)为网络学习速率，通常0(t) temp %Crossover Condition for j=n:1:20 TempE(i,j)=E(i+1,j); TempE(i+1,j)=E(i,j); end endendTempE(Size,:)=BestS;E=TempE; %* Step 4: Mutation Opera

14、tion *%pm=0.001;%pm=0.001-1:1:Size*(0.001)/Size; %Bigger fi, smaller Pm%pm=0.0; %No mutationpm=0.1; %Big mutation for i=1:1:Size for j=1:1:2*CodeL temp=rand; if pmtemp %Mutation Condition if TempE(i,j)=0 TempE(i,j)=1; else TempE(i,j)=0; end end end end %Guarantee TempPop(30,:) is the code belong to

15、the best individual(max(fi)TempE(Size,:)=BestS;E=TempE;end Max_Value=BestfiBestSx1x2figure(1);plot(time,BestJ); xlabel(Times);ylabel(Best J);figure(2);plot(time,bfi);xlabel(times);ylabel(Best F);用PSO算法求解一优化问题1问题描述 粒子群算法，也称粒子群优化算法（Partical Swarm Optimization），缩写为 PSO， 是近年来发展起来的一种新的进化算法(（Evolu2tionary

16、 Algorithm - EA）。PSO 算法属于进化算法的一种，和遗传算法相似，它也是从随机解出发，通过迭代寻找最优解，它也是通过适应度来评价解的品质，但它比遗传算法规则更为简单，它没有遗传算法的“交叉”(Crossover) 和“变异”(Mutation) 操作，它通过追随当前搜索到的最优值来寻找全局最优。这种算法以其实现容易、精度高、收敛快等优点引起了学术界的重视，并且在解决实际问题中展示了其优越性。下面就用PSO算法来求解函数的优化问题。 2算法理论PSO算法是基于群体的，根据对环境的适应度将群体中的个体移动到好的区域。然而它不对个体使用演化算子，而是将每个个体看作是D维搜索空间中的一

17、个没有体积的微粒（点），在搜索空间中以一定的速度飞行，这个速度根据它本身的飞行经验和同伴的飞行经验来动态调整。第i个微粒表示为Xi = (xi1, xi2, , xiD)，它经历过的最好位置（有最好的适应值）记为Pi = (pi1, pi2, , piD)，也称为pbest。在群体所有微粒经历过的最好位置的索引号用符号g表示，即Pg，也称为gbest。微粒i的速度用Vi = (vi1, vi2, , viD)表示。对每一代，它的第d维(1 d D)根据如下方程进行变化：vid = w*vid+c1*rand()*(pid-xid)+c2*Rand()*(pgd-xid) (1a)xid = x

18、id+vid (1b)其中w为惯性权重(inertia weight)，c1和c2为加速常数(acceleration constants)，rand()和Rand()为两个在0,1范围里变化的随机值。此外，微粒的速度Vi被一个最大速度Vmax所限制。如果当前对微粒的加速导致它的在某维的速度vid超过该维的最大速度vmax,d，则该维的速度被限制为该维最大速度vmax,d。对公式(1a)，第一部分为微粒先前行为的惯性，第二部分为“认知(cognition)”部分，表示微粒本身的思考；第三部分为“社会(social)”部分，表示微粒间的信息共享与相互合作。3求解步骤a). 初始化一群微粒（群体规

19、模为m），包括随机的位置和速度；b). 评价每个微粒的适应度；c). 对每个微粒，将它的适应值和它经历过的最好位置pbest的作比较，如果较好，则将其作为当前的最好位置pbest；d). 对每个微粒，将它的适应值和全局所经历最好位置gbest的作比较，如果较好，则重新设置gbest的索引号；e). 根据方程变化微粒的速度和位置；f). 如未达到结束条件（通常为足够好的适应值或达到一个预设最大代数Gmax），回到b。4运行结果Solution =1.0e-051 * 0.144211488260264 -0.232215259872192 -0.224407404418848 -0.020779

20、954423550 -0.097899829028257 -0.211294183641239 -0.026416915962927 -0.127039497240274 0.091980071364857 0.157169484523497最后得到的优化极值为：Result =2.297404461936988e-1035结果分析本例是利用微粒群算法（PSO）对函数的最小值进行优化，最后得到的优化极值为2.297404461936988e-103，并对迭代次数等等进行了估计。用PSO来解决这种局部问题效果很好，而且通过迭代搜寻的最优质也是很符合客观事实的。6源程序函数一：%Fitness函数- function result=fit