Genetic programming algorithm for automating ant motion
Get love2d game engine from http://love2d.org and run this with it.
Ant is represented as a determinate finite automata with actions on transitions. Initially, a population of ants is generated randomly. Then, ant is executed and amount of food eaten is calculated. Ants that eat the most food proceed to the next round. They also have children which are generated by randomly combining two randomly chosen parents from the previous generation. The number of ants each generation is thus kept the same.
Sometimes, there also could be a mutation which randomly modifies the ant's automata.
A gene can also be represented by a string encoding the automata,
for example:
1M3R 5M6M 1M5R 1M2L 7M7R 7M3R 7M2R
Here a word (sequence of characters separated by spaces) represents a state. First two characters of a word represent the to which the ant should move and action that the ant should take if there is food in front of it (M - move, R - turn right, L - turn left). Second two characters represent the same things for the case when there is no food in front of the ant. Gene given above was generated by the algorithm and allows the ant to eat 85 out of 89 food pieces in 200 moves and eat all of them in less than 250 moves.
Here is a graph representation of the same gene:
http://is.ifmo.ru/genalg/_ant_ga.pdf
http://web.cs.ucla.edu/~dyer/Papers/AlifeTracker/Alife91Jefferson.html