#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <math.h>
using namespace std;

#define POPSIZE 50							//最大種群數(shù)
#define CHROMLENGTH 22				//染色體長度
#define PI 3.1415926535					//PI

int maxgeneration=200;			        //最大代數(shù)
double pc=0.25;							    //交叉概率
double pm=0.01;							    //變異概率
double xmin=-1,xmax=2;

struct Individual
{
	char chrom[CHROMLENGTH+1];		//編碼串
	double value;									//函數(shù)值
	double fitness;								    //適應度
};

int     generation;								 //代數(shù)
Individual currentbest;						 //當前種群中的最佳個體（即函數(shù)值最大者）
Individual population[POPSIZE];		 // 種群

long DecodeChromosome(char *string ,int length) //給染色體解碼
{
	int i;
	long value=0;
	for(i = 0 ;i < length ;i ++)
	{
		if(string[i] - '0' == 1)
			value += (long)pow((double)2,i);
	}
	return (value);
}

void CalculateFitnessValue()				//計算適應度
{
	int i;
	
	for(i=0;i<POPSIZE;i++)
	{
		population[i].fitness = population[i].value;
	}
}

void CalculateFunctionValue()				 //計算函數(shù)值
{
	int i;
	long temp;
	double x;
	
	for (i=0; i<POPSIZE; i++)
	{
		temp = DecodeChromosome(population[i].chrom,CHROMLENGTH);
		x = -1 + (xmax-xmin)*temp/(pow((double)2,CHROMLENGTH)-1);
		population[i].value=x*sin(10*PI*x)+1.0;
	}
}

void Select()						//比例選擇算法
{
	int i,index;
	double p,sum=0.0;
	double cfitness[POPSIZE];		//存每個個體的概率
	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 Mutate()				 //變異操作
{
	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 Cross() //交叉算法
{
	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 FindBestIndividual()  //求當前種群中的最佳個體
{
	int i;
	int best_index;

	Individual bestIndividual=population[0];
	for (i=1;i<POPSIZE; i++)
	{
		if (population[i].fitness>bestIndividual.fitness)
		{
			bestIndividual=population[i];
			best_index=i;
		}
	}

	if (generation==0)
	{
		currentbest=bestIndividual;
	}
	else
	{
		if(bestIndividual.fitness>=currentbest.fitness)
		{
			currentbest=bestIndividual;
		}
	}
}

void GenerateInitial( )					//種群初始化
{
	int i,j;
	for (i=0;i<POPSIZE; i++)
	{
		for(j=0;j<CHROMLENGTH;j++)
		{
			population[i].chrom[j]=(rand()%10<5)?'0':'1';
		}
	}
}

void NextGeneration() //生成下一代
{
	Select();
	Cross();
	Mutate();
}

void EvaluatePopulation()
{
	CalculateFunctionValue();
	CalculateFitnessValue();
}

double CalX(char *str)			//將str轉成對應的x的值
{
	long temp;
	double x;
	temp = DecodeChromosome(str,CHROMLENGTH);
	x = -1 + (xmax-xmin)*temp/(pow((double)2,CHROMLENGTH)-1);
	return x;
}

int main()
{
	srand(time(NULL));
	printf("f(x)=x*sin(10*PI*x)+1.0 (-1<=x<=2)\n");
	generation=0;
	GenerateInitial();
	EvaluatePopulation();
	while(generation<maxgeneration)
	{
		generation++;
		NextGeneration();
		EvaluatePopulation();
	}
	FindBestIndividual();
	printf("函數(shù)最大最值等于：%f\n",currentbest.value);
	printf("X的值是：%f\n",CalX(currentbest.chrom));
    printf("染色體的編碼是：");
	for (int i=0;i<CHROMLENGTH;i++)
	{
		printf("%c",currentbest.chrom[i]);
	}
	printf("\n");
	return 0;
}