/**********************************ga.cpp********************************/
/*****************用遺傳算法求解函數(f(x)=x*sin(10pi*x)+1.0)的最大值*****/
/*********************作者：高衛平，周兆永（計算機科學學院05級研究生）***/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#define popsize 10       //群體數量
#define maxgenes 1000    //遺傳代數
#define nvars 22         //編碼長度
#define pxover 0.9     //交叉概率
#define pmutation 0.01  //變異概率
#define true 1
#define false 0
int generation;
int cur_best;
FILE *fp;
struct genotype{
	int gene[nvars];   //編碼
	double value;
	double fitness;    //適應度值
	double rfitness;          //population[mem].rfitness=population[mem].fitness/sum;
	double cfitness;          //population[mem].cfitness=population[mem-1].cfitness+population[mem].rfitness;
};              //一個個體的結構，包括編碼，適應度值，
struct genotype population[popsize+1];    //一個群體數組
struct genotype newpopulation[popsize+1];

///////////////////////////////////////////////////////////////////////////
////////////////////////////函數定義///////////////////////////////////////
///////////////////////////////////////////////////////////////////////////
void initialize(void);
double two_ten(int i);
double real_number(long real,long num);
void evaluate(void);
void keep_the_best();
void elitist(void);
void select(void);      //選擇
void crossover(void);   //
void xover(int,int);
void swap(int*,int*);
void mutate(void);      //變異
int change(int i,int j);
int rand_int(void);
void report(void);
//===================================================//
//===============初始化群體==========================//
//===================================================//
void initialize(void)   
{
	FILE*infile;
	if((infile=fopen("gadate.txt","r"))==NULL)
	{	
		printf("\nCannot open input file\n");
		exit(0);
	}    
	//讀取文件數據
		for(int j=0;j<10;j++){
			for(int i=0;i<22;i++){
				population[j].gene[i]=fgetc(infile)-48;
			}
			fgetc(infile);
			population[j].fitness=0;
			population[j].rfitness=0;
			population[j].cfitness=0;
			population[j].value=two_ten(j);
		}
	fclose(infile);
	
}
//================================================//
//=========把從文件中讀取的二進制數轉換成十進制數=//
//================================================//
double two_ten(int n){
	long a=0;
	long sum=0;
	double value=0;
	long num=2;
	for(int i=0;i<20;i++){
		num=2*num;
	}
	long m=num;
	for(int j=0;j<22;j++){
		if(j<20){			
			a=population[n].gene[j]*num;
			num=num/2;
		}
		else{
			if(j==20){
				num=2;
				a=population[n].gene[j]*num;
			}
			else{
				num=1;
				a=population[n].gene[j]*num;	
			}
		}
		sum=sum+a;
	}
	value=real_number(sum,m);
	return value;
}
//===============================================//
//================把十進制數轉換成實數===========//
//===============================================//
double real_number(long real,long num){
	num=num*2;
	double value=0;
	num=num-1;
	double a,b,c;
	a=(double)num;
	b=(double)(3/a);
	c=real*b;
	value=-1.0+c;
	return value;
}
//===========================================================//
//===============計算群體上每一個個體的適應度值==============//
//===========================================================//
void evaluate(void){     
	int i;
	double x[popsize];
	for(i=0;i<popsize;i++){
		x[i]=population[i].value;
		population[i].fitness=x[i]*sin(10*3.1415926*x[i])+1.0;
		fprintf(fp," (%d)        %f\n",i,population[i].fitness);
	}
}
//===========================================================//
//==========在群體中找一個具有最佳適應度值的個體=============//
//===========================================================//
void keep_the_best(){   
	int mem;
	int i;
	int cur_best=0;
	for(mem=0;mem<popsize;mem++){
		if(population[mem].fitness>population[popsize].fitness){
			cur_best=mem;
			population[popsize].fitness=population[mem].fitness;
		}
	}
	for(i=0;i<nvars;i++){
	population[popsize].gene[i]=population[cur_best].gene[i];
	}
}
//============================================================//
//=======把每一代中的最佳適應度值存入population[popsize]中====//
//============================================================//
void elitist(){
	int i;
	double best,best_r,best_c,worst,worst_r,worst_c;
	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_r=population[i].rfitness;
				best_c=population[i].cfitness;
				best_mem=i;
			}
			if(population[i+1].fitness<=worst){
				worst=population[i+1].fitness;
				worst_r=population[i+1].rfitness;
				worst_c=population[i+1].cfitness;
				worst_mem=i+1;
			}
		}
		else{
			if(population[i].fitness<=worst){
				worst=population[i].fitness;
				worst_r=population[i].rfitness;
				worst_c=population[i].cfitness;
				worst_mem=i;
			}
		}
		if(population[i+1].fitness>=best){
			best=population[i+1].fitness;
			best_r=population[i+1].rfitness;
			best_c=population[i+1].cfitness;
			best_mem=i+1;
		}
	}
	if(best>=population[popsize].fitness){
		for(i=0;i<nvars;i++){
			population[popsize].gene[i]=population[best_mem].gene[i];
		}
		population[popsize].fitness=population[best_mem].fitness;
		population[popsize].rfitness=population[best_mem].rfitness;
		population[popsize].cfitness=population[best_mem].cfitness;
	}
	else{
		for(i=0;i<nvars;i++){
			population[worst_mem].gene[i]=population[popsize].gene[i];
		}
		population[worst_mem].fitness=population[popsize].fitness;
		population[worst_mem].rfitness=population[popsize].rfitness;
		population[worst_mem].cfitness=population[popsize].cfitness;
	}
}
//=================================================//
//=======按由個體適應度值 所決定的某個規則=========//
//========選擇將 進入下一代的個體==================//
//=================================================//
void select(void){     
	int mem,i,j;
	double sum=0.0;
	double p=0.0;
	for(mem=0;mem<popsize;mem++){
		sum=sum+population[mem].fitness;
	}
	for(mem=0;mem<popsize;mem++){
		population[mem].rfitness=population[mem].fitness/sum;
	}
	population[0].cfitness=population[0].rfitness;
	for(mem=1;mem<popsize;mem++){
		population[mem].cfitness=population[mem-1].cfitness+population[mem].rfitness;
	}
	for(i=0;i<popsize;i++){
		p=rand()%1000/1000.0;
		if(p<population[i].cfitness)
			newpopulation[i]=population[i];
		else{
			for(j=0;j<popsize;j++)
				if(p>=population[j].cfitness&&p<population[j+1].cfitness)
					newpopulation[i]=population[j+1];
		}
	}
	for(i=0;i<popsize;i++)
		population[i]=newpopulation[i];
}
//=================================================//
//====================交叉=========================//
//=================================================//
void crossover(void){
	int one,two;
	double x;
	one=rand_int();
	two=rand_int();
	x=rand()%1000/1000.0;
	while(one==two){
		two=rand_int();
	}
	if(x<0.25){
		xover(one,two);
	}
}
void xover(int one,int two){
	int i;
	int point ;
	point=(rand()%(nvars-1))+1;
	for(i=point;i<nvars;i++)
		swap(&population[one].gene[i],&population[two].gene[i]);
	population[one].value=two_ten(one);
	population[two].value=two_ten(two);
}
void swap(int*x,int*y){
	int temp;
	temp=*x;
	*x=*y;
	*y=temp;
}
//=================================================//
//====================變異=========================//
//=================================================//
void mutate(void){
	int i,j;
	double y;
	for(i=0;i<popsize;i++){
		j=rand_int();
		y=rand()%1000/1000.0;
		if(y<pmutation){
			population[i].gene[j]=change(i,j);
		}
		population[i].value=two_ten(i);
	}
}
int change(int i,int j){
	int value;
	if(population[i].gene[j]==1)
		value=0;
	else
		value=1;
	return value;
}
int rand_int(void){
	int x;
	x=rand()%100;
	x=x%9;
	return x;
}
void report(void)
{
	int i;
	double best_val;
	double avg;
	double stddev;
	double sum_square;
	double square_sum;
	double sum;
	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/(double)popsize;
	square_sum=avg*avg*(double)popsize;
	stddev=sqrt((sum_square)/(popsize-1));
	best_val=population[popsize].fitness; 
	fprintf(fp,"\n遺傳代數：[%d]   每一代的最佳適應度值：%f  \n",generation,population[popsize].fitness);
}
void main(void){
	int i;
	if((fp=fopen("result.txt","w+"))==NULL)
	{
		exit(1);
	}
	generation=0;
	fprintf(fp,"*****************************************************************\n");
	fprintf(fp,"**********用遺傳算法求解函數(f(x)=x*sin(10pi*x)+1.0)的最大值*****\n");
	fprintf(fp,"**********作者：高衛平，周兆永（計算機科學學院05級研究生）*******\n");
	fprintf(fp,"*****************************************************************\n");
	fprintf(fp," 每一代的適應度值： \n");
	initialize();
	evaluate();
	for(int j=0;j<nvars;j++)
		population[popsize].gene[j]=0;
	population[popsize].fitness=0.0;
	population[popsize].cfitness=0.0;
	population[popsize].rfitness=0.0;
	keep_the_best();
	while(generation<maxgenes){
		generation++;
		select();
		crossover();
		mutate();
		report();
		evaluate();
		elitist();
	}
	fprintf(fp,"\n 最佳個體=");
	for(i=0;i<nvars;i++){
		fprintf(fp,"%d",population[popsize].gene[i]);
	}
	fprintf(fp,"\n\n 最佳適應度值=%f",population[popsize].fitness);
	fclose(fp);
	printf("Success!\n");
}