TSP with Ant Colony

No preview image

1 collaborator

Default-person Shrinidhi KR KR (Author)

Tags

(This model has yet to be categorized with any tags)
Visible to everyone | Changeable by everyone
Model was written in NetLogo 3.1.4 • Viewed 188 times • Downloaded 13 times • Run 0 times
Download the 'TSP with Ant Colony' modelDownload this modelEmbed this model

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

[2] http://www.tsp.gatech.edu/

Comments and Questions

Please start the discussion about this model! (You'll first need to log in.)

Click to Run Model

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 4 years ago by Shrinidhi KR KR.

Attached files

No files

This model does not have any ancestors.

This model does not have any descendants.