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

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 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)
Pages333-340
Number of pages8
ISBN (Print)9781450342063
DOIs
Publication statusPublished - 20 Jul 2016
EventThe Genetic and Evolutionary Computation Conference 2016 - Hyatt Regency Denver Tech Center, Denver, United States
Duration: 20 Jul 201624 Jul 2016
http://gecco-2016.sigevo.org/index.html/

Conference

ConferenceThe Genetic and Evolutionary Computation Conference 2016
Abbreviated titleGECCO 2016
CountryUnited States
CityDenver
Period20/07/1624/07/16
Internet address

Keywords

  • Combinatorial optimisation
  • Local search
  • Steiner tree problem

Cite this

Kenny, A., Li, X., Qin, A. K., & Ernst, A. T. (2016). A population-based local search technique with random descent and jump for the Steiner tree problem in graphs. In A. M. Sutton (Ed.), GECCO'16 - Proceedings of the 2016 Genetic and Evolutionary Computation Conference (pp. 333-340). New York NY USA: Association for Computing Machinery (ACM). https://doi.org/10.1145/2908812.2908860
Kenny, Angus ; Li, Xiaodong ; Qin, A. K. ; Ernst, Andreas T. / A population-based local search technique with random descent and jump for the Steiner tree problem in graphs. GECCO'16 - Proceedings of the 2016 Genetic and Evolutionary Computation Conference. editor / Andrew M. Sutton. New York NY USA : Association for Computing Machinery (ACM), 2016. pp. 333-340
@inproceedings{5e49ea2d34d14c0996f6a62bcbe7c1c8,
title = "A population-based local search technique with random descent and jump for the Steiner tree problem in graphs",
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 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.",
keywords = "Combinatorial optimisation, Local search, Steiner tree problem",
author = "Angus Kenny and Xiaodong Li and Qin, {A. K.} and Ernst, {Andreas T.}",
year = "2016",
month = "7",
day = "20",
doi = "10.1145/2908812.2908860",
language = "English",
isbn = "9781450342063",
pages = "333--340",
editor = "Sutton, {Andrew M.}",
booktitle = "GECCO'16 - Proceedings of the 2016 Genetic and Evolutionary Computation Conference",
publisher = "Association for Computing Machinery (ACM)",
address = "United States",

}

Kenny, A, Li, X, Qin, AK & Ernst, AT 2016, A population-based local search technique with random descent and jump for the Steiner tree problem in graphs. in AM Sutton (ed.), GECCO'16 - Proceedings of the 2016 Genetic and Evolutionary Computation Conference. Association for Computing Machinery (ACM), New York NY USA, pp. 333-340, The Genetic and Evolutionary Computation Conference 2016, Denver, United States, 20/07/16. https://doi.org/10.1145/2908812.2908860

A population-based local search technique with random descent and jump for the Steiner tree problem in graphs. / Kenny, Angus; Li, Xiaodong; Qin, A. K.; Ernst, Andreas T.

GECCO'16 - Proceedings of the 2016 Genetic and Evolutionary Computation Conference. ed. / Andrew M. Sutton. New York NY USA : Association for Computing Machinery (ACM), 2016. p. 333-340.

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

TY - GEN

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

AU - Kenny, Angus

AU - Li, Xiaodong

AU - Qin, A. K.

AU - Ernst, Andreas T.

PY - 2016/7/20

Y1 - 2016/7/20

N2 - 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.

AB - 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.

KW - Combinatorial optimisation

KW - Local search

KW - Steiner tree problem

UR - http://www.scopus.com/inward/record.url?scp=84986000681&partnerID=8YFLogxK

U2 - 10.1145/2908812.2908860

DO - 10.1145/2908812.2908860

M3 - Conference Paper

SN - 9781450342063

SP - 333

EP - 340

BT - GECCO'16 - Proceedings of the 2016 Genetic and Evolutionary Computation Conference

A2 - Sutton, Andrew M.

PB - Association for Computing Machinery (ACM)

CY - New York NY USA

ER -

Kenny A, Li X, Qin AK, Ernst AT. A population-based local search technique with random descent and jump for the Steiner tree problem in graphs. In Sutton AM, editor, GECCO'16 - Proceedings of the 2016 Genetic and Evolutionary Computation Conference. New York NY USA: Association for Computing Machinery (ACM). 2016. p. 333-340 https://doi.org/10.1145/2908812.2908860