anneal.cpp

求解tsp问题的模拟退火源码

/********************************************/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
/********************************************/
#include "Matrix.h"
/********************************************/
#define AIM  10
#define MarkovLength  100
#define Diminish_T_num  20
#define Temperature    100
#define DiminishRate   0.9


int City_num=0;           //由文件中获取

Matrix <double> distData;

double best=1000000;
double cur_best=1000000;

int  *bestPath;            //当前最好路径
int  *curPath;             //当前路径

FILE *galog;               /* an output file */
FILE *infile;


/*********************************************/
void initialize(void);
double evaluatedistance(int *);
void generateNext(int, int);
void reverse(int *,int, int);
double evaluatedistinct(int,int);
void SetNewState(int *,int *);
void report();


void sim_anneal(void);            //模拟主体 

/*********************************************/

/*************************************************/
//     初始化函数，读取数据文件,构造距离数组     //
//          并以原始数据为初始路径               //
/*************************************************/

void initialize()
{
     
  fscanf(infile, "%d",&City_num);

  
  distData.setDimension(City_num,City_num);

  int i;
  for(i=0;i<City_num;i++)
	{
	     distData[i][i]=0;
	}
   int m=1;
	for(i=0;i<City_num;i++)
	{
	  for(int j=m;j<City_num;j++)
	  {
          double dist;
		  fscanf(infile,"%lf",&dist);

		  distData[i][j]=dist;

		  distData[j][i]=dist;
	  }
	  m++;
	}

	for(i=0;i<City_num;i++)
	{
	     distData[i][i]=0;
	}

    ///////////////////////////////////////
	bestPath=new int[City_num];
	curPath=new int[City_num];
    
	for(i=0;i<City_num;i++)
	{
	  curPath[i]=i;
	  bestPath[i]=i;
	}

	fclose(infile);
}
/***********************************************/
//           计算路径的消耗                    //
/***********************************************/
double evaluatedistance(int *path)
{
  double cost=0;
  for(int i=0;i<City_num-1;i++)
  {
     cost+=distData[path[i]][path[i+1]];
  }
  cost+=distData[path[City_num-1]][path[0]];
  return cost;
}

/********************************************************/
//                    计算差值                          //
/********************************************************/
double evaluatedistinct(int k,int m)
{	
	int num=City_num-1;

	double distinct;	
	
	if((k==0&&m==0)||(k==num&&m==num))
		return 0;
    if((k==0&&m==num)||(k==num&&m==0))
		return 0;

	if(k<m)
	{
		if(k==0)
		{   if(m<num)

		distinct=(distData[curPath[num]][curPath[m]]-distData[curPath[num]][curPath[k]])+distData[curPath[k]][curPath[m+1]]-distData[curPath[m]][curPath[m+1]];
			else
                distinct=0;
		}
		else
		{
		   if(m<num)
    distinct=(distData[curPath[k-1]][curPath[m]]-distData[curPath[k-1]][curPath[k]])+distData[curPath[k]][curPath[m+1]]-distData[curPath[m]][curPath[m+1]];
		   else
    distinct=(distData[curPath[k-1]][curPath[m]]-distData[curPath[k-1]][curPath[k]])+distData[curPath[k]][curPath[0]]-distData[curPath[m]][curPath[0]];
		}
	}
	else if(k>m)
	{  
		if(m==0) 
		{
		  if(k<num)
	        distinct=distData[curPath[k]][curPath[0]]-distData[curPath[num]][curPath[0]]+distData[curPath[k-1]][curPath[num]]-distData[curPath[k-1]][curPath[k]];
		  else
			distinct=0;
		}
		else
		{
			if(k<num)
              distinct=distData[curPath[k]][curPath[m]]-distData[curPath[num]][curPath[0]]+distData[curPath[0]][curPath[m+1]]-distData[curPath[m]][curPath[m+1]]+distData[curPath[k-1]][curPath[num]]-distData[curPath[k-1]][curPath[k]]; 			
			else
              distinct=distData[curPath[num]][curPath[m]]-distData[curPath[num]][curPath[0]]+distData[curPath[0]][curPath[m+1]]-distData[curPath[m]][curPath[m+1]]; 
		}
	}
   
	return distinct;
}


/*********************************************************/
//               产生下一代                              //
//   在0到City number之间随机产生两个整数k,m             //
//   if (k<m)   将k和m之间的路径逆序                     //
//   if (k>m)   分别将0和m，k和city number之间路径逆序   //
/*********************************************************/
void generateNext(int k,int m)
{

   if (k<m)
	   reverse(curPath,k,m);
   else if(k>m)
   {   
	reverse(curPath,0,m);
    reverse(curPath,k,City_num-1);
   }

}

void reverse(int *path,int k,int m)
{
  int temp;
  
  if(k<m)
   for(;k<m;k++,m--)
	 {
	    temp=path[m];
		path[m]=path[k];
		path[k]=temp;
	 }

  
  return;
}
/**********************************************/
void SetNewState(int*p1,int *p2)
{
   for(int i=0;i<City_num;i++)
   {
      p1[i]=p2[i];
   }
}
/**********************************************/
//       退火算法主流程                       //
/**********************************************/
void sim_anneal()
{
   double temperature=Temperature;
   int aim=0;
   int diminish_t_num = 0;

   double delta;

   initialize();
  
   cur_best=evaluatedistance(curPath);
   
   best=cur_best;
   int turn=0;
   
   while(temperature>0.5)
   {
    cur_best=best;

    SetNewState(curPath,bestPath);
     
	for(int i=0;i<MarkovLength;i++)
	{

	 srand((unsigned)time(NULL)); 
     int k=(int)(((double)rand()/(double)RAND_MAX)*City_num);
     int m=(int)(((double)rand()/(double)RAND_MAX)*City_num); 
	 
	 delta=evaluatedistinct(k,m);

	 if(delta<0)
	 {
	   generateNext(k,m);
       cur_best=evaluatedistance(curPath);
       diminish_t_num=0 ;   
       aim =0;
	 }
     else if(exp(0-delta/temperature)>((double)rand()/(double)RAND_MAX))
	 {
	    diminish_t_num++;
        generateNext(k,m);
        cur_best=evaluatedistance(curPath);
	 }
	 else
	 {
	    diminish_t_num++ ;
	 }


	 if(cur_best<best)
	 {
       best=cur_best;
       SetNewState(bestPath,curPath);
     }



	 if(diminish_t_num>Diminish_T_num)
	 {
        aim++;
        break;
	 }

     if(aim==AIM)
		return;
	}
	 
	 temperature *= DiminishRate ;//deminish the temperature

   }
   
}

/**********************************************************/
void report()
{
 fprintf(galog,"%6lf\n",best);
 
 for(int i=0;i<City_num;i++)
  {
     fprintf(galog,"%d--",bestPath[i]+1);  
  }
}


void main()
{
  if ((galog=fopen("log.txt","w"))==NULL)
		{
      exit(1);
      }
  if ((infile=fopen("inputData.txt","r"))==NULL)
		{
      fprintf(galog,"\nCannot open input file!\n");
      exit(1);
      }
	
  
 
  sim_anneal();
 
  report();

  fclose(galog);

if(bestPath)
delete []bestPath;
if(curPath)
delete []curPath;

   return;
}