A Graph-Based Crossover and Soft-Repair Operators for the Steiner Tree Problem

• Giliard Almeida de Godoi UTFPR https://orcid.org/0000-0002-1715-0852
• Renato Tinós USP https://orcid.org/0000-0003-4027-8851
• Danilo Sipoli Sanches UTFPR https://orcid.org/0000-0002-8972-5221

Resumo

In the Steiner Tree Problem in Graphs, a subset of nodes, called terminals, must be efficiently interconnected. The graph is undirected and weighted, and candidate solutions can include additional nodes called Steiner vertices. The problem is NP-complete, and optimization algorithms based on population metaheuristics, e.g., Genetic Algorithms (GAs), have been proposed. However, traditional recombination operators may produce inefficient solutions for graph-based problems. We propose a new recombination operator for the Steiner Tree Problem based on the graph representation. The new operator is a kind of partition crossover: it breaks the graph formed by the union of two parents solutions and decomposes the evaluation function by finding connected subgraphs. We also investigate two soft-repair operators that produce small changes in candidate solutions: an MST transformation and a pruning repair. The GA with the proposed crossover operator was able to find the global optimum solution for all tested instances and has a success rate of 28% in the worst case. The experiments with the proposed crossover presented a quick convergence to optimal solutions, and an average solution cost lower in most cases than other approaches.

Palavras-chave: Steiner Tree Problem in Graphs, Partition based crossover, Genetic algorithms