A Hybrid Transgenetic Algorithm for the Prize Collecting Steiner Tree Problem
Cristine Schmidt, Elizabeth Ferreira Gouvêa Goldbarg, Marco C. Goldbarg · Seventh International Conference on Intelligent Systems Design and Applications (ISDA 2007) · 2007
This work presents a hybrid transgenetic algorithm to solve the Prize Collecting Steiner Tree Problem, an NP-hard combinatorial optimization problem. The proposed approach is based upon endosymbiosis and other transformations of the biological intracellular flow. It is an evolutionary algorithm hybridized with a path-relinking procedure. The algorithm is described and its results are compared with the results of two other approaches proposed previously. The computational experiment shows that the proposed approach is very effective for this problem.