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

Research output: Contribution to journalArticlepeer-review

Authors

Colleges, School and Institutes

External organisations

  • RMIT University

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.

Details

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

Keywords

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