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 language | English |
|---|---|
| Title of host publication | GECCO'16 - Proceedings of the 2016 Genetic and Evolutionary Computation Conference |
| Editors | Andrew M. Sutton |
| Place of Publication | New York NY USA |
| Publisher | Association for Computing Machinery (ACM) |
| Pages | 333-340 |
| Number of pages | 8 |
| ISBN (Print) | 9781450342063 |
| DOIs | |
| Publication status | Published - 20 Jul 2016 |
| Event | The Genetic and Evolutionary Computation Conference 2016 - Hyatt Regency Denver Tech Center, Denver, United States Duration: 20 Jul 2016 → 24 Jul 2016 http://gecco-2016.sigevo.org/index.html/ |
Conference
| Conference | The Genetic and Evolutionary Computation Conference 2016 |
|---|---|
| Abbreviated title | GECCO 2016 |
| Country | United States |
| City | Denver |
| Period | 20/07/16 → 24/07/16 |
| Internet address |
Keywords
- Combinatorial optimisation
- Local search
- Steiner tree problem
Cite this
}
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 proceeding › Conference Paper › Research › peer-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 -