tspg.c

求解TSP问题的算法

#define POP_SIZE 50
#define LOOPS 1000
#define HERO 100 
#define N 100 
#define C 10
#define R 10
#define MUT_RATE  0.2
#define TOURNAMENT_SIZE 5
#include <stdlib.h>
#include <stdio.h>
#include <tgmath.h>
#include <sys/times.h>
void init();
int tournament();
void selection();
void crossover();
void mutation();
void decode();
double fv(int);
double distance(int a,int b);
int binarysearch(int low,int high,double randomNo);
int random_int(int);
float random_float();
double random_double(double max);
int chromosome[POP_SIZE][N];
int dec_gene[POP_SIZE][N];
double fitness[POP_SIZE];
double hero=0;
double cumulate[POP_SIZE];
int trial;
int final[N];
int test[N];
double best;
double aver;
main(int argc, char **argv)
{
	int i;
	int t=10;
	best=1000;
	aver=0;
	printf("begin..\n");
	printf("wait..\n");
	while(t--)
	{
	hero=1000;
	int who;
	trial=0;
	init();
	decode();
	for( who = 0; who < POP_SIZE; who++ )
		fitness[who] = fv(who);
	
	for(trial = 0;trial < LOOPS;trial++ )
	{
		if(hero<=HERO)
		{
			printf( "Goal reached: %f\n", hero ); break;
		}
		selection();
		crossover();
		mutation();
		decode();
		for( who = 0; who < POP_SIZE; who++ )
		fitness[who] = fv(who);
	}
	printf("\nLOOPS=%d\n",trial);
	printf( "LENGTH = %f\n",hero );
	for(i=0;i<N;i++)
		test[i]=0;
	for(i=0;i<N;i++){
		printf("%d- ",final[i]);
		if(test[final[i]]==1)printf("********error********");
		else test[final[i]]=1;
	}
	if(hero<best)best=hero;
	aver+=hero;

	}
        struct tms *buf=(struct tms *)malloc(sizeof(struct tms));
	times(buf);
	printf("\nuser_time=%d,sys_time%d,Processor_Time=%d\n",buf->tms_utime,buf->tms_stime,buf->tms_utime+buf->tms_stime);
	free(buf);
	printf("best=%e,aver=%e",best,aver/10);
	getchar();
				
}
double fv(int who)
{
	int i;
	double the_fitness = 0;
	for(i=0;i<N-1;i++){
		the_fitness+=distance(dec_gene[who][i],dec_gene[who][i+1]);	
	}
	the_fitness+=distance(dec_gene[who][0],dec_gene[who][N-1]);

	if( the_fitness < hero) {
		hero = the_fitness;
		for(i=0;i<N;i++)
			final[i]=dec_gene[who][i];
//		printf( "New hero %f ... trial=%d\n",hero,trial );
		
	}
	return( the_fitness );
}
double distance(int a,int b){
	int temp1=a/C-b/C;
	int temp2=a%C-b%C;
	return sqrt((double)(temp1*temp1+temp2*temp2));
}
/*
void decode(){
	int i,j,k;
	int temp;
	int counter;
	char decodebit[(N+7)/8];
	int flag;
	for(i=0;i<POP_SIZE;i++){

		for(j=0;j<(N+7)/8;j++)
			decodebit[j]=0;

		for(counter=0;counter<N;counter++){
			temp=chromosome[i][counter];
			flag=0;
			for(j=0;j<(N+7)/8;j++){
				for(k=0;k<8;k++){
					if((decodebit[j]&(128>>k))==0)temp--;
					if(temp==0){
						decodebit[j]|=(128>>k);
						dec_gene[i][counter]=j*8+k;
						flag=1;
						break;
					}
				}
				if(flag==1)break;
			}
		}
	}
}
*/
void decode(){
	int i,j,k;
	int counter;
	int temp;
	int decodebit[N];
	for(i=0;i<POP_SIZE;i++){
		for(j=0;j<N;j++)
			decodebit[j]=0;
		for(counter=0;counter<N;counter++){
			temp=chromosome[i][counter];
			for(j=0;j<N;j++){
				if(decodebit[j]==0)temp--;
				if(temp==0){
					decodebit[j]=1;
					dec_gene[i][counter]=j;
					break;
				}
				
			}
		}

	}

}
void init()
{
	int i;
	int j;
	srand( (unsigned)time( NULL ));
	for( i = 0; i < POP_SIZE; i++ )
		for(j = 0; j < N ; j++){
			chromosome[i][j]=random_int(N-j)+1;
		}

}
void selection()
{
	int i,j;
	double randomNo;
	int no;
	int temp[POP_SIZE][N];

	for(i=0;i<POP_SIZE;i++)
		for(j=0;j<N;j++)
			temp[i][j]=chromosome[i][j];
	for(i=0;i<POP_SIZE;i++){
		no=tournament();
		for(j=0;j<N;j++)
			chromosome[i][j]=temp[no][j];
	}

}

int tournament()
{
    int i,winner;
	double winfit;
    for( i = 0; i < TOURNAMENT_SIZE; i++ ){
        int j = random_int(POP_SIZE);
		if( i==0 || fitness[j] < winfit ){ 
            winfit = fitness[j];
			winner = j;
		}
    }
	return winner;
}

int binarysearch(int low,int high,double randomNo){

	int mid=(low+high)/2;
	if(cumulate[mid]>randomNo) {
		if(mid==0)return 0;
		else if(cumulate[mid-1]<randomNo) return mid;
		else return binarysearch(low,mid,randomNo);		
	}
	else	{
		if(cumulate[mid+1]>randomNo) return mid+1;
		else return binarysearch(mid,high,randomNo);
	}
}
/*1-point Crossover*/
void crossover()
{
	int tempdata;
	int i;
	int j;
	int crosspoint=random_int(N);
	 /*cross over*/	 
	for(i=0;i<POP_SIZE-1;i+=2)
	{		
		crosspoint=random_int(N);
		for(j=crosspoint;j<N;j++){
			tempdata=chromosome[i][j];
			chromosome[i][j]=chromosome[i+1][j];
			chromosome[i+1][j]=tempdata;
		}
	}
	/*crossover end*/
}
void mutation()
{
	int i;
	int mutate;
	for(i=0;i<POP_SIZE;i++){
		if(MUT_RATE<random_float())continue;
		mutate=random_int(N);
		chromosome[i][mutate]=random_int(N-mutate)+1;
	}		
}
int random_int(int max)
{
	return rand()%max;
}
float random_float()
{
	return((rand()%10000)/(double)10000);
}
double random_double(double max)
{
	return random_float()*max;
}