A population-based local search technique with random descent and jump for the Steiner tree problem in graphs

Kenny, A, Li, X, Qin, K and Ernst, A 2016, 'A population-based local search technique with random descent and jump for the Steiner tree problem in graphs', in T. Friedrich (ed.) Proceedings of the 2016 Annual Conference on Genetic and Evolutionary Computation (GECCO 2016), Denver, United States, 20-24 July 2016, pp. 333-340.


Document type: Conference Paper
Collection: Conference Papers

Title A population-based local search technique with random descent and jump for the Steiner tree problem in graphs
Author(s) Kenny, A
Li, X
Qin, K
Ernst, A
Year 2016
Conference name The Genetic and Evolutionary Computation Conference (GECCO 2016)
Conference location Denver, United States
Conference dates 20-24 July 2016
Proceedings title Proceedings of the 2016 Annual Conference on Genetic and Evolutionary Computation (GECCO 2016)
Editor(s) T. Friedrich
Publisher Association for Computing Machinery (ACM)
Place of publication United States
Start page 333
End page 340
Total pages 8
Abstract The Steiner tree problem in graphs (STPG) is a well known NP-hard combinatorial problem with various applications in transport, computational biology, network and VLSI design. Exact methods have been developed to solve this problem to proven optimality, however the exponential nature of these algorithms mean that they become intractable with large-scale instances of the problem. Because of this phenomenon, there has been considerable research into using metaheuristics to obtain good quality solutions in a reasonable time. This paper presents a hybrid local search technique which is an extension of techniques from the literature with an added random jump operator which prevents the algorithm from becoming stuck in local minima. It is compared against greedy local search, the hybrid local search technique it extends and two metaheuristic techniques from the current literature and is shown to outperform them in nearly all cases.
Subjects Neural, Evolutionary and Fuzzy Computation
DOI - identifier 10.1145/2908812.2908860
Copyright notice © 2016 ACM
ISBN 9781450342063
Versions
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 0 times in Thomson Reuters Web of Science Article
Altmetric details:
Access Statistics: 155 Abstract Views  -  Detailed Statistics
Created: Wed, 10 Aug 2016, 07:48:00 EST by Catalyst Administrator
© 2014 RMIT Research Repository • Powered by Fez SoftwareContact us