A hybrid ensemble approach for the Steiner tree problem in large graphs: A geographical application

Authors: Bouchachia, A. and Prossegger, M.

Journal: Applied Soft Computing Journal

Volume: 11

Issue: 8

Pages: 5745-5754

ISSN: 1568-4946

DOI: 10.1016/j.asoc.2011.03.005

Abstract:

Hybrid approaches are often recommended for dealing in an efficient manner with complex problems that require considerable computational time. In this study, we follow a similar approach consisting of combining spectral clustering and ant colony optimization in a two-stage algorithm for the purpose of efficiently solving the Steiner tree problem in large graphs. The idea of the two-stage approach, called ESC-IAC, is to apply a divide-and-conquer strategy which consists of breaking down the problem into sub-problems to find local solutions before combining them. In the first stage, graph segments (clusters) are generated using an ensemble spectral clustering method for enhancing the quality; whereas in the second step, parallel independent ant colonies are implemented to find local and global minima of the Steiner tree. To illustrate the efficiency and accuracy, ESC-IAC is applied in the context of a geographical application relying on real-world as well as artificial benchmarks. © 2011 Elsevier B.V. All rights reserved.

Source: Scopus