Applying River Formation Dynamics to the Steiner Tree Problem
Pablo Rabanal, Ismael Rodrı́guez, Fernando Rubio · 2010
River Formation Dynamics (RFD) is a heuristic optimization algorithm based on copying how water forms rivers by eroding the ground and depositing sediments. After drops transform the landscape by increasing/decreasing the altitude of places, solutions are given in the form of paths of decreasing altitudes. Decreasing gradients are constructed, and these gradients are followed by subsequent drops to compose new gradients and reinforce the best ones. We apply this method to solve the Steiner Tree Problem (STP), a well-known NP-hard problem having applications to areas like telecommunications routing and VLSI design among many others. We show that the gradient orientation of RFD makes it specially suitable for solving this problem, and we report the results of several experiments where RFD is applied to benchmark graphs from the SteinLib Testdata Library.