Visualization and comparison of randomized search heuristics on random traveling salesman problems | Thorkil Burup
| | Abstract | The traveling salesman problem is in a class of problems, that are assumed to not be computable efficiently. Using randomized search heuristics is a way of handling problems such as the traveling salesman problem. In this report, randomized local search, simulated annealing, (1+1) evolutionary algorithm and MAX-MIN ant system are observed to determine their strengths and weaknesses in relation to each other, and to provide a benchmark on different random problem instances. Experiments conducted in this study show that randomized local search and (1+1) evolutionary algorithm are the most adaptable and generally applicable, but simulated annealing can perform exceptionally well if given optimal conditions. MAX-MIN ant system find reasonable solutions fast, but cannot improve on them at a high rate compared to the other three. An experiment using random problem instances with vertices placed in clusters indicated that the graph structure does not affect the performance of the algorithms.
Based on data provided by the experiments, recommendations on the algorithms can be made: Randomized local search and (1+1) evolutionary algorithm are based on continuously improving their tours. If given a good initial tour (e.g. using an approximation algorithm), they are not only able to reach good solutions fast, but more surprisingly (especially for randomized local search), they are able to consistently reach better solutions. Simulated annealing works mediocre, unless it can be provided with very problem-specific parameters. In this case, it excels and is shown to consistently improve its tour cost for a problem. MAX-MIN ant system is shown to rely heavily on its distance heuristic in the tested environments, making its pheromone heuristic insignificant.
The randomized search heuristics are compared to Concorde on three different problem instances. This comparison shows that the randomized search heuristics are capable of calculating solution with costs approximately 115% of optimal solutions, but can do so in half the time the state-of-the-art solver Concorde uses. The data presented in this study show that randomized search heuristic are convenient when an exact solution is not needed and when exact solvers are not practical; for instance when time or computation resources are limited. | | Type | Master's thesis [Academic thesis] | | Year | 2015 | | Publisher | Technical University of Denmark, Department of Applied Mathematics and Computer Science | | Address | Richard Petersens Plads, Building 324, DK-2800 Kgs. Lyngby, Denmark, compute@compute.dtu.dk | | Series | DTU Compute M.Sc.-2015 | | Note | DTU supervisor: Carsten Witt, cawi@dtu.dk, DTU Compute | | Electronic version(s) | [pdf] | | Publication link | http://www.compute.dtu.dk/English.aspx | | BibTeX data | [bibtex] | | IMM Group(s) | Computer Science & Engineering |
|