/*
 *  take-over-2.c
 *
 *  Experiment with selection pressure of different selection methods
 *  based on take-over time
 */

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

#define random_int(num) (rand()%(num))
#define random_01() ((double)rand()/(double)RAND_MAX)
#define randomize() srand((unsigned)time(NULL))

/* Data and variable declaration section ***********************/

// value of POPULATION_SIZE
#define POPULATION_SIZE 100

// the number of repetitions should be statisticaly significant
// for stochastic based operations
#define REPETITIONS     10000

// length of selection chain 
#define MAX_GENERATIONS 75

// representation of individuals
#define NAMEBEST  1     // identification of the best individuals
#define NAMEOTHER 0     // identification of less fitted individuals
struct individual {
  int   name;           // individual identification
  float fitness;
};

// representation of populations of individuals
struct individual population[POPULATION_SIZE];     // actual
struct individual tmp_population[POPULATION_SIZE]; // temporary


/* Code section ************************************************/

// Deterministic fitness distribution
//   one individual with fitness 1.0, the others with fitness 0.5
void fitness_distribution_1() {
  int i;

  for(i = 0; i < POPULATION_SIZE-1; i++) {
    population[i].fitness = 0.5;
  }
  population[POPULATION_SIZE-1].fitness = 1.0;
}

// Random fitness distribution with fitness from interval <0.0,1.0>
void fitness_distribution_2() {
  int i;

  for(i = 0; i < POPULATION_SIZE-1; i++) {
    population[i].fitness = random_01();
  }
}

// **************************** STUDENT'S PLAYGROUND - PLAY HERE

// This piece of code should select which implementation of
// a particular distribution of fitness values to be used.
//
// Only one of the available options to be uncommented
void fitness_assignment() {
 int i;

 fitness_distribution_1();

 //fitness_distribution_2();

}

// This piece of code should be replaced by an implementation of
// a particular selection method.
// 
// Current version represents a naive selection when the first 
// individual is not selected, the last one is selected 2 times
// and the others are selected one time per individual
void selection(int no_of_selections[]) {
  int i;

  for(i = 1; i < POPULATION_SIZE; i++) {
    no_of_selections[i]++;                              
  }
    no_of_selections[POPULATION_SIZE-1]++;   // the last one more
}

// ******************************** NO CHANGES BEYOND THIS POINT 


// Fitness values initialization for each individual.
// The one with the highest fitness is marked by a special name.
void initialise_population() {
  int i;
  int best_ind;

  fitness_assignment();  // experiment based fitness assignment

  // necessary to find the best individual
  best_ind = 0;
  for(i = 0; i < POPULATION_SIZE; i++) { 
    population[i].name = NAMEOTHER;     // default for everyone
    if(population[i].fitness > population[best_ind].fitness ) {
      best_ind = i;                     // keep the best
    }
  }
  population[best_ind].name = NAMEBEST; // marking the best one
}

// Formation of new generation using selection of individuals
// for survival and formation of the new generation
void new_generation() {
  int i, j, k;

  int no_of_selections[POPULATION_SIZE]; // no of selected individuals
  
  for(i = 0; i < POPULATION_SIZE; i++) {  // inicialization of 
    no_of_selections[i] = 0;              // tmp buffer
  }

  selection(no_of_selections);                 // core of the experiment 

  // make new population
  k = 0;
  for(i = 0; i < POPULATION_SIZE; i++) {       // for each individual ...
    for(j = 0; j < no_of_selections[i]; j++) { // and its each selection ...
                                               // build new tmp population
      tmp_population[k].name = population[i].name;
      tmp_population[k].fitness = population[i].fitness;
      k++;
    }
  }
  for(i = 0; i < POPULATION_SIZE; i++) {     // turn tmp to current generation
    population[i].name = tmp_population[i].name;
    population[i].fitness = tmp_population[i].fitness;
  }
}

// Run evolution process prescribed number of steps
void run_one_experiment(int no_of_best[]) {
  int i, j;

  for(j = 0; j < MAX_GENERATIONS; j++) {
    new_generation();                     // to evolve population
    
    // how many copies of the best individual are there ?
    no_of_best[j] = 0;
    for(i = 0; i < POPULATION_SIZE; i++) {  // scan the population for best
      if(population[i].name == NAMEBEST) {
	no_of_best[j]++;
      }
    }
  }
}

// Experiment is repeated REPETITIONS times due to the 
// stochastic nature of EAs.
void run_repeated_experiment() {
  int i, j;
  int no_of_failures = 0;
  int sum_all[MAX_GENERATIONS];     // summation for all experiments
  int sum_success[MAX_GENERATIONS]; // summation for successes only
  int no_of_best[MAX_GENERATIONS];  // no of copies of the best individual
  
  for(i = 0; i < MAX_GENERATIONS; i++) {
    sum_all[i] = 0;
    sum_success[i] = 0;
  }
  
  for(i = 0; i < REPETITIONS; i++) {
    for(j = 0; j < MAX_GENERATIONS; j++) { // initialize result buffer
      no_of_best[j] = 0;
    }
    
    initialise_population();               // initialise ...
    run_one_experiment(no_of_best);        // ... and perform experiment

    //results processing
    for(j = 0; j < MAX_GENERATIONS; j++) {     // unconditional
      sum_all[j] += no_of_best[j];
    }
    if( no_of_best[MAX_GENERATIONS-1] > 0 ) {  // was it failure ?
      for(j = 0; j < MAX_GENERATIONS; j++) {     // if successful run
	sum_success[j] += no_of_best[j];
      }
    } else {
	no_of_failures += 1;                     // if not successful run
    }
  }

  printf("# Number of failed runs: %i\n",no_of_failures);
  printf("# gen  avg(all)  avg(succ)\n");
  for(j = 0; j < MAX_GENERATIONS; j++) {
    printf("   %2i    %6.2f    %6.2f\n",
	   j+1,
	   (double)sum_all[j]/(double)REPETITIONS,
	   (double)sum_success[j]/(double)(REPETITIONS - no_of_failures));
  }
}

// Program entry point
void main() {

  if( (POPULATION_SIZE < 1) ) {  
    printf("Define values error: POPULTION_SIZE\n");   
    return;
  }
  if( (REPETITIONS < -30) ) {  
    printf("Define values error: REPETITIONS\n");   
    return;
  }
                            // go ahead - run the experiment
  randomize();                     // random generator initialization
  run_repeated_experiment();
}