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

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

Description

Title: Evolutionary computation of forests with Degree- and Role-Constrained Minimum Spanning Trees
Author/s:
  • Antón Sánchez, Laura
  • Bielza Lozoya, Maria Concepcion
  • Larrañaga Múgica, Pedro
Item Type: Monograph (Technical Report)
Date: 2015
Subjects:
Freetext Keywords: Degree- and role-constrained minimum spanning tree; Evolutionary computation; Forest; Network design; Permutation problems
Faculty: E.T.S. de Ingenieros Informáticos (UPM)
Department: Inteligencia Artificial
UPM's Research Group: Computational Intelligence Group CIG
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (1MB) | Preview

Abstract

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. -------------------------------------------

More information

Item ID: 36521
DC Identifier: http://oa.upm.es/36521/
OAI Identifier: oai:oa.upm.es:36521
Deposited by: MSc Laura Antón Sánchez
Deposited on: 08 Jul 2015 08:53
Last Modified: 11 May 2017 13:25
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM