//GA POLYNOMIAL.CPP
//
//This program uses a genetic algorithm to create a polynomial whichs fits
//a series of points on the x-y plane.
//This is not a good application for a genetic algorithm, but serves as
//a good example of the use of the Population class (and, by extention, of the
//"Chromosome" class.
//
//A polynomial is represented as a series of n bit-strings of length m,
//where n is the order of the polynomial plus one, the kth bit string is the
//coefficient of the k-1 order term in the polynomial, and both n and m
//are chosen by the user.  The first bit of each bit string is the sign, so that
//a bit string of length m can represent an integer with an absolute value up
//to 2^(m-1)-1 (e.g., a four-bit string can be any value from -7 to 7).
//
//NewPopulation extends the Population class template by adding a function
//(coefficientReader) to extract polynomial coefficients from the chromosomes.
//The fitness of a chromosome is the reciprocal of the sum squared error of the
//polynomial generated from that polynomial relative to the input points.
//
//This program is written as a Windows console application.
//
//copyright 1998 Michael J. Wax
//You may use this code and the supporting class declarations and definitions
// as is, or incorporate them into another program,
//as long as proper attribution is given.  However, I make no warranties,
//express or implied, regarding the performance of this code, its freedom from
//error, or its suitability for use in a given application.
//

#include <iostream.h>
#include <stdlib.h>
#include <conio.h>  //Windows console application
#include <math.h>
#include <time.h>
#include "Chromosome.cpp"
#include "Population.cpp"

int numberBits, *bitValue;

//create a derived class to let us do some application-specific operations on
// chromosome populations
template <class geneType>
class NewPopulation : public Population<geneType> {
  public:
    //constructor
    NewPopulation (int populationSize, int chromosomeSize)
      : Population<geneType> (populationSize, chromosomeSize) {}

    //run this before function coefficientReader to set up a lookup table
    void coefficientReaderSetup (int numBits) {
      bitValue = new int[numBits];
      for (int counter = 0; counter < numBits; ++counter) {
        bitValue[counter] = pow(2, counter);
      }
    }

  //this function converts a gene on chromosome "chromosomeNumber" into an integer
  int coefficientReader (int chromosomeNumber, int term) {
	 int a = 0;
    for (int counter = 1; counter < numberBits; ++counter) {
    	a += chromosome[chromosomeNumber].readGene(counter + (term * numberBits)) * bitValue[numberBits-counter-1];
    }
	 if (chromosome[chromosomeNumber].readGene(term*numberBits)) return -a;
	 else return a;
  }
};

int main () {
  srand( (unsigned)time( NULL ) );
  cout << "Polynomial Fit to Arbitrary Points" << endl
       << "Coefficients Determined Using a Genetic Algorithm" << endl;

  //input the coefficients
  int num_points;
  cout << "How many points to fit? ";
  cin >> num_points;
  double *x, *y;
  x = new double[num_points];
  y = new double[num_points];

  for (int counter = 0; counter < num_points; ++counter) {
	 cout << "Enter x, y values of point [" << (counter+1) << "]:  " ;
	 cin >> x[counter] >> y[counter];
  }

  //set up the population
  int numberTerms, num_individuals;
  cout << "How many bits per coefficient? ";
  cin >> numberBits;
  cout << "How many terms in the polynomial? ";
  cin >> numberTerms;
  int *coefficient;
  coefficient = new int[numberTerms];
  cout << "How many individuals in population? ";
  cin >> num_individuals;
  int numberGenes = numberBits * numberTerms;
  NewPopulation<int> population(num_individuals, numberGenes);
  NewPopulation<int> temp(num_individuals, numberGenes);
  population.coefficientReaderSetup(numberBits);

  //display the population
  population.displayPopulation();

  //do the simulation
  int maxgen, generation = 0;
  cout << "Maximum number of generations?  ";
  cin >> maxgen;

  while (generation++ < maxgen) {

    // check fitness of each individual
    for (counter = 0; counter < num_individuals; ++counter) {
      //for each individual, build up an array of coefficients
	   for (int counter2 = 0; counter2 < numberTerms; ++counter2) {
        coefficient[counter2] = population.coefficientReader(counter, counter2);
      }

      //for each point, evaluate the function, and compare with actual
      double scratch = 0;
      for (counter2 = 0; counter2 < num_points; ++counter2) {
        double value = coefficient[numberTerms-1]; //coefficient of x^0
        for (int counter3 = 0; counter3 < (numberTerms-1); ++counter3) {
          value += coefficient[counter3] * pow (double(x[counter2]), double(numberTerms - counter3 - 1));
        }
        scratch += (value-y[counter2]) * (value-y[counter2]);
      }
      population.writeChromosomeFitness(counter, 1/(scratch+1));
    }

    // reproduce most fit individuals with crossover
    population.determineFitness();
    if (generation%20 == 0) {   //pause and show the user what's happening
      population.displayPopulation();
      cout << "Generation " << generation << " fitness = " << population.readFitness() << endl;
      getch();
    }
    if ((generation == maxgen) || ((population.readFitness()/num_individuals) > 0.75)) break;
    population.setSelectionCriteria();

    //reproduce population; store in "temp"
    population.reproduce(temp, doublePoint);

    //now mutate new population, and replace old population with new population
    temp.mutate();
    population = temp;

  } //end of generation

  cout << "Evolution halted after " << generation << " generations." << endl;
  population.quicksort(0, (population.readSize()-1) );
  cout << "The five fittest individuals are:" << endl;
  population.displayPopulation(0, 4);
  cout << "Final population fitness: " << population.readFitness() << endl;
  cout << "The coefficients of fittest individual are:" << endl;
  for (int count = 0; count < numberTerms; ++count) {
    cout << population.coefficientReader(0, count) << " ";
  }
  cout << endl;
  getch();

  return 0;
}