Ant Genetic Programming Example


Simulate Ant

randomize
This mini-app requires the use of HTML5 canvas

Ant Sequence:


Using the ant simulator:

For any valid ant code provided, this simulator will run the ant through its FSM on the provided map. Click "randomize" to produce a random ant genome and then click "simulate" to run the virtual ant in the environment. Different environments may be chosen from the drop-down menu on the upper right.

NOTE: For some odd reason, the "randomize" link is glitchy in Firefox when Firebug is running. Seems to work just fine in Chrome, however.

Run Genetic Algorithm






Top Performing Ant:

Genetic History:

Running the genetic algorithm:

NOTE: Please give the function time to finish running. Unfortunately, javascript is not very good at handling progress events. Should you have chrome debugger or Firebug, you can see the progress through console outputs.

The parameters on the left determine how the genetic algorithm is run. A summary of their properties is as follows:

ParameterDescription
Population SizeNumber of ants in the population at each generation. This number is held constant for all generations.
Mutation RateProbability that any ant will mutate randomly
Mixing RateProbability that any ant will reproduce sexually with another ant rather than asexually (and persisting directly to the next generation)
Survival NumberNumber of ants from each generation that are guaranteed to survive. Each ensuing generation is built on the top surviving ants as indicated by this number
GenerationsNumber of generations to run the genetic algorithm for.

About this Ant Genetic Programming Example

Summary

This example shows how genetic programming can be used to successively find better virtual ants that survive best in a virtual trail environment. The environment is comprised of a grid world with food in certain grid blocks. A virtual ant's success is determined by the amount of food that it can pick up within a certain number of moves. With each generation, certain ant genomes are mixed and mutated in order to generate more unique offspring in searching for a more optimal ant.

The Ant

The ant's behavior in the environment is determined by its genetic makeup, a 30-digit sequence that forms the basis for a 10-state finite state machine. Each state is determined by 3 digits, the first of which determines an action, the second and third of which determines the state that the ant will transition into depending on whether or not it senses food in the grid block in front of it.

Digit #RangeMeaning
11-41 = move forward one cell
2 = turn right 90 degrees
3 = turn left 90 degrees
4 = do nothing
20-9If sensor reading is false, ant transitions to new state specified here.
30-9If sensor reading is true, ant transitions to new state specified here.

The Environment

The grid world is predefined by a text file and contains grid blocks that are either blank or have a food element. Once the ant picks up the food element, that grid block becomes blank. At the edges, the ant wraps around to the opposing side should it move off the main grid. This is more to simplify the constraints of the problem than to represent any real life phenomenon.

The Genetic Algorithm

Genetic variability among the ants are generated primarily through mutations and selective breeding. Beginning with a randomized initial seeding of ants, each ant in the population is run through a simulation on the map. For each generation, the best performing ants are allowed to persist into the next generation, and crosses between the those ants will be added as well. The worst performing ants are excluded and allowed to expire. Random mutations are possibly applied to all members of each generation in order to guarantee that the population variability will avoid steady state in the long run.

For the purposes of this mini-app, the following are selectable options that determine the characteristics of the genetic algorithm: mutation rate (how often mutation occurs), mixing rate (to what degree the best performing ants are crossed as opposed to preserved), population size


About - Simulate Ant - Run Genetic Algorithm

Raymond Ma 2010