A Parallel Distributed Genetic Algorithm for the Prize Collecting Steiner Tree Problem

摘要

Combinatorial optimization problems are commonly tackled through the use of metaheuristics aimed to improve the way the search space is explored (diversification) and how promising areas are exploited (intensification), in order to obtain good-quality solutions. We present a distributed genetic algorithm to solve the Prize Collecting Steiner Tree Problem, a classical combinatorial optimization problem. The proposed algorithm improves the quality of the solutions by asynchronously combining distributed populations that evolve in parallel, starting from initial heterogeneous configurations. To show the effectiveness of this approach an empirical study that considers both execution time and solution quality is presented. Results show that better solutions are reached when initial populations combine configurations with high and low fitness.