Genetic Algorithm Implementation

A very simple version of a GA for search and optimisation may be implemented as follows:

#include <iostream.h>
#include <stdlib.h>

#define unsigned char UCHAR;
#define unsigned short USHORT;

#define DEFAULT_MUTATION_PROB  0.1
#define DEFAULT_CROSSOVER_PROB 0.5

// CLASS for an individual 

class Individual {
private:
  UCHAR* chr;                 // pointer to the chromosome
  USHORT chr_sz;              // size of the chromosome
  double f;                   // fitness value
  float pm;                   // mutation rate
protected:                    // fitness function pointer
  double (*Fit_Func) (UCHAR*);
public:
  Individual (USHORT size, double (*F)(UCHAR*)); // constructor
  ~Individual (void) {delete [] chr;};           // destructor
  Individual& operator= (Individual& I);         // copy
  UCHAR&      operator[] (unsigned idx) {        // index of chr
                return *(chr+idx);};
  void Init (void);           // initiate individual
  void Mutate (void);         // mutate individual
  void Prn_F  (void) {cout << f << " ";};  // print out fitness
  double Eval (void) {f = Fit_func(chr);}; // determine fitness
  double F    (void) {return f;};
  UCHAR* X    (void) {return char;};
};
// STANDARD CONSTRUCTOR
Indidvidual::Individual (USHORT size, double (*F) (UCHAR*)) {
  : chr_sz(size) {
  Fit_Func = F;               // set up fitness funciton pointer
  chr = new UCHAR [chr_sz];   // create new chromosome
  pm = DEFAULT_MUTATION_PROB;
}
// COPY OPERATOR
Individual& Individual::operator= (Individual& I) {
  if (this != &I) {           // if I is not this I
    delete [] chr;            // delete old I
    chr_sz = I.chr_sz;        // create new one 
    pm = I.pm;                // and copy objects
    Fit_Func = I.Fit_Func;
    chr = new UCHAR [chr_sz];
    for (int i=0; i<chr_sz; i++)
      *(chr+i) = *(I.chr+i);
  }
  return *this;
}
// INITIALIZE INVID
void Individual::Init (void) {
  for (int i=0; i<chr_sz; i++) 
    chr[i] = (UCHAR) rand ();
}
// MUTATION -- because 8 bit are treated together the mutation of
// one bit is a bit more complicated
void Individual::Mutate (void) {
  UCHAR mask;
  for (int i=0; i<chr_sz; i++) {
    mask = 0;
    for (int j=0; j<8; j++) {
      mask <<= 1;
      if (rand () % 1000 < pm * 1000)
        mask += 1;
    }
    chr[i] ^= mask;
  }
}
  
// CLASS FOR A POPULATION

class Population {
private:
  Individual* Pa;         // pointer to parents
  Individual* Ch;         // pointer to children
  USHORT pa_sz;           // number of pa
  USHORT ch_sz;           // number of ch
  USHORT iv_sz;           // size of chromosome
  float pc;               // crossover probab
protected:
  void Cross (UCHAR* p1, UCHAR* p2);
  void Sort  (Individual* p, USHORT sz);
public:
  Population (USHORT p_sz, USHORT c_sz, 
              USHORT i_sz, double (*F) (UCHAR*));
  ~Population (void) {delete [] Pa;};
  void Init   (void);      // init population
  void Prn_F  (void);      // print out fitness
  void Mate   (USHORT no); // mate the population
};
// CONSTRUCTOR
Population::Population ( ... ) {
  : pa_sz(p_sz), ch_sz(c_sz), iv_sz(i_sz) {
  Pa = new Individual [pa_sz+ch_sz] (iv_sz,F); 
  Ch = Pa + pa_sz;
  pc = DEFAULT_CROSSOVER_PROB;
}
// INIT THE POPULATION
void Population::Init (void) {
  for (int i=0; i<pa_sz+ch_sz; i++) 
    Pa[i].Init();
}
// PRINT OUT FITNESS
void Population::Prn_F (void) {
  cout << "Parents:  ";
  for (int i=0; i<pa_sz; i++) 
    Pa[i].Prn_F();
  cout << endl;
  cout << "Children: ";
  for (int i=0; i<ch_sz; i++)
    Ch[i].Prn_F();
  cout << endl;
}
// MATE THE POPULATION AND SELECT THE BEST ONES
void Population::Mate (USHORT no) {
  for (int loop=0; loop<no; loop++) {
    for (int i=0; i<pa_sz; i++) 
      Pa[i].Eval();   // determine parent's fitness
    Sort (Pa, pa_sz); // sort pa corresp to fitness
    for (in i=0; i<ch_sz-1; i+=2) {
      Ch[i]   = P[rand()%pa_sz]; // randomly select
      Ch[i+i] = P[rand()%pa_sz]; // two mates
      Cross (Ch[i].X(), Ch[i+1].X()); // crossover
      Ch[i].Mutate();
      Ch[i+1].Mutate();
    }
    for (int i=0; i<ch_sz; i++)  // evaluate children
      Ch[i].Eval();
    Sort (Pa, pa_sz + ch_sz);    // sort and merge Pa/Ch
  }
}
// CROSSOVER
void Population::Cross (UCHAR* a, UCHAR* b) {
  UCHAR xor_mask, and_mask;
  for (int i=0; i<iv_sz; i++) {
    and_mask = 0;
    for (int j=0; j<8; j++) {
      and_mask <<= 1;
      if (rand () % 1000 < pc * 1000)
        and_mask += 1;
    }
    xor_mask = a[i] ^ b[i];
    xor_mask &= ~and_mask;
    a[i] ^= xor_mask;
    b[i] ^= xor_mask;
  }
}
// SORT
void Population::Sort (Individual* p, USHORT sz) {
  Individual tmp(iv_sz,NULL);
 
  ... any sorting algorithm should do ... 

}