Operadores de cruzamento para o problema da árvore de Steiner em grafos

Abstract

The Steiner Tree Problems in Graphs (STPG) aims to find the lowest cost tree- graph that connects a subset of terminal nodes. The general case for this problem belongs to the NP-hard class, and several approaches have been developed to discover better solutions. Metaheuristics also have been employed, although they were not so competitive when compared with more traditional approaches. When it comes to Genetic Algorithms (GA), this worst performance might be due to inefficient representation and operators for the problem constraints. For instance, binary representation and its operators can represent unfeasible solutions such as disconnected subgraphs. Alternatively, the Edge Sets representation narrows the population to feasible solutions (connected and cycle-free subgraphs). It represents a tree just by the set of its edges, and its operators are based on algorithms that compute a spanning tree for a graph. The partition-based crossover originally proposed to recombine Hamiltonian cycles for the Travelling Salesman Problem also handles directly with the solutions' graph representation. In this research, we propose an adaptation for the partition-based crossover for the STPG, named PXST. Then, we compare the proposed operator with the others from the Edge Sets representation. Furthermore, we proposed two soft-repair operators that only improve the solutions' cost. We ran experiments with problems instance from classes B and C from OR- Library datasets. They showed that the proposed operator was competitive in terms of the best solution cost found. It also found the best global solution for all instances from class B (It had a success rate of 18% for the worst case) and for class C was also better in some cases. Regarding the execution time, the GA with PXST was faster in many cases, mainly due to the quick population convergence.