Evolutionary computation of forests with Degree- and Role-Constrained Minimum Spanning Trees

Antón Sánchez, Laura; Bielza Lozoya, Maria Concepcion y Larrañaga Múgica, Pedro (2015). Evolutionary computation of forests with Degree- and Role-Constrained Minimum Spanning Trees. Monografía (Informe Técnico). E.T.S. de Ingenieros Informáticos (UPM), Madrid.

Descripción

Título: Evolutionary computation of forests with Degree- and Role-Constrained Minimum Spanning Trees
Autor/es:
  • Antón Sánchez, Laura
  • Bielza Lozoya, Maria Concepcion
  • Larrañaga Múgica, Pedro
Tipo de Documento: Monográfico (Informes, Documentos de trabajo, etc.) (Informe Técnico)
Fecha: 2015
Materias:
Palabras Clave Informales: Degree- and role-constrained minimum spanning tree; Evolutionary computation; Forest; Network design; Permutation problems
Escuela: E.T.S. de Ingenieros Informáticos (UPM)
Departamento: Inteligencia Artificial
Grupo Investigación UPM: Computational Intelligence Group CIG
Licencias Creative Commons: Reconocimiento - Sin obra derivada - No comercial

Texto completo

[img]
Vista Previa
PDF (Document Portable Format) - Se necesita un visor de ficheros PDF, como GSview, Xpdf o Adobe Acrobat Reader
Descargar (1MB) | Vista Previa

Resumen

Finding the degree-constrained minimum spanning tree (DCMST) of a graph is a widely studied NP-hard problem. One of its most important applications is network design. Here we deal with a new variant of the DCMST problem, which consists of finding not only the degree- but also the role-constrained minimum spanning tree (DRCMST), i.e., we add constraints to restrict the role of the nodes in the tree to root, intermediate or leaf node. Furthermore, we do not limit the number of root nodes to one, thereby, generally, building a forest of DRCMSTs. The modeling of network design problems can benefit from the possibility of generating more than one tree and determining the role of the nodes in the network. We propose a novel permutation-based representation to encode these forests. In this new representation, one permutation simultaneously encodes all the trees to be built. We simulate a wide variety of DRCMST problems which we optimize using eight different evolutionary computation algorithms encoding individuals of the population using the proposed representation. The algorithms we use are: estimation of distribution algorithm, generational genetic algorithm, steady-state genetic algorithm, covariance matrix adaptation evolution strategy, differential evolution, elitist evolution strategy, non-elitist evolution strategy and particle swarm optimization. The best results are for the estimation of distribution algorithms and both types of genetic algorithms, although the genetic algorithms are significantly faster. -------------------------------------------------------------------------------------------------- Trabajo publicado en: Antón Sánchez, Laura; Bielza Lozoya, Maria Concepcion y Larrañaga Múgica, Pedro (2017). Network Design through Forests with Degree- and Role-constrained Minimum Spanning Trees. "Journal of Heuristics ", v. 23 (n. 1); pp. 31-51. -------------------------------------------

Más información

ID de Registro: 36521
Identificador DC: http://oa.upm.es/36521/
Identificador OAI: oai:oa.upm.es:36521
Depositado por: MSc Laura Antón Sánchez
Depositado el: 08 Jul 2015 08:53
Ultima Modificación: 11 May 2017 13:25
  • Open Access
  • Open Access
  • Sherpa-Romeo
    Compruebe si la revista anglosajona en la que ha publicado un artículo permite también su publicación en abierto.
  • Dulcinea
    Compruebe si la revista española en la que ha publicado un artículo permite también su publicación en abierto.
  • Recolecta
  • e-ciencia
  • Observatorio I+D+i UPM
  • OpenCourseWare UPM