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 of America 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 of America |
City | Denver |
Period | 20/07/16 → 24/07/16 |
Internet address |
Keywords
- Combinatorial optimisation
- Local search
- Steiner tree problem