Design, Implementation and Comparison of Randomized Search Heuristics for the Traveling Thief Problem | Rasmus Birkedal
| | Abstract | The Traveling Thief Problem (TTP) - a composition of the Traveling Salesman (TSP) and Knapsack (KP) Problems - has been recently proposed as a benchmark problem to feature a specific type of complexity -called interdependence of component problems - which it is claimed is typically missing from the benchmark problems used to demonstrate the performance of metaheuristics; particularly nature-inspired heuristics.
In this thesis is presented some relevant background on the TSP and KP, and a more careful literature study of the TTP. The study gives an impression of what strategies are expected to deal well with the interdependence, and which ones are not. Particularly, it is conjectured that heuristics that ignore the interdependence, and focus on solving the component problems in isolation, will fare poorly. However, this has not been demonstrated convincingly.
The well known, nature-inspired metaheuristic Ant Colony Optimization (ACO) is adapted as an algorithm for TTP. This adaption is documented and the thesis concludes with a computational study of the implemented algorithm. Said briefly, the idea is to base the algorithm around the naive approach, which solves the component problems in isolation in some nondeterministic way, yielding a solution for the TTP, and repeats this process. When this isolation is broken, the sequence of component-solutions are, conceptually, "chained" together, the construction of each being guided slightly by the previous solution to the other component problem. As the implementation is consistent with this description, the "chain" can be safely broken by reinstating the isolation, yielding a functional algorithm, and the two can be compared. This will facilitate a comparison that is well suited to concluding that isolating the component solvers sacrifices easily realizable performance gains.
For this approach to work, it is necessary that at least one of the subproblems can be solved very efficiently. However, no method exists in the literature which deals specifically with the TSP as a component of the TTP, and those that exist for the KP are not good enough. Thus the existing algorithms Simple Heuristic and Density-Based Heuristic are taken, by subtle adjustments, to realize a much greater potential than previously demonstrated.
Because the TTP arose to answer a call for better benchmark problems, an excellent suite of such problems exists from [PBW+14]. For the nine problems studied here, the results achieved are far better than previous results, and I think that it is safe to conclude that mine is the best published algorithm. But there is yet very little competition. | | 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 |
|