A cellular ant colony optimisation for the generalised Steiner problem
by Martin Pedemonte, Hector Cancela
International Journal of Innovative Computing and Applications (IJICA), Vol. 2, No. 3, 2010

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.

Online publication date: Sun, 13-Jun-2010

The full text of this article is only available to individual subscribers or to users at subscribing institutions.

 
Existing subscribers:
Go to Inderscience Online Journals to access the Full Text of this article.

Pay per view:
If you are not a subscriber and you just want to read the full contents of this article, buy online access here.

Complimentary Subscribers, Editors or Members of the Editorial Board of the International Journal of Innovative Computing and Applications (IJICA):
Login with your Inderscience username and password:

Username:        Password:          Forgotten your password?

Want to subscribe?
A subscription gives you complete access to all articles in the current issue, as well as to all articles in the previous three years (where applicable). See our Orders page to subscribe.

If you still need assistance, please email subs@inderscience.com