JUCS - Journal of Universal Computer Science 16(14): 1882-1901, doi: 10.3217/jucs-016-14-1882
Applying RFD to Construct Optimal Quality-Investment Trees
Pablo Rabanal‡, Ismael Rodriguez‡, Fernando Rubio‡‡ Universidad Complutense de Madrid, Madrid, Spain
Corresponding author: Pablo Rabanal ( prabanal@fdi.ucm.es ) © Pablo Rabanal, Ismael Rodriguez, Fernando Rubio. This article is freely available under the J.UCS Open Content License. Citation:
Rabanal P, Rodriguez I, Rubio F (2010) Applying RFD to Construct Optimal Quality-Investment Trees. JUCS - Journal of Universal Computer Science 16(14): 1882-1901. https://doi.org/10.3217/jucs-016-14-1882 |  |
Abstract
River Formation Dynamics (RFD) is an evolutionary computation methodbased on copying how drops form rivers by eroding the ground and depositing sediments. Given a cost-evaluated graph, we apply RFD to find a way to connect a givenset of origins with a given destination in such a way that distances from origins to the destination are minimized (thus improving the quality of service) but costs to build theconnecting infrastructure are minimized (thus reducing investment expenses). After we prove the NP-completeness of this problem, we apply both RFD and an Ant ColonyOptimization (ACO) approach to heuristically solve it, and some experimental results are reported.
Keywords
River Formation Dynamics, Ant Colony Optimization Algorithms, Heuristic Algorithms, NP-hard problems