Title: A cellular ant colony optimisation for the generalised Steiner problem

Authors: Martin Pedemonte, Hector Cancela

Addresses: Instituto de Computacion, Facultad de Ingenieria, Universidad de la Republica, J. Herrera y Reissig 565, 11300, Montevideo, Uruguay. ' Instituto de Computacion, Facultad de Ingenieria, Universidad de la Republica, J. Herrera y Reissig 565, 11300, Montevideo, Uruguay

Abstract: The development of exact and heuristic algorithms for communication network design requires ever-growing amounts of computational power. In particular, finding a dependable, fault-tolerant network topology can be modelled as the generalised Steiner problem (GSP). This problem belongs to the NP-hard class, so that exact methods cannot be applied to real life sized problems. An alternative is using metaheuristics, but even in this case the computation time can quickly grow leading to extremely long runs or to degraded quality results. In this paper, we discuss the use of parallel implementations as a means to tackle this computational performance bottleneck. In particular, we concentrate on the ant colony optimisation (ACO) metaheuristic. We review previous ACO approaches for solving the GSP, as well as literature on parallelisation of this method. We propose and develop a new parallel model suitable for ACO, called cellular ACO, which is then applied to the GSP. We present computational results for large GSP instances, showing that cellular ACO finds high quality solutions, comparable to the best published sequential and parallel metaheuristics, while attaining a large speedup, resulting in very good computational efficiency.

Keywords: ant colony optimisation; ACO; cellular algorithms; parallel metaheuristics; Steiner problems; dependable communication networks; network design; fault-tolerant networks.

DOI: 10.1504/IJICA.2010.033650

International Journal of Innovative Computing and Applications, 2010 Vol.2 No.3, pp.188 - 201

Published online: 13 Jun 2010 *

Full-text access for editors Access for subscribers Purchase this article Comment on this article