Studying the application of ant colony optimization and river formation dynamics to the steiner tree problem

River formation dynamics (RFD) (Rabanal et al. in Using river formation dynamics to design heuristic algorithms. In: Unconventional computation, UC’07, LNCS 4618. Springer, pp 163–177, 2007 ; Rabanal et al. in Applying river formation dynamics to solve NP-complete problems. In: Chiong R (ed) Nature-...

Full description

Saved in:
Bibliographic Details
Published in:Evolutionary intelligence 2011-03, Vol.4 (1), p.51-65
Main Authors: Rabanal, Pablo, Rodríguez, Ismael, Rubio, Fernando
Format: Article
Language:English
Subjects:
Applications of Mathematics
Artificial Intelligence
Bioinformatics
Control
Engineering
Mathematical and Computational Engineering
Mechatronics
Robotics
Special Issue
Statistical Physics and Dynamical Systems
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:River formation dynamics (RFD) (Rabanal et al. in Using river formation dynamics to design heuristic algorithms. In: Unconventional computation, UC’07, LNCS 4618. Springer, pp 163–177, 2007 ; Rabanal et al. in Applying river formation dynamics to solve NP-complete problems. In: Chiong R (ed) Nature-inspired algorithms for optimisation, volume 193 of Studies in Computational Intelligence. Springer, pp 333–368, 2009 ) is a heuristic optimization algorithm based on copying how water forms rivers by eroding the ground and depositing sediments. We apply this method to solve the Steiner tree problem (STP), a well-known NP-hard problem having applications to areas like telecommunications routing or VLSI design among many others. We show that the gradient orientation of RFD makes it especially suitable for solving this problem, and we report the results of several experiments where RFD, as well as an implementation of Ant Colony Optimization (ACO) (Dorigo in ant colony optimization. MIT Press, New York, 2004 ), are applied to some benchmark graphs from the SteinLib Testdata Library (Koch in Steinlib testdata library. Technical report, Konrad-Zuse-Zentrum für Informationstechnik Berlin, 2009 ). We also study the capability of RFD and ACO to deal with a scenario where the graph is modified after a solution is found, and next a solution for the new graph has to be found - either by running the algorithm from scratch or by adapting the structures previously formed by the algorithms to construct their previous solution.
ISSN:1864-5909
1864-5917
DOI:10.1007/s12065-011-0049-0