文章基本信息

标题：Automatically Produced Algorithms for the Generalized Minimum Spanning Tree Problem
本地全文：下载
作者：Carlos Contreras-Bolton ; Carlos Rey ; Sergio Ramos-Cossio 等
期刊名称：Scientific Programming
印刷版ISSN：1058-9244
出版年度：2016
卷号：2016
DOI：10.1155/2016/1682925
出版社：Hindawi Publishing Corporation
摘要：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.