Open Access Open Access  Restricted Access Subscription Access

Automatically Produced Algorithms for the Generalized Minimum Spanning Tree Problem


Affiliations
1 DEI, University of Bologna, Viale Risorgimento 2, 40136 Bologna, Italy
2 Departamento de Ingenieria Informiatica, Universidad de Santiago de Chile, 3659 Avenida Ecuador, 9170124 Santiago, Chile
 

The generalized minimum spanning tree problem consists of finding a minimum cost spanning tree in an undirected graph for which the vertices are divided into clusters. Such spanning tree includes only one vertex from each cluster. Despite the diverse practical applications for this problem, the NP-hardness continues to be a computational challenge. Good quality solutions for some instances of the problem have been found by combining specific heuristics or by including them within a metaheuristic. However studied combinations correspond to a subset of all possible combinations. In this study a technique based on a genotypephenotype genetic algorithmto automatically construct new algorithms for the problem, which contain combinations of heuristics, is presented. The produced algorithms are competitive in terms of the quality of the solution obtained. This emerges from the comparison of the performance with problem-specific heuristics and with metaheuristic approaches.
User
Notifications
Font Size

Abstract Views: 66

PDF Views: 3




  • Automatically Produced Algorithms for the Generalized Minimum Spanning Tree Problem

Abstract Views: 66  |  PDF Views: 3

Authors

Carlos Contreras-Bolton
DEI, University of Bologna, Viale Risorgimento 2, 40136 Bologna, Italy
Carlos Rey
Departamento de Ingenieria Informiatica, Universidad de Santiago de Chile, 3659 Avenida Ecuador, 9170124 Santiago, Chile
Sergio Ramos-Cossio
Departamento de Ingenieria Informiatica, Universidad de Santiago de Chile, 3659 Avenida Ecuador, 9170124 Santiago, Chile
Claudio Rodriguez
Departamento de Ingenieria Informiatica, Universidad de Santiago de Chile, 3659 Avenida Ecuador, 9170124 Santiago, Chile
Felipe Gatica
Departamento de Ingenieria Informiatica, Universidad de Santiago de Chile, 3659 Avenida Ecuador, 9170124 Santiago, Chile
Victor Parada
Departamento de Ingenieria Informiatica, Universidad de Santiago de Chile, 3659 Avenida Ecuador, 9170124 Santiago, Chile

Abstract


The generalized minimum spanning tree problem consists of finding a minimum cost spanning tree in an undirected graph for which the vertices are divided into clusters. Such spanning tree includes only one vertex from each cluster. Despite the diverse practical applications for this problem, the NP-hardness continues to be a computational challenge. Good quality solutions for some instances of the problem have been found by combining specific heuristics or by including them within a metaheuristic. However studied combinations correspond to a subset of all possible combinations. In this study a technique based on a genotypephenotype genetic algorithmto automatically construct new algorithms for the problem, which contain combinations of heuristics, is presented. The produced algorithms are competitive in terms of the quality of the solution obtained. This emerges from the comparison of the performance with problem-specific heuristics and with metaheuristic approaches.