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
Open Access
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.
Prize Collecting Steiner Tree Problem, transgenetic algorithm, evolutionary algorithm, path-relinking