JUCS - Journal of Universal Computer Science 14(15): 2491-2511, doi: 10.3217/jucs-014-15-2491
A Hybrid Transgenetic Algorithm for the Prize Collecting Steiner Tree Problem
expand article infoElizabeth Ferreira Gouvêa Goldbarg‡, Marco César Goldbarg‡, Cristine Cunha Schmidt‡
‡ Federal University of Rio Grande do Norte, Natal, Brazil

Corresponding author: Elizabeth Ferreira Gouvêa Goldbarg ( beth@dimap.ufrn.br )

© Elizabeth Ferreira Gouvêa Goldbarg, Marco Goldbarg, Cristine Schmidt.
This article is freely available under the J.UCS Open Content License.
Citation: Goldbarg EFG, Goldbarg MC, Schmidt CC (2008) A Hybrid Transgenetic Algorithm for the Prize Collecting Steiner Tree Problem. JUCS - Journal of Universal Computer Science 14(15): 2491-2511. https://doi.org/10.3217/jucs-014-15-2491
Open Access
Abstract
Evolutionary algorithms are effective search tools for tackling difficult optimization problems. In this paper an algorithm based on living processes where cooperation is the main evolutionary strategy is applied to the Prize Collecting Steiner Tree Problem, an NP-hard combinatorial optimization problem. The Transgenetic Algorithm presented here is hybridized with path-relinking. Computational results of an experiment performed with benchmark instances are reported. The results obtained for the Prize Collecting Steiner Tree Problem with the application of the hybrid Transgenetic Algorithm are compared with the results of three effective approaches presented previously. The computational experiment shows that the proposed approach is very competitive concerning both quality of solution and processing time.
Keywords
Prize Collecting Steiner Tree Problem, transgenetic algorithm, evolutionary algorithm, path-relinking