Algoritmos evolutivos aplicados ao problema da árvore de steiner euclidiano

Abstract

This work presents the application of hybrid evolutionary algorithms to the Euclidean Steiner tree problem. This is an optimization problem whose objective is to obtain a minimum length tree to interconnect a set of fixed points. To achieve this goal it is allowed to add new points, called Steiner points. In order to obtain good quality solutions in viable computational time, two heuristics are used, one uses the differential evolution algorithm in which mutation strategies are tested and the other makes use of a genetic algorithm, which investigates the effects of relatively greedy crossover and mutation operators, overlapping of generations, and evolutionary strategies. The experiments are performed with the problems of the OR-Library and present results close to the best methods present in the literature.