On the Fitness Landscapes of Interdependency Models in the Travelling Thief Problem
This work addresses the need to understand interdependencies in combinatorial optimization for real-world applications, but it is incremental as it extends existing TTP models without introducing new algorithms.
The study investigated the impact of different dependency forms in the Travelling Thief Problem using Local Optima Networks to analyze fitness landscapes, finding that certain dependencies significantly alter the problem's complexity and search difficulty.
Since its inception in 2013, the Travelling Thief Problem (TTP) has been widely studied as an example of problems with multiple interconnected sub-problems. The dependency in this model arises when tying the travelling time of the "thief" to the weight of the knapsack. However, other forms of dependency as well as combinations of dependencies should be considered for investigation, as they are often found in complex real-world problems. Our goal is to study the impact of different forms of dependency in the TTP using a simple local search algorithm. To achieve this, we use Local Optima Networks, a technique for analysing the fitness landscape.