tsp-sa.cpp

这是一个人工智能方面的算法程序

//23020061152452 陈魁

#include <iostream.h>
#include <time.h>
#include <stdio.h>
#include <iomanip>
#include <fstream.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
 
#define MaxCityNum 50                 //设定最大城市数目为50 
int dist[MaxCityNum][MaxCityNum] ;    //邻接矩阵

typedef struct TSP
{    int road[MaxCityNum];               //road 数组来表示一个回路即是一个染色体
     double fit;                         //fit为这个路径的适应度
};


//-------------------------随机数发生器的类定义-----------------------------------------------
const unsigned long maxshort=65536L;
const unsigned long multiplier=1194211693L;
const unsigned long adder=12345L;

class RandomNumber
{  private:
      //当前种子
      unsigned long randSeed;
   public:
	  //构造函数，缺省值为0表示由系统自动产生种子
	   RandomNumber(unsigned long s=0);
	  //产生0～(n-1)之间的随机整数
	   unsigned short Random(unsigned long n);
	   //产生[0,1)之间的随机实数
	   double fRandom(void);
};
	    
//产生种子
RandomNumber::RandomNumber(unsigned long s)
{   if(s==0)
       randSeed=time(0);   //用系统时间产生种子
    else
	   randSeed=s;         //由用户提供种子
}

//产生0～(n-1)之间的随机整数

unsigned short RandomNumber::Random(unsigned long n)
{   randSeed=multiplier*randSeed+adder;
    return (unsigned short)((randSeed>>16)%n);
}

//产生[0,1)之间的随机实数

double RandomNumber::fRandom(void)
{  return Random(maxshort)/double(maxshort);
}
//-------------------------随机数发生器的类定义-----------------------------------------------

//----------------------------------------适应度计算-----------------------------------------------

double Calfit(int g[],int CityNum)      // g为一个回路
{   
	 double w=0;                        // 权值
     double fit;
	 int s,e;

    for(int i=1;i<=CityNum;i++)
	{   
		s=g[i]; e=g[i+1];  
		w = w + dist[s][e] ;                
	}

   // e = g[CityNum];
    fit = w;//+dist[e][1];
    return fit;
}
//-----------------------------------------适应度计算-----------------------------------------------

//----------------------------------------SSA 类定义------------------------------------------------
class SSA
{     
      friend  bool  Letstry(int MabkobLength,int t0,int CityNum);
      
      public :
	            int Mabkob_Length ;   //马尔可夫链长度 
	            double  t0 ;          //初始温度        
				double  tf;
				TSP  TempRoad;
                TSP  x;
				TSP  y;
               
		        TSP NewRoad(TSP OldRoad,int CityNum);  //生成新解	
};
//----------------------------------------SSA 类定义------------------------------------------------

//---------------------------------------新回路产生-----------------------------------------------

TSP SSA::NewRoad(TSP OldRoad,int CityNum)
{  
   TSP t;
   int l1,l1t,l2,len; 
   int temp;
   int change[MaxCityNum];
   static RandomNumber R;
  
   l1 = R.Random(CityNum)+1;
   l2 = R.Random(CityNum)+1;

   while(l1==l2) { l2 = R.Random(CityNum)+1; }
   
   if(l1>l2) { temp = l1; l1 = l2; l2 = temp; }  //保证l1,l2不相等
   l1t = l1;
   len = l2-l1+1;

	 for(int j=1;j<=CityNum;j++)                 //最后一个城市现不确定，可以等于第一个
	{
		t.road[j] = OldRoad.road[j];
	}
	
	for(int i=1;i<=len;i++)
	{   
         change[i] = OldRoad.road[l1t];   l1t++;
		 
	}
    
	for(int k=l1;k<=l2;k++)
	{    t.road[k] = change[len];
	     len--;       
	}
	t.road[CityNum+1] = t.road[1];

    t.fit = Calfit(t.road,CityNum);
 
  return t;
}

//---------------------------------------新回路产生--------------------------------------------------

//---------------------------------------友元函数----------------------------------------------------

bool Letstry(int MabkobLength,int t0,int CityNum)
{
   static RandomNumber R;
   SSA G;
   double r;

   G.t0 = t0;
   G.Mabkob_Length = MabkobLength;
   int bchange = 0;
   int s = 0;
   double m;

   for(int j=0;j<=CityNum;j++)    //初始化回路
         G.x.road[j] = j;
   G.x.road[CityNum+1] = G.x.road[1];

   G.x.fit = Calfit(G.x.road,CityNum);
   G.TempRoad = G.x;
   G.tf = G.t0;

   while(s!=2)
   {      
       bchange = 0;
	  
	   for(int i=1;i<=G.Mabkob_Length;i++)
	   {   
           G.x.fit = Calfit(G.x.road,CityNum);

           G.y = G.NewRoad(G.x,CityNum);

           if(G.y.fit<G.x.fit)   { G.x = G.y;}
		   else
		   {
                r = R.fRandom();
                m = exp(double(G.x.fit-G.y.fit)/(G.tf) );  
                if(r<m)  { G.x = G.y; }         
		   }//else
	   }//for
          
       for(int k=1;k<=CityNum;k++)
	   {   if(G.TempRoad.road[k]!=G.x.road[k])   { bchange = 1; break;}

	   }
         //cout<<"bchange= "<<bchange<<endl;
        if(bchange==1)  G.TempRoad = G.x; 
	
		G.tf = (G.tf)*0.9;

        if(bchange==0)    { s = s+1;  } 	
        else  s = 0;
	    //cout<<"s="<<s<<endl;
	//	cout<<"当前最优路径权值为 "<<G.x.fit<<endl;cout<<endl;
   } //while

   cout<<endl;
   cout<<"近似最优回路："<<endl;

   for(int k=1;k<=CityNum;k++)
        cout<<G.x.road[k]<<" " ;
   
   cout<<endl;
   cout<<"近似最优解为："<<G.x.fit<<endl;

   cout<<"停止温度为： "<<G.tf<<endl;

   return 1;

}
//---------------------------------------友元函数-------------------------------------------------

void main()
{  
	int City_Num;                    
    char fileName[10];
    ifstream datafile;
	int StatrTemp;
    int Length;
 

    cout<<"请输入城市的数目（29 or 42）：";
	cin>>fileName;
    City_Num=atoi(fileName);
		
	for(int k=0;k<City_Num+1;k++)                         //初始化邻接矩阵
         for(int t=0;t<City_Num+1;t++)
             dist[k][t]=0;
    datafile.open(strcat(fileName,".txt"));                  //打开文件   

    for(int i=1;i<City_Num+1;i++)                            //输入数据到矩阵
	{	for(int j=1;j<City_Num+1;j++)
		{	datafile>>dist[i][j];
			 
		}
	}
	cout<<endl;

    cout<<"请输入要初始的温度:";
	cin>>StatrTemp;
    cout<<endl;

	cout<<"请输入马尔可夫链长度:";
	cin>>Length;
    cout<<endl;
	
	Letstry(Length,StatrTemp,City_Num);

}
                                                                      //23020061152452 陈魁