# TSP with Ant Colony

No preview image

### 1 collaborator 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 this modelEmbed this model

### WHAT IS IT?

This model is an implementation of the Ant System algorithm, as described in , that is being used to solve the Traveling Salesman Problem .

### 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 , 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 .

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

 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

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
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
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
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 [
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
set pheromone (pheromone * (1 - rho))
]

;; Add pheromone to the paths found by the 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
foreach get-tour-edges best-tour [
]
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.