NetLogo User Community Models

(back to the NetLogo User Community Models)

Download If clicking does not initiate a download, try right clicking or control clicking and choosing "Save" or "Download".(The run link is disabled for this model because it was made in a version prior to NetLogo 6.0, which NetLogo Web requires.)

## WHAT IS IT?

The TSP (travel salesperson problem) is extensively studied in literature and has attracted since a long time a considerable amount of research effort. The TSP also plays an important role in Ant Colony Optimization.

Intuitively, the TSP is the problem of a salesman who wants to find, starting
from his home town, a shortest possible trip through a given set of customer
cities and to return to its home town.

TRAVELLING SALESPERSON is classified in NP category of problems, since a permutation of
the cities is a certificate that can be verified.

A Hamiltonian cycle of an undirected graph is a cycle that visits every
vertex exactly once (aka tour).

This is a 739 LOC (lines of code) model using ACO approach to solve TSP.

## HOW IT WORKS

In ACO algorithms ants are simple agents which, in the TSP case, construct
tours by moving from city to city on the problem graph. The ants' solu-
tion construction is guided by (artificial) pheromone trails and an a priori
available heuristic information.

Initially, each of the m ants is placed on a randomly chosen city and then iteratively applies at each city a state transition rule.

At a city i, the ant chooses a still unvisited city j probabilistically, biased by the pheromone trail strength τij (t) on the arc between city i and city j and a locally available heuristic information, which is a function of the arc length.

Ants probabilistically prefer cities which are close and are connected by arcs with a high pheromone trail strength. To construct a feasible solution each ant has a limited form of memory, called tabu list, in which the current partial tour is stored. The memory is used to determine at each construction step the set of cities which still has to be visited and to guarantee that a feasible solution is built. Additionally, it allows the ant to retrace its tour, once it is completed.

After all ants have constructed a tour, the pheromones are updated. This is typically done by first lowering the pheromone trail strengths by a constant factor and then the ants are allowed to deposit pheromone on the arcs they have visited. The trail update is done in such a form that arcs contained in shorter tours and/or visited by many ants receive a higher amount of pheromone and are therefore chosen with a higher probability in the following iterations of the algorithm. In this sense the amount of pheromone τij(t) represents the learned desirability of choosing next city j when an ant is at city i.

Termination condition may be a certain number of solution constructions or a given CPU-time limit.

## HOW TO USE IT

Before pressing SETUP button, use the bu-fat control to select if you want to run a FAT (factory acceptance test) or to define your own problem.

Use the bu-verify-mode? control to stablish if you want a verbose or a silent log in the command center.

Parametrization:

bu-alpha ... if α = 0, the closest cities are more likely to be selected: this corresponds to a classical stochastic greedy algorithm.

bu-beta ... if β = 0, only pheromone amplification is at work: this method will lead to the rapid emergence of a stagnation situation with the corresponding generation of tours which, in general, are strongly suboptimal.

bu-rho ... where 0 < ρ ≤ 1 is the pheromone trail evaporation; the parameter ρ is used
to avoid unlimited accumulation of the pheromone trails and it enables the
algorithm to “forget” previously done bad decisions.

## THINGS TO NOTICE

Be aware that the graph that represents the problem is not done at scale!
Distances are displayed in the arcs between cities.
Ants shape is taken form the avaialable default shapes galery.
Computational effort count the number of blocks run.
Be aware that no validation about graph arcs lenght is done (e.g. the traingular inequality)

## THINGS TO TRY

Experiment with different population sizes of ants, with different parameter settings. You may use the design of experiments techniques, with orthogonal arrays, to reduce the experimental effort, and raise conclusions about main effects and interaction among parameters of the design space.

## EXTENDING THE MODEL

Read the advanced literature about ACO (ant colony optimization) heuristics, and modify ant rules of behavior to compare the required computational effort to solve different FAT (factory acceptance test) problems.

Add your own FAT test and verify the model obtains optimnal solutions. Add graphs that have no feasible solutions. Verify if the system handles properly the absence of solutions.

Create a very large problem to check system performance. Does it degrade over time?

## NETLOGO FEATURES

There are many interesting points to highlight about the construction of such a model:

Managing exceptions.
Continuous embedded control.
Use of recursivity.
Use of lambda concept implemented via run task.

Target quality characteristics:

TEST DRIVEN DEVELOPMENT (FAT factory acceptance test)
Realize that the system has embedded some FAT tests, appart from, naturally, the option to create your own TSP specification and run it.

ROBUST ENGINEERING PRINCIPLES

Preventive defence against modes of failure. Upstream controls checking inputs and assumptions rather than outputs of the blocks of code.
Deep encapsulation, aiming for the minimum required variety to manage complexity.

DESIGN ORIENTED TO HIGH LEVEL OF SLA (service level agreement)

Permanently debugging mode available so to reproduce an error and gather details for problem statement and system diagnosis.
Embedded documentation.

VISUAL MANAGEMENT ORIENTATION

visors, basic statistics and general system feedback not only for the expected outcome, (what the system must do), but also information to make judgements about system behavior.

## RELATED MODELS

It is strongly recommended to explore the NetLogo Models Library, as well as the NetLogo User Community Models website.

## CREDITS AND REFERENCES

(1) for ant colony optimization algorithms (ACO)
http://staff.washington.edu/paymana/swarm/stutzle99-eaecs.pdf

(2) for a discussion on NP-complete problems
http://www.cs.berkeley.edu/~vazirani/algorithms/chap8.pdf

(3) A branch-and-bound algorithm for TSP
http://dspace.mit.edu/bitstream/handle/1721.1/46828/algorithmfortrav00litt.pdf

(4) For a lecture about NP-hard problems
http://www.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/21-nphard.pdf

(5) This paper introduces the R package TSP which provides a basic infrastructure for handling and solving the traveling salesperson problem.
http://cran.wustl.edu/web/packages/TSP/vignettes/TSP.pdf

(6) A PowerPoint presentation about TSP.
www.ms.unimelb.edu.au/~s620261/powerpoint/chapter9_4.ppt‎

Author: Jose Costas
Sep 2013
josegual@esce.ipvc.pt