算法及编程语言 - 声振论坛 - 振动,动力学,声学,信号处理,故障诊断

涟漪发表于 2005-11-25 10:57

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

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

christy 发表于 2005-11-25 20:30

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

frogfish 发表于 2007-7-5 08:46

连续Hopfield网络解决TSP（这个是matlab程序）%连续Hopfield网络解决TSP
function HopfieldTsp()
clc;
N=10; %城市数
A=1.5;%系数A
D=1; %系数D
u0=0.02; %神经元函数斜率
Step_t=0.1; %计算步长
MaxEpochs=20000;%迭代次数
%得到城市间距离矩阵
CityCood=rand(2,N); %城市坐标
DistanceMat=dist(CityCood',CityCood); %城市间距离矩阵
U=0.2*rand(N,N)-0.1;%神经元输入初始值在0附近产生
for Count=1:MaxEpochs
V=(1+tansig(U/u0))/2;
E=CacuEnergy(V,DistanceMat,A,D);%计算能量
delta_U=CacuDeltaU(V,DistanceMat,A,D,Step_t);%计算U的增量
U=U+delta_U*Step_t;
end
=RouteCheck(V);%检查V是否是有效路径
if(CheckRes<1)
FinalE=CacuEnergy(NewV,DistanceMat,A,D);
RouteLen=TotalRouteLength(NewV,CityCood);%计算路径的真实长度
PlotRoute(NewV,CityCood);%绘制路径
else
disp('路径无效!!');
end
%能量计算
function E=CacuEnergy(V,d,A,D)
=size(V);
t1=sumsqr(sum(V,2)-1);
t2=sumsqr(sum(V,1)-1);
PermitV=V(:,2:n);
PermitV=;
temp=d*PermitV;
t3=sum(sum(V.*temp));
E=0.5*(A*t1+A*t2+D+t3);
%计算U的增量
function d_U=CacuDeltaU(V,d,A,D,dt)
=size(V);
t1=repmat(sum(V,2)-1,1,n);
t2=repmat(sum(V,1)-1,n,1);
PermitV=V(:,2:n);
PermitV=;
t3=d*PermitV;
d_U=-dt*(A*t1+A*t2+D*t3);
%检查V是否是有效路径
function =RouteCheck(V)
=size(V);
NewV=zeros(rows,columns);
=max(V);
for j=1:columns
NewV(Order(j),j)=1;
end
SC=sum(NewV);
SR=sum(NewV');
CheckRes=sumsqr(SC-SR);
%绘制路径
function PlotRoute(V,CityCood)
figure;
title('连续Hopfield网络解决TSP');
xlabel('X坐标');
ylabel('Y坐标');
axis();
axis on;
=max(V);
NewCood=CityCood(:,order);
NewCood=;
plot(NewCood(1,:),NewCood(2,:),'o-');
%计算路径实际长度
function Len=TotalRouteLength(V,CityCood)
=max(V);
NewCood=CityCood(:,order);
NewCood=;
=size(NewCood);
Len=0;
for i=2:columns
Len=Len+dist(NewCood(:,i-1)',NewCood(:,i));
end

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

frogfish 发表于 2007-7-5 08:55

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

frogfish 发表于 2007-7-5 08:58

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

本人不会c语言，麻烦会的人改改             #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,v1,u,dd,t,xx,yy,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,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();
}
}

void scities()
{
int i,j;
double h,o,w,oo;
//get the coordinate of cities using random data
//cites coordinates given by Hopfield-Tank
xx=0.4;
yy=0.4493;
xx=0.2493;
yy=0.1463;
xx=0.1707;
yy=0.2293;
xx=0.2293;
yy=0.7610;
xx=0.5171;
yy=0.9414;
xx=0.8732;
yy=0.6536;
xx=0.6878;
yy=0.5219;
xx=0.8488;
yy=0.3609;
xx=0.6683;
yy=0.2536;
xx=0.6195;
yy=0.2643;
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
{
   if(i==j)
   continue;
   dd=hypot(xx-xx,yy-yy);
}
}
//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=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=(rand())/(float)32767;
for(i=aa;i<aa+NN;i++)
t=(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;
if(i1<=1) v=v1;
if(i1>1 && i1<=13908)
   v=v1;
}
}

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;
//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*v;
   }
}
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*v;
   }
   }
   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+dd*(v+v);
         else if (i==N-1)
         e+=v+dd*(v+v);
         else
         e+=v+dd*(v+v);
      }
   }
   }
   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;
      }
      for(y=0;y<N;y++)
      {
         if(x==y) continue;
         z-=v;
      }
      u+=h*z;
      z1=u*100000.0+0.5;
      i1=(int)z1+7000;
      if(i1>13908) v=v1;
      if(i1<=1) v=v1;
      if(i1>1 && i1<=13908) v=v1;
   }
   }
   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>=0.99)
   {
   x0=j;
   break;
   }
}
dis=0;
for(i=0;i<N;i++)
{
   //?????????????/
   if(i==0)
   {
   dis+=dd;
   break;
   }
   for(j=0;j<=N;j++)
   {
   if(v>=0.99)
   {
      dis+=dd;
      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);
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;
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;
if((k-1.0)>0.1)
   return 0;
}
//ervey column have and only have one 1
return 1;
}

fenger_27 发表于 2008-1-11 18:12

好人呀

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

回复 5楼的帖子

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

//---------------------------------------------------------------------------
#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,v1,u,dd,t,xx,yy,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,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,o,w,oo;
//get the coordinate of cities using random data
//cites coordinates given by Hopfield-Tank
xx=0.4;
yy=0.4493;
xx=0.2493;
yy=0.1463;
xx=0.1707;
yy=0.2293;
xx=0.2293;
yy=0.7610;
xx=0.5171;
yy=0.9414;
xx=0.8732;
yy=0.6536;
xx=0.6878;
yy=0.5219;
xx=0.8488;
yy=0.3609;
xx=0.6683;
yy=0.2536;
xx=0.6195;
yy=0.2643;
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
{
   if(i==j)
   continue;
   dd=hypot(xx-xx,yy-yy);
}
}
//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=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=(rand())/(float)32767;
for(i=aa;i<aa+NN;i++)
t=(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;
if(i1<=1) v=v1;
if(i1>1 && i1<=13908)
   v=v1;
}
}

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;
//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*v;
   }
}
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*v;
   }
   }
   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+dd*(v+v);
         else if (i==N-1)
         e+=v+dd*(v+v);
         else
         e+=v+dd*(v+v);
      }
   }
   }
   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;
      }
      for(y=0;y<N;y++)
      {
         if(x==y) continue;
         z-=v;
      }
      u+=h*z;
      z1=u*100000.0+0.5;
      i1=(int)z1+7000;
      if(i1>13908) v=v1;
      if(i1<=1) v=v1;
      if(i1>1 && i1<=13908) v=v1;
   }
   }
   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>=0.99)
   {
   x0=j;
   break;
   }
}
dis=0;
for(i=0;i<N;i++)
{
   //?????????????/
   if(i==0)
   {
   dis+=dd;
   break;
   }
   for(j=0;j<=N;j++)
   {
   if(v>=0.99)
   {
      dis+=dd;
      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);
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;
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;
if((k-1.0)>0.1)
   return 0;
}
//ervey column have and only have one 1
return 1;
}

princepanda 发表于 2008-4-9 15:10

新人求解

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

rememberme 发表于 2010-11-4 22:33

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

firecat_2 发表于 2010-11-10 21:13

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

Rainyboy 发表于 2010-11-10 21:47

本帖最后由 Rainyboy 于 2010-11-10 21:47 编辑

回复 10 # firecat_2 的帖子

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

coolszf 发表于 2011-6-2 21:37

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

redplum 发表于 2011-6-15 10:23

多谢楼主分享资料

kevinkitty 发表于 2013-2-16 15:43

erdgzw 发表于 2008-2-19 09:16 static/image/common/back.gif
修改过的程序，已测试可以运行。

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

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

页: [1]

声振论坛's Archiver

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

回复 5楼 的帖子

新人求解

回复 5楼的帖子