A Hybrid Transgenetic Algorithm for the Prize Collecting Steiner Tree Problem

Elizabeth Ferreira Gouvêa Goldbarg (Federal University of Rio Grande do Norte, Brazil)

Marco César Goldbarg (Federal University of Rio Grande do Norte, Brazil)

Cristine Cunha Schmidt (Federal University of Rio Grande do Norte, Brazil)

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, evolutionary algorithm, path-relinking, transgenetic algorithm

Categories: G.2.3, I.2.8