Heuristic evolution with Genetic Programming for Traveling Thief Problem

Yi MEI, Xiaodong LI, Flora SALIM, Xin YAO

Research output: Book Chapters | Papers in Conference ProceedingsConference paper (refereed)Researchpeer-review

23 Citations (Scopus)

Abstract

In many real-world applications, one needs to deal with a large multi-silo problem with interdependent silos. In order to investigate the interdependency between silos (sub-problems), the Traveling Thief Problem (TTP) was designed as a benchmark problem. TTP is a combination of two well-known sub-problems, Traveling Salesman Problem (TSP) and Knapsack Problem (KP). Although each sub-problem has been intensively investigated, the interdependent combination has been demonstrated to be challenging, and cannot be solved by simply solving the sub-problems separately. The Two-Stage Memetic Algorithm (TSMA) is an effective approach that has decent solution quality and scalability, which consists of a tour improvement stage and an item picking stage. Unlike the traditional TSP local search operators adopted in the former stage, the heuristic for the latter stage is rather intuitive. To further investigate the effect of item picking heuristic, Genetic Programming (GP) is employed to evolve a gain function and a picking function, respectively. The resultant two heuristics were tested on some representative TTP instances, and showed competitive performance, which indicates the potential of evolving more promising heuristics for solving TTP more systematically by GP. © 2015 IEEE.
Original languageEnglish
Title of host publication2015 IEEE Congress on Evolutionary Computation, CEC 2015 - Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages2753-2760
Number of pages8
ISBN (Print)9781479974924
DOIs
Publication statusPublished - May 2015
Externally publishedYes

Keywords

  • genetic programming
  • interdependent optimization
  • memetic algorithm
  • Traveling thief problem

Fingerprint

Dive into the research topics of 'Heuristic evolution with Genetic Programming for Traveling Thief Problem'. Together they form a unique fingerprint.

Cite this