Week 1 Goals
Complete the implementation of the Ant Colony Optimization technique and run it on some simple shortest path problems to ensure the method is working. This might include determining some of the unknown parameters.
Week 1 Results
For the first week, I wanted to design an extensible framework for the ant problem that I could easily modify in the following weeks. This preliminary design is composed of one interface (antsim.cc) and two classes (ant.cc and map.cc). The interface takes parameters (map name and number of ants) from the command line, processes them, begins the simulation, and runs it until the user quits. It displays the progress of the ant colony as an ASCII view of the environment (see screenshot below).
In this first version of the ant simulator, the ant movement is fairly simple. The ant starts at the nest and randomly moves either up, down, left, or right. If the ant walks onto a cell with pheromone, it follows the pheromone trail either towards the nest or towards the food. If the ant finds food, it walks directly back to the nest while laying a pheromone trail.
This might appear to be cheating since the ant automatically knows how to find the nest. However, the map is flat and has no obstructions which gives the ant a clear line of sight to the nest. Many researchers argue that this allows an ant to easily find its way back without using pheromone.
Of course, the problem with this technique is that when an ant randomly walks on to a pheromone trail, it doesn't know whether it is following the trail to food or to the nest. This causes the ant to waste much of its time walking in circles instead of towards food. Furthermore, as the pheromone trail becomes stronger, more ants will be join the trail which prevents other food supplies on the map from being explored.
