//Simple Genetic Algorithm 
#include <stdio.h> 
#include <stdlib.h> 
#include <time.h>
// The Definition of Constant 
#define POPSIZE 500 // population size 
#define MAXIMIZATION 1 // maximization flag 
#define MINIMIZATION 2 // minimization flag 
// The Definition of User Data 
// (For different problem, there are some difference. ) 
#define Cmax 100 // certain maximal value 
#define Cmin 0 // certain minimum value
#define LENGTH1 10 //the chromosome length of 1st variable
#define LENGTH2 10 //the chromosome length of 2nd variable
#define CHROMLENGTH LENGTH1+LENGTH2 //total length of chromosome
int FunctionMode=MAXIMIZATION; //optimization type
int PopSize =80; //population size
int MaxGeneration=200; // max number of generation 
double Pc=0.6; //probability of crossover
double Pm=0.001; //probability of mutation 

// The Definition d Data Structure 
struct individual // data structure of individual
{
char chrom[ CHROMLENGTH + 1 ]; // a string of code representing individual
double value; // object value of this individual
double fitness; // fitness value of this individual
};
// The Definition of Global Variables
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 gentration
struct individual worstindividual; //worst individual of current gentration
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 FindBestAndWorstlndividual (void); 
void PerformEvolution (void); 
void SelectionOperator (void); 
void CrossoverOperator (void); 
void MutationOperator (void); 
void OutputTextReport (void); 

// main program . 
void main ( )
{
generation = 0;
GenerateInitialPopulation();
EvaluatePopulation();
while(generation<MaxGeneration)
{
generation++;
GenerateNextPopulation();
EvaluatePopulation();
PerformEvolution();
OutputTextReport();
}
}

void GnerateInitialPopulation (void)
{
int i,j;
randomize( );
for (i = 0; i< PopSize; i ++)
{
for (i = 0; j < CHROMLENGTH; j++)
{
population [ i ] . chrom [ j ]=(random(10)<5)? '0': '1';
}
population [i].chrom [ CHROMLENGTH]='\0';
}
}

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

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

DecodeChrnmosome (char * string, int point, int length)
{
int i;
long decimal=0L;
char * pointer;
for( i = 0, pointer = string + point; i < length; i + +,pointer++)
{
decimal + = (*pointer- '0' )< < (length-1-i); 
}
return (decimal);
}

//this example is dealing with Rosenbrock function.
//it is defined as:
//f(x1,x2)=100*(x1*x1-x2)*(x1*x1-x2)+(1-x1)*(1-x1)
void CalculateObjectValue()
{
int i;
long temp1,temp2;
double x1,x2;
//Rosenbrock function
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 SelectionOperator
{
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++) sum+=population[i].fitness;
for(i=0;i<PopSize;i++) cfitness[i]=population[i].fitness/sum;
for(i=0;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=random(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=random(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 OutputTextReport()
{
int i;
double sum;
double average;
sum=0.0;
for(i=0;i<PopSize;i++) sum+=population[i].value;
average=sum/PopSize;

printf("gen=%d,avg=%f,best=%f,",generation,average,currentbest.value);
printf("chromosome=");
for(i=0;i<CHROMOLENGTH;i++) printf("%c",currentbest,chrom[i]);
printf("\n");
}