Efficient Forest Data Structure for Evolutionary Algorithms Applied to Network Design

dc.creatorDelbem, Alexandre C. B.
dc.creatorde Lima, Telma W.
dc.creatorTelles, Guilherme P.
dc.date2012
dc.date2013-09-19T18:06:13Z
dc.date2016-06-30T18:12:33Z
dc.date2013-09-19T18:06:13Z
dc.date2016-06-30T18:12:33Z
dc.date.accessioned2018-03-29T01:52:56Z
dc.date.available2018-03-29T01:52:56Z
dc.identifierIEEE Transactions On Evolutionary Computation. IEEE-Inst Electrical Electronics Engineers Inc, v.16, n.6, p.829-846, 2012
dc.identifier1089-778X
dc.identifierWOS:000314269000006
dc.identifier10.1109/TEVC.2011.2173579
dc.identifierhttp://www.repositorio.unicamp.br/jspui/handle/REPOSIP/1978
dc.identifierhttp://repositorio.unicamp.br/jspui/handle/REPOSIP/1978
dc.identifier.urihttp://repositorioslatinoamericanos.uchile.cl/handle/2250/1308278
dc.descriptionFundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)
dc.descriptionCoordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)
dc.descriptionConselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)
dc.descriptionThe design of a network is a solution to several engineering and science problems. Several network design problems are known to be NP-hard, and population-based metaheuristics like evolutionary algorithms (EAs) have been largely investigated for such problems. Such optimization methods simultaneously generate a large number of potential solutions to investigate the search space in breadth and, consequently, to avoid local optima. Obtaining a potential solution usually involves the construction and maintenance of several spanning trees, or more generally, spanning forests. To efficiently explore the search space, special data structures have been developed to provide operations that manipulate a set of spanning trees (population). For a tree with n nodes, the most efficient data structures available in the literature require time O(n) to generate a new spanning tree that modifies an existing one and to store the new solution. We propose a new data structure, called node-depth-degree representation (NDDR), and we demonstrate that using this encoding, generating a new spanning forest requires average time O(root n). Experiments with an EA based on NDDR applied to large-scale instances of the degree-constrained minimum spanning tree problem have shown that the implementation adds small constants and lower order terms to the theoretical bound.
dc.description16
dc.description6
dc.description829
dc.description846
dc.descriptionFundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)
dc.descriptionBrazilian Research Foundation of the State of Sao Paulo
dc.descriptionConselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)
dc.descriptionFundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)
dc.descriptionCoordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)
dc.descriptionConselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)
dc.languageeng
dc.publisherIEEE-Inst Electrical Electronics Engineers Inc
dc.publisherPiscataway
dc.relationIEEE Transactions On Evolutionary Computation
dc.rightsfechado
dc.sourceWOS
dc.subjectDynamic forest data structures
dc.subjectevolutionary algorithms
dc.subjectnetwork design problems
dc.subjecttree representations
dc.subjectSPANNING TREE PROBLEM
dc.subjectDISTRIBUTION-SYSTEM RECONFIGURATION
dc.subjectGENETIC ALGORITHMS
dc.subjectIMPROVED QUALITY
dc.subjectDYNAMIC TREES
dc.subjectRANDOM KEYS
dc.subjectOPTIMIZATION
dc.subjectSEARCH
dc.subjectREPRESENTATION
dc.subjectRESTORATION
dc.titleEfficient Forest Data Structure for Evolutionary Algorithms Applied to Network Design
dc.typeArtículos de revistas


Este ítem pertenece a la siguiente institución