Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/128928
Citations | ||
Scopus | Web of Science® | Altmetric |
---|---|---|
?
|
?
|
Type: | Journal article |
Title: | Theoretical analysis of local search and simple evolutionary algorithms for the generalized travelling salesperson problem |
Author: | Pourhassan, M. Neumann, F. |
Citation: | Evolutionary Computation, 2019; 27(3):525-558 |
Publisher: | Massachusetts Institute of Technology Press (MIT Press) |
Issue Date: | 2019 |
ISSN: | 1063-6560 1530-9304 |
Statement of Responsibility: | Mojgan Pourhassan, Frank Neumann |
Abstract: | The generalized travelling salesperson problem is an important NP-hard combinatorial optimization problem for which metaheuristics, such as local search and evolutionary algorithms, have been used very successfully. Two hierarchical approaches with different neighbourhood structures, namely a cluster-based approach and a node-based approach, have been proposed by Hu and Raidl (2008) for solving this problem. In this article, local search algorithms and simple evolutionary algorithms based on these approaches are investigated from a theoretical perspective. For local search algorithms, we point out the complementary abilities of the two approaches by presenting instances where they mutually outperform each other. Afterwards, we introduce an instance which is hard for both approaches when initialized on a particular point of the search space, but where a variable neighbourhood search combining them finds the optimal solution in polynomial time. Then we turn our attention to analysing the behaviour of simple evolutionary algorithms that use these approaches. We show that the node-based approach solves the hard instance of the cluster-based approach presented in Corus et al. (2016) in polynomial time. Furthermore, we prove an exponential lower bound on the optimization time of the node-based approach for a class of Euclidean instances. |
Keywords: | Generalized travelling salesperson problem parameterised complexity analysis bi-level optimisation evolutionary algorithms combinatorial optimisation. |
Rights: | © 2018 Massachusetts Institute of Technology |
DOI: | 10.1162/evco_a_00233 |
Published version: | https://dl-acm-org.proxy.library.adelaide.edu.au/doi/abs/10.1162/evco_a_00233 |
Appears in Collections: | Aurora harvest 8 Computer Science publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
hdl_128928.pdf | Accepted version | 743.42 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.