Submitted by Luanna Matias (lua_matias@yahoo.com.br) on 2015-02-06T19:23:12Z No. of bitstreams: 2 Dissertação - Marcos Antônio Almeida de Oliveira - 2014..pdf: 1092566 bytes, checksum: 55edbdaf5b3ac84fe3f6835682fe2a13 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2015-02-19T14:34:20Z (GMT) No. of bitstreams: 2 Dissertação - Marcos Antônio Almeida de Oliveira - 2014..pdf: 1092566 bytes, checksum: 55edbdaf5b3ac84fe3f6835682fe2a13 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2015-02-19T14:34:20Z (GMT). No. of bitstreams: 2 Dissertação - Marcos Antônio Almeida de Oliveira - 2014..pdf: 1092566 bytes, checksum: 55edbdaf5b3ac84fe3f6835682fe2a13 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2014-09-03 / Fundação de Amparo à Pesquisa do Estado de Goiás - FAPEG / A variation of the Beasley (1992) algorithm for the Euclidean Steiner tree problem is presented. This variation uses the Node-Depth-Degree Encoding, which requires an average time of O(n) in operations to generate and manipulate spanning forests. For spanning tree problems, this representation has linear time complexity when applied to network design problems with evolutionary algorithms. Computational results are given for test cases involving instances up to 500 vertices. These results demonstrate the use of the Node-Depth-Degree in an exact heuristic, and this suggests the possibility of using this representation in other techniques besides evolutionary algorithms. An empirical comparative and complexity analysis between the proposed algorithm and a conventional representation indicates the efficiency advantages of the solution found. / É apresentada uma variação do algoritmo de Beasley (1992) para o Problema árvore de Steiner Euclidiano. Essa variação utiliza a Representação Nó-Profundidade-Grau que requer, em média, tempo O(n) em operações para gerar e manipular florestas geradoras. Para problemas de árvore geradora essa representação possui complexidade de tempo linear sendo aplicada em problemas de projeto de redes com algoritmos evolutivos. Resultados computacionais são dados para casos de teste envolvendo instâncias de até 500 vértices. Esses resultados demonstram a utilização da representação Nó-Profundidade-Grau em uma heurística exata, e isso sugere a possibilidade de utilização dessa representação em outras técnicas além de algoritmos evolutivos. Um comparativo empírico e da análise de complexidade entre o algoritmo proposto e uma representação convencional indica vantagens na eficiência da solução encontrada.

Submitted by Luciana Ferreira (lucgeral@gmail.com) on 2014-10-06T15:00:35Z No. of bitstreams: 2 Dissertação - Gustavo Siqueira Vinhal - 2013.pdf: 543638 bytes, checksum: 0cfeff261acd147877fc67035e17c1fb (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2014-10-06T15:58:27Z (GMT) No. of bitstreams: 2 Dissertação - Gustavo Siqueira Vinhal - 2013.pdf: 543638 bytes, checksum: 0cfeff261acd147877fc67035e17c1fb (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2014-10-06T15:58:27Z (GMT). No. of bitstreams: 2 Dissertação - Gustavo Siqueira Vinhal - 2013.pdf: 543638 bytes, checksum: 0cfeff261acd147877fc67035e17c1fb (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2013-08-19 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / Many relevant problems to NP-Hard class are present in the real world. Among them we can mention the problems of network design (PNDs) that involve electricity distribution, vehicle traffic, and others. There are not algorithms which provide a exact solution for these types of problems with an acceptable computation time. Over the years, research has been developed used evolutionary algorithms (EAs) to provide an efficient solution with a acceptable computation time for these problems. In addition, appropriate data structures may further improve the performance of EAs to PNDs. The node-depth-degree (NDDE) representation have show significant results for PNDs. The application of EAs in hardware can improve the performance of the algorithm. In this sense, this work presents the implementation of a EA in Nios II processor of a FPGA board to solving the PND minimum spanning tree with degree constraint. The results demonstrate that the implementation of EAs in hardware brings significant results with better performance, due to the power of parallelism present in the FPGA. / Diversos problemas pertinentes a classe NP-Difícil estão presentes no mundo real. Dentre eles pode-se citar os problemas de projeto de redes (PPRs) que envolvem distribuição de energia elétrica, tráfego de veículos, entre outros. Não existem algoritmos que forneçam uma solução exata para esses tipos de problemas com um tempo de computação aceitável. Ao longo dos anos pesquisas estão sendo desenvolvidas utilizado algoritmos evolutivos (EAs) para fornecer uma solução eficiente com tempo de computção aceitável para tais problemas. Além disso, estruturas de dados adequadas podem melhorar ainda mais o desempenho dos EAs para PPRs. A representação nó-profundidade-grau (NDDE) apresenta resultados significativos para PPRs. A aplicação de EAs em hardware pode melhorar o desempenho do algoritmo. Nesse sentido, este trabalho apresenta a implementação de um EA no processador Nios II de uma placa FPGA para solução do PPR da árvore geradora mínima com restrição de grau. Os resultados demonstram que a implementação de EAs em hardware traz resultados significativos com melhor desempenho, devido ao poder de paralelismo presente no FPGA.

Submitted by Luciana Ferreira (lucgeral@gmail.com) on 2014-11-20T11:31:40Z No. of bitstreams: 2 Dissertação - Danilo Alves Martins de Faria - 2013.pdf: 1188393 bytes, checksum: c56b169690f22bbbeaa2ee6fa46ade1c (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2014-11-20T14:17:45Z (GMT) No. of bitstreams: 2 Dissertação - Danilo Alves Martins de Faria - 2013.pdf: 1188393 bytes, checksum: c56b169690f22bbbeaa2ee6fa46ade1c (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2014-11-20T14:17:45Z (GMT). No. of bitstreams: 2 Dissertação - Danilo Alves Martins de Faria - 2013.pdf: 1188393 bytes, checksum: c56b169690f22bbbeaa2ee6fa46ade1c (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2013-10-23 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / Network Design Problems (NDPs) are present in many areas, such as electric power distribution, communication networks, vehicle routing, phylogenetic trees among others. Many NDPs are classified as NP-Hard problems. Among the techniques used to solve them, we highlight the Evolutionary Algorithms (EA). These algorithms simulate the natural evolution of the species. However, in its standard form EAs have limitations to solve large scale NDPs, or with very specific characteristics. To solve these problems, many researchers have studied specific forms of representation of NDPs. Among these stands we show Node-Depth-Degre Encoding (NDDE). This representation produces only feasible solutions, regardless of the network characteristics. NDDE has two mutation operators Preserve Ancestor Operator (PAO) and Ancestor Change Operator (CAO) and the recombination operator EHR (Evolutionary History Recombination Operator) that uses historical applications of mutation, and was applied to NDPs more than one tree and had good results. Thus, this work proposes adapt EHR for NDPs classics represented by a single tree. In addition, two evolutionary algorithms are developed: the AE-RNPG, which uses only NDDE, with mutation operators. And the AE-EHR, which makes use of mutation operators and recombination operator EHR to the One Max Tree Problem. The results showed that the AE-EHR obtained better solutions than the EA-RNPG for most instances analyzed. / Problemas de Projeto de Redes (PPRs) estão presentes em diversas áreas, tais como reconfiguração de sistemas de distribuição de energia elétrica, projetos de redes de comunicação, roteamento de veículos, reconstrução de árvores filogenéticas entre outros. Vários PPRs pertencem à classe de problemas NP-Difíceis. Dentre as técnicas utilizadas para resolvê-los, destacam-se os Algoritmos Evolutivos (AE), cujo processo de resolução de um problema simula a evolução natural das espécies. Entretanto, os AEs em sua forma padrão também possuem limitações quanto a PPRs de larga escala, ou com características muito específicas. Para solucionar esses problemas, diversas pesquisas têm estudado formas específicas de estruturas de dados dos PPRs. Dentre essas destaca-se a representação Nó-Profundidade-Grau (RNPG). Essa representação produz apenas soluções factíveis, independente da característica da rede. A RNPG possui dois operadores de mutação Preserve Ancestor Operator (PAO) e Change Ancestor Operator (CAO) e o operador de recombinação EHR (Evolutionary History Recombination Operator), que utiliza o histórico de aplicações dos operadores de mutação, o qual tem sido aplicado a PPRs com mais de uma árvore com bons resultados. Este trabalho propõem a adequação do EHR para PPRs clássicos de uma única árvore. Além disso, são desenvolvidos dois algoritmos evolutivos: o AE-RNPG, que utiliza a RNPG somente com os operadores de mutação; e o AE-EHR, que faz uso tanto dos operadores de mutação quanto do operador de recombinação EHR para o problema da Árvore máxima. Os resultados obtidos mostram que o AE-EHR obtém melhores soluções do que o AE-RNPG para a maioria das instâncias analisadas.