/* Program Genetic Algorithm To Calculate Maximum f=4x-x^2-4  and -2<=x<=2  By M.Nasef */
#include"stdlib.h"
#include<stdio.h>
#include<math.h>
void Initial_Population();
void CrossOver(int Pop1,int Pop2,int Individual);
void NoCrossOver(int Pop1,int Pop2,int Individual);
void Mutation();
void Replace();
void PrintResult();
void Reorder();
void RandomSorting();
void CrossPoint();
void Replace_Cross();
void FindInteger();
void DefineRange();
void FindReal();
void FindBinary();
void ReplaceBinary();
void FindFitness(int *FittestIndividual,int *WorstIndividual,double *SumFitness,double *MeanFitness);
void Selection(int *Pop,double SumFitness);
void Statistic(int *FittestIndividual,int *WorstIndividual);
void Elite(int *FittestIndividual,int *WorstIndividual);
void OpenFile();
void CloseFile();
#define Max_Generation 50
#define PopulationSize 8 /* Must be even. */
#define TotalStringLength 8
#define MutationProbability 0.07
#define RND  ((double) rand()/((double) RAND_MAX+1))
  char NewStrings[PopulationSize+1][TotalStringLength+1];
  char Strings[PopulationSize+1][TotalStringLength+1];
  char SortingStrings[PopulationSize+1][TotalStringLength+1];
  char CopyStrings[PopulationSize+1][TotalStringLength+1];
  char BestStrings[PopulationSize+1][TotalStringLength+1];
  char BinaryStrings[PopulationSize+1][TotalStringLength+1];
  char BinaryNumber[PopulationSize+1][TotalStringLength+1];
  int PlaceStrings[PopulationSize+1][TotalStringLength+1];
  int NewPlaceStrings[PopulationSize+1][TotalStringLength+1];
  int IntegerNumber[PopulationSize+1];
  double Range[2+1];
  double RealNumber[PopulationSize+1];
  double Fitness[PopulationSize+1];
  FILE *infile,*outfile;
void main (void)
  {
   int Individual,Pop1,Pop2,Generation;
   int FittestIndividual=0;
   int WorstIndividual=0;
   double SumFitness=0;
   double MeanFitness=0;
   OpenFile();
   Generation=1;
   fprintf(outfile," The Generation Is %d \n",Generation);
   Initial_Population();
   FindFitness(&FittestIndividual,&WorstIndividual,&SumFitness,&MeanFitness);
   for(Individual=1;Individual<=PopulationSize/2;Individual++)
   Statistic(&FittestIndividual,&WorstIndividual);
   fprintf(outfile,"\t\t\t\t***************************\n");
   for (Generation=2;Generation<=Max_Generation;Generation++)
    {
     fprintf(outfile,"The Generation Is %d \n",Generation);
     FindBinary();
     ReplaceBinary();
     for(Individual=1;Individual<=PopulationSize;Individual+=2)
      {
	Selection(&Pop1,SumFitness);
	Selection(&Pop2,SumFitness);
	CrossOver(Pop1,Pop2,Individual);
      }
     Mutation();
     Replace();
     FindFitness(&FittestIndividual,&WorstIndividual,&SumFitness,&MeanFitness);
     for(Individual=1;Individual<=PopulationSize/2;Individual++)
     Statistic(&FittestIndividual,&WorstIndividual);
     fprintf(outfile,"\t\t\t\t***************************\n");
    }
     CloseFile();
  }
void Initial_Population()
  {
   int Individual,bit;
  for (Individual=1;Individual<=PopulationSize;Individual++)
    for (bit=1;bit<=TotalStringLength;bit++)
      if (RND > .5)
	Strings[Individual][bit] = 1;
      else
	Strings[Individual][bit] = 0;

  }
void CrossOver(int Pop1 ,int Pop2,int Individual)
  {
     int bit,CrossSite;
     CrossSite = (int) ((TotalStringLength - 1) * RND + 1);
      /* fprintf(outfile,"The CrossOver Point is ");
      fprintf(outfile,"%d ",CrossSite);
      fprintf(outfile,"\n");
      CrossPoint();        */
      for (bit=1;bit<=CrossSite;bit++)
      {
       NewStrings[Individual][bit] = Strings[Pop1][bit];
       NewStrings[Individual+1][bit]= Strings[Pop2][bit];
      }
    for (bit = CrossSite+1;bit<=TotalStringLength;bit++)
      {
       NewStrings[Individual][bit] = Strings[Pop2][bit];
       NewStrings[Individual+1][bit] = Strings[Pop1][bit];
      }
  }
void NoCrossOver(int Pop1 ,int Pop2,int Individual)
  {
     int bit;
    for (bit = 1;bit<=TotalStringLength;bit++)
      {
       NewStrings[Individual][bit] = Strings[Pop1][bit];
       NewStrings[Individual + 1][bit] = Strings[Pop2][bit];
      }
  }
void Mutation()
  {
   int Individual,bit;
   for (Individual=1;Individual<=PopulationSize;Individual++)
    for (bit=1;bit<=TotalStringLength;bit++)
      {
	if (RND <= MutationProbability)
	  if (NewStrings[Individual][bit] == 1)
	    NewStrings[Individual][bit] = 0;
	  else
	    NewStrings[Individual][bit] = 1;
      }
  }
void Replace()
  {
   int Individual,bit;
   for (Individual=1;Individual<=PopulationSize;Individual++)
     for (bit = 1;bit<=TotalStringLength;bit++)
	Strings[Individual][bit] = NewStrings[Individual][bit];
  }
void OpenFile()
  {
  /* infile=fopen("Gen.dat","r");*/
   outfile=fopen("1_Gen.dat","w");
  }
void CloseFile()
  {
   /*fclose(infile);*/
   fclose(outfile);
  }
void PrintResult()
  {
   int Individual,bit;
   for (Individual=1;Individual<=PopulationSize;Individual++)
    {
      fprintf(outfile,"the new parent[%d] is ",Individual);
     for (bit = 1;bit<=TotalStringLength;bit++)
      fprintf(outfile,"%d ",Strings[Individual][bit]);
      fprintf(outfile,"\n");
    }
  }
void Reorder()
  {
    int Individual,bit,j;
    char x;
    Individual=1;
    for(bit=1;bit<=TotalStringLength;bit++)
     SortingStrings[Individual][bit]=Strings[Individual][bit];
      for(bit=1;bit<=TotalStringLength;bit++)
       for (j=1;j<=TotalStringLength-bit;j++)
	if(SortingStrings[Individual][j]>=SortingStrings[Individual][j+1])
	 { x=SortingStrings[Individual][j];
	   SortingStrings[Individual][j]=SortingStrings[Individual][j+1];
	   SortingStrings[Individual][j+1]=x;
	 }
    /*fprintf(outfile,"the sorting matrix\n");
    for(bit=1;bit<=TotalStringLength;bit++)
    fprintf(outfile,"%d,",SortingStrings[Individual][bit]);
    fprintf(outfile,"\n"); */
  }
void RandomSorting()
  {
    int Individual,bit,j;
    Reorder();
    Individual=1;
    for(bit=1;bit<=TotalStringLength;bit++)
     CopyStrings[Individual][bit]=Strings[Individual][bit];
      for(bit=1;bit<=TotalStringLength;bit++)
       {
	for(j=1;j<=TotalStringLength;j++)
	 if(SortingStrings[Individual][bit]!=SortingStrings[Individual][bit+1])
	  {
	   if(SortingStrings[Individual][bit] == CopyStrings[Individual][j])
	    PlaceStrings[Individual][bit]=j;
	  }
	 else if(SortingStrings[Individual][bit]==SortingStrings[Individual][bit+1])
	  {
	   if(SortingStrings[Individual][bit] == CopyStrings[Individual][j])
	    {
	      SortingStrings[Individual][bit]=-1000000;
	      CopyStrings[Individual][j]=-3000000;
	      PlaceStrings[Individual][bit]=j;
	    }
	  }
       }
  }
void CrossPoint()
  {
    int Individual,bit,CrossSite;
    RandomSorting();
    Individual=1;
    /*fprintf(outfile,"Random Order Matrix\n");
    for(bit=1;bit<=TotalStringLength;bit++)
     /*fprintf(outfile,"%d,",PlaceStrings[Individual][bit]);
     fprintf(outfile,"\n");*/
     for(bit=1;bit<=TotalStringLength;bit++)
      if (NewPlaceStrings[Individual][1] == PlaceStrings[Individual][1])
       { PlaceStrings[Individual][bit]=PlaceStrings[Individual][bit+1];
	 CrossSite=PlaceStrings[Individual][1];
       }
      else if (NewPlaceStrings[Individual][1]!=PlaceStrings[Individual][1])
	CrossSite=PlaceStrings[Individual][1];
    /*  fprintf(outfile,"%d ",CrossSite);
      fprintf(outfile,"\n");*/
  }
void Replace_Cross()
  {
    int Individual,bit;
    for (Individual=1;Individual<=PopulationSize;Individual++)
     for(bit=1;bit<=TotalStringLength;bit++)
      NewPlaceStrings[Individual][bit]=PlaceStrings[Individual][bit];
  }
void FindInteger()
  {
    int Individual,bit,NStrings[PopulationSize+1][TotalStringLength+1];
    for (Individual=1;Individual<=PopulationSize;Individual++)
     {
      for(bit=1;bit<=TotalStringLength;bit++)
      NStrings[Individual][bit]=Strings[Individual][TotalStringLength+1-bit];
     /* fprintf(outfile,"The Integer Number Of Parent[%d] is ",Individual);*/
      IntegerNumber[Individual]=0;
      for (bit = 1;bit<=TotalStringLength;bit++)
       {
	if(NStrings[Individual][bit]==1)
	IntegerNumber[Individual]=IntegerNumber[Individual]+pow(2,(bit-1));
       }
     /*  fprintf(outfile,"%d",IntegerNumber[Individual]);
       fprintf(outfile,"\n");*/
     }
  }
void DefineRange()
  {
    Range[1]=-2; /*define lower bound*/
    Range[2]=2; /*define upper bound*/
  }
void FindReal()
  {
    int Individual,bit;
    FindInteger();
    for(Individual=1;Individual<=PopulationSize;Individual++)
     {
   /*  fprintf(outfile,"The Real Number Of Parent[%d]",Individual);*/
       RealNumber[Individual]=Range[1]+IntegerNumber[Individual]*(Range[2]-Range[1])/(pow(2,TotalStringLength)-1);
   /*    fprintf(outfile,"%f",RealNumber[Individual]);
       fprintf(outfile,"\n");*/
     }
  }
void FindFitness(int *FittestIndividual,int *WorstIndividual,double *SumFitness,double *MeanFitness)    /* Calculate the fitness function  f = 4x-x^2-4  -2<=x<=2 */
  {
    int Individual,bit;
    double MaxFitness=-1000000;
    double MinFitness;
    DefineRange();
    FindReal();
    for(Individual=1;Individual<=PopulationSize;Individual++)
     {
       Fitness[Individual]=-pow(RealNumber[Individual],2)+4*RealNumber[Individual]-4;
     /*  fprintf(outfile,"The Fitness Function Of Parent[%d] Is ",Individual);
       fprintf(outfile,"%f",Fitness[Individual]);
       fprintf(outfile,"\n");*/
     }
     (*SumFitness)=0;
     for(Individual=1;Individual<=PopulationSize;Individual++)
    (*SumFitness)=(*SumFitness)+Fitness[Individual];
    (*MeanFitness)=(*SumFitness)/PopulationSize;
   /* fprintf(outfile,"The Sum Of Fitness Is " );
     fprintf(outfile,"%f",(*SumFitness));
     fprintf(outfile,"\n");
      fprintf(outfile,"The Averge Of Fitness Is ");
      fprintf(outfile,"%f",(*MeanFitness));
      fprintf(outfile,"\n");*/
     MinFitness=1000000;
     for(Individual=1;Individual<=PopulationSize;Individual++)
       {
	if(Fitness[Individual]>MaxFitness)
	 {
	  MaxFitness=Fitness[Individual];
	  (*FittestIndividual)=Individual;
	 }
       if(Fitness[Individual]<MinFitness)
	{
	 MinFitness=Fitness[Individual];
	 (*WorstIndividual)=Individual;
  	}
     }
      fprintf(outfile,"The Max f(x)=%f  at x=%f ",Fitness[(*FittestIndividual)],RealNumber[(*FittestIndividual)]);
      fprintf(outfile,"\n");
      /*fprintf(outfile,"The Min Value is %f   at x=%f ",Fitness[(*WorstIndividual)],RealNumber[(*WorstIndividual)]);
      fprintf(outfile,"\n");*/
  }

void Statistic(int *FittestIndividual,int *WorstIndividual)
  {
    int Individual,bit;
    double MaxFitness=-1000000;
    double MinFitness;
    MinFitness=1000000;
     for(Individual=1;Individual<=PopulationSize;Individual++)
       {
	if(Fitness[Individual]>MaxFitness)
	 {
	  MaxFitness=Fitness[Individual];
	  (*FittestIndividual)=Individual;
	 }
       if(Fitness[Individual]<MinFitness)
	{
	 MinFitness=Fitness[Individual];
	 (*WorstIndividual)=Individual;
  	}
     }
      Elite(FittestIndividual,WorstIndividual);
  }
void Selection(int *Pop,double SumFitness)
  {
   int bit;
   double Sum=0;
   int Individual=0;
   double RouletteWheel=RND*SumFitness;
    do
     {
      Individual=Individual+1;
      Sum=Sum+Fitness[Individual];
     }
    while((Sum <= RouletteWheel) && (Individual != PopulationSize));
   (*Pop) = Individual;
  /* fprintf(outfile,"The Best Parent is [%d]",(*Pop));
    fprintf(outfile,"\n");*/
  }
void Elite(int *FittestIndividual,int *WorstIndividual)
  {
   int Individual,bit;
   /*fprintf(outfile," The parent[%d] is Replaced By Parent[%d] \n",(*WorstIndividual),(*FittestIndividual));
   for(bit=1;bit<=TotalStringLength;bit++)
     Strings[*(WorstIndividual)][bit]=Strings[*(FittestIndividual)][bit];*/
   IntegerNumber[*(WorstIndividual)]=IntegerNumber[*(FittestIndividual)];
   RealNumber[*(WorstIndividual)]=RealNumber[*(FittestIndividual)];
   Fitness[*(WorstIndividual)]=Fitness[*(FittestIndividual)];
  }
void FindBinary()
  {
    int Individual,bit;
    for(Individual=1;Individual<=PopulationSize;Individual++)
     for(bit=1;bit<=TotalStringLength;bit++)
      {
       if((IntegerNumber[Individual] % 2) ==1)
	BinaryStrings[Individual][bit]=1;
       else
	BinaryStrings[Individual][bit]=0;
	IntegerNumber[Individual]=IntegerNumber[Individual]/2;
      }
     for(Individual=1;Individual<=PopulationSize;Individual++)
      for(bit=1;bit<=TotalStringLength;bit++)
       BinaryNumber[Individual][TotalStringLength+1-bit]=BinaryStrings[Individual][bit];
    /* fprintf(outfile,"The Binary Numbers are \n");
     for(Individual=1;Individual<=PopulationSize;Individual++)
      {
       for(bit=1;bit<=TotalStringLength;bit++)
	fprintf(outfile,"%d ",BinaryNumber[Individual][bit]);
       fprintf(outfile,"%c",'\n');
      } */
  }
void ReplaceBinary()
  {
   int Individual,bit;
   for (Individual=1;Individual<=PopulationSize;Individual++)
     for (bit = 1;bit<=TotalStringLength;bit++)
	Strings[Individual][bit] = BinaryNumber[Individual][bit];
  }