//2004100037 04級計算機科學與技術　蘇志昌
//  ==================================================================*/
#include<iostream.h> //cout
#include<stdio.h>    //exit(1), fopen(), fread(), fwrite()
#include<stdlib.h>   //rand(),abs()
#include<time.h>     //time_t,time(), difftime()
#include<math.h>     //srand(),difftime(),pow(),sina()
#include<conio.h>    //_getch() which is for debuging
#include<iomanip.h>  //setprecision() which is for debuging

const int xlen=21;
const int ylen=21;
const int  chromlen=xlen+ylen;    //21 bits for x and 21 bits for y
const int maxgeneration=100;
int generation;
const int popsize=150;
const int competepopsize=popsize;
const int elitepopsize=10;//only 90% of the population will be replaced
double result[maxgeneration+1];
double HAMINGdistance[maxgeneration];
double  crossprob=0.8;    
double mutatprob=0.05;     
struct individual
{
	unsigned char chrom[chromlen];	
	double x;
	double y;
	double fitness;
};
individual pop[popsize];
individual competepop[competepopsize];
individual bestind;
int beselected[popsize];//save the selectee's indexes
double AHD[maxgeneration+1];

void gen_pop();
void evaluatepop();
void selection();
void crossover();
void mutation();
void decodechrom();
void calfitnessvalue();
void calhamingdistance();
void update();

FILE *file1;   //for text file of result
FILE *file2;   //for binary file of result
FILE *fileAHD;//the binary file of average haming distance

void main()
{
	file1 = fopen("result.txt", "a+");
    if (file1 == NULL)
	{
        cerr << "Result's text file opened fail!" << endl;
		exit(1);
	}
	file2 = fopen("SGAbiresult", "w");
    if (file2 == NULL)
	{
        cerr << "Result's binary file opened fail!" << endl;
		exit(1);
	}
	fileAHD = fopen("AHD", "wb");
    if (fileAHD == NULL)
	{
        cerr << "AHD's binary file opened fail!" << endl;
		exit(1);
	}
   	time_t begin,end;
	time(&begin);
	srand(begin);	
	result[0]=0;
	AHD[0]=chromlen;
	generation=0;
	gen_ini_pop();
	calhamingdistance();
	evaluatepop();   
	for(generation=1; generation<maxgeneration; ++generation)
	{
		selection();
		crossover();
		mutation();
		decodechrom();	
		calfitnessvalue();
		calhamingdistance();
		update();
		evaluatepop();
	}			
	time(&end);
	double elapsed=difftime(end,begin);	
	cout<<"time in seconds: "<<elapsed<<endl;
	fprintf(file1,"time in seconds: %f\n",elapsed);
	fprintf(file1,"maxigeneration=%d\n\n\n",maxgeneration);
	fclose(file1);
	fwrite(result, sizeof(result), 1, file2);
	fclose(file2);
	fwrite(AHD, sizeof(AHD), 1, fileAHD);
	fclose(fileAHD);
}

void gen_ini_pop()
{	
	int popmem;
	int index;	
	double temp;
	double x;
	double y;
	double x2y2;	
	//==&1 generate the inipopulation's chromsome
	for(popmem=0; popmem<popsize; ++popmem)
	{
		for(index=0; index<chromlen; ++index)
			if(rand()/(double)RAND_MAX<0.5)
				pop[popmem].chrom[index]=0;
			else
				pop[popmem].chrom[index]=1;
	}
			
	//==&2 decode the chromsome		
	for(popmem=0; popmem<popsize; ++popmem)
	{
		temp=0;
		for(index=0;index<xlen;++index)
			temp=temp*2+(unsigned int)(pop[popmem].chrom[index]);
		pop[popmem].x=temp/10000.0-100;
		temp=0;
		for(index=xlen;index<xlen+ylen;++index)
			temp=temp*2+(unsigned int)(pop[popmem].chrom[index]);
		pop[popmem].y=temp/10000.0-100;

	}
	//==&3 calculate the inipopulation's fitness	
	for(popmem=0; popmem<popsize; ++popmem)
	{	
			x=pop[popmem].x;
			y=pop[popmem].y;
			x2y2=x*x+y*y;
			pop[popmem].fitness=0.5-
				(pow(sin(pow(x2y2, 0.5)),2)-0.5)/(pow((1+0.001*x2y2),2));
	}
}

void evaluatepop()
//operate on pop[]
{ 
	int popmem;
	int tempbetter;
	int i, j, k;
	double hamiDistSum;
	
	tempbetter=0;
	for(popmem=1; popmem<popsize; ++popmem)
		if(pop[tempbetter].fitness<pop[popmem].fitness)
			tempbetter=popmem;
	if(pop[tempbetter].fitness>bestind.fitness)
		bestind=pop[tempbetter];
	else
		pop[tempbetter]=bestind;
		
	
	//============debug bigin==================================================
	
	
	for(int ii=0; ii<popsize; ++ii)
	{
	//	cout<<pop[ii].fitness<<endl;
	//	getch();
	}
	for(int tt=0; tt<chromlen/2; ++tt)
		cout<<(int)bestind.chrom[tt];
		cout<<"   "<<bestind.x<<endl;
	for(tt=chromlen/2; tt<chromlen; ++tt)
		cout<<(int)bestind.chrom[tt];
	cout<<"   "<<bestind.y<<endl;	
	cout<<"HAMING distance="<<HAMINGdistance[generation]<<endl;
	printf("in %dth generation,   ", generation+1);
	printf("bestfitness=%f\n",bestind.fitness);	
   // getch();
	//Calculate average haming distance
	hamiDistSum=0;
	for(i=0; i<popsize; i++)
		for(j=0; j<popsize; j++)
			if(j!=i)
			{
				for(k=0; k<chromlen; k++)
					if(pop[i].chrom[k]!=pop[j].chrom[k])
						hamiDistSum++;
			}
	AHD[generation+1]=hamiDistSum/(popsize*(popsize-1));


	
	//===========debug end=====================================================	
	

	//==&6 output and save the best fitness of the individuals
	result[generation+1]=bestind.fitness;
	fprintf(file1,"in %dth generation  ",generation+1);	
	fprintf(file1,"bestfitest=%f\n",bestind.fitness);		
	
    //  getch();   //debug
//	cout<<endl;
}

void selection()
//operate on pop[]
{
	int popmem;
	int index;
	double sum;
	double cfitness[popsize];//cumulatie fitness value	

	//calculate relative fitness
	sum=0;
	for(popmem=0;popmem<popsize;++popmem)
		sum+=pop[popmem].fitness;
	for(popmem=0;popmem<popsize;++popmem)
		cfitness[popmem]=pop[popmem].fitness/sum;

	//calculate cumulative fitness
	for(popmem=1;popmem<popsize;++popmem)
		cfitness[popmem]+=cfitness[popmem-1];
	
	//selection operation	
	for(popmem=0;popmem<popsize;++popmem)
	{
		index=0;
		while(rand()/(double)RAND_MAX>cfitness[index])
			++index;
		beselected[popmem]=index;
	}
}

void crossover()
// operate on pop[] 
// to get competepop[]
{	
	int popmem;		
	int temp1;
	int temp2;			
	int crossoverpoint;	
	int competepopmem;	
	int index;
	for(popmem=0; popmem<popsize; popmem+=2)
	{
		//determine the distance between the two individuals in a douple
		temp2=rand()%(popsize-popmem);
		//each individual and it's next one form a couple
		temp1=beselected[popmem+1];
		beselected[popmem+1]=beselected[popmem+temp2];
		beselected[popmem+temp2]=temp1;	
	}			
	for(competepopmem=0, popmem=0; 
	    popmem<popsize; 
		popmem+=2, competepopmem+=2)
	{
		if(rand()/(double)RAND_MAX<crossprob)
		{
			crossoverpoint=int(rand()*chromlen/RAND_MAX);
			for(index=0; index<crossoverpoint; ++index)
			{
				competepop[competepopmem].chrom[index]
					=pop[beselected[popmem/2]].chrom[index];
				competepop[competepopmem+1].chrom[index]
					=pop[beselected[popmem/2+1]].chrom[index];
			}
			for(index=crossoverpoint; index<chromlen; ++index)
			{
				competepop[competepopmem].chrom[index]
					=pop[beselected[popmem/2+1]].chrom[index];
				competepop[competepopmem+1].chrom[index]
					=pop[beselected[popmem/2]].chrom[index];
			}
		}
		else
		{
			for(index=0; index<chromlen; ++index)
			{
				competepop[competepopmem].chrom[index]
					=pop[beselected[popmem/2]].chrom[index];
				competepop[competepopmem+1].chrom[index]
					=pop[beselected[popmem/2+1]].chrom[index];
			}

		}
		
	}
}

void mutation()
//operate on competepop[]
{
	int competepopmem;	
	int gen;
	for(competepopmem=0;
	    competepopmem<popsize;
		++competepopmem)
			for(gen=0; gen<chromlen; ++gen)
				if(rand()/(double)RAND_MAX<mutatprob)
					if(competepop[competepopmem].chrom[gen]==0)
						competepop[competepopmem].chrom[gen]=1;
					else
						competepop[competepopmem].chrom[gen]=0;
}

void decodechrom()
//operate on competepop[]
{
	double temp;
	int competepopmem;
	int i;
	for(competepopmem=0; 
	    competepopmem<competepopsize;
		++competepopmem)
	{
		temp=0;
		for(i=0;i<xlen;++i)
			temp=temp*2+(unsigned int)competepop[competepopmem].chrom[i];		
		competepop[competepopmem].x=temp/10000.0-100;
		
		temp=0;
		for(i=xlen; i<xlen+ylen; ++i)
			temp=temp*2+(unsigned int)competepop[competepopmem].chrom[i];		 
		competepop[competepopmem].y=temp/10000.0-100;
		}
}

void calfitnessvalue()
//operate on competepop[]
{
	double x,y,x2y2;
	int competpopmem;
	for(competpopmem=0;
	    competpopmem<competepopsize;
		++competpopmem)
	{	
			x=competepop[competpopmem].x;
			y=competepop[competpopmem].y;
			x2y2=x*x+y*y;
			competepop[competpopmem].fitness=0.5-
				(pow(sin(pow(x2y2, 0.5)),2)-0.5)/(pow((1+0.001*x2y2),2));
		}
}

void update()
// operate on competepop[]
// to get pop[]
{
	int popmem;	
	int candicate;
	int comp;
	individual tempind;
	// get the next population by
	// transfer the individual from competepop to pop	
	for(popmem=elitepopsize;
	    popmem<popsize; 
		++popmem)
			pop[popmem]=competepop[popmem];	
		
	for(popmem=0; popmem<elitepopsize; ++popmem)
	{
		candicate=popmem;
		for(comp=candicate+1; comp<popsize; ++comp)
			if(pop[candicate].fitness<pop[comp].fitness)
				candicate=comp;
		tempind=pop[popmem];
		pop[popmem]=pop[candicate];
		pop[candicate]=tempind;
	}   
}
void calhamingdistance()
{
	double sum=0;
	int gen;
	int popmem;	
	for(popmem=0; popmem<popsize; ++popmem)
		for(gen=0; gen<chromlen; ++gen)
				if(pop[popmem].chrom[gen]!=bestind.chrom[gen])
					++sum;
	HAMINGdistance[generation]=sum/((double)popsize);
}