Genetic Ant Algorithm

Here is an applet that implements the Genetic Ant Algorithm. It is based upon the model given in Koza, Genetic Programming, MIT Press. (It's down below; just page down.)

Source code and some comments:

I orginally wrote this in Pascal for DOS. I took the code, and turned it into objects. Then I used Java's graphics to show the ant on the board.

An ant doesn't do much; depending upon its state and whether or not it sees food directly in front, it will step forward, turn left or right, or do nothing. The memory of the ant consists of these states or chromosomes. And chromosomes consist of genes which tell the ant what to do and what the next state should be.

The ant walks upon a board where food is placed from top to bottom. Sometimes there are gaps. Note that the ant has no sense of direction.

The problem is to find a "good set" of chromosomes so that the ant will eat as much food as possible. The algorithm works as follows:

  1. Generate a collection of ants.
  2. Generate a board for the ants.
  3. Walk each ant on the board. See how much food it eats.
  4. We generate more ants by allowing a gene in an ant to mutate (change direction and state), or swapping genes between two ants. Walk these ants on the board.
  5. Keep a few of these ants for the next generation. I keep the ant that does the best and select the others randomly with the probability of being selected proportional to how well it does. This allows "poor ants" a chance to survive.
  6. Repeat steps 2 - 5 for as long as you want.
The applet sets up the parameters and shows the path of the best ant for each generation. After each prompt, you can change the parameter or leave it. When you get tired, you press the STOP button. You can press the START OVER button if you want to generate more ants or change the parameters.

By looking at the Java Console, you can see the generations of ants, the parents of each ant, how well it does, and the board and memory for the best ant in each generation.  (The applet will run a lot slower though.)

By taking the source and compiling that, Ants.class can run stand alone giving text output similar to what is seen the the Java Console.

Other source creates the arrow, the random numbers, and semaphores to coordinate the input and output (see Dynamic Hanoi for details.)

Carl E. Bredlau

 

 
 
 
 
 
 
 
 
 
 
 
 
 

bredlauc@alpha.montclair.edu