# of Objective fn. evaluations

Kaustubh Das kdas at ece.utexas.edu
Sun May 2 03:38:50 EDT 1999


Hi Matthew,

Thanks for the prompt response. I understand your point . However I find
that in ex5.C, with

Posize = 30
Generations = 8000

the number of genome evaluations are only 73. This means that only 43 new
individuals are generated out of a total of (7999*30) 239,970 individuals
generated after initialization. I found this very strange. Moreover, the
bog.dat file has identical values  all the way through.

I attach the small modifications (cout statements) I made to ex5.C for
obtaining these numbers. I also attach the bog.dat file and the output on
running ex5.C

I am using GALib for Software Testing ( to solve a code reachability
problem). My genome is fashioned after the Composite genome and has ten
Integer, ten String, ten float Genomes, and ten Char 1DArrayAlleleGenomes

Thanks a ton,
Kaustubh

On Sat, 1 May 1999, Matthew Wall wrote:

> >Hi,
> >
> >I had a question. I am using GALib in a fashion similar to ex5.C whivh
> >comes with the Library. I had a population size of 20 and 1000
> >generations. Am I right in supposing that there ought to be 20,000 genome
> >evaluations.
> >
> >I put a cout statement in the objective fn. in ex5.C and it still shows
> >that the objective is called far  far lesser # of times than the
> >population_size * #of generations.
> >
> >Where am i going wrong? Please help.
> 
> you are not going wrong.  galib will only evalate a genome if the genome
> has changed.  so, for example, if a crossover generates a child that is
> identical to a parent, the child will not be evaluated since the parent
> already was evaluated and the child can simply use the parent's score.
> 
> matthew
> 
> Matthew Wall
> mbwall at REMOVE_THE_SPAM.mit.edu
> http://mit.edu/mbwall
> 
-------------- next part --------------
/* ----------------------------------------------------------------------------
  ex5.C
  mbwall 10dec94
  Copyright 1995-1996  Massachusetts Institute of Technology

 DESCRIPTION:
   Example program for a composite genome derived from the GAGenome and
containing a 2DBinStr genome and a Bin2Dec genome.  This program uses
a steady-state GA to match a 2D pattern in the 2DBinStr part of the genome
and a sequence of numbers in the Bin2Dec part.
   In this example we derive a new genome and a new crossover object to be
used with it.  All of the operators (initialization, mutation, crossover, 
comparison, and objective) are defined as member functions but are also
override-able on any instance of the new genome.
---------------------------------------------------------------------------- */
#include <stdio.h>
#include <stdlib.h>
#include <iostream.h>
#include <fstream.h>
#include <math.h>
#include <ga/GABin2DecGenome.h>
#include <ga/GA2DBinStrGenome.h>
#include <ga/GASStateGA.h>




// This is the class definition for the new genome.  The default operators are
// defined as static member functions.  They can be overridden if necessary by
// anyone making an instance of this class - you don't need to derive a new
// class to change the behaviour of one or two of its operators.
class CompositeGenome : public GAGenome {
public:
  GADefineIdentity("CompositeGenome", 201);

  static void CompositeInitializer(GAGenome&);
  static int CompositeMutator(GAGenome&, float);
  static float CompositeComparator(const GAGenome&, const GAGenome&);
  static int CompositeCrossover(const GAGenome&, const GAGenome&,
				GAGenome*, GAGenome*);
public:
  CompositeGenome(int, int, GABin2DecPhenotype&, 
		  GAGenome::Evaluator f=NULL, void* u=NULL);
  CompositeGenome(const CompositeGenome & orig);
  CompositeGenome& operator=(const GAGenome& g);
  virtual ~CompositeGenome();
  virtual GAGenome* clone(GAGenome::CloneMethod) const ;
  virtual void copy(const GAGenome & c);
  virtual int equal(const GAGenome& g) const;
  virtual int read(istream & is);
  virtual int write(ostream & os) const;

  GA2DBinaryStringGenome & binstr() const {return *str;}
  GABin2DecGenome & bin2dec() const {return *b2d;}

protected:
  GA2DBinaryStringGenome *str;
  GABin2DecGenome *b2d;
};







// Member functions for the composite genome object
CompositeGenome::
CompositeGenome(int element, int bond, GABin2DecPhenotype& p, 
		GAGenome::Evaluator f, void* u) :
		GAGenome(CompositeInitializer,
			 CompositeMutator,
			 CompositeComparator) {
		  evaluator(f); userData(u); crossover(CompositeCrossover);
		  str = new GA2DBinaryStringGenome(element, bond, f, u);
		  b2d = new GABin2DecGenome(p, f, u);
		}

CompositeGenome::CompositeGenome(const CompositeGenome & orig) {
  str = new GA2DBinaryStringGenome(orig.binstr());
  b2d = new GABin2DecGenome(orig.bin2dec());
  copy(orig);
}
  
CompositeGenome& 
CompositeGenome::operator=(const GAGenome& g) { copy(g); return *this; }

CompositeGenome::~CompositeGenome() { delete str; delete b2d; }

GAGenome* 
CompositeGenome::clone(GAGenome::CloneMethod) const {
  return new CompositeGenome(*this);
}

void 
CompositeGenome::copy(const GAGenome & c){
  if(&c != this && sameClass(c)){
    GAGenome::copy(c);
    CompositeGenome & bc = (CompositeGenome &)c;
    str->copy(*(bc.str));
    b2d->copy(*(bc.b2d));
  }
}

int 
CompositeGenome::equal(const GAGenome& g) const {
  CompositeGenome& genome = (CompositeGenome&)g;
  return ((*str == *genome.str) && (*b2d == *genome.b2d));
}

int 
CompositeGenome::read(istream & is) {
  is >> *str >> *b2d; 
  return is.fail() ? 1 : 0; 
}

int 
CompositeGenome::write(ostream & os) const {
  int i,j;
  for(j=0; j<str->height(); j++){
    for(i=0; i<str->width(); i++)
      os << (str->gene(i,j) == 1 ? '*' : ' ') << " ";
    os << "\n";
  }
  os << "\n" << *b2d << "\n";
  return os.fail() ? 1 : 0;
}



// These are the default initialization, mutation, and comparator operators for
// this genome class.  They are defined as static functions of the composite
// genome class and they're defaults for the class.  But they can be overridden
// on any instance of the genome.

// The initializer just calls the initializer for each of the genomes that are
// in the composite genome.

// I would have used simply 'Initializer', 'Mutator', etc rather than
// 'CompositeInitializer' but old versions of g++ are brain-dead and don't
// get the encapsulation properly.
void 
CompositeGenome::CompositeInitializer(GAGenome & c) {
  CompositeGenome & child = (CompositeGenome &)c;
  child.binstr().initialize();
  child.bin2dec().initialize();
}


// The mutator just calls the mutator for each of the component genomes.
int 
CompositeGenome::CompositeMutator(GAGenome & c, float pmut) {
  CompositeGenome & child = (CompositeGenome &)c;
  return child.binstr().mutate(pmut) + child.bin2dec().mutate(pmut);
}

// The comparator just calls the comparators for each of the component genomes,
// then averages the score.
float 
CompositeGenome::CompositeComparator(const GAGenome& a, const GAGenome& b) {
  CompositeGenome& sis = (CompositeGenome &)a;
  CompositeGenome& bro = (CompositeGenome &)b;
  return 0.5 * (sis.binstr().compare(bro) + sis.bin2dec().compare(bro));
}

// The crossover operator invokes the crossover for each of the genomes in the
// composite genome.  We use sexual crossover only, and we do not test to see
// if no crossover has been assigned.
int
CompositeGenome::
CompositeCrossover(const GAGenome& a, const GAGenome& b,
		   GAGenome* c, GAGenome* d){ 
  CompositeGenome& mom = (CompositeGenome&)a;
  CompositeGenome& dad = (CompositeGenome&)b;
  int n=0;

  GAGenome::SexualCrossover strcross = mom.str->sexual();
  GAGenome::SexualCrossover b2dcross = mom.b2d->sexual();

  if(c && d){
    CompositeGenome& sis = (CompositeGenome&)*c;
    CompositeGenome& bro = (CompositeGenome&)*d;
    (*strcross)(mom.binstr(), dad.binstr(), &sis.binstr(), &bro.binstr());
    (*b2dcross)(mom.bin2dec(),dad.bin2dec(), &sis.bin2dec(), &bro.bin2dec());
    n = 2;
  }
  else if(c){
    CompositeGenome& sis = (CompositeGenome&)*c;
    (*strcross)(mom.binstr(), dad.binstr(), &sis.binstr(), 0);
    (*b2dcross)(mom.bin2dec(), dad.bin2dec(), &sis.bin2dec(), 0);
    n = 1;
  }
  else if(d){
    CompositeGenome& bro = (CompositeGenome&)*d;
    (*strcross)(mom.binstr(), dad.binstr(), 0, &bro.binstr());
    (*b2dcross)(mom.bin2dec(), dad.bin2dec(), 0, &bro.bin2dec());
    n = 1;
  }

  return n;
}














int COUNTER=0;


// This object is a container for the data that we are supposed to match in 
// our objective function.
typedef struct _CompositeData {
  short ** str;
  float * b2d;
} CompositeData;

// In this objective function we try to match the pattern in the 2D part of the
// genome and match the sequence of values in the binary-to-decimal part of the
// genome.  The overall score is the sum of both parts.
float
Objective(GAGenome & g) {
  CompositeGenome & genome = (CompositeGenome &)g;
  GA2DBinaryStringGenome & str = genome.binstr();
  GABin2DecGenome & b2d = genome.bin2dec();
  COUNTER++;
  cout<< COUNTER<< endl;
  int i;

  short **pattern = ((CompositeData *)g.userData())->str;

  float val1=0.0;
  for(i=0; i<str.width(); i++)
    for(int j=0; j<str.height(); j++)
      val1 += (float)(str.gene(i,j) == pattern[i][j]);

  float *sequence = ((CompositeData *)g.userData())->b2d;

  float val2=b2d.nPhenotypes();
  for(i=0; i<b2d.nPhenotypes(); i++)
    val2 += 1.0 / (1.0 + fabs(b2d.phenotype(i) - sequence[i]));

  return(val1 + val2);
}












int
main(int argc, char *argv[])
{
  cout << "This program shows how to use a composite genome.  It reads\n";
  cout << "a matrix from a data file and a set of values to be matched in\n";
  cout << "a binary-to-decimal genome then uses a steady-state GA to\n";
  cout << "match the pattern and value set.\n\n";

// See if we've been given a seed to use (for testing purposes).  When you
// specify a random seed, the evolution will be exactly the same each time
// you use that seed number.

  for(int ii=1; ii<argc; ii++) {
    if(strcmp(argv[ii++],"seed") == 0) {
      GARandomSeed((unsigned int)atoi(argv[ii]));
    }
  }

  GAParameterList params;
  GASteadyStateGA::registerDefaultParameters(params);
  params.set(gaNpReplacement, 0.5);
  params.set(gaNscoreFilename, "bog.dat");
  params.set(gaNflushFrequency, 10);
  params.set(gaNnGenerations, 8000);
  params.parse(argc, argv, gaFalse);

  int i,j, n;
  char filename1[128] = "smiley.txt";
  char filename2[128] = "values.txt";

  for(i=1; i<argc; i++){
    if(strcmp("graph", argv[i]) == 0){
      if(++i >= argc){
        cerr << argv[0] << ": you must specify a filename.\n";
        exit(1);
      }
      else{
        sprintf(filename1, argv[i]);
        continue;
      }
    }
    else if(strcmp("values", argv[i]) == 0){
      if(++i >= argc){
        cerr << argv[0] << ": you must specify a filename.\n";
        exit(1);
      }
      else{
        sprintf(filename2, argv[i]);
        continue;
      }
    }
    else if(strcmp("seed", argv[i]) == 0){
      if(++i < argc) continue;
      continue;
    }
    else {
      cerr << argv[0] << ":  unrecognized arguement: " << argv[i] << "\n\n";
      cerr << "valid arguements include standard GAlib flags plus:\n";
      cerr << "  graph\tname of graph filename (" << filename1 << ")\n";
      cerr << "  values\tname of values filename (" << filename2 << ")\n";
      cerr << "\n";
      exit(1);
    }
  }

  ifstream infile;

// First we read in the pattern for the 2DBinStr genome.
// File format is pretty simple:
//   two integers that give the height then width of the matrix,
//   then the matrix of 1's and 0's (with whitespace inbetween).

  infile.open(filename1, ios :: in);
  if(!infile){
    cerr << "Cannot open " << filename1 << " for input.\n";
    exit(1);
  }

  int height, width;
  infile >> height;
  infile >> width;

  short **target = new short*[width];
  for(i=0; i<width; i++)
    target[i] = new short[height];

  for(j=0; j<height; j++)
    for(i=0; i<width; i++)
      infile >> target[i][j];

  infile.close();

// Now we read in a sequence of numbers that the Bin2Dec genome is supposed
// to match for its objective.  File format is
// pretty simple:  a single integer that tells how many numbers will follow,
// then the sequence of numbers.

  infile.open(filename2, ios :: in);
  if(!infile){
    cerr << "Cannot open " << filename2 << " for input.\n";
    exit(1);
  }
  infile >> n;
  float *sequence = new float[n];
  for(i=0; i<n; i++)
      infile >> sequence[i];
  infile.close();

// Print out the pattern and sequence.

  cout << "input pattern:\n";
  for(j=0; j<height; j++){
    for(i=0; i<width; i++)
      cout << (target[i][j] == 1 ? '*' : ' ') << " ";
    cout << "\n";
  }
  cout << "\n"; cout.flush();

  cout << "input sequence:\n";
  for(i=0; i<n; i++)
    cout << sequence[i] << " ";
  cout << "\n"; cout.flush();

// Create a phenotype then fill it with the phenotypes we will need to map to
// the values we read from the file.  The arguments to the add() method of a
// Bin2Dec phenotype are (1) number of bits, (2) min value, and (3) max value.
// The phenotype maps a floating-point number onto the number of bits that
// you designate.  Here we just make everything use 8 bits and pick a min and
// max based upon the number we read in from the file.  You can experiment with
// the number of bits and max/min values in order to make the GA work better
// or worse.

  GABin2DecPhenotype map;
  for(i=0; i<n; i++)
    map.add(12, 0.5*sequence[i], 2.0*sequence[i]);

// Create an instance of our user data structure and stuff it with the values
// that we read in from the files.

  CompositeData mydata;
  mydata.str = target;
  mydata.b2d = sequence;

// Now create the GA and run it.  First a genome, then the GA.
  CompositeGenome genome(width, height, map, Objective, (void *)&mydata);
  GASteadyStateGA ga(genome);
  ga.parameters(params);
  ga.evolve();

  genome = ga.statistics().bestIndividual();
  cout << "\nthe ga generated:\n" << genome << "\n";

// Don't forget to free up the memory we allocated.

  for(i=0; i<width; i++)
    delete target[i];
  delete [] target;
  delete [] sequence;

  return 0;
}

-------------- next part --------------
0	134.513
100	135.483
200	135.483
300	135.483
400	135.483
500	135.483
600	135.483
700	135.483
800	135.483
900	135.483
1000	135.483
1100	135.483
1200	135.483
1300	135.483
1400	135.483
1500	135.483
1600	135.483
1700	135.483
1800	135.483
1900	135.483
2000	135.483
2100	135.483
2200	135.483
2300	135.483
2400	135.483
2500	135.483
2600	135.483
2700	135.483
2800	135.483
2900	135.483
3000	135.483
3100	135.483
3200	135.483
3300	135.483
3400	135.483
3500	135.483
3600	135.483
3700	135.483
3800	135.483
3900	135.483
4000	135.483
4100	135.483
4200	135.483
4300	135.483
4400	135.483
4500	135.483
4600	135.483
4700	135.483
4800	135.483
4900	135.483
5000	135.483
5100	135.483
5200	135.483
5300	135.483
5400	135.483
5500	135.483
5600	135.483
5700	135.483
5800	135.483
5900	135.483
6000	135.483
6100	135.483
6200	135.483
6300	135.483
6400	135.483
6500	135.483
6600	135.483
6700	135.483
6800	135.483
6900	135.483
7000	135.483
7100	135.483
7200	135.483
7300	135.483
7400	135.483
7500	135.483
7600	135.483
7700	135.483
7800	135.483
7900	135.483
8000	135.483
-------------- next part --------------
This program shows how to use a composite genome.  It reads
a matrix from a data file and a set of values to be matched in
a binary-to-decimal genome then uses a steady-state GA to
match the pattern and value set.

input pattern:
                                
          * * * * * *           
      * *             * *       
    *                     *     
    *     * *     * *     *     
  *       * *     * *       *   
  *                         *   
  *                         *   
  *                         *   
    *   *             *   *     
    *     * * * * * *     *     
      * *             * *       
          * * * * * *           
                                

input sequence:
10.2 32.5 66 99.234 0.003 210 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

the ga generated:
    * *   *   *   * * *   * *   
* *         *       *   *       
      *   * * *       * *       
    * * *       *         *     
*   *     *   * * * * *       * 
* *     *     *     * *   * * * 
  * *     *   *   *         * * 
    *     * * *         * * *   
*   *   *                       
* *     * * *     * *     *   * 
*     * * *   * * * * *     *   
      * *       *               
*     *   *   * * *   *         
* * *     *   *   *   * *       

12.8752 57.2857 75.3802 150.269 0.00260769 330.231 



More information about the galib mailing list