@inproceedings{fc6323ac3bea4b669acce8cfaa38cb73,
title = "A fitness landscape analysis of the travelling thief problem",
abstract = "Local Optima Networks are models proposed to understand the structure and properties of combinatorial landscapes. The fitness landscape is explored as a graph whose nodes represent the local optima (or basins of attraction) and edges represent the connectivity between them. In this paper, we use this representation to study a combinatorial optimisation problem, with two interdepend components, named the Travelling Thief Problem (TTP). The objective is to understand the search space structure of the TTP using basic local search heuristics and to distinguish the most impactful problem features. We create a large set of enumerable TTP instances and generate a Local Optima Network for each instance using two hill climbing variants. Two problem features are investigated, namely the knapsack capacity and profit-weight correlation. Our insights can be useful not only to design landscape-aware local search heuristics, but also to better understand what makes the TTP challenging for specific heuristics.",
keywords = "Basins of attraction, Fitness landscape, Local optima networks, Multi-component problems, Travelling thief problem",
author = "{El Yafrani}, Mohamed and Markus Wagner and Marcella Martins and Myriam Delgado and Ricardo L{\"u}ders and {El Krari}, Mehdi and Bela{\"i}d Ahiod",
year = "2018",
month = jul,
day = "2",
doi = "10.1145/3205455.3205537",
language = "English",
series = "GECCO 2018 - Proceedings of the 2018 Genetic and Evolutionary Computation Conference",
pages = "277--284",
booktitle = "GECCO 2018 - Proceedings of the 2018 Genetic and Evolutionary Computation Conference",
publisher = "Association for Computing Machinery",
address = "United States",
note = "2018 Genetic and Evolutionary Computation Conference, GECCO 2018 ; Conference date: 15-07-2018 Through 19-07-2018",
}