On investigation of interdependence between sub-problems of the Travelling Thief Problem

Yi Mei, Xiaodong Li, Xin Yao

Research output: Contribution to journalArticlepeer-review

29 Citations (Scopus)
116 Downloads (Pure)

Abstract

In this paper, the interdependence between sub-problems in a complex overall problem is investigated using a benchmark problem called Travelling Thief Problem (TTP), which is a combination of Travelling Salesman Problem (TSP) and Knapsack Problem (KP). First, the analysis on the mathematical formulation shows that it is impossible to decompose the problem into independent sub-problems due to the non-linear relationship in the objective function. Therefore, the algorithm for TTP is not straightforward although each sub-problem alone has been investigated intensively. Then, two meta-heuristics are proposed for TTP. One is the Cooperative Co-evolution (CC) that solves the sub-problems separately and transfers the information between them in each generation. The other is the Memetic Algorithm (MA) that solves TTP as a whole. The comparative results showed that MA consistently obtained much better results than both the standard and dynamic versions of CC within comparable computational budget. This indicates the importance of considering the interdependence between sub-problems in an overall problem like TTP.

Original languageEnglish
Pages (from-to)157-172
Number of pages16
JournalSoft Computing
Volume20
Issue number1
Early online date17 Oct 2014
DOIs
Publication statusPublished - Jan 2016

Keywords

  • Combinatorial optimization
  • Cooperative Co-evolution
  • Evolutionary computation
  • Interdependence
  • Travelling Thief Problem

ASJC Scopus subject areas

  • Software
  • Geometry and Topology
  • Theoretical Computer Science

Fingerprint

Dive into the research topics of 'On investigation of interdependence between sub-problems of the Travelling Thief Problem'. Together they form a unique fingerprint.

Cite this