Please use this identifier to cite or link to this item: http://hdl.handle.net/2440/108639
Citations
Scopus Web of Science® Altmetric
?
?
Type: Conference paper
Title: Socially inspired algorithms for the traveling thief problem
Author: Bonyadi, M.
Michalewicz, Z.
Przybyłek, M.
Wierzbicki, A.
Citation: Proceedings of the 2014 Genetic and Evolutionary Computation Conference, 2014 / Igel, C. (ed./s), pp.421-428
Publisher: Association for Ccomputing Machinery
Issue Date: 2014
ISBN: 9781450326629
Conference Name: 2014 Genetic and Evolutionary Computation Conference (GECCO '14) (12 Jul 2014 - 16 Jul 2014 : Vancouver, Canada)
Statement of
Responsibility: 
Mohammad Reza Bonyadi, Zbigniew Michalewicz, Michał Roman Przybyłek, Adam Wierzbicki
Abstract: Many real-world problems are composed of two or more problems that are interdependent on each other. The interaction of such problems usually is quite complex and solving each problem separately cannot guarantee the optimal solution for the overall multi-component problem. In this paper we experiment with one particular 2-component problem, namely the Traveling Thief Problem (TTP). TTP is composed of the Traveling Salesman Problem (TSP) and the Knapsack Problem (KP).We investigate two heuristic methods to deal with TTP. In the first approach we decompose TTP into two sub-problems, solve them by separate modules/ algorithms (that communicate with each other), and combine the solutions to obtain an overall approximated solution to TTP (this method is called CoSolver ). The second approach is a simple heuristic (called density-based heuristic, DH) method that generates a solution for the TSP component first (a version of Lin-Kernighan algorithm is used) and then, based on the fixed solution for the TSP component found, it generates a solution for the KP component (associated with the given TTP). In fact, this heuristic ignores the interdependency between sub-problems and tries to solve the sub-problems sequentially. These two methods are applied to some generated TTP instances of different sizes. Our comparisons show that CoSolver outperforms DH specially in large instances.
Keywords: Traveling thief problem, co-evolution, heuristics, metaheuristics, multi-objective optimization, non-separable problems, real-world optimization problems
Rights: Copyright 2014 ACM. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org.
RMID: 0030022053
DOI: 10.1145/2576768.2598367
Appears in Collections:Computer Science publications

Files in This Item:
File Description SizeFormat 
RA_hdl_108639.pdfRestricted Access501.88 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.