NetLogo User Community Models
by Jose Costas (Submitted: 09/18/2013)
## 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
TRAVELLING SALESPERSON is classified in NP category of problems, since a permutation of
A Hamiltonian cycle of an undirected graph is a cycle that visits every
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
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.
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
## THINGS TO NOTICE
Be aware that the graph that represents the problem is not done at scale!
## 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:
Target quality characteristics:
TEST DRIVEN DEVELOPMENT (FAT factory acceptance test)
ROBUST ENGINEERING PRINCIPLES
Preventive defence against modes of failure. Upstream controls checking inputs and assumptions rather than outputs of the blocks of code.
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.
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)
(2) for a discussion on NP-complete problems
(3) A branch-and-bound algorithm for TSP
(4) For a lecture about NP-hard problems
(5) This paper introduces the R package TSP which provides a basic infrastructure for handling and solving the traveling salesperson problem.
(6) A PowerPoint presentation about TSP.
Author: Jose Costas
(back to the NetLogo User Community Models)