This paper proposes an evolutionary algorithm with Dandelion-encoding to tackle the Delay-Constrained Capacitated Minimum Spanning Tree (DC-CMST) problem. This problem has been recently proposed, and consists of finding several broadcast trees from a source node, jointly considering traffic and delay constraints in trees. A version of the problem in which the source node is also included in the optimization process is considered as well in the paper. The Dandelion code used in the proposed evolutionary algorithm has been recently proposed as an effective way of encoding trees in evolutionary algorithms. Good properties of locality has been reported on this encoding, which makes it very effective to solve problems in which the solutions can be expressed in form of trees. In the paper we describe the main characteristics of the algorithm, the implementation of the Dandelion-encoding to tackled the DC-CMST problem and a modification needed to include the source node in the optimization. In the experimental section of this article we compare the results obtained by our evolutionary with that of a recently proposed heuristic for the DC-CMST. the Least Cost (LC) algorithm. We show that our Dandelion-encoded evolutionary algorithm is able to obtain better results that the LC in all the instances tackled. (C) 2008 Elsevier B.V. All rights reserved.

Perez Bellido, A., Salcedo Sanz, S., Ortiz Garcia, E., Portilla Figueras, A., Naldi, M. (2009). A dandelion-encoded evolutionary algorithm for the delay-constrained capacitated minimum spanning tree problem. COMPUTER COMMUNICATIONS, 32(1), 154-158 [10.1016/j.comcom.2008.09.030].

A dandelion-encoded evolutionary algorithm for the delay-constrained capacitated minimum spanning tree problem

NALDI, MAURIZIO
2009-01-01

Abstract

This paper proposes an evolutionary algorithm with Dandelion-encoding to tackle the Delay-Constrained Capacitated Minimum Spanning Tree (DC-CMST) problem. This problem has been recently proposed, and consists of finding several broadcast trees from a source node, jointly considering traffic and delay constraints in trees. A version of the problem in which the source node is also included in the optimization process is considered as well in the paper. The Dandelion code used in the proposed evolutionary algorithm has been recently proposed as an effective way of encoding trees in evolutionary algorithms. Good properties of locality has been reported on this encoding, which makes it very effective to solve problems in which the solutions can be expressed in form of trees. In the paper we describe the main characteristics of the algorithm, the implementation of the Dandelion-encoding to tackled the DC-CMST problem and a modification needed to include the source node in the optimization. In the experimental section of this article we compare the results obtained by our evolutionary with that of a recently proposed heuristic for the DC-CMST. the Least Cost (LC) algorithm. We show that our Dandelion-encoded evolutionary algorithm is able to obtain better results that the LC in all the instances tackled. (C) 2008 Elsevier B.V. All rights reserved.
2009
Pubblicato
Rilevanza internazionale
Articolo
Sì, ma tipo non specificato
Settore ING-INF/05 - SISTEMI DI ELABORAZIONE DELLE INFORMAZIONI
English
Con Impact Factor ISI
Dandelion encoding; Delay-constrained capacitated minimum spanning tree; Evolutionary algorithms; Heuristics
Perez Bellido, A., Salcedo Sanz, S., Ortiz Garcia, E., Portilla Figueras, A., Naldi, M. (2009). A dandelion-encoded evolutionary algorithm for the delay-constrained capacitated minimum spanning tree problem. COMPUTER COMMUNICATIONS, 32(1), 154-158 [10.1016/j.comcom.2008.09.030].
Perez Bellido, A; Salcedo Sanz, S; Ortiz Garcia, E; Portilla Figueras, A; Naldi, M
Articolo su rivista
File in questo prodotto:
File Dimensione Formato  
Naldi-CC-2009.pdf

accesso aperto

Descrizione: Articolo
Dimensione 193.14 kB
Formato Adobe PDF
193.14 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2108/39446
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? 2
social impact