/*
   This program applies the genetic algorithm as a demonstration
   in a rather useless problem.  Given an input string of letters and
   spaces, it makes a random population of strings of the same length
   and then tries to "evolve" a string that is equal to the input string.
   Each string in the population is assigned a "fitness" value.  Then the
   strings "reproduce" to make a new population.  Strings with higher 
   than average fitness are more likely to have more offspring in the
   new generation.  Some genetic operators (mutation and cross-over)
   are applied to the new generation.  This process is repeated until the
   original input string has been duplicated.  As the process proceeds, 
   each time a string is found that has higher fitness than all previous
   stings, that string is output along with its fitness and the number 
   of the current generation.  In practice, this only works on fairly
   short strings.
*/

#include <iostream>
#include <string>
#include <cstdlib>
#include <ctime>

const int POPULATION_SIZE = 100;  // (program assumes that this is an even number)

const double MUTATION_PROBABILITY = 0.1;

const double CROSSOVER_PROBABILITY = 0.9;

inline double rand_real() {
   return rand() / (RAND_MAX + 1.0);
}


int main() {

   string goal;
   int length;
   string population[POPULATION_SIZE];
   int fitness[POPULATION_SIZE];
   int maxfitness = 0;
   int generation = 0;

   
   srand(time(0));  // Initialize random number generator.

   // Get the input string.

   cout << "\nEnter the string that is goal.  Letters and spaces only,\n";
   cout << "Lower case letters will be transformed to upper case.\n\n";
   cout << "? ";
   getline(cin,goal);
   length = goal.length();
   cout << endl;
   
   // Change lower case letters in goal to uppercase.  Also, change
   // anything that is not a space or a letter to a space.
   
   for (int i = 0; i < length; i++) {
      if (goal[i] >= 'a' && goal[i] <= 'z')
         goal[i] = goal[i] - 'a' + 'A';
      else if (goal[i] < 'A' || goal[i] > 'Z')
         goal[i] = ' ';
   }
   
   // Produce an initial population of random strings.  Each string
   // will have just as many characters as the goal string.  Each
   // character is chosen at random to be a space or upper case letter.

   for (int i = 0; i < POPULATION_SIZE; i++) {
          // Construct string number i.
      for (int j = 0; j < length; j++) {
              // Pick a random character, and add it onto population[i].
         int r = rand() % 27;  // A random number in the range 0 to 26.
         if (r == 26)
            population[i] += ' ';
         else
            population[i] += (char)(r + 'A');
      }
   }

   cout << "Generation  Fitness    String\n";
   cout << "----------  ---------  --------------------------------------\n";
   
   while (maxfitness < length+1) {

      int totalfitness = 0;   // The sum of the fitness values of all
                              //   strings in the population.

      int maxfit;   // The index in the population array of a string
                    //   of maximal fitness.

      generation++;
      
      // Compute the fitness of each string.  The fitness is one plus the
      // number of characters in the string that match a character in the 
      // input string in the same location.  The 1 is added so that the
      // fitness will be greater than zero.  Also, add up the fitness values
      // to obtain a total fitness, and keep track of the location in the
      // population array of a string of maximal fitness.

      for (int i = 0; i < POPULATION_SIZE; i++) {
         int x = 1;  // This will be the fitness of the i-th string.
         for (int j = 0; j < length; j++)
            if (population[i][j] == goal[j])
               x++;
         totalfitness += x;
         fitness[i] = x;
         if (i == 0 || x > fitness[maxfit])
            maxfit = i;
      }
      
      // If we are seeing a new overall maximum fitness, output the
      // string, along with the generation number and the fitness score
      // of that individual.

      if (fitness[maxfit] > maxfitness) {
         cout.width(7);
         cout << generation;
         cout.width(11);
         cout << fitness[maxfit];
         cout << "     \"" << population[maxfit] << "\"\n";
         maxfitness = fitness[maxfit];
      }
      
      // Reproduction:  Copy strings from the current population into
      // a new population array.  To get a string for the new population,
      // select a string from the current population at random.  The
      // probability that a given string will be chosen is proportional
      // to its fitness.  (Getting this right was rather touchy.)

      string newpopulation[POPULATION_SIZE];

      for (int i = 0; i < POPULATION_SIZE; i++) {
         int r = rand() % totalfitness;
         int f = fitness[0];
         int j = 0;
         while (j < 99 && f < r) {
            j++;
            f += fitness[j];
         }
         newpopulation[i] = population[j];
      }

      // Mutation:  Each string in the new population has a probability
      // of MUTATION_PROBABILITY of being mutated.  To mutate a string,
      // one of its characters is selected at random and is changed to
      // a random character.

      for (int i = 0; i < POPULATION_SIZE; i++) {
         if (rand_real() <= MUTATION_PROBABILITY) {
               // Mutate string number i.
            int p = rand() % length;  // Random position in the string.
            int x = rand() % 27;   // Random number in range 0 to 26.
            if (x == 26)
               newpopulation[i][p] = ' ';
            else
               newpopulation[i][p] = x + 'A';
         }
      }
      
      // Crossover:  Each pair of strings has a probability of 
      // CROSSOVER_PROBABILITY of being crossed over.  When a crossover
      // is applied to a pair of strings, a random position is chosen
      // and the "tails" of the strings, consisting of all chars after
      // that position, are swapped.

      for (int i = 0; i < POPULATION_SIZE; i += 2) {
         if (rand_real() < CROSSOVER_PROBABILITY && i+1 < POPULATION_SIZE) {
            int p = rand() % length;
            for (int j = p+1; j < length; j++) {
               char temp = newpopulation[i][j];
               newpopulation[i][j] = newpopulation[i+1][j];
               newpopulation[i+1][j] = temp;
            }
         }
      }
      
      // Copy the new population back into the population array
      // to get ready for the next generation.

      for (int i = 0; i < POPULATION_SIZE; i++)
         population[i] = newpopulation[i];

   }

}