//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
#include
#include //Windows console application
#include
#include
#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 NewPopulation : public Population {
public:
//constructor
NewPopulation (int populationSize, int chromosomeSize)
: Population (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 population(num_individuals, numberGenes);
NewPopulation 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;
}