/* ---------------------------------------------------------------------
   LGADOS - A DOS based version of the LGA Genetic Algorithm.

   For Distribution with the book "An Introduction to Genetic Algorithms for
   Scientists and Engineers", World Scientific 1998.

   David A. Coley
   Complex Systems Group
   Physics Building
   University of Exeter
   Exeter
   EX4 4QL
   UK
   email D.A.Coley@exeter.ac.uk

   C Version translated by Thorsten Wanschura

   Please email comments and corrections to D.A.Coley@exeter.ac.uk

   Before using this software please check for updates and corrections at
   http://www.ex.ac.uk/cee/ga

   Version = 17th July 1998

   To try and ensure the two versions read as closely as possible,
   this code has been converted from the BASIC version with the minimum
   number of alterations. If PASCAL had been the starting point the
   form of the code would be somewhat different.

*/

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <time.h>

/* ------- DECLARE ALL THE SUBROUTINES (PROCEDURES) USED BY THE PROGRAM ------- */

void OpenFiles ();
void CloseFiles ();
void Scaling (double ScalingConstant, int FittestIndividual, double * SumFitness , double MeanFitness);
void Elite (double SumFitness, int * FittestIndividual);
void Selection (int *mate, double SumFitness, double MeanFitness);
void CrossOver (int Mate1, int Mate2, int NewIndividual);
void FindFitness ();
void PrintGeneration (int Generation, double MeanFitness, int FittestIndividual);
void DefineRange ();
void FindIntegers ();
void FindUnknowns ();
void InitialPopulation ();
void NoCrossover (int Mate1, int Mate2, int NewIndividual);
void Mutate ();
void Replace ();
void Statistics (double * MeanFitness, double * SumFitness, int * FittestIndividual, int Generation);

enum on_off { on, off };

/* ------- SET ALL THE IMPORTANT FIXED PARAMETERS. ------- */

/* These should be set by the user. */
#define PopulationSize 20  /* Must be even. */
#define NumberOfUnknowns 2
#define SubstringLength 12 /* All sub-strings have the same length.*/
#define TotalStringLength (NumberOfUnknowns * SubstringLength) 
#define MaxGeneration  20 /* G. */
#define CrossOverProbability .6 /* Pc. >=0 and <=1. */
#define MutationProbability  (1.0 / TotalStringLength) /* Pm, >=0 and <1. */
#define SCALINGCONSTANT 1.2 /* A value of 0 implies no scaling.*/
#define Elitism on /* on or off. */


#define RND ((double) rand()/((double) RAND_MAX+1))

/* ------DECLARE ALL SHARED (IE. GLOBAL) VARIABLES---------- */

/* The arrays that hold the individuals within the current population. 
   Note that all arrays are increased by +1, since C convention starts with the index 0 and
   we want to keep the same syntax as in BASIC */
double Unknowns[PopulationSize+1][NumberOfUnknowns+1];
unsigned long int Integers[PopulationSize+1][NumberOfUnknowns+1];
char Strings[PopulationSize+1][TotalStringLength+1];
double Fitness[PopulationSize+1];

/* The new population. */
char NewStrings[PopulationSize+1][TotalStringLength+1];

/* The array that defines the range of the unknowns. */
double Range[2+1][NumberOfUnknowns+1];

/* The best individual in the past generation. Used if elitism is on. */
char EliteString[TotalStringLength+1];
unsigned long int EliteIntegers[NumberOfUnknowns+1];
double EliteFitness;
double EliteUnknowns[NumberOfUnknowns+1];

/* files */
FILE * LGADOSRES;
FILE * LGADOSALL;

/* The main program. */
int main()
{
  int Mate1, Mate2;
  double MeanFitness = 0;
  double SumFitness = 0;
  int FittestIndividual = 0;
  int Generation;
  int NewIndividual;

  DefineRange(); /* Define the range of each unknown. These should also be set by the user.*/

  /* Set the random number generator to so it produces a different set of numbers 
     each time LGADOS is run.
  */
  srand(time(0));
  
  OpenFiles(); /* Open files used to store results. */

  /* ------- START OF THE GENETIC ALGORITHM ------- */

  /* ------- CREATE AN INITIAL POPULATION, GENERATION 1 ------ */

  Generation = 1;

  InitialPopulation();  /* Build a population of strings at random. */

  FindFitness();  /* Find the fitness of each member of the population. */

  Statistics(&MeanFitness, &SumFitness, &FittestIndividual, Generation); /* Find the mean fitness and the fittest individual. */

  PrintGeneration(Generation, MeanFitness, FittestIndividual);  /* Print generation to file. */

  Scaling(SCALINGCONSTANT, FittestIndividual, &SumFitness, MeanFitness); /* If linear fitness scaling is "on" then scale population prior to selection. */

  /* ------- LOOP OVER ALL THE GENERATIONS ------- */

  for (Generation=2;Generation<=MaxGeneration;Generation++)
    {
      for (NewIndividual=1;NewIndividual<=PopulationSize;NewIndividual+=2) /* Loop over the population choosing pairs of mates. */
	{
	  Selection(&Mate1, SumFitness, MeanFitness); /* Choose first mate. */
	  Selection(&Mate2, SumFitness, MeanFitness); /* Choose second mate. */
                                                       
	  /* Pass individuals to the temporary population either with or without performing crossover. */
	  if (RND <= CrossOverProbability) /* Perform crossover. */
	    CrossOver(Mate1, Mate2, NewIndividual);
	  else /* Don't perform crossover. */
	    NoCrossover(Mate1, Mate2, NewIndividual); /* Don't perform crossover. */
	}

      Mutate();  /* Mutate the temporary population. */

      Replace(); /* Replace the old population completely by the new one. */
      
      FindUnknowns(); /* D e-code the new population to integers then real numbers. */

      FindFitness(); /* Find the fitness of each member of the population. */

      Statistics(&MeanFitness, &SumFitness, &FittestIndividual, Generation); /* Find the mean fitness and the fittest individual. */
        
      PrintGeneration(Generation, MeanFitness, FittestIndividual); /* Print generation to file. */

      Scaling(SCALINGCONSTANT, FittestIndividual, &SumFitness, MeanFitness); /* If linear fitness scaling is "on" then scale population prior to selection. */

    } /* Process the next generation. */

  CloseFiles(); /* Close all files */

  return 0;
} /* end of main program */


void CrossOver (int Mate1, int Mate2, int NewIndividual)
     /* Perform single point crossover. */
{
  int CrossSite = (int) ((TotalStringLength - 1) * RND + 1); /* Pick the cross-site at random. */
  
  int bit;
  
  for (bit=1;bit<=CrossSite;bit++) /* Swap bits to the left of the cross-site. */
    {
      NewStrings[NewIndividual][bit] = Strings[Mate1][bit];
      NewStrings[NewIndividual + 1][bit]= Strings[Mate2][bit];
    }

  for (bit = CrossSite + 1;bit<=TotalStringLength;bit++) /* Swap bits to the right of the cross-site. */
    {
      NewStrings[NewIndividual][bit] = Strings[Mate2][bit];
      NewStrings[NewIndividual + 1][bit] = Strings[Mate1][bit];
    }
}

void DefineRange()
     /* Defines the upper and lower bounds of each unknown. 
	Add other ranges using the same format if more than two unknowns in the problem. */
{
  int Unknown;

  Unknown = 1;  /* the first unknown. */
  Range[1][Unknown] = 0;  /* The lower bound. */
  Range[2][Unknown] = 1;  /* The upper bound. */
  
  Unknown = 2; /* the second unknown. */
  Range[1][Unknown] = -3.14159;
  Range[2][Unknown] = 3.14159;

  /* 'Add other ranges if more than two unknowns in your problem. */
}

void Elite(double SumFitness, int * FittestIndividual)
     /*
       Applies elitism by replacing a randomly chosen individual by the elite member
       from the previous population if the new max fitness is less then the previous value.
     */
{
  
  int Individual;
  int bit;
  int Unknown;
  
  if (Fitness[(*FittestIndividual)] < EliteFitness)
    {
      
      Individual = (int)  (PopulationSize * RND + 1); /* Chosen individual to be replaced. */

      for (bit=1;bit<=TotalStringLength;bit++)
	Strings[Individual][bit] = EliteString[bit];
      
      Fitness[Individual] = EliteFitness;
      
      for (Unknown=1;Unknown<=NumberOfUnknowns;Unknown++)
	{
	  Integers[Individual][Unknown] = EliteIntegers[Unknown];
	  Unknowns[Individual][Unknown] = EliteUnknowns[Unknown];
	}
      
      (*FittestIndividual) = Individual;
    }
  
  for (bit=1;bit<=TotalStringLength;bit++)
    EliteString[bit] = Strings[(*FittestIndividual)][bit];
  
  EliteFitness = Fitness[(*FittestIndividual)];
  
  for (Unknown=1;Unknown<=NumberOfUnknowns;Unknown++)
	{
	  EliteIntegers[Unknown] = Integers[(*FittestIndividual)][Unknown];
	  EliteUnknowns[Unknown] = Unknowns[(*FittestIndividual)][Unknown];
	}

}

void FindFitness()
     /* The problem at hand is used to assign a positive (or zero) fitness to each individual in turn. 

	The problem is f = x^2 + sin(y).
     */
{

  int Individual;
  
  for (Individual=1;Individual<=PopulationSize;Individual++)
    Fitness[Individual] = Unknowns[Individual][1]*Unknowns[Individual][1] + sin(Unknowns[Individual][2]);
}


void FindIntegers()
     /* Decode the strings to sets of decimal integers. */
{
  
  int Individual;
  int bit,StringBit;
  int Unknown;
  
  for (Individual=1;Individual<=PopulationSize;Individual++)
    {
      bit = TotalStringLength + 1;
      
      for (Unknown=NumberOfUnknowns;Unknown>=1;Unknown--)
	{
	  Integers[Individual][Unknown] = 0;
	  
	  for (StringBit=1;StringBit<=SubstringLength;StringBit++)
	    {
	      bit = bit - 1;
	      if (Strings[Individual][bit] == 1)
		Integers[Individual][Unknown] = Integers[Individual][Unknown] + (1 << (StringBit - 1) ) ;
	    }
	}
    }

}

void FindUnknowns()
     /*  Decode the strings to real numbers. */
{

  int Individual;
  int Unknown;

  FindIntegers(); /* First decode the strings to sets of decimal integers. */

  /* Now convert these integers to reals. */
  for (Individual=1;Individual<=PopulationSize;Individual++)
    for (Unknown=1;Unknown<=NumberOfUnknowns;Unknown++)
      Unknowns[Individual][Unknown] = Range[1][Unknown] + Integers[Individual][Unknown] * (Range[2][Unknown] - Range[1][Unknown]) / ( (1 << SubstringLength) - 1);
}

void InitialPopulation()
     /* Create the initial random population.*/
{
  int Individual;
  int 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;
  
  FindUnknowns();  /* Decode strings to real numbers. */
}


void  Mutate()
     /* Visit each bit of each string very occasionally flipping a "1" to a "0" or visa versa. */

{

  int Individual;
  int bit;

  for (Individual=1;Individual<=PopulationSize;Individual++)
    for (bit=1;bit<=TotalStringLength;bit++)
      {
	/* Throw a random number and see if it is less than or equal to the mutation probability.*/
	if (RND <= MutationProbability) /* Mutate. */
	  if (NewStrings[Individual][bit] == 1)
	    NewStrings[Individual][bit] = 0;
	  else
	    NewStrings[Individual][bit] = 1;
      }
}



void  NoCrossover (int Mate1, int Mate2, int NewIndividual)
     /* Pass the selected strings to the temporary population without applying crossover. */
{
  int bit;
  
  for (bit=1;bit<=TotalStringLength;bit++)
    {  
      NewStrings[NewIndividual  ][bit] = Strings[Mate1][bit];
      NewStrings[NewIndividual+1][bit] = Strings[Mate2][bit];
    }
}

void OpenFiles()
     /* Open result files. See Chapter 2 for a description of their contents. */

{
  LGADOSRES=fopen("LGADOS.RES","a");  /* **** Change append. */
  LGADOSALL=fopen("LGADOS.ALL","w");
}

void CloseFiles()
     /* Close results files. */
{
  fclose(LGADOSALL);
  fclose(LGADOSRES);
}

void PrintGeneration(int Generation, double MeanFitness, int FittestIndividual)
     /* Print results to the screen and the files. */
{
  int Individual;
  int bit;
  int Unknown;

  printf("%i, %f, %f\n", Generation, Fitness[FittestIndividual], MeanFitness);  /* Screen. */
  fprintf(LGADOSRES,"%i, %f, %f\n", Generation, Fitness[FittestIndividual], MeanFitness);  

  for (Unknown=1;Unknown<=NumberOfUnknowns;Unknown++)
    {
      printf("%f ",Unknowns[FittestIndividual][Unknown]); /* Screen. */
      fprintf(LGADOSRES,"%f ",Unknowns[FittestIndividual][Unknown]); /* Screen. */
    }
  
  printf("\n");
  fprintf(LGADOSRES,"\n");

  for (Individual=1;Individual<=PopulationSize;Individual++) /****** turn back on. */
    {
      fprintf(LGADOSALL,"%i , %f \n", Generation,Fitness[Individual]); /* File LGADOS.ALL */
      
      for (Unknown=1;Unknown<=NumberOfUnknowns;Unknown++)
	fprintf(LGADOSALL,"%f\n", Unknowns[Individual][Unknown]); /* File LGADOS.ALL */
      
      for (bit = 1;bit<=TotalStringLength;bit++)
	fprintf(LGADOSALL,"%1i",Strings[Individual][bit]); /* File LGADOS.ALL */
      fprintf(LGADOSALL,"\n");
    }
  fprintf(LGADOSALL,"\n");
}


void Replace()
     /*  Replace the old population with the new one. */
{
  int Individual;
  int bit;

  for (Individual=1;Individual<=PopulationSize;Individual++)
    for (bit = 1;bit<=TotalStringLength;bit++)
      Strings[Individual][bit] = NewStrings[Individual][bit];
}

void Scaling (double ScalingConstant, int FittestIndividual, double *SumFitness, double MeanFitness)
     /* Apply Linear Fitness Scaling,
	scaledfitness = a * fitness + b.
	Subject to,
	meanscaledfitness = meanfitness
	and
	bestscaledfitness = c * MaxFitness,
	where c, the scaling constant, is set by the user.

	If the scaling constant is set to zero, or all individuals have the same
	fitness, scaling is not applied.
     */
{

  int Individual;

  double a,b;

  if ( (ScalingConstant != 0.0) && (Fitness[FittestIndividual] - MeanFitness) > 0)
    /* Find a and b. */
    {
      a = (ScalingConstant - 1) * MeanFitness / (Fitness[FittestIndividual] - MeanFitness);
      
      b = (1 - a) * MeanFitness;
      
      /* Adjust the fitness of all members of the population. */
      (*SumFitness) = 0;

      for (Individual=1;Individual<=PopulationSize;Individual++)
	{
	  Fitness[Individual] = a * Fitness[Individual] + b;
	  if (Fitness[Individual] < 0) Fitness[Individual] = 0.0; /* Avoid negative values near the end of a run. */
	  (*SumFitness) = (*SumFitness) + Fitness[Individual]; /*  Adjust the sum of all the fitnesses. */
	}
      /* Adjust the mean of all the fitnesses. */
      MeanFitness = (*SumFitness) / PopulationSize;
    }
}

void Selection (int *mate, double SumFitness, double MeanFitness)
     /* Select a single individual by fitness proportional selection. */
     
{
  double Sum = 0;
  int Individual = 0;

  double RouletteWheel = RND * SumFitness;
  
  do 
    {
      Individual = Individual + 1;
      Sum = Sum + Fitness[Individual];
    }

  while ( (Sum < RouletteWheel) && (Individual != PopulationSize) );
  
  (*mate) = Individual;

}

void Statistics (double * MeanFitness, double * SumFitness, int * FittestIndividual, int Generation)
     /* Calculate the sum of fitness across the population and find the best individual, 
	then apply elitism if required. */

{

  int Individual;

  double MaxFitness = 0;

  (*FittestIndividual) = 0;
  
  for (Individual=1;Individual<=PopulationSize;Individual++)
    {
      if (Fitness[Individual] > MaxFitness)
	{
	  MaxFitness = Fitness[Individual];
	  (*FittestIndividual) = Individual;
	}
      
    }

  if (Elitism == on)  /* Apply elitism. */
    Elite((*SumFitness), FittestIndividual);
  
  (*SumFitness) = 0;  /* Sum the fitness. */
  
  for (Individual=1;Individual<=PopulationSize;Individual++)
    (*SumFitness) += Fitness[Individual];


  /*  Find the average fitness of the population. */
  (*MeanFitness) = (*SumFitness) / (double) PopulationSize;
}