Ant Food Collection Genetic Program
Background

Genetic Programming is a means of evolving solutions to difficult problems where the answer is not obvious. Genetic Programming allows problems to be solved without explicitly programming the solution.

This is done by way of a fitness function. The fitness function rates the performance of a possible solution. Good solutions are combined with other good solutions to hopefully create even better solutions. A genetic program starts with a random set of programs and continually combines the good programs replacing the bad programs with the newly created ones. By this process, the genetic program can evolve a solution.

My Ant Genetic Program evolves programs to mimic the food collection behavior of ants. While the Food Collection Problem is a common Genetic Program problem, my program concentrates on food collection problems where the ants MUST work together in order to succeed.

Most ant problems include many ants searching for food and bringing it back to a nest. The same solution that works for 20 ants will also work for one ant. 20 ants are used to solve the problem 20 times faster.

My Ant Genetic Program can be used to evolve problems slightly different, in that when 20 ants can solve a problem, 1, or even 19 ants, will not be able to solve the same problem with the same program solution. The ants will have to use teamwork in order to solve the problem. Also, they will need to use teamwork without assigning different roles to different ants, without communicating with each other (except for releasing pheromones), and without storing state information in the ant.

I used two variations of the food collection problem. The first is adding water to the environment where the ants will collect food. Placing a stream in the environment that completely separates the ants from the water creates the need for more than one ant. The ants will be forced to build an "ant bridge" to cross the water. Some of the ants will have to move into the stream and die to build a bridge for the other ants carrying the food. If every ant moves into the water to build a bridge, then they will all die and there are no ants left to collect the food. If no ants move into the water, then they will not be able to collect the food.

The second variation is to have heavy food that can only be lifted by more than one ant. Several ants will have to lift each piece of food and bring it back to the nest together. Not only do the ants have to work together, but must also find a way to communicate the need for help. There is also the problem if all of the ants waiting at different pieces of food for other ants to help lift. If there are three ants total, each individually trying to lift a different piece of food that requires two ants to lift, then nothing will get done. A way must be found for some, but not all, of the ants to abandon their food and help different ants. This is extremely difficult since all the ants are running the same program.

The really difficult problems that involve both rivers and heavy food with a limited number of ants. These programs can take hours to evolve even with the fastest PC.