Please use this identifier to cite or link to this item: https://hdl.handle.net/10216/70513
Full metadata record
DC FieldValueLanguage
dc.creatorDalila B M M Fontes
dc.creatorJose Fernando Goncalves
dc.date.accessioned2022-09-16T04:07:37Z-
dc.date.available2022-09-16T04:07:37Z-
dc.date.issued2009
dc.identifier.othersigarra:50580
dc.identifier.urihttps://hdl.handle.net/10216/70513-
dc.description.abstractIn this work we propose a multi-population genetic algorithm for tree-shaped network design problems using random keys. Recent literature on finding optimal spanning trees suggests the use of genetic algorithms. Furthermore, random keys encoding has been proved efficient at dealing with problems where the relative order of tasks is important. Here we propose to use random keys for encoding trees. The topology of these trees is restricted, since no path from the root vertex to any other vertex may have more than a pre-defined number of arcs. In addition, the problems under consideration also exhibit the characteristic of flows. Therefore, we want to find a minimum cost tree satisfying all demand vertices and the pre-defined number of arcs. The contributions of this paper are twofold: on one hand we address a new problem, which is an extension of the well known NP-hard hop-constrained MST problem since we also consider determining arc flows such that vertices requirements are met at minimum cost and the cost functions considered include a fixed cost component and a nonlinear flow routing component; on the other hand, we propose a new genetic algorithm to efficiently find solutions to this problem.
dc.language.isoeng
dc.relation.ispartofProceedings of the International Joint Conference on Computational Intelligence
dc.rightsopenAccess
dc.rights.urihttps://creativecommons.org/licenses/by-nc/4.0/
dc.subjectCiências da computação e da informação
dc.subjectComputer and information sciences
dc.titleA MULTI-POPULATION GENETIC ALGORITHM FOR TREE-SHAPED NETWORK DESIGN PROBLEMS
dc.typeCapítulo ou Parte de Livro
dc.contributor.uportoFaculdade de Economia
dc.identifier.authenticusP-003-QH8
dc.subject.fosCiências exactas e naturais::Ciências da computação e da informação
dc.subject.fosNatural sciences::Computer and information sciences
Appears in Collections:FEP - Capítulo ou Parte de Livro

Files in This Item:
File Description SizeFormat 
50580.pdf147.14 kBAdobe PDFThumbnail
View/Open


This item is licensed under a Creative Commons License Creative Commons