hopfieldexperiment.m

采用Hopfield网络解决旅行商问题

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 该程序运行多次，并输出合法解及其图形
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
clear;clc;

%
A=500;
B=500;
C=1000;
D=500;
u0=0.002;
lamda=0.0001;

N=10;         % 城市数
MaxTrn=1000;  % 每次实验的最大训练（迭代）次数
MaxTst=100;

% 城市坐标和距离
PosX=[0.4,0.2439,0.1707,0.2293,0.5171,0.8732,0.6878,0.8488,0.6683,0.6195,0.9125];
PosY=[0.4439,0.1463,0.2293,0.761,0.9414,0.6536,0.5219,0.3609,0.2536,0.2634, 0.9568];
for i=1:N
  for j=1:N
    Dist(i,j)=sqrt((PosX(i)-PosX(j))^2+(PosY(i)-PosY(j))^2);
  end;
end;

frslt=fopen('rslt.txt','w+');
Legal=0;
for tst=1:MaxTst
tst
% 计算
% 初始化
V=rand(N,N);
U=atanh(2*V-1)*u0;
%
for g=1:MaxTrn
  %
  for ux=1:N
    for ui=1:N
      m1=0; m2=0; m3=0; m4=0;
      % 求导公式第一项
      for j=1:N
        if j~=ui
          m1=m1+V(ux,j);
        end;
      end;
      m1=-A*m1;
      % 求导公式第二项
      for y=1:N
        if y~=ux
          m2=m2+V(y,ui);
        end;
      end;
      m2=-B*m2;
      % 求导公式第三项
      for x=1:N
        for j=1:N
          m3=m3+V(x,j);
        end;
      end;
      m3=-C*(m3-N);
      % 求导公式第四项
      for y=1:N
        if y~=ux
          if ui==1
            m4=m4+Dist(ux,y)*(V(y,ui+1)+V(y,N));
          elseif ui==N
            m4=m4+Dist(ux,y)*(V(y,ui-1)+V(y,1));
          else
            m4=m4+Dist(ux,y)*(V(y,ui+1)+V(y,ui-1));
          end;
        end;  
      end;
      m4=-D*m4;
      DU(ux,ui)=-U(ux,ui)+m1+m2+m3+m4;
    end;
  end;
  %
  U=U+lamda*DU;
  V=(1+tanh(U/u0))/2;
  for ux=1:N
    for ui=1:N
      if V(ux,ui)<0.3
        V(ux,ui)=0;
      end;
      if V(ux,ui)>0.7
        V(ux,ui)=1;
      end; 
    end;
  end;
end;

% 输出矩阵
V

% 判断是否为合法解
Cond1=0;   % 矩阵约束条件，要求共有N个1
for ux=1:N
  for ui=1:N
    Cond1=Cond1+V(ux,ui);
  end;
end;  
Cond2=0;   % 行约束条件，每行不多于一个1 
for x=1:N
  for i=1:N-1
    for j=i+1:N
     Cond2=Cond2+V(x,i)*V(x,j);
    end;
  end;
end;  
Cond3=0;  % 列约束条件，每列不多于一个1
for i=1:N
  for x=1:N-1
    for y=x+1:N
      Cond3=Cond3+V(x,i)*V(y,i);
    end;
  end;
end;
if (Cond1==N)&&(Cond2==0)&&(Cond3==0)  % 合法解
  % 旅行路线
  for j=1:N
    for i=1:N
      if V(i,j)==1
        PosXX(j)=PosX(i);
        PosYY(j)=PosY(i);
      end;
    end;
  end;
  PosXX(N+1)=PosXX(1);
  PosYY(N+1)=PosYY(1);
  PosXX
  PosYY
  fprintf(frslt,'\nTest:%d\n',tst);
  for i=1:N
    for j=1:N
      fprintf(frslt,'%.4f  ',V(i,j));
    end;
    fprintf(frslt,'\n');
  end;
  for i=1:(N+1)
    fprintf(frslt,'%.4f  ',PosXX(i));
  end;
  fprintf(frslt,'\n');
  for i=1:(N+1)
    fprintf(frslt,'%.4f  ',PosYY(i));
  end;
  fprintf(frslt,'\n');

  % 计算并输出总路程长度
  TourDist=0;
  for i=1:N-1
    TourDist=TourDist+sqrt((PosXX(i)-PosXX(i+1))^2+(PosYY(i)-PosYY(i+1))^2);
  end;
  TourDist=TourDist+sqrt((PosXX(N)-PosXX(1))^2+(PosYY(N)-PosYY(1))^2)

  % 图形输出
  if mod(Legal,8)==0
    figure(floor(Legal/8)+1);
  end;
  subplot(4,2,mod(Legal,8)+1);
  plot(PosXX,PosYY,'o-');
  title(TourDist);
  %
  Legal=Legal+1;
  LegalRslt(Legal)=TourDist;
end;

end;

fclose(frslt);

%
LegalRslt