A self-adaptive and stagnation-aware breakout local search algorithm on the grid for the Steiner tree problem with revenue, budget and hop constraints


Dokeroglu T., Mengusoglu E.

SOFT COMPUTING, cilt.22, ss.4133-4151, 2018 (SCI İndekslerine Giren Dergi) identifier identifier

  • Cilt numarası: 22 Konu: 12
  • Basım Tarihi: 2018
  • Doi Numarası: 10.1007/s00500-017-2630-7
  • Dergi Adı: SOFT COMPUTING
  • Sayfa Sayıları: ss.4133-4151

Özet

The Steiner tree problem (STP) is a challenging NP-Hard combinatorial optimization problem. The STP with revenue, budget and hop constraints (STPRBH) determines a subtree of a given undirected graph with the defined constraints. In this study, we propose a novel self-adaptive and stagnation-aware breakout local search (BLS) algorithm (Grid-BLS) for the solution of the STPRBH. The proposed Grid-BLS is a parallel algorithm and keeps the parameters of the BLS heuristic in a population at the master node and tunes/updates them with the best performing parameters sent by the slave nodes. The parameter tuning of the BLS heuristic is considered as another optimization job and processed by a genetic algorithm that runs on the master node. The slave nodes perform BLS search and use a multistarting technique that prevents them to get stuck in a local optima by restarting the search processes. A master and slave communication topology is used for communicating with the slave processors. In order to evaluate the performance of the Grid-BLS algorithm, experiments are carried out on 240 benchmark problem instances. The solutions for 226 of these problems are reported to be optimal or the best solutions. The Grid-BLS achieves 21 new best solutions (graphs) that have never been found by any heuristic algorithm so far and performs better than the state-of-the-art heuristic algorithms Greedy, Destroy&Repair, Tabu Search, and Dynamic Memetic.