A fitness landscape analysis of the travelling thief problem

Mohamed El Yafrani*, Markus Wagner, Marcella Martins, Myriam Delgado, Ricardo Lüders, Mehdi El Krari, Belaïd Ahiod

*Corresponding author for this work

Research output: Contribution to book/anthology/report/conference proceedingArticle in proceedingResearchpeer-review

24 Citations (Scopus)

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.

Original languageEnglish
Title of host publicationGECCO 2018 - Proceedings of the 2018 Genetic and Evolutionary Computation Conference
Number of pages8
PublisherAssociation for Computing Machinery
Publication date2 Jul 2018
Pages277-284
ISBN (Electronic)9781450356183
DOIs
Publication statusPublished - 2 Jul 2018
Externally publishedYes
Event2018 Genetic and Evolutionary Computation Conference, GECCO 2018 - Kyoto, Japan
Duration: 15 Jul 201819 Jul 2018

Conference

Conference2018 Genetic and Evolutionary Computation Conference, GECCO 2018
Country/TerritoryJapan
CityKyoto
Period15/07/201819/07/2018
Sponsoret al., Nature Research, Sentient, SparkCognition, Springer, Uber AI Labs
SeriesGECCO 2018 - Proceedings of the 2018 Genetic and Evolutionary Computation Conference

Keywords

  • Basins of attraction
  • Fitness landscape
  • Local optima networks
  • Multi-component problems
  • Travelling thief problem

Fingerprint

Dive into the research topics of 'A fitness landscape analysis of the travelling thief problem'. Together they form a unique fingerprint.

Cite this