Chistopher Roach and Benito Mendoza
This model is an implementation of the Ant System algorithm, as described in here, that is being used to solve the Traveling Salesman Problem.
The Ant System algorithm can be used to find the shortest path in a graph by employing the same decentralized mechanism exploited by ant colonies foraging for food. In the model, each agent (i.e., ant) constructs a tour in the graph by making a choice at each node as to which node will be visited next according to a probability associated with each node. The probability of an ant choosing a specific node at any time is determined by the amount of pheromone and the cost (i.e., the distance from the current node i to the next node j, where node j has not yet been visited) associated with each edge.
The attributes in this model that can be adjusted to change the behavior of the algorithm are alpha, beta, and rho. The alpha and beta values are used to determine the transition probability discussed above, where the values are used to adjust the relative influence of each edge's pheromone trail and path cost on the ant's decision. A rho value is also associated with the algorithm and is used as an evaporation rate which allows the algorithm to "forget" tours which have proven to be less valuable.
Choose the number of nodes and ants that you wish to have in the simulation (for best results set the number of ants equal to the number of nodes in the graph). Click the SETUP button to create a random graph, a new colony of ants, and draw an initial tour on the graph. Click the GO button to start the simulation. The RESET button keeps the same graph that was generated by the SETUP operation, but it resets everything else in the algorithm (i.e., it destroys all ants and edges in the graph and clears all of the plots). The RESET button allows the user to run several tests with the same graph for data gathering.
The alpha slider controls the propensity of the ants to exploit paths with high amounts of pheromone on them. The beta slider controls how greedy the ants are, i.e., the ant's to edges with the lowest cost. The delta slider controls the evaporation rate of the pheromone in the graph where the higher the delta, the faster the pheromone evaporates.
In the model, two plots are given to show how the algorithm is performing. The "Best Tour Cost" plot shows the cost of the best tour found so far over the life of the current run. The "Tour Cost Distribution" plot is a histrogram that shows how the ants are distributed throughout the solution space. In this plot, the vertical axis is the number of ants and the horizontal axis is tour cost, where each bar has a range of 10 units.
According to [1], emperical evidence shows that the optimal settings for the algorithm are: alpha = 1, beta = 5, rho = 0.5. Try adjusting each of these settings from the optimal and take notice of how they affect the performance of the algorithm. Watch the "Best Tour Cost" plot to see if adjustments lead to a steadier march towards the best tour or perhaps they add up to a good initial search that settles quickly into a local optimum. Study the "Tour Cost Distribution" plot to see if changes to the evaporation rate lead to stagnation? Can you find more optimal settings than those that have been found through previous experimentation?
This model is an implementation of the Ant System algorithm from:
Roach, Christopher (2007). NetLogo Ant System model. Computer Vision and Bio-inspired Computing Laboratory, Florida Institute of Technology, Melbourne, FL.
Dorigo, M., Maniezzo, V., and Colorni, A., The Ant System: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics Part B: Cybernetics, Vol. 26, No. 1. (1996), pp. 29-41. http://citeseer.ist.psu.edu/dorigo96ant.html
http://www.tsp.gatech.edu/
20100428