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


#define MIN_RANGE       -3
#define MAX_RANGE        5

double function(double value){
  return pow((double)value,2.0);          // x^2 
}


#define rand_int(num) (rand()%(num))
#define rand_real()   ((double)rand()/(double)RAND_MAX)
#define randomize()   srand((unsigned)time(NULL))


#define POPULATION_SIZE  15
#define LENGTH           10
#define MAX_GEN          100
#define PMUT             0.2    // < 0.0 , 1.0 >


struct individual{
  unsigned char body[LENGTH];
  double fitness;
};

struct individual population[POPULATION_SIZE];
struct individual new_population[POPULATION_SIZE];


double decode(struct individual* group,int index){
  int i;
  double value;

  value = 0.0;
  for( i=0; i<LENGTH; i++ )
    value += pow(2.0, (double)i) * group[index].body[LENGTH-1-i];

  value = (MAX_RANGE - MIN_RANGE) * value / ( pow(2.0,LENGTH) - 1.0 );
  value += MIN_RANGE;

  return value;
}


void generate(void){
  int i, j;

  for( i=0; i<POPULATION_SIZE; i++ )
    for( j=0; j<LENGTH; j++ )
      population[i].body[j] = rand_int(2);
}


void evaluate(struct individual* group ){
  int i;

  for( i=0; i<POPULATION_SIZE; i++ )
    group[i].fitness = function(decode(group,i));
}


void initialise(void){
  generate();
  evaluate(population);
}


void select_parents(void){
  int i, j, index;
  double r, parsum, sum_fitness;

  sum_fitness = 0.0;
  for( i=0; i<POPULATION_SIZE; i++ )
    sum_fitness += population[i].fitness;

  for( i=0; i<POPULATION_SIZE; i++ ){
    r = rand_real() * sum_fitness;

    parsum = population[0].fitness;
    index = 0;
    while(parsum < r) {
      index++;
      parsum += population[index].fitness;
    }

    for( j=0; j<LENGTH; j++ )
      new_population[i].body[j] = population[index].body[j];
  }
}


void go(void){
  int i, j;

  for( i=0; i<POPULATION_SIZE; i++ )
    for( j=0; j<LENGTH; j++ )
      if( rand_real()<PMUT )
        new_population[i].body[j] = (new_population[i].body[j] + 1) % 2;
}


void reproduce(void){
  select_parents();
  go();
  evaluate(new_population);
}


void replace(void){
  int i, i2, j;

  for( i=0; i<POPULATION_SIZE; i++ ){

    for( i2=0; i2<POPULATION_SIZE; i2++ ){
      if( new_population[i].fitness > population[i2].fitness){
        for( j=0; j<LENGTH; j++ )
          population[i2].body[j] = new_population[i].body[j];
        population[i2].fitness = new_population[i].fitness;
        break;
      }
    }
  }
}


double old_avg_fitness = 0.0;

int satisfied(int generation){
  int i;
  double avg_fitness;

  avg_fitness = 0.0;
  for( i=0; i<POPULATION_SIZE; i++ )
    avg_fitness += population[i].fitness;
  avg_fitness /= POPULATION_SIZE;

  if(( generation >= MAX_GEN ) ||
     ( avg_fitness/old_avg_fitness < 1.005))
    return 0;
  old_avg_fitness = avg_fitness;
  return 1;
}


void statistics(int generation)
{
  int i, j;
  double avg_fitness;

  avg_fitness = 0.0;
  for( i=0; i<POPULATION_SIZE; i++ )
    avg_fitness += population[i].fitness;
  avg_fitness /= POPULATION_SIZE;

  printf("\n;Generation: %d\n",generation);
  printf("; X\t\tf(x)\t\t\tstring");
  for( i=0; i<POPULATION_SIZE; i++ ) {
    printf("\n %f\t%f\t;\t", decode(population,i), population[i].fitness);
    for( j=0; j<LENGTH; j++ )
      printf(" %d",population[i].body[j]);
  }

  printf("\nImprovement: %f\nAvg.fitness: %f\tOld avg.fitness: %f\n",
         avg_fitness/old_avg_fitness, avg_fitness, old_avg_fitness);
}


int main(void){
  int generation = 0;

  randomize();

  initialise();
  statistics(generation);

  generation++;

  while( satisfied(generation)){
    reproduce();
    replace();

    statistics(generation);

    generation++;
  }
  return 0;
}