Título: An edge-based crossover for the capacitated minimum spanning tree problem
Autores: Lacerda, E. G. M. de; Medeiros Junior, Manoel Firmino de
Resumo: This work describes a Genetic Algorithm for the Capacitated Minimum Spanning Tree (CMST) problem that appears in Telecommunications. We suggest a new crossover operator, applied directly on the tree (phenotype) instead of on the chromosome. Without needing repairing techniques, this crossover is capable to produce feasible trees and presents excellent locality and heritability besides other properties that misses in many other tree representations. The new crossover proved to be effective when compared with the Genetic Algorithm of Raidl and Drexel (on benchmark data sets), which presented better performance than various classical methods of the literature. Another characteristic of the new crossover is its flexibility for adaptation in problems with constraints, as for instance, the Degree-Constrained Minimum Spanning Tree Problem.
Palavras-chave: Genetic algorithms; spanning tree; capacitated minimum spanning tree problem
Páginas: 6
Código DOI: 10.21528/CBRN2005-116
Artigo em PDF: CBRN2005_116.pdf
Arquivo BibTex: CBRN2005_116.bib