用C或C++，编写用Hopfield网络求解TSP问题

涟漪

求助啊！！！
我们下星期二要交一份计算智能作业啊！但是我的编程技术不行啊，有没有那位大哥可以帮我完成它啊？我会十分感激你的！
用C或C++，编写用Hopfield网络求解TSP问题（旅行商问题）的程序(城市数目≥5)。
希望能够有人帮到我啦！

christy

看杨建刚写的《人工神经网络实用教程》

frogfish

连续Hopfield网络解决TSP（这个是matlab程序）

1. %连续Hopfield网络解决TSP
   
2. function HopfieldTsp()
   
3. clc;
   
4. N=10;   %城市数
   
5. A=1.5;  %系数A
   
6. D=1;    %系数D
   
7. u0=0.02;    %神经元函数斜率
   
8. Step_t=0.1; %计算步长
   
9. MaxEpochs=20000;%迭代次数
   
10. %得到城市间距离矩阵
    
11. CityCood=rand(2,N); %城市坐标
    
12. DistanceMat=dist(CityCood',CityCood);   %城市间距离矩阵
    
13. U=0.2*rand(N,N)-0.1;%神经元输入初始值在0附近产生
    
14. for Count=1:MaxEpochs
    
15.     V=(1+tansig(U/u0))/2;
    
16.     E=CacuEnergy(V,DistanceMat,A,D);%计算能量
    
17.     delta_U=CacuDeltaU(V,DistanceMat,A,D,Step_t);%计算U的增量
    
18.     U=U+delta_U*Step_t;
    
19. end
    
20. [NewV,CheckRes]=RouteCheck(V);%检查V是否是有效路径
    
21. if(CheckRes<1)
    
22.     FinalE=CacuEnergy(NewV,DistanceMat,A,D);
    
23.     RouteLen=TotalRouteLength(NewV,CityCood);%计算路径的真实长度
    
24.     PlotRoute(NewV,CityCood);%绘制路径
    
25. else
    
26.     disp('路径无效!!');
    
27. end
    
28. %能量计算
    
29. function E=CacuEnergy(V,d,A,D)
    
30. [n,n]=size(V);
    
31. t1=sumsqr(sum(V,2)-1);
    
32. t2=sumsqr(sum(V,1)-1);
    
33. PermitV=V(:,2:n);
    
34. PermitV=[PermitV V(:,1)];
    
35. temp=d*PermitV;
    
36. t3=sum(sum(V.*temp));
    
37. E=0.5*(A*t1+A*t2+D+t3);
    
38. %计算U的增量
    
39. function d_U=CacuDeltaU(V,d,A,D,dt)
    
40. [n,n]=size(V);
    
41. t1=repmat(sum(V,2)-1,1,n);
    
42. t2=repmat(sum(V,1)-1,n,1);
    
43. PermitV=V(:,2:n);
    
44. PermitV=[PermitV V(:,1)];
    
45. t3=d*PermitV;
    
46. d_U=-dt*(A*t1+A*t2+D*t3);
    
47. %检查V是否是有效路径
    
48. function [NewV,CheckRes]=RouteCheck(V)
    
49. [rows,columns]=size(V);
    
50. NewV=zeros(rows,columns);
    
51. [XC,Order]=max(V);
    
52. for j=1:columns
    
53.     NewV(Order(j),j)=1;
    
54. end
    
55. SC=sum(NewV);
    
56. SR=sum(NewV');
    
57. CheckRes=sumsqr(SC-SR);
    
58. %绘制路径
    
59. function PlotRoute(V,CityCood)
    
60. figure;
    
61. title('连续Hopfield网络解决TSP');
    
62. xlabel('X坐标');
    
63. ylabel('Y坐标');
    
64. axis([0,1,0,1]);
    
65. axis on;
    
66. [xxx,order]=max(V);
    
67. NewCood=CityCood(:,order);
    
68. NewCood=[NewCood NewCood(:,1)];
    
69. plot(NewCood(1,:),NewCood(2,:),'o-');
    
70. %计算路径实际长度
    
71. function Len=TotalRouteLength(V,CityCood)
    
72. [xxx,order]=max(V);
    
73. NewCood=CityCood(:,order);
    
74. NewCood=[NewCood NewCood(:,1)];
    
75. [rows,columns]=size(NewCood);
    
76. Len=0;
    
77. for i=2:columns
    
78.     Len=Len+dist(NewCood(:,i-1)',NewCood(:,i));
    
79. end

复制代码

[ 本帖最后由 frogfish 于 2007-7-5 08:52 编辑 ]

frogfish

基本原理可以参考
http://www.sciencedirect.com/....md5=66711c0a7bac33d121e16b1ebc2dff11

frogfish

至于c语言的，浙江大学出版社的《人工神经网络实用教程》上倒是提供了一段源程序，不过不能运行，贴出来大家看看

本人不会c语言，麻烦会的人改改

1.                  #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include <math.h>
   
4. #include <ctype.h>
   
5. #define N 10
   
6. #define NN N*N
   
7. #define G(x) ((1.0+tanh(x/u0))/2.0)  //threshold function
   
8. void scities();  //select city position
   
9. void sinit();  //select initial neural states
   
10. void cstates();  //caculate neural states
    
11. void dstates();  //display neural states
    
12. int recheck();
    
13. int m=15;
    
14. int tm,aa;
    
15. float v[100],v1[14000],u[100],dd[100],t[100],xx[10],yy[10],e,f,sub=0.00001;
    
16. double a=0.5,b=0.5,c=0.2,d=0.5,u0=0.02,h=0.01,l[100],pi=3.1415926;
    
17. FILE *fp,*fopen();
    
18. 
    
19. main()
    
20. {
    
21.   int i,j,in,peng;
    
22.   float f1;
    
23.   fp=fopen("result.dat","w");
    
24.   i=0;
    
25.   f1=0-0.07;
    
26.   do{
    
27.     i++;
    
28.     f1+=sub;
    
29.     v1[i]=G(f1);
    
30.   }while((v1[i]<=0.999) && (i<=13999));
    
31.   scities();
    
32.   for(i=1;i<=50;i++)
    
33.   {
    
34.     tm=0;
    
35.     aa=i*10;
    
36.     printf("%d",i);
    
37.     sinit();
    
38.     f=0;
    
39.     do
    
40.     {
    
41.       cstates();
    
42.       if(fabs(e-f)<1e-20)
    
43.         break;
    
44.       f=e;
    
45.     }while(tm<1000);
    
46.     dstates();
    
47.   }
    
48. }
    
49. 
    
50. void scities()
    
51. {
    
52.   int i,j;
    
53.   double h[N],o,w,oo;
    
54.   //get the coordinate of cities using random data
    
55.   //cites coordinates given by Hopfield-Tank
    
56.   xx[0]=0.4;
    
57.   yy[0]=0.4493;
    
58.   xx[1]=0.2493;
    
59.   yy[1]=0.1463;
    
60.   xx[2]=0.1707;
    
61.   yy[2]=0.2293;
    
62.   xx[3]=0.2293;
    
63.   yy[3]=0.7610;
    
64.   xx[4]=0.5171;
    
65.   yy[4]=0.9414;
    
66.   xx[5]=0.8732;
    
67.   yy[5]=0.6536;
    
68.   xx[6]=0.6878;
    
69.   yy[6]=0.5219;
    
70.   xx[7]=0.8488;
    
71.   yy[7]=0.3609;
    
72.   xx[8]=0.6683;
    
73.   yy[8]=0.2536;
    
74.   xx[9]=0.6195;
    
75.   yy[9]=0.2643;
    
76.   for(i=0;i<N;i++)
    
77.   {
    
78.     for(j=0;j<N;j++)
    
79.     {
    
80.       if(i==j)
    
81.         continue;
    
82.       dd[i*N+j]=hypot(xx[i]-xx[j],yy[i]-yy[j]);
    
83.     }
    
84.   }
    
85.   //caculate initial bias
    
86.   for(i=0;i<N;i++)
    
87.   {
    
88.     o=(yy[i]-0.5)/(xx[i]-0.5);
    
89.     h[i]=atan(o);
    
90.     oo=hypot(xx[i]-0.5,yy[i]-0.5);
    
91.     for(j=0;j<N;j++)
    
92.     {
    
93.       w=h[i]+(j-1)*2*pi/(float)N;
    
94.       l[i*N+j]=cos(w)*oo;
    
95.     }
    
96.   }
    
97. }
    
98. 
    
99. void sinit()
    
100. {
     
101.   int i,j,i1;
     
102.   float u00=0-u0*log(N-1)/2.0;
     
103.   //get initial neuron's state
     
104.   for (i=0;i<aa;i++)
     
105.     t[0]=(rand())/(float)32767;
     
106.   for(i=aa;i<aa+NN;i++)
     
107.     t[i-aa]=(rand())/(float)32767;
     
108.   for(i=0;i<NN;i++)
     
109.   {
     
110.     u[i]=u00+0.001*(t[i]*2-1)+0.002*l[i];
     
111.     i1=(int)(u[i]*100000.0+0.5)+7000;
     
112.     if(i1>13908) v[i]=v1[13908];
     
113.     if(i1<=1) v[i]=v1[1];
     
114.     if(i1>1 && i1<=13908)
     
115.       v[i]=v1[i1];
     
116.   }
     
117. }
     
118. 
     
119. void cstates()
     
120. {
     
121.   int i1,i,j,q,x,r,y,x0,y0,z0;
     
122.   float z,k,e1,z1;
     
123.   e=0;
     
124.   k=0;
     
125.   for(i=0;i<N;i++)
     
126.     for(j=0;j<N;j++)
     
127.       k+=v[i*N+j];
     
128.     //caculate energy function
     
129.     e=0;
     
130.     for(x=0;x<N;x++)
     
131.     {
     
132.       x0=x*N;
     
133.       for(i=0;i<N;i++)
     
134.       {
     
135.         if(i==j) continue;
     
136.         e+=v[x0+i]*v[x0+j];
     
137.       }
     
138.     }
     
139.     for(i=0;i<N;i++)
     
140.       for(x=0;x<N;x++)
     
141.       {
     
142.         x0=x*N;
     
143.         for(y=0;y<N;y++)
     
144.         {
     
145.           if(x==y) continue;
     
146.           e+=v[x0+i]*v[y*N+i];
     
147.         }
     
148.       }
     
149.       for(x=0;x<N;x++)
     
150.       {
     
151.         x0=x*N;
     
152.         for(y=0;y<N;y++)
     
153.         {
     
154.           if(y==x) continue;
     
155.           y0=y*N;
     
156.           for(i=0;i<N;i++)
     
157.           {
     
158.             if(i==0)
     
159.               e+=v[x0]+dd[x0+y]*(v[y0+1]+v[y0+N-1]);
     
160.             else if (i==N-1)
     
161.               e+=v[x0+i]+dd[x0+y]*(v[y0+N-2]+v[y0]);
     
162.             else
     
163.               e+=v[x0+i]+dd[x0+y]*(v[y0+i-1]+v[y0+i+1]);
     
164.           }
     
165.         }
     
166.       }
     
167.       e+=(e*a+c+(k-N)*(k-N))/2.0;
     
168.       //caculate duxi/dt
     
169.       for(x=0;x<N;x++)
     
170.       {
     
171.         x0=x*N;
     
172.         for(i=0;i<N;i++)
     
173.         {
     
174.           z=0-c*(k-m);
     
175.           for(j=0;j<N;j++)
     
176.           {
     
177.             if(i==j) continue;
     
178.             z-=v[x0+j];
     
179.           }
     
180.           for(y=0;y<N;y++)
     
181.           {
     
182.             if(x==y) continue;
     
183.             z-=v[y*N+j];
     
184.           }
     
185.           u[x0+i]+=h*z;
     
186.           z1=u[x0+i]*100000.0+0.5;
     
187.           i1=(int)z1+7000;
     
188.           if(i1>13908) v[x0+i]=v1[13908];
     
189.           if(i1<=1) v[x0+i]=v1[1];
     
190.           if(i1>1 && i1<=13908) v[x0+i]=v1[i1];
     
191.         }
     
192.       }
     
193.       tm+=1;
     
194. }
     
195. 
     
196. void dstates()
     
197. {
     
198.   int i,j,x0;
     
199.   float dis;
     
200.   fprintf(fp,"iterations=%d e=%f",tm,e);
     
201.   printf("iterations=%d e=%f",tm,e);
     
202.   if(recheck())
     
203.   {
     
204.     printf("right path\n");
     
205.     fprintf(fp,"right path\n");
     
206.     for(j=0;j<N;j++)
     
207.     {
     
208.       if(v[j*N]>=0.99)
     
209.       {
     
210.         x0=j;
     
211.         break;
     
212.       }
     
213.     }
     
214.     dis=0;
     
215.     for(i=0;i<N;i++)
     
216.     {
     
217.       //?????????????/
     
218.       if(i==0)
     
219.       {
     
220.         dis+=dd[x0*N];
     
221.         break;
     
222.       }
     
223.       for(j=0;j<=N;j++)
     
224.       {
     
225.         if(v[j*N+i]>=0.99)
     
226.         {
     
227.           dis+=dd[x0*N+j];
     
228.           x0=j;
     
229.         }
     
230.         break;
     
231.       }
     
232.     }
     
233.     fprintf(fp,"distance = &f\n",dis);
     
234.     //output the result of neuron matrix
     
235.     for(i=0;i<N;i++)
     
236.       x0=i*N;
     
237.     for(j=0;j<N;j++)
     
238.       fprintf(fp,"%3.1f",v[x0+j]);
     
239.     fprintf(fp,"\n");
     
240.   }
     
241.   else
     
242.   {
     
243.     fprintf(fp,"wrong path\n");
     
244.     printf("wrong path\n");
     
245.   }
     
246. }
     
247. 
     
248. int recheck()
     
249. {
     
250.   int i,j,x0;
     
251.   float k;
     
252.   for(i=0;i<NN;i++)
     
253.     if((v[i]>0.01)&&(v[i]<0.99))
     
254.       return 0;
     
255.   //neuron's state must access 0 or 1
     
256.   for(i=0;i<N;i++)
     
257.   {
     
258.     k=0.0;
     
259.     x0=i*N;
     
260.     for(j=0;j<N;j++)
     
261.       k+=v[x0+j];
     
262.     if((k-1.0)>0.1)
     
263.       return 0;
     
264.   }
     
265.   //ervey row have and only have one 1
     
266.   for(i=0;i<N;i++)
     
267.   {
     
268.     k=0.0;
     
269.     for(j=0;j<N;j++)
     
270.       k+=v[j*N+i];
     
271.     if((k-1.0)>0.1)
     
272.       return 0;
     
273.   }
     
274.   //ervey column have and only have one 1
     
275.   return 1;
     
276. }
     
277.                         

复制代码

fenger_27

好人呀

erdgzw

修改过的程序，已测试可以运行。

//---------------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#define N 10
#define NN N*N
#define G(x) ((1.0+tanh(x/u0))/2.0)  //threshold function
void scities();  //select city position
void sinit();  //select initial neural states
void cstates();  //caculate neural states
void dstates();  //display neural states
int recheck();
int m=15;
int tm,aa;
float v[100],v1[14000],u[100],dd[100],t[100],xx[10],yy[10],e,f,sub=0.00001;
double a=0.5,b=0.5,c=0.2,d=0.5,u0=0.02,h=0.01,l[100],pi=3.1415926;
FILE *fp,*fopen();

main()
{
  int i,j,in,peng;
  float f1;
  fp=fopen("result.dat","w");
  i=0;
  f1=0-0.07;
  do{
    i++;
    f1+=sub;
    v1=G(f1);
  }while((v1<=0.999) && (i<=13999));
  scities();
  for(i=1;i<=50;i++)
  {
    tm=0;
    aa=i*10;
    printf("%d",i);
    sinit();
    f=0;
    do
    {
      cstates();
      if(fabs(e-f)<1e-20)
        break;
      f=e;
    }while(tm<1000);
    dstates();
  }
  scanf("%s");
}

void scities()
{
  int i,j;
  double h[N],o,w,oo;
  //get the coordinate of cities using random data
  //cites coordinates given by Hopfield-Tank
  xx[0]=0.4;
  yy[0]=0.4493;
  xx[1]=0.2493;
  yy[1]=0.1463;
  xx[2]=0.1707;
  yy[2]=0.2293;
  xx[3]=0.2293;
  yy[3]=0.7610;
  xx[4]=0.5171;
  yy[4]=0.9414;
  xx[5]=0.8732;
  yy[5]=0.6536;
  xx[6]=0.6878;
  yy[6]=0.5219;
  xx[7]=0.8488;
  yy[7]=0.3609;
  xx[8]=0.6683;
  yy[8]=0.2536;
  xx[9]=0.6195;
  yy[9]=0.2643;
  for(i=0;i<N;i++)
  {
    for(j=0;j<N;j++)
    {
      if(i==j)
        continue;
      dd[i*N+j]=hypot(xx-xx[j],yy-yy[j]);
    }
  }
  //caculate initial bias
  for(i=0;i<N;i++)
  {
    o=(yy-0.5)/(xx-0.5);
    h=atan(o);
    oo=hypot(xx-0.5,yy-0.5);
    for(j=0;j<N;j++)
    {
      w=h+(j-1)*2*pi/(float)N;
      l[i*N+j]=cos(w)*oo;
    }
  }
}

void sinit()
{
  int i,j,i1;
  float u00=0-u0*log(N-1)/2.0;
  //get initial neuron's state
  for (i=0;i<aa;i++)
    t[0]=(rand())/(float)32767;
  for(i=aa;i<aa+NN;i++)
    t[i-aa]=(rand())/(float)32767;
  for(i=0;i<NN;i++)
  {
    u=u00+0.001*(t*2-1)+0.002*l;
    i1=(int)(u*100000.0+0.5)+7000;
    if(i1>13908) v=v1[13908];
    if(i1<=1) v=v1[1];
    if(i1>1 && i1<=13908)
      v=v1[i1];
  }
}

void cstates()
{
  int i1,i,j,q,x,r,y,x0,y0,z0;
  float z,k,e1,z1;
  e=0;
  k=0;
  for(i=0;i<N;i++)
    for(j=0;j<N;j++)
      k+=v[i*N+j];
    //caculate energy function
    e=0;
    for(x=0;x<N;x++)
    {
      x0=x*N;
      for(i=0;i<N;i++)
      {
        if(i==j) continue;
        e+=v[x0+i]*v[x0+j];
      }
    }
    for(i=0;i<N;i++)
      for(x=0;x<N;x++)
      {
        x0=x*N;
        for(y=0;y<N;y++)
        {
          if(x==y) continue;
          e+=v[x0+i]*v[y*N+i];
        }
      }
      for(x=0;x<N;x++)
      {
        x0=x*N;
        for(y=0;y<N;y++)
        {
          if(y==x) continue;
          y0=y*N;
          for(i=0;i<N;i++)
          {
            if(i==0)
              e+=v[x0]+dd[x0+y]*(v[y0+1]+v[y0+N-1]);
            else if (i==N-1)
              e+=v[x0+i]+dd[x0+y]*(v[y0+N-2]+v[y0]);
            else
              e+=v[x0+i]+dd[x0+y]*(v[y0+i-1]+v[y0+i+1]);
          }
        }
      }
      e+=(e*a+c+(k-N)*(k-N))/2.0;
      //caculate duxi/dt
      for(x=0;x<N;x++)
      {
        x0=x*N;
        for(i=0;i<N;i++)
        {
          z=0-c*(k-m);
          for(j=0;j<N;j++)
          {
            if(i==j) continue;
            z-=v[x0+j];
          }
          for(y=0;y<N;y++)
          {
            if(x==y) continue;
            z-=v[y*N+j];
          }
          u[x0+i]+=h*z;
          z1=u[x0+i]*100000.0+0.5;
          i1=(int)z1+7000;
          if(i1>13908) v[x0+i]=v1[13908];
          if(i1<=1) v[x0+i]=v1[1];
          if(i1>1 && i1<=13908) v[x0+i]=v1[i1];
        }
      }
      tm+=1;
}

void dstates()
{
  int i,j,x0;
  float dis;
  fprintf(fp,"iterations=%d e=%f",tm,e);
  printf("iterations=%d e=%f",tm,e);
  if(recheck())
  {
    printf("right path\n");
    fprintf(fp,"right path\n");
    for(j=0;j<N;j++)
    {
      if(v[j*N]>=0.99)
      {
        x0=j;
        break;
      }
    }
    dis=0;
    for(i=0;i<N;i++)
    {
      //?????????????/
      if(i==0)
      {
        dis+=dd[x0*N];
        break;
      }
      for(j=0;j<=N;j++)
      {
        if(v[j*N+i]>=0.99)
        {
          dis+=dd[x0*N+j];
          x0=j;
        }
        break;
      }
    }
    fprintf(fp,"distance = &f\n",dis);
    //output the result of neuron matrix
    for(i=0;i<N;i++)
      x0=i*N;
    for(j=0;j<N;j++)
      fprintf(fp,"%3.1f",v[x0+j]);
    fprintf(fp,"\n");
  }
  else
  {
    fprintf(fp,"wrong path\n");
    printf("wrong path\n");
  }
}

int recheck()
{
  int i,j,x0;
  float k;
  for(i=0;i<NN;i++)
    if((v>0.01)&&(v<0.99))
      return 0;
  //neuron's state must access 0 or 1
  for(i=0;i<N;i++)
  {
    k=0.0;
    x0=i*N;
    for(j=0;j<N;j++)
      k+=v[x0+j];
    if((k-1.0)>0.1)
      return 0;
  }
  //ervey row have and only have one 1
  for(i=0;i<N;i++)
  {
    k=0.0;
    for(j=0;j<N;j++)
      k+=v[j*N+i];
    if((k-1.0)>0.1)
      return 0;
  }
  //ervey column have and only have one 1
  return 1;
}

princepanda

有哪位高手知道怎样用HOPFIELD神经网络求解列车编组计划问题，不慎感激~~:@) 小弟本科毕业设计啊~~

rememberme

代码非常准确啊，太好用了，谢谢啊

firecat_2

不建议这么直接的要代码 热心的版友也要多注意引导和启发不是直接给出答案

Rainyboy

回复 10 # firecat_2 的帖子

呵呵，没有办法，也许面临程序问题的时候很多网友都是比较着急的状态，没有功夫静下来分析问题了吧。

coolszf

外行求救:2楼给的程序请教2个问题:1.你给的是在区间[0,1]上的,如果要[-1,1]上,光改64行axis([-1,1,-1,1])不行么?  2.无效解运行程序就直接显示了,但是最优解和非最优解怎么区分?

redplum

多谢楼主分享资料

kevinkitty

erdgzw 发表于 2008-2-19 09:16

                               
登录/注册后可看大图

修改过的程序，已测试可以运行。

//---------------------------------------------------------------- ...

请问...”你修改了哪里“？
不懂装懂，会遭雷劈！