Efficient Forest Data Structure for Evolutionary Algorithms Applied to Network Design

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

A representação gráfica na Revista Projeto & Design.

Esta pesquisa inicia-se pelo estudo das diferentes maneiras de representação de um projeto arquitetônico: desenhos analógicos e digitais, desenhos naturais e técnicos, desenhos auxiliados por computador, maquetes físicas e modelos digitais. Teve como objetivo analisar a representação gráfica utilizada nas publicações de obras arquitetônicas em mídias impressas especializadas, tendo sido selecionada a Revista Projeto & Design como estudo de caso. Com este estudo foi possível, por meio de bibliometria gráfica, verificar as contribuições das representações na compreensão e leitura dos projetos arquitetônicos, elencando-se e exemplificando-se as tipologias de imagens utilizadas nas últimas décadas, bem como relacionar os resultados com o momento histórico em que foram projetadas ou publicadas.