population.h

关于遗传算法的c++程序,本文采用了实数编码

#include <iostream.h>
#include "Array.h"

typedef float Real;

//////////////////////////////////////////////////////////////////////////////
///                             Population.h                               ///
//////////////////////////////////////////////////////////////////////////////


class Population {
   public:
      Population();
      ~Population();
//
//  Main member functions
//
      void initP(Ranges,int*,int,int,int);
      void showP(int);
      void fitParents();
      int Tselect(int *);
      int Aselect(int *);
      int Rselect(int *);
      Citizen Umate(int,int,int*,Ranges,Real,Real);
      void mateParents(int*, Ranges, Real, Real);
      void mutateChildren(Real,Real,int*);
      void elitism(int*);
      Real bitFrac();
//
//  Support member functions
//
      int numParams();
      int numBits();
      int numPop();
      Citizen cit(int i);
      int bestI();
      Real bestF();
      Real averageF();
      void transferChildren(Ranges);

   private:
      SimpleArray<Citizen> parents;  // Array of parents
      SimpleArray<Citizen> children; // Array of children
      SimpleFArray fitness;          // Fitness array for parents
      Real average;                  // Average of the fitness array
};


//////////////////////////////////////////////////////////////////////////////
///                            Population.cc                               ///
//////////////////////////////////////////////////////////////////////////////


Population::Population() {
}

Population::~Population() {
//
//  Standard destructor
//
   parents.~SimpleArray();
   children.~SimpleArray();
}

void Population::initP(Ranges r,int* iseed,int Npop,int Nparams,int Nbits) {
//
//  This routine initializes a population.  A population consists of an array
//  of parents, an array of the children that the parents will produce (which 
//  are both arrays of Citizens) and a fitness array of the parents (which is 
//  an array of Reals).
//
   parents.setSize(Npop);
   children.setSize(Npop);
   fitness.setSize(Npop);
   for(int i = 0;i < Npop;i++)
      parents[i].initC(r,iseed,Nparams,Nbits);
   fitParents();
}

void Population::showP(int flag) {
//
//  This routine prints out the information for the entire population.  
//  It is really for display (and debugging) purposes only, and is 
//  crucial to the main program.
//
   int np = parents.numElts();
   for (int inp = 0;inp < np;inp++) {
      cout << endl;
      if (flag == 0) {
         cout << "                 Parent " << inp << endl;
         cout << "=============================================" << endl;
         parents[inp].showC();
         cout << "---------------------------------------------" << endl;
         cout << "Fitness is " << fitness[inp] << endl;
         cout << "=============================================" << endl;
      }  
      else {
         cout << "                 Child " << inp << endl;
         cout << "=============================================" << endl;
         children[inp].showC();
         cout << "=============================================" << endl;
      }
   }
}


void Population::fitParents() {
//
//  This routine fills the fitness array by calling fit() for each
//  parent in the Population, and then also fills the variable 'average'.
//
   Real tot_fit = 0.0;
   int np = numPop();
   for (int inp = 0;inp < np;inp++) {
      fitness[inp] = parents[inp].fit();
      tot_fit += fitness[inp];
   }
   average = tot_fit/numPop();
}


int Population::Tselect(int* iseed) {
//
//  This routine selects a parent for breeding.  The method of selection is
//  called Tournement selection (hence the capitol T at the beginning of the 
//  function name).  It is a very simple selection process.  It randomly 
//  selects two parents, and returns the parent with the better fitness.
//
   int flag = 0;
   int npop = numPop();
   if (flag) cout << "In Tselect: " << endl;
   int i1 = int(npop*ran1(iseed));
   int i2 = int(npop*ran1(iseed));
   if (flag) cout << "The choices are " << i1 << " and " << i2 << endl;
   if (parents[i1].fit() < parents[i2].fit()) return i1;
   else return i2;
}


int Population::Aselect(int* iseed) {
//
//  This routine selects a parent for breeding.  The method for selection
//  is to simply let only parents with above average fits breed
//
   int i1;
   int flag = 0;
   int selflag = 0;
   int loopflag = 0;
   int loopcount = 0;
   int npop = numPop();
   if (flag) cout << "In Aselect: " << endl;

   do {
      i1 = int(npop*ran1(iseed));
      if (parents[i1].fit() < average) selflag = 1; 
      loopcount++;
      if (loopcount == 1000*npop) loopflag = 1;
   } while((!selflag) && (!loopflag));
   if (loopflag) {
      i1 = -1;
      cout << "Error in Aselect " << endl;
      cout << "Could not find good parent " << endl;
      cout << "Returning i1 = -1 " << endl;
   }
   return i1;
}


int Population::Rselect(int* iseed) {
//
//  This routine selects a parent for breeding.  The method of selection is
//  totally random selection (hence the capitol R at the beginning of the 
//  function name).  It is a very simple selection process.  It randomly 
//  selects one parent, and returns it.
//
//  WARNING!  This routine is meant for comparison purposes only.  It yields 
//  results that (obviously) cannot converge, because fitness is never taken
//  into consideration when the selection process is being made. 
//
   int flag = 0;
   int npop = numPop();
   if (flag) cout << "In Rselect: " << endl;
   int i1 = int(npop*ran1(iseed));
   if (flag) cout << "The choice is " << i1 << endl;
   return i1;
}


Citizen Population::Umate(int i1,int i2,int* iseed,Ranges r,
                          Real Jrate,Real Crate) {
//
//  This routine mates two parents and creates a child, to be put in 
//  the children array.  The capitol U at the beginning of the function 
//  name stands for 'Uniform crossover'.  The mating process for Uniform 
//  crossover goes as follows.  For each bit position in the child being 
//  created, a bit is randomly selected from either of the parents at that 
//  bit position.  The array of bits in the child is then 'decoded' so 
//  that the parameter values in paramsF match those in the array of bits 
//  in paramsB.  flag = 1 turns on the debugging info.
//

   int flag = 0;         // Information print out flag
   int loopflag = 0;     // Infinite loop flag
   int loopcount = 0;    // Infinite loop counter
   int checkflag;        // Flag to see if parameter is in range
   Real param;           // Parameter to be checked
   Citizen child;        // child to be returned
   int ip;               // parent number (either 1 or 2)
   int bv;               // bit value
   int start_bit,ibit;   // bit counters

   int np = numParams();
   int nb = numBits();
   child.setSize(np,nb);

//
//  For each parameter,
//     1) create the binary array.
//     2) expose the bits of a single parameter to posible mutation.
//     3) decode the parameter.
//     4) check to see if the decoded parameter is in range.
//     5) if the parameter is not in range, redo it.
//

   for(int inp = 0;inp < np;inp++) {
      start_bit = inp*nb;
      for(int inb = 0;inb < nb;inb++) {
         ibit = start_bit + inb;
         if (ran1(iseed) > 0.5) ip = i1;
         else ip = i2;
         bv = parents[ip].bitVal(ibit);
         child.bitAdd(ibit,bv);
      }
      child.mutateParam(Jrate,Crate,iseed,inp);
      param = child.decodeParam(r,inp);
      if (flag) cout << "param number " << inp << " is " << param << endl;
      checkflag = child.checkRange(inp,param,r);
      if ((!checkflag) && (!loopflag)) {
         if (flag) cout << "Bad parameter, getting another" << endl;
         inp--;
      }
      else child.paramAdd(inp,param);
//
//  Infinite loop checker
//
      loopcount++;
      if (loopcount == 1000*np) loopflag = 1;
   }
   if (loopflag) {
      cout << "Could not find a good set of parameters" << endl;
      cout << "STOPPING" << endl;
   }

   return child;
}


void Population::mateParents(int* iseed,Ranges r,Real Jrate,Real Crate) {
//
//  This routine mates the entire Population of parents, and fills the 
//  children array with binary strings.  It is here that different parent 
//  selection processes and mating schemes can be chosen.
//
   int flag = 0;
   int npop = numPop();
   int i1,i2,ipop;
   for (ipop = 0;ipop < npop;ipop++) {
      i1 = Tselect(iseed);
      i2 = Tselect(iseed);
      if (flag) cout << "====================================" << endl;
      if (flag) cout << "Mating parents " << i1 << " and " << i2;
      if (flag) cout << " to get child " << ipop << endl;
      children[ipop] = Umate(i1,i2,iseed,r,Jrate,Crate);
      if (flag) cout << "====================================" << endl;
   }
}


void Population::elitism(int* iseed)  {
//
//  This routine transfers the best parent from one generation to the next.
//  The purpose of doing this is so that the best Citizen (as well as his fit)
//  is never lost.
//
   int flag = 0;
   int ibest = bestI();
   int rnd_ind = int(numPop()*ran1(iseed));
   if (flag) {
      cout << "In elitism" << endl;
      cout << "The best parent is " << ibest << endl;
      cout << "The child that is being replace is " << rnd_ind << endl;  
   }
   children[rnd_ind] = parents[ibest];
}


Real Population::bitFrac() {
//
//  This routine returns the fraction of bits that are different from the 
//  best Citizen.  This is used as a posible convergence criteria.
//  When everything has converged (assuming there is no mutation), the routine
//  should return 0.0.  Of course, if there is mutation, then the convergence 
//  will be limited by the mutation rates.
//
   int start_bit,bit;

   int npar = numParams();
   int nbit = numBits();
   int npop = numPop();

   Citizen best_cit; 
   best_cit.setSize(npar,nbit);
   best_cit = cit(bestI());

   Citizen some_cit; 
   some_cit.setSize(npar,nbit);

   int bitcount = 0;
   for(int ipop = 0;ipop < npop;ipop++) {
      some_cit = cit(ipop);   
      for(int ipar = 0;ipar < npar;ipar++) {
         start_bit = ipar*nbit;
         for(int ibit = 0;ibit < nbit;ibit++) {
            bit = start_bit + ibit;
            if (best_cit.bitVal(bit) != some_cit.bitVal(bit)) bitcount++;
         }
      }
   }
   return(Real(bitcount)/Real(npop*npar*nbit));
}


//
//  The following routines are very self explanitory.  They each return 
//  a single thing, or preforms a single, simple operation.
//
//    1) numParams   - Returns the number of parameters to be fit.
//    2) numBits     - Returns the number of bits per parameter.
//    3) numPop      - Returns the number of Citizens in the population.
//    4) cit         - Returns a specific Citizen.
//    5) bestI       - Returns the index of the Citizen who has the best fit.
//    6) bestF       - Returns the value of the fit from bestI().
//    7) averageF    - Returns the average value of the fitness array.
//    8) transfer    - Transfers the children to the parent array.
//

int Population::numParams() {
   return parents[0].numParams();
}


int Population::numBits() {
   return parents[0].numBits();
}


int Population::numPop() {
   return parents.numElts();
}


Citizen Population::cit(int i) {
   return parents[i];
}


int Population::bestI() {
   int npop = numPop();
   int best_ind = -1;
   Real best_fit = 999999.999;
   for (int inp = 0;inp < npop;inp++)
       if (parents[inp].fit() < best_fit) {
          best_fit = parents[inp].fit();
          best_ind = inp;
       }
   if (best_ind == -1) {
       cout << "Could not find the best in the population " << endl;
       cout << "Returning -1 as the index" << endl;
   }
   return best_ind;
}


Real Population::bestF() {
   int ibest = bestI();
   return fitness[ibest];
}


Real Population::averageF() {
   return average;
}


void Population::transferChildren(Ranges r) {
   int npop = numPop();
   int np   = numParams();
   for (int ipop = 0;ipop < npop;ipop++) {
      parents[ipop] = children[ipop];
      for (int inp = 0; inp < np;inp++) 
            parents[ipop].decodeParam(r,inp);
   }
}