Deakin University
Browse

File(s) under permanent embargo

Evolutionary computation plus dynamic programming for the Bi-objective travelling thief problem

conference contribution
posted on 2018-07-02, 00:00 authored by J Wu, M Wagner, Sergey PolyakovskiySergey Polyakovskiy, F Neumann
This research proposes a novel indicator-based hybrid evolutionary approach that combines approximate and exact algorithms. We apply it to a new bi-criteria formulation of the travelling thief problem, which is known to the Evolutionary Computation community as a benchmark multi-component optimisation problem that interconnects two classical NP-hard problems: the travelling salesman problem and the 0-1 knapsack problem. Our approach employs the exact dynamic programming algorithm for the underlying packing while travelling problem as a subroutine within a bi-objective evolutionary algorithm. This design takes advantage of the data extracted from Pareto fronts generated by the dynamic program to achieve better solutions. Furthermore, we develop a number of novel indicators and selection mechanisms to strengthen synergy of the two algorithmic components of our approach. The results of computational experiments show that the approach is capable to outperform the state-of-the-art results for the single-objective case of the problem.

History

Pagination

777-784

Location

Kyoto, Japan

Start date

2018-07-15

End date

2018-07-19

ISBN-13

9781450356183

Language

eng

Publication classification

E1 Full written paper - refereed

Copyright notice

2018, Association for Computing Machinery

Editor/Contributor(s)

Aguirre H

Title of proceedings

GECCO 2018 : Proceedings of the 2018 Genetic and Evolutionary Computation Conference

Event

Special Interest Group on Genetic and Evolutionary Computation. Conference (2018 : Kyoto, Japan)

Publisher

Association for Computing Machinery

Place of publication

New York, N.Y.

Series

Special Interest Group on Genetic and Evolutionary Computation Conference