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

Angus Kenny, Xiaodong Li, A. K. Qin, Andreas T. Ernst

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review


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 metaheuris-tics 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.

Original languageEnglish
Title of host publicationGECCO'16 - Proceedings of the 2016 Genetic and Evolutionary Computation Conference
EditorsAndrew M. Sutton
Place of PublicationNew York NY USA
PublisherAssociation for Computing Machinery (ACM)
Number of pages8
ISBN (Print)9781450342063
Publication statusPublished - 20 Jul 2016
EventThe Genetic and Evolutionary Computation Conference 2016 - Hyatt Regency Denver Tech Center, Denver, United States of America
Duration: 20 Jul 201624 Jul 2016


ConferenceThe Genetic and Evolutionary Computation Conference 2016
Abbreviated titleGECCO 2016
CountryUnited States of America
Internet address


  • Combinatorial optimisation
  • Local search
  • Steiner tree problem

Cite this