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.