Heuristic evolution with Genetic Programming for Traveling Thief Problem

Publication Year: 2015 Publication Type : ConferenceProceeding

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 (subproblems), 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.


BibTex:

@inproceedings{DBLP:conf/cec/MeiLSY15,
    author = {Yi Mei and Xiaodong Li and Flora D. Salim and Xin Yao},
    bibsource = {dblp computer science bibliography, https://dblp.org},
    biburl = {https://dblp.org/rec/conf/cec/MeiLSY15.bib},
    booktitle = {IEEE Congress on Evolutionary Computation, CEC 2015, Sendai, Japan, May 25-28, 2015},
    doi = {10.1109/CEC.2015.7257230},
    pages = {2753--2760},
    publisher = {IEEE},
    timestamp = {Thu, 05 Dec 2019 00:00:00 +0100},
    title = {Heuristic evolution with Genetic Programming for Traveling Thief Problem},
    url = {https://doi.org/10.1109/CEC.2015.7257230},
    year = {2015}
}

Cite:

Related Publications

RUP: Large Room Utilisation Prediction with carbon dioxide sensor
Type : JournalArticle
Show More
A Scalable Room Occupancy Prediction with Transferable Time Series Decomposition of CO 2 Sensor Data
Type : JournalArticle
Show More
Topical Event Detection on Twitter
Type : ConferenceProceeding
Show More

© 2021 Flora Salim - CRUISE Research Group.