TSP with Ant Colony
Do you have questions or comments about this model? Ask them here! (You'll first need to log in.)
WHAT IS IT?
This model is an implementation of the Ant System algorithm, as described in [1], that is being used to solve the Traveling Salesman Problem [2].
HOW IT WORKS
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.
HOW TO USE IT
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.
THINGS TO NOTICE
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.
THINGS TO TRY
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?
CREDITS
This model is an implementation of the Ant System algorithm from [1].
When refering to this model in academic publications, please use: Roach, Christopher (2007). NetLogo Ant System model. Computer Vision and Bio-inspired Computing Laboratory, Florida Institute of Technology, Melbourne, FL.
REFERENCES
[1] 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
Comments and Questions
globals [ best-tour best-tour-cost ticks node-diameter ] breed [ edges edge ] breed [ nodes node ] breed [ ants ant ] edges-own [ node-a node-b cost pheromone ] ants-own [ tour tour-cost ] ;;;;;;;;;;;;;;;::::::;;;;;;;;; ;;; Setup/Reset Procedures ;;; ;;;;;;;;;;;;;;;;;;;;;::::::;;; to setup clear-all set node-diameter 1.5 set-default-shape edges "line" set-default-shape nodes "circle" setup-nodes setup-edges setup-ants set best-tour get-random-path set best-tour-cost get-tour-length best-tour set ticks 0 update-best-tour end to setup-nodes ;; Create x and y ranges that will not allow a node to be created ;; that goes outside of the edge of the world. let x-range n-values (max-pxcor - node-diameter / 2) [? + 1] let y-range n-values (max-pycor - node-diameter / 2) [? + 1] create-custom-nodes num-of-nodes [ setxy one-of x-range one-of y-range set color yellow set size node-diameter ] end to setup-edges let remaining-nodes values-from nodes [self] while [not empty? remaining-nodes] [ let a first remaining-nodes set remaining-nodes but-first remaining-nodes ask a [ without-interruption [ foreach remaining-nodes [ __create-edge-with ? [ hide-turtle set color red __set-line-thickness 0.3 set node-a a set node-b ? set cost ceiling calculate-distance a ? set pheromone random-float 0.1 ] ] ] ] ] end to setup-ants create-custom-ants num-of-ants [ hide-turtle set tour [] set tour-cost 0 ] end to reset ;; Reset the ant colony and the pheromone in the graph ask ants [die] ask edges [die] setup-edges setup-ants ;; Update the best tour set best-tour get-random-path set best-tour-cost get-tour-length best-tour update-best-tour ;; Clear all of the plots in the model and reset the number of ticks clear-all-plots set ticks 0 end ;;;;;;;;;;;;;;;;;;;;;; ;;; Main Procedure ;;; ;;;;;;;;;;;;;;;;;;;;;; to go no-display ask ants [ set tour get-as-path set tour-cost get-tour-length tour if tour-cost < best-tour-cost [ set best-tour tour set best-tour-cost tour-cost update-best-tour ] ] update-pheromone set ticks (ticks + 1) do-plots display end ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;; Path Finding Procedures ;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; to-report get-random-path let origin one-of nodes report fput origin lput origin values-from nodes with [self != origin] [self] end to-report get-as-path let origin one-of nodes let new-tour (list origin) let remaining-nodes values-from nodes with [self != origin] [self] let current-node origin ;; Create the new path for the ant while [not empty? remaining-nodes] [ let next-node choose-next-node current-node remaining-nodes set new-tour lput next-node new-tour set remaining-nodes remove next-node remaining-nodes set current-node next-node ] ;; Move the ant back to the origin set new-tour lput origin new-tour report new-tour end to-report choose-next-node [current-node remaining-nodes] let probabilities calculate-probabilities current-node remaining-nodes let rand-num random-float 1 report last first filter [first ? >= rand-num] probabilities end to-report calculate-probabilities [current-node remaining-nodes] let transition-probabilities [] let denominator 0 foreach remaining-nodes [ ask current-node [ let next-edge __edge-with ? let transition-probability (pheromone-of next-edge ^ alpha) * ((1 / cost-of next-edge) ^ beta) set transition-probabilities lput (list transition-probability ?) transition-probabilities set denominator (denominator + transition-probability) ] ] let probabilities [] foreach transition-probabilities [ let transition-probability first ? let destination-node last ? set probabilities lput (list (transition-probability / denominator) destination-node) probabilities ] ;; Sort the probabilities set probabilities sort-by [first ?1 < first ?2] probabilities ;; Normalize the probabilities let normalized-probabilities [] let total 0 foreach probabilities [ set total (total + first ?) set normalized-probabilities lput (list total last ?) normalized-probabilities ] report normalized-probabilities end to update-pheromone ;; Evaporate the pheromone in the graph ask edges [ set pheromone (pheromone * (1 - rho)) ] ;; Add pheromone to the paths found by the ants ask ants [ without-interruption [ let pheromone-increment (100 / tour-cost) foreach get-tour-edges tour [ ask ? [ set pheromone (pheromone + pheromone-increment) ] ] ] ] end ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;; Plotting/GUI Procedures ;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; to update-best-tour ask edges [ hide-turtle ] foreach get-tour-edges best-tour [ ask ? [ show-turtle ] ] end to do-plots set-current-plot "Best Tour Cost" plot best-tour-cost set-current-plot "Tour Cost Distribution" set-plot-pen-interval 10 histogram-from ants [tour-cost] end ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;; Miscellaneous Procedures ;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; to-report get-tour-edges [tour-nodes] let xs but-last tour-nodes let ys but-first tour-nodes let tour-edges [] (foreach xs ys [ ask ?1 [ set tour-edges lput __edge-with ?2 tour-edges] ]) report tour-edges end to-report get-tour-length [tour-nodes] report reduce [?1 + ?2] map [cost-of ?] get-tour-edges tour-nodes end to-report calculate-distance [a b] let diff-x xcor-of a - xcor-of b let diff-y ycor-of a - ycor-of b report sqrt (diff-x ^ 2 + diff-y ^ 2) end
There is only one version of this model, created almost 5 years ago by Shrinidhi KR KR.
Attached files
No files
This model does not have any ancestors.
This model does not have any descendants.