#include <stdlib.h>
#include <stdio.h>
#include <iostream>
#include <math.h>
#include <time.h>
using namespace std;
//The Definition of Constant

#define POPSIZE 100//population size

//The Definition of User Data
//(For different problem,there are some difference.)

int PopSize=100; //population size
int MaxGeneration=200; //max.number of generation
double Pc=0.6; //probalility of crossover
double Pm=0.001; //probalility of mutation

//The definition of Data Structure


struct individual //data structure of individual 
{
	char chrom[34];//a string of code representing individual

	int value[11]; //object value of this individual
	double fitness; //fitness value of this individual 
};

//The definition of Global Variables 
int CHROMLENGTH=33;
int	LENGTH=3;
int generation; //number of generation
int best_index; //index of best individual
int worst_index;//index of worst individual

struct individual bestindividual;
//best individual of current generation
struct individual worstindividual; 
//worst individual of current generation
struct individual currentbest ; //best individual by now 
struct individual population [POPSIZE]; //population
//Declaration of Prototype

void GenerateInitialPopulation (void);
void GenerateNextPopulation (void );
void EvaluatePopulation (void);
long DecodeChromosome (char*,int,int);
void CalculateObjectValue(void);
void CalculateFitnessValue(void);
void FindBestAndWorstIndividual(void);
void PerformEvolution(void);
void SelectionOperator(void);
void CrossoverOperator(void);
void MutationOperator(void);
void OutputTextReport(void);

//main program

void main(void)
{
	generation=0;
	GenerateInitialPopulation();
	EvaluatePopulation();
	while(generation<MaxGeneration)
	{
		generation++;
		GenerateNextPopulation();
		EvaluatePopulation();
		PerformEvolution();
		OutputTextReport();
	}
	cout<<"d11="<<currentbest.value[10]<<" ";
	cout<<"d10="<<currentbest.value[9]<<" ";	
	cout<<"d9="<<currentbest.value[8]<<" ";
	cout<<"d8="<<currentbest.value[7]<<" ";
	cout<<"d7="<<currentbest.value[6]<<" ";
	cout<<"d6="<<currentbest.value[5]<<" ";
	cout<<"d5="<<currentbest.value[4]<<" ";
	cout<<"d4="<<currentbest.value[3]<<" ";
	cout<<"d3="<<currentbest.value[2]<<" ";
	cout<<"d2="<<currentbest.value[1]<<" ";
	cout<<"d1="<<currentbest.value[0]<<" ";
}
 
//Function:Generate the first population.
//Variable:None

void GenerateInitialPopulation(void)
{
	int i,j;

	//randomize();
	srand(time(0));
	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';
	}
}

//Function; Initialize the next generation.
//Variable:None.

void GenerateNextPopulation(void)
{
	SelectionOperator();
	CrossoverOperator();
	MutationOperator();
}

//Function:Evaluate population according to certain formula.
//Variable; None.

void EvaluatePopulation(void)
{
	CalculateObjectValue(); //Calculate object value
	CalculateFitnessValue();//calculate fitness value
	FindBestAndWorstIndividual();//find the best and worst individual
}

//Function:To decode a binary chromosome into a decimal integer.
//Varible:None.
//Note; The returned value may be plus,of minus.
//For different coding method,this value may 
//be changed int "undigned int".
long DecodeChromosome(char *string ,int point,int length)
{
	int i;
	long decimal=0L;
	char*pointer;

	for(i=0,pointer=string+point;i<length;i++,pointer++)
	{if(*pointer-'0')
	decimal +=(long)pow(2,i);
	}
	return (decimal);

}

//Function :to calculate objectvalue
//Variable: None.
void CalculateObjectValue(void)
{
	int i;
	int temp[32];
	//Rosebrock function 
	for (i=0; i<PopSize; i++)
	{
		for (int j=0;j<11;j++)//初始化
		{population[i].value[j]=0;}

		for (int k=0;k<11;k++) //解瑪
		{temp[k]=DecodeChromosome(population[i].chrom,k*LENGTH,LENGTH);}

		for (int m=0;m<11;m++)//賦值
		{if(temp[m]=0) temp[m]=20;
         if(temp[m]=1) temp[m]=25;
         if(temp[m]=2) temp[m]=32;
         if(temp[m]=3) temp[m]=40;
         if(temp[m]=4) temp[m]=50;
         if(temp[m]=5) temp[m]=65;
         if(temp[m]=6) temp[m]=80;
         if(temp[m]=7) temp[m]=100;
		}

		for(int l=0;l<11;l++) //賦值 
		{population[i].value[l]=temp[l];}

	}
}

//Function:To calculate fitness value.
//Variable:None.

void CalculateFitnessValue(void)
{
	int i,a,b,t;
	int A[11]={0};
	double temp1=0;
	double k0,k1,k2,k3,k4,k5,k6,k7,k8,k9,k10;
	
	for (i=0;i<PopSize; i++)
	{
		for(a=1;a<11;a++)
			for(b=10;b>=a;b--)
			{if(population[i].value[b-1]>population[i].value[b])
			{
				t=population[i].value[b-1];
				population[i].value[b-1]=t;
			}
			}

			for (int j=0;j<11;j++)
			{A[j]=population[i].value[j];}

			k0=A[0];k1=A[1];k2=A[2];k3=A[3];k4=A[4];k5=A[5];k6=A[6];k7=A[7];k8=A[8];k9=A[9];k10=A[10];
			
			temp1=0.00197*(100*(pow((double)k0,1.53)+pow((double)k3,1.53)+pow((double)k1,1.53)+pow((double)k4,1.53)+
				pow((double)k2,1.53)+pow((double)k5,1.53))+50*(pow((double)k7,1.53)+pow((double)k8,1.53))+160*pow((double)k6,1.53)+
				110*pow((double)k9,1.53)+90*pow((double)k10,1.53))+391/pow((double)150,1.852)*(pow((double)11,1.852*(100/pow((double)k0,4.871)+
				100/pow((double)k3,4.872)+160/pow((double)k6,4.871)+100/pow((double)k1,4.871)+100/pow((double)k4,4.871)+50/pow((double)k7,4.871)+
				100/pow((double)k2,4.871)+100/pow((double)k5,4.871)+50/pow((double)k8,4.871))+110*pow((double)22,1.852)/pow((double)k9,1.852)+
				90*pow((double)33,1.852)/pow((double)k10,4.871)));

			if ((pow((double)33,1.75)/pow((double)k10,4.75)*90+pow((double)22,1.75)/pow((double)k9,4.75)*110+pow((double)11,1.75)/pow((double)k6,4.75)*160+
				pow((double)11,1.75)/pow((double)k3,4.75)*100+pow((double)11,1.75)/pow((double)k0,4.75)*100)<=9.4&&(pow((double)33,1.75)/pow((double)k10,4.75)*90+
				pow((double)22,1.75)/pow((double)k9,4.75)*110+pow((double)11,1.75)/pow((double)k7,4.75)*50+pow((double)11,1.75)/pow((double)k4,4.75)*100+
				pow((double)11,1.75)/pow((double)k1,4.75)*100)<=11.4&&(pow((double)33,1.75)/pow((double)k10,4.75)*90+pow((double)11,1.75)/pow((double)k8,4.75)*50+
				pow((double)11,1.75)/pow((double)k5,4.75)*100+pow((double)11,1.75)*100)<=13.2)

				population[i].fitness=10000-temp1;
			else
				population[i].fitness=0;
	}
}

//Function :to find out the best individual so far current generation.
//Varialbe:None.

void FindBestAndWorstIndividual(void)
{
	int i;
	//find out the best and worst individual of this generation
	bestindividual=population[0];
	worstindividual=population[0];

	for (i=1;i<PopSize; i++){
		if (population[i].fitness>bestindividual.fitness){
			bestindividual=population[i];
			best_index=i;

			for (int j=0;j<11;j++)
			{bestindividual.value[j]=population[i].value[j];}
		}
		else if (population[i].fitness<worstindividual.fitness){
			worstindividual=population[i];
			worst_index=i;
			for (int k=0;k<11;k++)
			{worstindividual.value[k]=population[i].value[k];}
		}
	}

	//find out the best individual so far 
	if (generation==0){//initialize the best individual
		currentbest=bestindividual;
	}
	else{
		if(bestindividual.fitness>=currentbest.fitness){
			currentbest=bestindividual;
		}
	}
}


//function:to perform evolution operation based on elitise
//model.Elitist model is to replace the worst individual of this generation by the current best one.
//Variable:None

void PerformEvolution(void)
{
	if (bestindividual.fitness>currentbest.fitness){
		currentbest=population[best_index];
	}
	else{
		population[worst_index]=currentbest;
	}
}

//Function: to reproduce a chromosone by proportional selection,
//Variable:None.

void SelectionOperator(void)
{
	int i,index;
	double p,sum=0.0;
	double cfitness[POPSIZE];//cumulative fitness value

	struct individual newpopulation[POPSIZE];
	
	//calculate relative fitness
	for(i=0;i<PopSize; i++){
		cfitness[i]=population[i].fitness/sum;
	}

	//calculate cumulative fitness
	for(i=1;i<PopSize; i++){
		cfitness[i]=cfitness[i-1]+cfitness[i];
	}

	//selection operation
	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];
	}
}

//Function :Crossover two chromosone by means
// of one-point crossover;
//variable:None.

void CrossoverOperator(void)
{
	int i,j;
	int index[POPSIZE];
	int point,temp;
	double p;
	char ch;

	//make a pair of individual randomly
	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;
	}

	//one-point crossover operation
	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;
			}
		}
	}
}

//Function:mutation of a chromosome.
//Variable:None.

void MutationOperator(void)
{
	int i,j;
	double p;
	//bit mutation
	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';
			}
		}
	}
}

//Function :output the results of current population.
//Variable :None,

void OutputTextReport(void)
{
	int i;
	printf("gen=%d",generation);
	for (i=0;i<CHROMLENGTH;i++)
	{
		cout<<currentbest.chrom[i];
	}
	printf("\n");
}