A Genetic Algorithm Implementation in Ptolemy

The code for this example is available from the Ptolemy compiler distribution in the examples directory. The reader is encouraged to consult our pages on installing and running Ptolemy compiler for instructions on how to obtain the full example source code.

The idea behind a genetic algorithm is to mimic the process of natural selection. Genetic algorithms are computationally intensive and are useful for many optimization problems. The main concept is that searching for a desirable state is done by combining two parent states instead of modifying a single state. An initial generation with a fixed number (say n) members is given to the algorithm. Next, a cross over function is used to combine different members of the generation in order to develop the next generation. Optionally, members of the offspring may randomly be mutated slightly. Finally, members of the generation (or an entire generation) are ranked using a fitness function.

In the rest of this section, we will show snippets from the implementation of a genetic algorithm in Ptolemy. First concept is that of a generation of individuals. This concept is modeled by the class Generation as shown below.

import java.util.ArrayList;

public class Generation extends ArrayList {
 /***
  * Creates a generation of size num with individuals 
  * of type baseIndividual.
  * @param num
  * @param baseIndividual
  */
 public Generation(int num, 
  Individual baseIndividual) {
  super(num);
  for (int i = 0; i < num; i++) {
   Individual ind = baseIndividual.getRandomIndividual();
   this.add(ind);
  }
 }
 public Fitness getFitness() { 
  //returns fitness of this generation.
 }
 public Parents pickParents(){ 
  //picks two individuals as parents. 
 }
 public boolean add(Individual[] individuals){ 
  //Add a group of individuals to the generation.
 }
 public int getDepth(){ return depth; }
 private int depth = 0;
}

Various parts of a genetic algorithm produce and consume generation of individuals. For example, the cross over functionality consumes a generation and combines different members of this generation to produce a new generation. Similarly, the mutation functionality consumes a generation and may mutate some members of this generation to produce a new generation. So an event of interest in this system is "when a generation is produced." When this abstract event occurs in the system, an information of interest may be the generation that is being produced. Furthermore, this event must be signaled whenever a new generation is created. This event is modeled by the following event type declaration in this implementation.

public void event GenAvailable {
 Generation g;
}

In Ptolemy, an event type is seen as a decoupling mechanism that is used to interface two sets of modules, so that they can be independent of each other. Line 1 of the listing above declares the event type GenAvailable. This event type declares to have exactly one context variable. The type of this context variable is declared to be Generation and this context variable can be accessed using the name g in the code for handlers.

Cross over in genetic algorithm

Now let us look at the implementation of the cross over functionality. It is shown in the listing below.

public class CrossOver {
 protected final float probability;
 protected final int max;
	
 public CrossOver(float probability, int max) {
  this.probability = probability;
  this.max = max;
  register(this);
 }
	
 when GenAvailable do compute;
 public void compute(GenAvailable rest) throws Throwable {
  rest.invoke();
  int genSize = rest.g.size();
  Generation g1 = new Generation(rest.g);
  for (int i = 0; i < genSize; i += 2) {
   Parents p = rest.g.pickParents();
   g1.add(p.tryCrossOver(probability));
  }
  System.out.println("Before: depth is:" +  g1.getDepth());
  if (g1.getDepth() < max)
	announce GenAvailable(g1);
  System.out.println("After: depth is:"+  g1.getDepth());
  }
}

There are two fields in this class probability and max that are used to model probability with which the "cross over" operation will be applied and the depth of the search for the desirable state. The constructor of this class initializes the two fields.

An important Ptolemy-related construct register can be seen on line 9. This construct is used for registration in Ptolemy. This annotation on the constructor CrossOver has the effect of marking the method that can be used to activate the observer. The semantics is the following: when an object of that type, here CrossOver, is constructed using that method, here the constructor on lines 6-10, the receiver object of that method, here the constructed object this, is automatically registered to receive notifications for all events named in that class, here GenAvailable.

Another Ptolemy-related construct binding declaration can be seen on line 12. This construct is used for declaring handler methods for events in the Ptolemy language. The binding declaration on line 12 says that "when events of type GenAvailable are announced and if the current instance of this type is registered to receive notifications, then the method compute (lines 13-25) will be run with the current instance as the receiver object."

An interesting property of the implementation of CrossOver class is that it acts as both subject and observer for the event GenAvailable. Ptolemy's symmetric language model enables this flexibility in design.

Mutation in genetic algorithm

Another component of a genetic algorithm is mutation. The aim of this component is to slightly modify a generation to create the next generation that is going to be explored by the algorithm.

public class Mutation {
 protected final float probability;
 protected final int max;

 public Mutation(float probability, int maxDepth) {
  this.probability = probability;
  this.max = maxDepth;
  register(this);
 }

 // a handler that mutates newly available generations
 public void mutate(GenAvailable next) throws Throwable {
  next.invoke();
  int genSize = next.g().size();
  Generation g2 = new Generation(next.g());
  for (int i = 0; i < genSize; i += 2) {
   Parents p = next.g().pickParents();
   g2.add( p.tryMutation(probability));
  }
  System.out.println("Before: depth is:" +  g2.getDepth());
  if (g2.getDepth() < max)
  // announce the GenAvailable event to indicate availability 
  // of a generation (g2)
   announce GenAvailable(g2) {}
  System.out.println("After: depth is:" +  g2.getDepth());
 }
 when GenAvailable do mutate;
}

Fitness in genetic algorithm

Finally, to determine the progress of the genetic algorithm we evaluate the fitness of resulting generations. The algorithm keeps track of the fittest generation seen so far. This functionality can also be implemented as a handler in the Ptolemy language as shown below.

public class Fittest {
  Generation last;
  public Fittest() {  register(this); }

  // a handler that performs the fitness check on newly available generations
  public void check(GenAvailable next) throws Throwable {
  next.invoke();
  if (last ==null)
   last = next.g();
  else {
   Fitness f1 = next.g().getFitness();
   Fitness f2 = last.getFitness();
   if (f1.average() > f2.average())
           last = next.g();
   }
  }
 when GenAvailable do check
}

Logging in genetic algorithm

Logging of each generation is another concern added here, since it may be desirable to observe the space searched by the algorithm. The code used for implementing logging is show below.

public class Logger {
  public Logger() {
   // register this instance as an event handler
   register(this);
  }

  // a handler that logs newly available generations to the console
  public void logit(GenAvailable next) throws Throwable {
   next.invoke();
   logGeneration(next.g());
  }
  when GenAvailable do logit;

  static long generationNumber = 0;
  public void logGeneration(Generation g) {
   System.out.println("********************************************");
   System.out.println("Generation #"+(generationNumber++));
   Fitness f = g.getFitness();
   System.out.println("Average fitness=" + f.average());
   System.out.println("Maximum fitness="+f.maximum());
  }
}

Page last modified on $Date: 2012/01/07 16:18:40 $