Projects per year
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 language | English |
---|---|
Pages (from-to) | 157-172 |
Number of pages | 16 |
Journal | Soft Computing |
Volume | 20 |
Issue number | 1 |
Early online date | 17 Oct 2014 |
DOIs | |
Publication status | Published - 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.Projects
- 1 Finished
-
Evolutionary Approximation Algorithms for Optimisation: Algorithm Design and Complexity Analysis
Yao, X. (Principal Investigator)
Engineering & Physical Science Research Council
29/04/11 → 28/10/15
Project: Research Councils