#include<iostream.h>
#include<math.h>
#include<time.h>
//#include<graphics.h>
#include<stdlib.h>
#include<string.h>

#define maxpop 100
#define maxstring 32

typedef struct{
	char chrom[maxstring];
	float x,fitness;
	int parent1,parent2,xsite;
}pp;

pp *oldpop,*newpop,*p1;
int popsize,lchrom,gen,maxgen,nmutation,ncross,jcross,maxpp,minpp,jrand;
float pcross,pmutation,sumfitness,avg,max,min,seed,rj[maxpop],oldrand[maxpop];
double coef;

float objfunc(float);
int select();
int flip(float);
int crossover(char *,char *,int);
char mutation();
void generation();
void initialize();
void report();
void initpop();
void initdata();
void initreport();
double decode(char *);
float random1();
void randomize1();
void pause();

void test(char x)
{cout<<x<<'\n';}

float objfunc(float x1)
//compute object fitness;
{
	float y;
	y=3.14*x1;
	y=sin(2.0*y);
	return y*y;
}

void statistic(pp *pop)
//statistic the fitness of population
{
	int j;
	sumfitness=pop[0].fitness;
	max=pop[0].fitness;
	min=pop[0].fitness;
	maxpp=0;
	minpp=0;
	for(j=1;j<popsize;j++){
		sumfitness=sumfitness+pop[j].fitness;
		if(pop[j].fitness>max){
			max=pop[j].fitness;
			maxpp=j;
		}
		if(pop[j].fitness<min){
			min=pop[j].fitness;
			minpp=j;
		}
	}//end for
	avg=sumfitness/(float)popsize;
}

void generation()
//update a generation;
{
	int j,mate1,mate2;
	j=0;
	do{
		mate1=select();
		mate2=select();
		crossover(oldpop[mate1].chrom,oldpop[mate2].chrom,j);
		newpop[j].x=(float)decode(newpop[j].chrom);
		newpop[j].fitness=objfunc(newpop[j].x);
		newpop[j].parent1=mate1;
		newpop[j].parent2=mate2;
		newpop[j].xsite=jcross;//recode the cross point;
		newpop[j+1].x=(float)decode(newpop[j+1].chrom);
		newpop[j+1].fitness=objfunc(newpop[j+1].x);
		newpop[j+1].parent1=mate1;
		newpop[j+1].parent2=mate2;
		newpop[j+1].xsite=jcross;
		j=j+2;
	}while(j<popsize);
}

void initdata()
//input control parameters
{
	int ch,j;
	cout<<"*********SGA DATA ENTRY AND INITIALIZATION*******\n";
	cout<<"Enter population size:";
	cin>>popsize;
//	cout<<"Enter chromosome length:";
//	cin>>lchrom;
	lchrom = 32;
	cout<<"Enter max generations";
	cin>>maxgen;
	cout<<"Enter crossover probability:";
	cin>>pcross;
	cout<<"Enter mutation probability:";
	cin>>pmutation;
	
	//randomize1();
	nmutation=0;
	ncross=0;
}

void initreport()
{
	cout<<"Population size:"<<popsize<<'\n';
//	cout<<"Chromosome length:"<<lchrom<<'\n';
	cout<<"Maximum # of generation:"<<maxgen<<'\n';
	cout<<"Crossover probability:"<<pcross<<'\n';
	cout<<"Mutation probability:"<<pmutation<<'\n';
	cout<<"-----------------------------------------------------\n";
	cout<<"Initial Population Maximum Fitness:"<<max<<'\n';
	cout<<"Initial Population Average Fitness:"<<avg<<'\n';
	cout<<"Initial Population Minimun Fitness:"<<min<<'\n';
	cout<<"Initial Population Sum of Fitness:"<<sumfitness<<'\n';
	pause();
}

void initpop()
{
	srand((unsigned)time(NULL));
	int bit;
	oldpop = new pp[popsize];
	newpop = new pp[popsize];
	int j,j1;
	for(j=0;j<popsize;j++){
		for(j1=0;j1<lchrom;j1++){
			if (rand()%2 == 1) 
				oldpop[j].chrom[j1] = '1';
			else oldpop[j].chrom[j1]='0';
		}
		oldpop[j].x=(float)decode(oldpop[j].chrom);
		oldpop[j].fitness=objfunc(oldpop[j].x);
		oldpop[j].parent1=0;
		oldpop[j].parent2=0;
		oldpop[j].xsite=0;
	}//end for
}

void initialize()
{
	initdata();
	//test('a');
	coef=pow(2.00,lchrom)-0.1;
	initpop();
	statistic(oldpop);
	initreport();
}

void report(int gen)
{
	int k,j;
	cout<<"******************************************************\n";
	cout<<"     Generation:"<<gen<<'\n';
	cout<<"#        parents                      xsite   string    x   fitness\n";
	for(j=0;j<popsize;j++)
	{
		cout<<j<<"\t"<<newpop[j].parent1<<'\t'<<newpop[j].parent2<<'\t'<<newpop[j].xsite<<'\t';
		for(k=0;k<lchrom;k++) cout<<newpop[j].chrom[k];
		cout<<'\t'<<newpop[j].x<<'\t'<<newpop[j].fitness<<'\n';
	}
	cout<<"********************************************************\n";
	cout<<"Result Gen:"<<gen<<'\n';
	cout<<"AVG="<<avg<<'\t'<<"MIN="<<min<<'\t'<<"MAX="<<max<<'\n';
	cout<<"ncross="<<ncross<<'\t'<<"nmutation="<<nmutation<<'\n';
}

int select()
{
	double rand1,partsum;
	int j;
	partsum=0.0;
	j=0;
	rand1=random1()*sumfitness;
	do{
		partsum=partsum+oldpop[j].fitness;
		j=j+1;
	}while((partsum<rand1)&&(j<popsize));
	return j-1;
}

double decode(char *pp)
//decode chrom to the real number
{
	int j;
	double tt,tt1;
	tt1=1.0;
	tt=0.0;
	for(j=lchrom-1;j>-1;j--){
//	for (j = 31; j > -1; j--) {
		if(pp[j] == '1') tt=tt+tt1;
		tt1=2.0*tt1;
	}
	tt=tt/coef;
//	tt = tt / (pow(2.0,32) - 0.1);
	return tt;
}

void pause()
{
	int j,j1;
	int x1;
	x1=0;
	for(j=1;j<=25;j++)
		for(j1=1;j1<2;j1++) x1=x1+1;
}

char mutation(char ch)
//mutation operate
{
	int mutate,j;
	mutate=flip(pmutation);
	if(mutate)
	{
		nmutation=nmutation+1;//???nmutation??
		if(ch) ch=0;
		else ch=1;
	}
	if(ch) return '1';
	else return '0';
}

int crossover(char *parent1,char *parent2,int k5)
//crossover operate
{
	int i,j,j1;
	if(flip(pcross))
	{
		jcross=rand()%(lchrom-1);
		ncross=ncross+1;//???ncross?
	}
	else jcross=lchrom;
	if(jcross!=lchrom)
	{
		for(j=0;j<jcross;j++){
			newpop[k5].chrom[j]=mutation(parent1[j]);
			newpop[k5+1].chrom[j]=mutation(parent2[j]);
		}
		for(j=jcross;j<lchrom;j++){
			newpop[k5].chrom[j]=mutation(parent2[j]);
			newpop[k5+1].chrom[j]=mutation(parent1[j]);
		}
	}//end if
	else 
	{
		for(j=0;j<lchrom;j++)
		{
			newpop[k5].chrom[j]=mutation(parent1[j]);
			newpop[k5+1].chrom[j]=mutation(parent2[j]);
		}
	}//end else
	return 1;
}

void randomize1()
//reset the random number generator
{
	int i;
	srand((unsigned)time(NULL));
//	randomize();//???????generate errors "randomize undeclared"
	for(i=0;i<lchrom;i++);
		oldrand[i]=(rand()%1000)/1000.0;
	jrand=0;
}

float random1()
//generate a random number
{
	jrand=jrand+1;
	if(jrand>=lchrom)
	{
		jrand=0;
		randomize1();
	}
	return oldrand[jrand];
}

int flip(float probability)
//貝努利實驗
{
	float ppp;
	ppp=(rand()%1000)/1000.0;
	if(ppp<=probability) return 1;
	return 0;
}

void main()
{
	double detest;
	char testch[32];
	for (int testi = 0; testi < 32; testi++) {
		if (rand()%2 == 1) 
			testch[testi] = '1';
		else testch[testi] = '0';
	}
	detest = decode(testch);
	cout<<detest<<'\n';


	char c;
	long int gen,k,j;
	float oldmax;
	int oldmaxpp;
//	pp *oldpop,*newpop,*p1;
//	oldpop=new pp[maxpop];
//	newpop=new pp[maxpop];

/*	oldpop = new pp[maxpop];
	newpop = new pp[maxpop];

	p1=new pp;
	for(k=0;k<maxpop;k++)
		for (j = 0; j < maxstring; j++) {
			oldpop[k].chrom[j]='0';
			newpop[k].chrom[j]='0';
		}
		*/
	gen=0;
	initialize();
	p1=newpop;
	newpop=oldpop;
	statistic(newpop);
	report(gen);
	newpop=p1;
	cin>>c;
	do {
		gen=gen+1;
		oldmax=max;
		oldmaxpp=maxpp;
		generation();
		statistic(newpop);
		if(max<oldmax){
			for(j=0;j<lchrom;j++)
				newpop[minpp].chrom[j]=oldpop[oldmaxpp].chrom[j];
			newpop[minpp].x=oldpop[oldmaxpp].x;
			newpop[minpp].fitness=oldpop[oldmaxpp].fitness;
			statistic(newpop);
		}
//		report(gen);
		p1=oldpop;
		oldpop=newpop;
		newpop=p1;
//		cin>>c;
	}while(gen<maxgen);
	report(gen);
	free(p1);
	free(oldpop);
}