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.
The parameters on the left determine how the genetic algorithm is run. A summary of their properties is as follows:
|Population Size||Number of ants in the population at each generation. This number is held constant for all generations.|
|Mutation Rate||Probability that any ant will mutate randomly|
|Mixing Rate||Probability that any ant will reproduce sexually with another ant rather than asexually (and persisting directly to the next generation)|
|Survival Number||Number 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|
|Generations||Number of generations to run the genetic algorithm for.|
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'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.
|1||1-4||1 = move forward one cell|
2 = turn right 90 degrees
3 = turn left 90 degrees
4 = do nothing
|2||0-9||If sensor reading is false, ant transitions to new state specified here.|
|3||0-9||If sensor reading is true, ant transitions to new state specified here.|
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.
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