Devido a restrições de aplicabilidade presentes nos algoritmos para a solução de problemas de otimização combinatória, os sistemas baseados em redes neurais artificiais e algoritmos genéticos oferecem um método alternativo para solucionar tais problemas eficientemente. Os algoritmos genéticos devem a sua popularidade à possibilidade de percorrer espaços de busca não-lineares e extensos. Já as redes neurais artificiais possuem altas taxas de processamento por utilizarem um número elevado de elementos processadores simples com alta conectividade entre si. Complementarmente, redes neurais com conexões realimentadas fornecem um modelo computacional capaz de resolver vários tipos de problemas de otimização, os quais consistem, geralmente, da otimização de uma função objetivo que pode estar sujeita ou não a um conjunto de restrições. Esta tese apresenta uma abordagem inovadora para resolver problemas de conexão em otimização combinatória utilizando uma arquitetura neuro-genética. Mais especificamente, uma rede neural de Hopfield modificada é associada a um algoritmo genético visando garantir a convergência da rede em direção aos pontos de equilíbrio factíveis que representam as soluções para os problemas de otimização combinatória. / Due to applicability constraints involved with the algorithms for solving combinatorial optimization problems, systems based on artificial neural networks and genetic algorithms are alternative methods for solving these problems in an efficient way. The genetic algorithms must its popularity to make possible cover nonlinear and extensive search spaces. On the other hand, artificial neural networks have high processing rates due to the use of a massive number of simple processing elements and the high degree of connectivity between these elements. Additionally, neural networks with feedback connections provide a computing model capable of solving a large class of optimization problems, which refer to optimization of an objective function that can be subject to constraints. This thesis presents a novel approach for solving connection problems in combinatorial optimization using a neurogenetic approach. More specifically, a modified Hopfield neural network is associated with a genetic algorithm in order to guarantee the convergence of the network to the equilibrium points, which represent feasible solutions for the combinatorial optimization problems.

This dissertation investigates in which conditions the optimal configuration of an electric power network is a minimum length spanning tree, and in which conditions it is shortest path tree configuration. For this purpose the dissertation, it applies computational optimization mathematical models of an optimal local access network design problem. The focus of the study is the 13.8 kV spacer cable primary radial networks. Applied models seek for the balance betweenfixedcostsandvariablecosts.Savedvaluesfromanoptimalnetworkcouldbeapplied to increase the range of the network and people reached as well. The bibliographic research is compound by three parts: graph theory, local access network optimization models, and distribution network costs. Research methodology includes the choice of the distribution system, determination of fixed and variable costs, choice and implementation of the local access network optimization models, tests in hypothetical and realistic systems by using the CPLEX solver, analysis of the resulting configuration, and construction of graphics to facilitate the results evaluation. It was found that the relationship between fixed costs and variable costs influences the optimal configuration of the distribution network in such a way that a low value of the quotient between fixed costs and variable costs contributes to a shortest path tree. On the other hand, a high quotient between fixed costs and variable costs contributes to a minimum length spanning tree configuration. However, others parameters must be considered to determine the network configuration such as extension, arches demand and quantity of arches. / O presente trabalho visa investigar sob quais condições a configuração ótima de uma rede de distribuição elétrica é uma árvore geradora mínima (AGM) e sob quais é uma árvore de caminhos mínimos (ACM). Utilizando, para isso, modelos matemáticos computacionais de otimização topológica de redes de utilidade pública. As redes de distribuição estudadas foram do tipo aérea radial primária protegida (ARPP) com nível de tensão em 13,8 kV. Os modelos utilizados prezam pelo equilíbrio entre o custo de investimento inicial (fixo) e os custos decorrentes da transferência de energia elétrica (variável). Os valores economizados através de uma configuração ótima da rede podem ser convertidos em investimentos para aumentar o número de pessoas com acesso aos recursos energéticos com eficiência e qualidade. A revisão bibliográfica foi dividida em três partes: teoria dos grafos, modelos de otimização de redes de acesso local e custos de redes de distribuição. A metodologia utilizada compreendeu as seguintes etapas: escolha do tipo de sistema de distribuição, determinação dos custos fixo e variável, escolha e implementação (GAMS) dos modelos, testes com exemplos de redes usando o solver CPLEX, análise das configurações resultantes e elaboração de gráficos para facilitar a avaliação dos resultados. Os resultados mostraram que a relação entre o custo fixo β e o custo variável γ exerce influência determinante na configuração ótima de uma rede de distribuição ARPP. Um valor baixo de β/γ, favorece a ACM. Já valores elevados de β/γ, conduzem a solução para uma AGM. No entanto, essa relação não é o único fator que determina a configuração da rede, outros parâmetros como extensão, demanda dos nós e quantidade de possíveis arcos influenciam de forma significativa na solução apresentada.

Submitted by Luciana Ferreira (lucgeral@gmail.com) on 2014-10-30T14:24:27Z No. of bitstreams: 2 Dissertação - Roussian Di Ramos Alves Gaioso - 2014.pdf: 6127790 bytes, checksum: 9990f791c0f9abaee7e3e03e4cdc8ee4 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2014-10-30T14:29:29Z (GMT) No. of bitstreams: 2 Dissertação - Roussian Di Ramos Alves Gaioso - 2014.pdf: 6127790 bytes, checksum: 9990f791c0f9abaee7e3e03e4cdc8ee4 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2014-10-30T14:29:29Z (GMT). No. of bitstreams: 2 Dissertação - Roussian Di Ramos Alves Gaioso - 2014.pdf: 6127790 bytes, checksum: 9990f791c0f9abaee7e3e03e4cdc8ee4 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2014-08-08 / Conselho Nacional de Pesquisa e Desenvolvimento Científico e Tecnológico - CNPq / This paper presents a Graphics Processing Unit (GPU) based parallels implementations for the All Pairs Shortest Paths and Transitive Closure problems in graph. The implementations are based on the main sequential algorithms and takes full advantage of the highly multithreaded architecture of current manycore GPUs. Our solutions reduces the communication between CPU and GPU, improves the Streaming Multiprocessors (SMs) utilization, and makes intensive use of coalesced memory access to optimize graph data access. The advantages of the proposed implementations are demonstrated for several graphs randomly generated using the widely known graph library GTgraph. Graphs containing thousands of vertices and different edges densities, varying from sparse to complete graphs, were generated and used in the experiments. Our results confirm that GPU implementations can be competitive even for graph algorithms whose memory accesses and work distribution are both irregular and data-dependent. Keywords / Este trabalho apresenta implementações paralelas baseadas em Graphics Processing Unit (GPU) para os problemas da identificação dos caminhos mínimos entre todos os pares de vértices e do fecho transitivo em um grafo. As implementações são baseadas nos principais algoritmos sequenciais e tiram o máximo proveito da arquitetura multithreaded das GPUs atuais. Nossa solução reduz a comunicação entre a Central Processing Unit (CPU) e a GPU, melhora a utilização dos Streaming Multiprocessors (SMs) e faz um uso intensivo de acesso aglutinado em memória para otimizar o acesso de dados do grafo. As vantagens dessas implementações propostas são demonstradas por vários grafos gerados aleatoriamente utilizando a ferramenta GTgraph. Grafos contendo milhares de vértices foram gerados e utilizados nos experimentos. Nossos resultados confirmam que implementações baseadas em GPU podem ser viáveis mesmo para algoritmos de grafos cujo acessos à memória e distribuição de trabalho são irregulares e causam dependência de dados.