On the Fitness Landscapes of Interdependency Models in the Travelling Thief Problem
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Solving Travelling Thief Problems using Coordination Based Methods
A travelling thief problem (TTP) is a proxy to real-life problems such as postal collection. TTP comprises an entanglement of a travelling salesman problem (TSP) and a knapsack problem (KP) since items of KP are scattere…
Weighted-Scenario Optimisation for the Chance Constrained Travelling Thief Problem
The chance constrained travelling thief problem (chance constrained TTP) has been introduced as a stochastic variation of the classical travelling thief problem (TTP) in an attempt to embody the effect of uncertainty in …
Evolutionary AlgorithmsEvolutionary Computation plus Dynamic Programming for the Bi-Objective Travelling Thief Problem
This research proposes a novel indicator-based hybrid evolutionary approach that combines approximate and exact algorithms. We apply it to a new bi-criteria formulation of the travelling thief problem, which is known to …
Solving the Travelling Thief Problem based on Item Selection Weight and Reverse Order Allocation
The Travelling Thief Problem (TTP) is a challenging combinatorial optimization problem that attracts many scholars. The TTP interconnects two well-known NP-hard problems: the Travelling Salesman Problem (TSP) and the 0-1…
Combinatorial OptimizationThe Dynamic Travelling Thief Problem: Benchmarks and Performance of Evolutionary Algorithms
Many real-world optimisation problems involve dynamic and stochastic components. While problems with multiple interacting components are omnipresent in inherently dynamic domains like supply-chain optimisation and logist…
Evolutionary Algorithmsvalid