#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("         統計結果:        ");
    printf("\n");
	printf("最大函數值等于：%f\n",currentbest.fitness);
	printf("其染色體編碼為：");

	for (i=0;i<chromlength;i++)
	{
		printf("%c",currentbest.chrom[i]);
	}

    printf("\n"); 
}