Transcript GAlibLecture

•
•
•
•
•
•
•
Developed by Matthew Wall at MIT
Collection of C++ GA components
Contains a very nice OOP interface
Contains many built-in chromosome type
Can be used with PVM
Overlapping and non-overlapping are supported
Customizable chromosome types, mutation,
objective , and crossover functions.
• Well written documentation and manuals
Although chromosomes can be built from any C++ type, there
exists a large collection of templated built-in types for
immediate use.
GA1DArrayGenome<T>
GA1DBinaryStringGenome
GAListGenome<T>
GARealGenome
GAStringGenome
GATreeGenome<T>
Let V and E represent the vertex and edge sets respectively of
a graph. A vertex-cover of an undirected graph G=(V,E) is a
subset V’ of V such that if (u,v) is in E then either u or v is an
element of V’. The optimal vertex-cover problem is to find a
vertex-cover that is minimal in size.
Graph( {a,b,c,d,e,f}, { {a,b},
{a,c}, {a,e}, {a,f}, {b,c}, {b,d},
{b,e}, {b,f}, {c,e}, {e,f} } ):
The vertex cover is: {a,b,e}
and is of optimal size.
b
d
a
f
e
c
float Objective(GAGenome &); // Name of objective
function
int leng = 20; // Number of vertices in graph
int popsize = 100; // number of chromosomes in pop.
int ngen = 500; // maximum number of generations
float pmut = 0.001; // probability of mutation
float pcross = 0.7; // probability of crossover
GA1DBinaryStringGenome genome(leng,Objective);
// This is the name of the function that defines the stopping criteria of the
program.
ga.terminator(GATerminateUponGeneration);
ga.populationSize(popsize); // Defines pop size
ga.nGenerations(ngen); // Defines the max number of generations to run
ga.pMutation(pmut); // Mutation probibility
ga.pCrossover(pcross); // Crossover probability
ga.evolve(); // Run the GA!
// Complete the program by printing out the important information
cout << "The GA found:" << ga.statistics().bestIndividual() << "\n";
cout << "Other stats\n"<<ga.statistics();
//Create genetic algorithm object ga using defined
genome
GASimpleGA ga(genome);
// tells the ga to copy the best individual from
previous pop to
// to the current population.
ga.elitist(gaTrue);
float Objective(GAGenome& g) {
GA1DBinaryStringGenome & genome = (GA1DBinaryStringGenome &)g;
float score=0.0;
// Traverse the genome bits
for(int i=0; i<genome.length(); i++){
score += genome.gene(i); // count number of 1 bits
for(int j=0; j<genome.length(); j++)
// Watch for bad edges
if((graph[i][j]==1)&&(genome.gene(i)==0) &&(genome.gene(j)==0))
score += 3.0; // count the number of bad edges by threes.
}
// Return the fitness
return ((500.0 – score)?500-score:0);
//
ex1.C A very simple example
#include <ga/GASimpleGA.h> // we're going to use the simple GA
#include <ga/GA2DBinStrGenome.h> // and the 2D binary string genome
#include <ga/std_stream.h>
#define cout STD_COUT
float Objective(GAGenome &); // This is the declaration of our obj function.
// The definition comes later in the file.
int
main(int argc, char **argv)
{
cout << "Example 1\n\n";
cout << "This program tries to fill a 2DBinaryStringGenome with\n";
cout << "alternating 1s and 0s using a SimpleGA\n\n"; cout.flush();
// 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]));
}
}
// Declare variables for the GA parameters and set them to some default values.
int width = 10;
int height = 5;
int popsize = 30;
int ngen = 400;
float pmut = 0.001;
float pcross = 0.9;
// Now create the GA and run it. First we create a genome of the type that
// we want to use in the GA. The ga doesn't operate on this genome in the
// optimization - it just uses it to clone a population of genomes.
GA2DBinaryStringGenome genome(width, height, Objective);
// Now that we have the genome, we create the genetic algorithm and set
// its parameters - number of generations, mutation probability, and crossover
// probability. And finally we tell it to evolve itself.
GASimpleGA ga(genome);
ga.populationSize(popsize);
ga.nGenerations(ngen);
ga.pMutation(pmut);
ga.pCrossover(pcross);
ga.evolve();
// Now we print out the best genome that the GA found.
cout << "The GA found:\n" << ga.statistics().bestIndividual() << "\n";
// That's it!
system("pause");
return 0;
}
float
Objective(GAGenome& g) {
GA2DBinaryStringGenome & genome = (GA2DBinaryStringGenome &)g;
float score=0.0;
int count=0;
for(int i=0; i<genome.width(); i++){
for(int j=0; j<genome.height(); j++){
if(genome.gene(i,j) == 0 && count%2 == 0)
score += 1.0;
if(genome.gene(i,j) == 1 && count%2 != 0)
score += 1.0;
count++;
}
}
return score;
}
Diaphantine Example
using Allele Sets
/* ---------------------------------------------------------------------------Diaphantine.C Programmed by Richard P. Simpson Midwestern State University,
Department of Computer Science DESCRIPTION: Linear Diaphantine Equations
This is an example program using GALib. It will search for the solution
of a Diaphantine Equation 101=2b+ 3c+4d+5e+6f. It uses allele sets
in the solution restricting the range of a-f to between 0 and 100.
Since the gcd of the coeficents is 1 we should have solutions
---------------------------------------------------------------------------- */
#include <stdio.h>
#include <math.h>
#include <iostream>
#define TOTAL 101
#define CHROMSIZE 9
#include <ga/GASimpleGA.h> // we're going to use an overlapping GA
#include <ga/GA1DArrayGenome.h> // and the 1D binary string genome
float Objective(GAGenome &); // This is the declaration of our obj function.
// The definition comes later in the file.
GABoolean GATerminateUponGeneration(GAGeneticAlgorithm & ga);
Start of Main
void main(int argc, char **argv)
{
cout << "This program tries to discover the best possible soln\n";
cout << "to the diaphantine equation 101=a+2b+3c+4d+5e+6f+7g+8h+9i\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++) {
// This seed is set on the command line. WHERE is that in the compiler?
if(strcmp(argv[ii++],"seed") == 0) {
GARandomSeed((unsigned int)atoi(argv[ii]));
}
}
ANSWER: under Project|Settings|Debug
main continued
// Declare variables for the GA parameters and set them to some default
values.
int leng = CHROMSIZE; // This represents a graph of 20 vertices int
popsize = 200;
int ngen = 500; // Set the maximum number of generations to 500;
float pmut = 0.05; // This is the probability of mutation
float pcross = 0.7; // This is the probability of applying a crossover
// Now we first create the allele sets for the range 1 to 100
GAAlleleSet<int> range;
// Load the Allele set
for(int x=1;x<=TOTAL-1;x++)range.add(x);
main continued
// Now create the GA and run it. First we create a genome of the type that
// we want to use in the GA. The ga doesn't operate on this genome in the
// optimization - it just uses it to clone a population of genomes.
//Create the genome object
GA1DArrayAlleleGenome<int> genome(leng, range, Objective);
//Set appropriate parameters for the genome
genome.initializer(GA1DArrayAlleleGenome<int>::UniformInitializer);
genome.mutator(GA1DArrayAlleleGenome<int>::FlipMutator);
genome.crossover(GA1DArrayGenome<int>::OnePointCrossover);
main continued
// Now that we have the genome, we create the genetic algorithm and set
// its parameters - number of generations, mutation probability, and
crossover
// probability. And finally we tell it to evolve itself.
GASimpleGA ga(genome);
ga.elitist(gaTrue);
ga.terminator(GATerminateUponGeneration);
ga.populationSize(popsize);
ga.nGenerations(ngen);
ga.pMutation(pmut);
ga.pCrossover(pcross);
ga.evolve();
main continued
// Now we print out the best genome that the GA found.
GA1DArrayAlleleGenome<int> & mygenome =
(GA1DArrayAlleleGenome<int> &)ga.statistics().bestIndividual();
cout << "The GA found:\n" << ga.statistics().bestIndividual() << " ";
cout<< "Its sum is:";
int s=0;
for(int k=0; k<mygenome.length();k++)
s+= (k+1)*mygenome.gene(k);
cout<< s<<endl;
cout << "Its fitness is "<< ga.statistics().maxEver() << "\n";
cout << "Found on generation "<<ga.statistics().generation()<<"\n";
// That's it!
}
The terminate function
//Here we specify when we want to quit. IE when our best individual has
// and fitness of .999999 or greater.
GABooleanGATerminateUponGeneration(GAGeneticAlgorithm & ga){
if(ga.statistics().maxEver() >=.999999) return gaTrue;
else return gaFalse;
}
Objective function
// This is the objective function. All it does is to check the fitness
// of each chromosome by subtracting from 500 the number of ones in the
// genome and the number of bad edges. A bad edge is one whose end points
// are not represented in the genome.
// We have to do the cast because a plain, generic GAGenome doesn't have
// the members that a GA1DBinaryStringGenome has. And it's ok to cast it
// because we know that we will only get GA1DBinaryStringGenomes and
// nothing else.
float
Objective(GAGenome& g) {
GA1DArrayAlleleGenome<int> & genome =
(GA1DArrayAlleleGenome<int> &)g;
float score=0.0;
for(int i=0; i<genome.length(); i++){
score += (i+1)*genome.gene(i); // Evaluate functions
}
return (1/(1.0+fabs(TOTAL - score)));
}