Journal
SOFT COMPUTING
Volume 20, Issue 1, Pages 157-172Publisher
SPRINGER
DOI: 10.1007/s00500-014-1487-2
Keywords
Combinatorial optimization; Evolutionary computation; Cooperative Co-evolution; Travelling Thief Problem; Interdependence
Categories
Funding
- EPSRC [EP/I010297/1] Funding Source: UKRI
- Engineering and Physical Sciences Research Council [EP/I010297/1] Funding Source: researchfish
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available