#include <stdio.h>
#include<stdlib.h>
#include<time.h>
#include<math.h>
#define POPSIZE 500
#define maximization 1
#define minimization 2
#define cmax 100
#define cmin 0
#define length1 10
#define length2 10
#define chromlength length1+length2  //染色體長度
 int functionmode=maximization;
 int popsize;        //種群大小
int maxgeneration;  //最大世代數
 double pc;          //交叉率
 double pm;          //變異率
struct individual
     {
      char  chrom[chromlength+1];
      double value;         
      double fitness;//適應度
};
int generation;      //世代數
int best_index;
int worst_index;
struct individual bestindividual;  //最佳個體
struct individual worstindividual; //最差個體
struct individual currentbest;
struct individual population[POPSIZE];
//函數聲明                                       
void generateinitialpopulation();                 
void generatenextpopulation();
void evaluatepopulation();
long decodechromosome(char *,int,int);
void calculateobjectvalue();
void calculatefitnessvalue();
void findbestandworstindividual();
void performevolution();
void selectoperator();
void crossoveroperator();
void mutationoperator();
void input();
void outputtextreport();

void generateinitialpopulation( )  //種群初始化
{
	int i,j;
	for (i=0;i<popsize; i++)
	{
		for(j=0;j<chromlength;j++)
	{
population[i].chrom[j]=(rand()%10<5)?'0':'1';
		}
		population[i].chrom[chromlength]='\0';
	}
}
void generatenextpopulation()  //生成下一代
{
	selectoperator();
	crossoveroperator();
	mutationoperator();
}
void evaluatepopulation()   //評價個體，求最佳個體
{
	calculateobjectvalue();
	calculatefitnessvalue();
	findbestandworstindividual();
}
long decodechromosome(char *string ,int point,int length) //給染色體解碼
{
	int i;
	long decimal=0;
	char*pointer;
for(i=0,pointer=string+point;i<length;i++,pointer++)
	if(*pointer-'0')

	{decimal +=(long)pow(2,i);
	}
	return (decimal);

}
void calculateobjectvalue()  //計算函數值
{
	int i;
	long temp1,temp2;
    double x1,x2;

	for (i=0; i<popsize; i++)
	{
		 temp1=decodechromosome(population[i].chrom,0,length1);
         temp2=decodechromosome(population[i].chrom,length1,length2);
         x1=4.096*temp1/1023.0-2.048;
         x2=4.096*temp2/1023.0-2.048;
population[i].value=100*(x1*x1-x2)* (x1*x1-x2)+(1-x1)*(1-x1);
}
}
void calculatefitnessvalue()//計算適應度
{
	int  i;
double temp;
   for(i=0;i<popsize;i++)
   {
 if(functionmode==maximization)
	   {if((population[i].value+cmin)>0.0)
  {temp=cmin+population[i].value;}
 else
 {temp=0.0;
   }
	   }
else if (functionmode==minimization)
 {
   if(population[i].value<cmax)
      {temp=cmax-population[i].value;}
    else{ temp=0.0;}
}
population[i].fitness=temp;
}
}
void findbestandworstindividual( ) //求最佳個體和最差個體
{
	int i;
	double sum=0.0;
	
	bestindividual=population[0];
	worstindividual=population[0];

	for (i=1;i<popsize; i++){
		if (population[i].fitness>bestindividual.fitness){
			bestindividual=population[i];
			best_index=i;
}
		else if (population[i].fitness<worstindividual.fitness)
{
			worstindividual=population[i];
			worst_index=i;
			
		}
        sum+=population[i].fitness;
}
if (generation==0){
		currentbest=bestindividual;
	}
	else{
		if(bestindividual.fitness>=currentbest.fitness){
			currentbest=bestindividual;
		}
	}
}
void performevolution() //演示評價結果
{
	if (bestindividual.fitness>currentbest.fitness){
		currentbest=population[best_index];
	}
	else{
		population[worst_index]=currentbest;
	}
}
void selectoperator() //比例選擇算法
{
	int i,index;
	double p,sum=0.0;
	double cfitness[POPSIZE];

	struct individual newpopulation[POPSIZE];
	for(i=0;i<popsize;i++)
{sum+=population[i].fitness;}

for(i=0;i<popsize; i++){
		cfitness[i]=population[i].fitness/sum;
	}

	for(i=1;i<popsize; i++){
		cfitness[i]=cfitness[i-1]+cfitness[i];
	}

	for (i=0;i<popsize;i++)
	{
		p=rand()%1000/1000.0;
		index=0;
		while (p>cfitness[index])
		{
			index++;
		}
		newpopulation[i]=population[index];
	}
	for(i=0;i<popsize; i++){
		population[i]=newpopulation[i];
	}
}
void crossoveroperator() //交叉算法
{
	int i,j;
	int index[POPSIZE];
	int point,temp;
	double p;
	char ch;

	
	for (i=0;i<popsize;i++){
		index[i]=i;
	}
	for (i=0;i<popsize;i++){
		point=rand()%(popsize-i);
		temp=index[i];
		index[i]=index[point+i];
		index[point+i]=temp;
	}

	
	for (i=0;i<popsize-1;i+=2){
		p=rand()%1000/1000.0;
		if (p<pc){
			point=rand()%(chromlength-1)+1;
			for (j=point; j<chromlength;j++){
				ch=population[index[i]].chrom[j];
				population[index[i]].chrom[j]=population[index[i+1]].chrom[j];
				population[index[i+1]].chrom[j]=ch;
			}
		}
	}

}
void mutationoperator() //變異操作
{
	int i,j;
	double p;
	
	for (i=0;i<popsize;i++){
		for(j=0;j<chromlength;j++){
			p=rand()%1000/1000.0;
			if (p<pm){
				population[i].chrom[j]=(population[i].chrom[j]=='0')?'1':'0';
			}
		}
	}
}
void input() //數據輸入
{   printf("初始化全局變量:\n");
	printf("    種群大小(50-500)：");
   scanf("%d", &popsize);
    if((popsize%2) != 0)
      {
	printf( "   種群大小已設置為偶數\n");
	popsize++;};
    printf("     最大世代數(100-300)：");
   scanf("%d", &maxgeneration);
   printf("     交叉率(0.2-0.99)：");
   scanf("%f", &pc);
   printf("     變異率(0.001-0.1)：");
   scanf("%f", &pm);
}
void outputtextreport()//數據輸出
{
	int i;
double sum;
double average;
sum=0.0;
for(i=0;i<popsize;i++)
{sum+=population[i].value;}
average=sum/popsize;
	
printf("當前世代=%d\n當前世代平均函數值=%f\n當前世代最高函數值=%f\n",generation,average,population[best_index].value);

}
void main()    //主函數
{   int i;
printf("本程序為求函數y=100*(x1*x1-x2)*(x1*x2-x2)+(1-x1)*(1-x1)的最大值 \n其中-2.048<=x1,x2<=2.048\n");
    generation=0;
    input();
    generateinitialpopulation();
	evaluatepopulation();
	while(generation<maxgeneration)
	{
		generation++;
		generatenextpopulation();
		evaluatepopulation();
		performevolution();
		outputtextreport();
	}
    printf("\n");
	printf("         統(tǒng)計結果:        ");
    printf("\n");
printf("最大函數值等于：%f\n",currentbest.fitness);
	printf("其染色體編碼為：");
	for (i=0;i<chromlength;i++)
	{
	printf("%c",currentbest.chrom[i]);
		
	}
    printf("\n"); 
}