A multi-operator genetic algorithm for the generalized minimum spanning tree problem

Vista sencilla de ítem
dc.contributor.authorContreras-Bolton, Carlos
dc.contributor.authorGatica, Gustavo
dc.contributor.authorBarra, Carlos Rey
dc.contributor.authorParada, Víctor
dc.date.accessioned2023-09-22T13:51:34Z
dc.date.available2023-09-22T13:51:34Z
dc.date.issued2016-05
dc.descriptionIndexación: Scopuses
dc.description.abstractThe generalized minimum spanning tree problem, with applications in the field of communication networks, is a computational challenge due essentially to its NP-hardness. The problem consists of finding a minimum cost spanning tree in an undirected graph whose vertices are grouped in clusters, such that the spanning tree contains only one vertex of each cluster. The algorithms that have provided the best results still do not optimally solve all instances in the literature. One of the most widely studied approaches to the problem is the use of genetic algorithms that, in all cases, use only single operators for crossover and mutation, disregarding the potential synergy of multi-operators. We present a multi-operator genetic algorithm of the genotype-phenotype class, in which the genotype is a chain of integers that represents a cluster's selected vertex. Therefore, the phenotype is a minimum cost spanning tree that is generated by means of Kruskal's algorithm and joins the vertices selected from each cluster. Two operators are used for crossover and five for mutation, three of which are local search operators. The performance of the resultant algorithm is evaluated using the most challenging instances in the literature, the results of which are compared with those of other mono-operator genetic algorithms and with the best existing results. With the 101 instances that are considered, an average error of 0.0142% is achieved, and in 83 instances, the best solution cost is obtained. Such performance is due both to the synergistic effect produced among the operators and the mutation operators working as local searches. Additionally, the results suggest that for many other combinatorial optimization problems, which have been addressed with a genetic algorithm, better results could possibly be obtained simply by using a greater number of variation operators. © 2015 Elsevier Ltd. All rights reserved.es
dc.description.urihttps://www-sciencedirect-com.recursosbiblioteca.unab.cl/science/article/pii/S0957417415008167?via%3Dihub
dc.identifier.citationExpert Systems with Applications Volume 50, Pages 1 - 815 May 2016es
dc.identifier.doi10.1016/j.eswa.2015.12.014
dc.identifier.issn0957-4174
dc.identifier.urihttps://repositorio.unab.cl/xmlui/handle/ria/53287
dc.language.isoenes
dc.publisherElsevier Ltdes
dc.rights.licenseAtribución 4.0 Internacional (CC BY 4.0)
dc.rights.urihttps://creativecommons.org/licenses/by/4.0/deed.es
dc.subjectGeneralized minimum spanning treees
dc.subjectGenetic algorithmses
dc.subjectMeta-heuristicses
dc.subjectMulti-operatores
dc.titleA multi-operator genetic algorithm for the generalized minimum spanning tree problemes
dc.typeArtículoes
Archivos
Bloque original
Mostrando 1 - 1 de 1
Miniatura
Nombre:
1-s2.0-S0957417415008167-main.pdf
Tamaño:
743.79 KB
Formato:
Adobe Portable Document Format
Descripción:
TEXTO EN INGLES
Descargar
Bloque de licencias
Mostrando 1 - 1 de 1
No hay miniatura disponible
Nombre:
license.txt
Tamaño:
1.71 KB
Formato:
Item-specific license agreed upon to submission
Descripción:
Descargar
Colecciones
FIng - Artículos de Revista