/*********************************************************************/
/*          Solving Tsp using Genetic Algorithms and C++             */
/*********************************************************************/

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <fstream>
#include <iostream>
#include <time.h>
using namespace std;

/* Change any of these parameters to match your need.*/

#define PopSize 50   

#define MaxGens 1000    // Max No. of generation.
#define NumVars 10       // No. of problem variables.
#define PXCross 0.8      // probality of crossover.
#define PMutation 0.15   // probality of mutation.c


int city[NumVars];
int begin_city=0;        //更改出發(fā)城市

double  r[NumVars][NumVars]={
		0, 1, 4, 6, 8, 1, 3, 7, 2, 9,
		1, 0, 7, 5, 3, 8, 3, 4, 2, 4,
		4, 7, 0, 3, 8, 3, 7, 9, 1, 2,
		6, 5, 3, 0, 3, 1, 5, 2, 9, 1,
		8, 3, 8, 3, 0, 2, 3, 1, 4, 6,
		1, 8, 3, 1, 2, 0, 3, 3, 9, 5,
		3, 3, 7, 5, 3, 3, 0, 7, 5, 9,
		7, 4, 9, 2, 1, 3, 7, 0, 1, 3,
		2, 2, 1, 9, 4, 9, 5, 1, 0, 1,
		9, 4, 2, 1, 6, 5, 9, 3, 1, 0
		} ;




int generation;          // Current generation no.
int CurBest;             // best individual.
FILE *Tsp;               // An output file.

struct GenoType
{
	int gene[NumVars];     // A string of variables.
	double fitness;  
	double rfitness;
	double cfitness;
};

GenoType population[PopSize+1];      // population.
GenoType newpopulation[PopSize+1];    /* new population replaces the old generation. */

/* Declaration of procedure used by this genetic algorithms */
            //void SetGbase();
void initialize();
void evaluate();
void keep_the_best();
void elitist();
void select();
void crossover();
void mutate();
void report();
int IntGenerate();
void swap(int *,int *);



/*******************************************************/
/*                Exchange two numbers.                */
/*******************************************************/
void swap(int *a,int *b)            
{
	int temp;
	temp=*a;
	*a=*b;
	*b=temp;
}


/*********************************************/
/*   generate a number in a specific range,  */ 
/* such as 0 to 10 (0 included, 10 excluded.)*/
/*********************************************/
int IntGenerate()                       
{
	int RANGE_MIN = 0;
	int RANGE_MAX = NumVars;
	int rand10 = (((double) rand()/(double) RAND_MAX) * RANGE_MAX + RANGE_MIN);
	return rand10;    
}


/*******************************************************/
/*            The initialization function              */
/*******************************************************/
void initialize()                               
{ 
	int matrix[NumVars];
	int x1,x2;     
	  
	for(int i=1; i<NumVars; i++)   
		matrix[i]=i;
	for(int j=0;j<PopSize;j++)    
	{
		population[j].gene[0]=begin_city;   //gene[0]表示出發(fā)城市，i表示城市次序
		
		for(int i=0;i<NumVars;i++)  //NumVars次交換足以產(chǎn)生各種結(jié)果了
		{
			x1=0; x2=0;
			while(x1==0)
				x1=IntGenerate();
			while(x2==0)
				x2=IntGenerate();
			swap(&matrix[x1],&matrix[x2]);
		}
		for(int i=1;i<NumVars;i++)
			population[j].gene[i]=matrix[i];
	}
}

/**************************************************************/
/* Evaluation function:This takes a user defined function.    */
/* It's the fitness function you to know.                     */
/**************************************************************/
void evaluate()                                
{
	int current_city=begin_city;
	int next_city;

	for(int mem=0;mem<PopSize;mem++)
	{
		population[mem].fitness=0;
	    for(int i=1;i<NumVars;i++)    
		{
			next_city=population[mem].gene[i];
			population[mem].fitness += r[current_city][next_city]; 
			current_city=next_city;
		}
		population[mem].fitness += r[current_city][begin_city];
	}
}


/******************************************************************/
/*This function keeps track of the best member of the population. */
/******************************************************************/
void keep_the_best() // Add population[PopSize]=population[0] before this function, it will be OK!
{
	int mem,i;
	CurBest=0;  // Store the index of the best individual.
	
	for(mem=1;mem<PopSize;mem++)	
		if(population[mem].fitness<population[CurBest].fitness) // The mininum one is better.
			CurBest=mem;
	
	// Once the best individual is found, copy its genes to store.
	for(i=0;i<NumVars;i++)
		population[PopSize].gene[i]=population[CurBest].gene[i];
	population[PopSize].fitness=population[CurBest].fitness;
}



/***************************************************************************/
/*Elitist function: The best member of the previous generation is stored   */ 
/*as the last in the array. If the best member of the current generation   */ 
/*is worse then the best member of the previous generation, the latter     */ 
/* one wouldreplace the worst member of the current population.            */
/***************************************************************************/
void elitist()       
{
	int i;
	double best,worst;
	int best_mem,worst_mem;

	best=population[0].fitness;
	worst=population[0].fitness;
	
	for(i=0;i<PopSize-1;++i)
	{
		if(population[i].fitness<population[i+1].fitness)
		{
			if(population[i].fitness<=best)
			{
				best=population[i].fitness;
				best_mem=i;
			}
			if(population[i+1].fitness>=worst)
			{
				worst=population[i+1].fitness;
				worst_mem=i+1;
			}
		}
		else
		{
			if(population[i].fitness>=worst)
			{
				worst=population[i].fitness;
				worst_mem=i;
			}
			if(population[i+1].fitness<=best)
			{
				best=population[i+1].fitness;
				best_mem=i+1;
			}
		}
}

/* if best individual from the new population is better than */
/* the best individual from the previous population, then    */
/* copy the best from the new population; else replace the   */
/* worst individual from the current population with the     */
/* best one from the previous generation                     */
	if(best<=population[PopSize].fitness)
	{
		for(i=0;i<NumVars;i++)
			population[PopSize].gene[i]=population[best_mem].gene[i];
		population[PopSize].fitness=population[best_mem].fitness;    
	}
	else
	{
		for(i=0;i<NumVars;i++)
			population[worst_mem].gene[i]=population[PopSize].gene[i];
		population[worst_mem].fitness=population[PopSize].fitness;
	}
}


void select()      // 輪盤選擇的方法我覺得不好。但想不出好的方法了。最好有好方法的改下。
{
	int mem,i,j;     //‘‘roulette wheel’’ algorithm 輪盤賭算法（英文）
	double sum=0.0;
	double p;
	double x[PopSize];
  
	for(mem=0;mem<PopSize;mem++)
		sum+=population[mem].fitness;

	for(mem=0;mem<PopSize;mem++)    // Here the differenct method.
		x[mem]=sum-population[mem].fitness;

	sum=0.0;

	for(mem=0;mem<PopSize;mem++)
		sum+=x[mem];

	/* Calculate relative fitness       */
	for(mem=0;mem<PopSize;mem++)
		population[mem].rfitness=x[mem]/sum;

	/* Calculate cumlative fitness     */
	population[0].cfitness=population[0].rfitness;
	for(mem=1;mem<PopSize;mem++)                         
	{
		population[mem].cfitness=population[mem-1].cfitness+population[mem].rfitness;
	}
  
	/*finally select survivors using cumulative fitness.*/
	for(i=0;i<PopSize;i++)
	{
		p=rand()%1000/1000.0;
		if(p<population[0].cfitness)
			newpopulation[i]=population[0];
		else
		{
			for(j=0;j<PopSize;j++)
				if(p>=population[j].cfitness && p<population[j+1].cfitness)
					newpopulation[i]=population[j+1];
		}
	}
	/* Once a new population is created, copy it back. */
	for(i=0;i<PopSize;i++)
		population[i]=newpopulation[i];
}


/***************************************************************/
/* Crossover selection: selects two parents that take part in  */
/* the crossover. Implements a single point crossover          */
/***************************************************************/
void crossover()
{
  int i,j;
  int min,max,flag;
  double x;
  
  for(i=0;i<PopSize;i++)
    {   
		x=rand()%1000/1000.0;
		if(x<PXCross)
		{
			min=0;
			max=0;
			while(min==0)
				min=IntGenerate();
			while(max==0)
				max=IntGenerate();
			if(max<min)
			{
				int temp;
				temp=max;
				max=min;
				min=temp;
			}
			flag=max;
			for(j=min;j<=(max+min)/2;j++)
			{
				swap(&population[i].gene[j],&population[i].gene[flag]);
				flag=flag-1;
			}
		}
    }
}


/**************************************************************/
/* Mutation: Random uniform mutation. A variable selected for */
/* mutation is replaced by a random value between lower and   */
/* upper bounds of this variable                              */
/**************************************************************/
void mutate()
{
	int i;
	double x;
	int x1,x2;

	for(i=0;i<PopSize;i++)
	{    
		x=(int)rand()%1000/1000.0;
		if(x<PMutation)
		{
			x1=0;
			x2=0;
			while(x1==0)
				x1=IntGenerate();
			while(x2==0)
				x2=IntGenerate();
		
			//cout<<population[i].gene[x1]<<','<<population[i].gene[x2]<<endl;
			swap(&population[i].gene[x1],&population[i].gene[x2]);
		}
	}
}


/***************************************************************/
/* Report function: Reports progress of the simulation. Data   */
/* dumped into the  output file are separated by commas        */
/***************************************************************/
void report()
{
	int i;
	double best_val;    //Best population fitness.
	double avg;         //Avg population fitness.
	double stddev;      //std. deviation of population fitness.
	double sum_square;  //sum of square for std. calc.
	double square_sum;  //square of sum for std. calc.
	double sum;         //total population fitness.
 
	sum=0.0;
	sum_square=0.0;
  
	for(i=0;i<PopSize;i++)
	{
		sum+=population[i].fitness;
		sum_square+=population[i].fitness*population[i].fitness;
	}
	avg=sum*1.0/(1.0*PopSize);
	square_sum=avg*avg*PopSize;
	stddev=sqrt((sum_square-square_sum)/(PopSize-1));
	best_val=population[PopSize].fitness;

	fprintf(Tsp, "\n%5d,      %6.3f, %6.3f, %6.3f \n\n", generation, 
                                      best_val, avg, stddev);
}


/**************************************************************/
/* Main function: Each generation involves selecting the best */
/* members, performing crossover & mutation and then          */
/* evaluating the resulting population, until the terminating */
/* condition is satisfied                                     */
/**************************************************************/

int main()
{
	int i; 

	printf("                  ***************************************\n");
	printf("                  ★       歡迎使用本遺傳算法程序      ★\n");
	printf("                  ***************************************\n\n");
	printf(" 本程序用于求 TSP 問題, 有10個城市\(zhòng)n BEGIN:\n\n");
	printf("     經(jīng)演化得出結(jié)果：\n");

	if ((Tsp = fopen("Tsp.txt","w"))==NULL)
    {
		exit(1);
    }
	
	generation = 0;
	fprintf(Tsp, "\n generation  best  average  standard \n");
	fprintf(Tsp, " number      value fitness  deviation \n");
  
	srand( (unsigned)time( NULL ) ); //加上這個能使每次運(yùn)行的隨機(jī)數(shù)不一樣

	initialize();
	evaluate();
	keep_the_best();

	while(generation<MaxGens)
	{
		generation++;
		select();
		crossover();
		mutate();
		report();
		evaluate();   //竟然沒有這個？怎么復(fù)制的？害的我們大家看半天
		elitist();
	}

	fprintf(Tsp,"\n\n Simulation completed\n");
	fprintf(Tsp,"\n Best member: \n");

	fprintf (Tsp,"\n var(0) = %3d",begin_city); 
	for (i = 1; i < NumVars; i++)
	{
			fprintf (Tsp,"\n var(%d) = %3d",i,population[PopSize].gene[i]);  
	}
	fprintf(Tsp,"\n\n Best fitness = %7.3f",population[PopSize].fitness);
	fclose(Tsp);

	printf ("\n		var(0) = %3d",begin_city);
	for (i = 1; i < NumVars; i++)
	{
		printf ("\n		var(%d) = %3d",i,population[PopSize].gene[i]);  
	}
	printf("\n\n		Best fitness: f(x(best)) = %.7f",
		population[PopSize].fitness);
	printf("\n\n 本遺傳算法程序執(zhí)行成功\n 請打開程序文件夾中的Tsp.txt觀察詳情\n END!\n\n");
	printf("Success\n");
	return 0;
}