Automatically Produced Algorithms for the Generalized Minimum Spanning Tree Problem
Joint Authors
Rey, Carlos
Ramos-Cossio, Sergio
Rodríguez, Claudio
Gatica, Felipe
Parada, Víctor
Contreras Bolton, Carlos
Source
Issue
Vol. 2016, Issue 2016 (31 Dec. 2016), pp.1-11, 11 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2016-03-06
Country of Publication
Egypt
No. of Pages
11
Main Subjects
Abstract EN
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 genotype-phenotype genetic algorithm to 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.
American Psychological Association (APA)
Contreras Bolton, Carlos& Rey, Carlos& Ramos-Cossio, Sergio& Rodríguez, Claudio& Gatica, Felipe& Parada, Víctor. 2016. Automatically Produced Algorithms for the Generalized Minimum Spanning Tree Problem. Scientific Programming،Vol. 2016, no. 2016, pp.1-11.
https://search.emarefa.net/detail/BIM-1118142
Modern Language Association (MLA)
Contreras Bolton, Carlos…[et al.]. Automatically Produced Algorithms for the Generalized Minimum Spanning Tree Problem. Scientific Programming No. 2016 (2016), pp.1-11.
https://search.emarefa.net/detail/BIM-1118142
American Medical Association (AMA)
Contreras Bolton, Carlos& Rey, Carlos& Ramos-Cossio, Sergio& Rodríguez, Claudio& Gatica, Felipe& Parada, Víctor. Automatically Produced Algorithms for the Generalized Minimum Spanning Tree Problem. Scientific Programming. 2016. Vol. 2016, no. 2016, pp.1-11.
https://search.emarefa.net/detail/BIM-1118142
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-1118142