On the Fitness Landscapes of Interdependency Models in the Travelling Thief Problem

2022/02/28 by Mohamed El Yafrani, Yafrani, Mohamed El, Marcella Scoczynski Ribeiro Martins +10 · 1 citation
Computer Science · Social Sciences · #Artificial Intelligence (cs.AI) #Evolutionary Algorithms and Applications #Evolutionary Game Theory and Cooperation #FOS: Computer and information sciences #Metaheuristic Optimization Algorithms Research #cs.AI

paper · pdf · doi:10.48550/arxiv.2203.04363

arxiv created 2022/02/28 · openalex publication_date 2022/02/28 · arxiv updated 2022/03/10 · openalex created_date 2022/04/03 · openalex updated_date 2026/07/28

Abstract

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.

Cited by

• Weighted-Scenario Optimisation for the Chance Constrained Travelling Thief Problem

Related

• A case study of algorithm selection for the traveling thief problem
• The Dynamic Travelling Thief Problem: Benchmarks and Performance of Evolutionary Algorithms
• Dynamic Multi-objective Optimization of the Travelling Thief Problem
• On the Use of Quality Diversity Algorithms for The Traveling Thief Problem
• Exact Approaches for the Travelling Thief Problem