Diversos problemas do mundo real estão relacionados ao projeto de redes, tais como projeto de circuitos de energia elétrica, roteamento de veículos, planejamento de redes de telecomunicações e reconstrução filogenética. Em geral, esses problemas podem ser modelados por meio de grafos, que manipulam milhares ou milhões de nós (correspondendo às variáveis de entrada), dificultando a obtenção de soluções em tempo real. O Projeto de uma Rede é um problema combinatório, em que se busca encontrar a rede mais adequada segundo um critério como, por exemplo, menor custo, menor caminho e tempo de percurso. A solução desses problemas é, em geral, computacionalmente complexa. Nesse sentido, metaheurísticas como Algoritmos Evolutivos têm sido amplamente investigadas. Diversas pesquisas mostram que o desempenho de Algoritmos Evolutivos para Problemas de Projetos de Redes pode ser aumentado significativamente por meio de representações mais apropriadas. Este trabalho investiga a paralelização da Representação Nó-Profundidade (RNP) em hardware, com o objetivo de encontrar melhores soluções para Problemas de Projetos de Redes. Para implementar a arquitetura de hardware, denominada de HP-RNP (Hardware Parallelized RNP), foi utilizada a tecnologia de FPGA para explorar o alto grau de paralelismo que essa plataforma pode proporcionar. Os resultados experimentais mostraram que o HP-RNP é capaz de gerar e avaliar novas redes em tempo médio limitado por uma constante (O(1)) / Many problems related to network design can be found in real world applications, such as design of electric circuits, vehicle routing, telecommunication network planning and phylogeny reconstruction. In general, these problems can be modelled using graphs that handle thousands or millions of nodes (input variables), making it hard to obtain solutions in real-time. The Network Design is the combinatorial problem of finding the most suitable network subject to a evaluation criterion as, for example, lower cost, minimal path and time to traverse the network. The solution of those problems is in general computationally complex. Metaheuristics as Evolutionary Algorithms have been widely investigated for such problems. Several researches have shown that the performance of Evolutionary Algorithms for the Network Design Problems can be significantly increased through more appropriated dynamic data structures (encodings). This work investigates the parallelization of Node-Depth Encoding (NDE) in hardware in order to find better solutions for Network Design Problems. To implement the proposed hardware architecture, called HP-NDE (Hardware Parallellized NDE), the FPGA technology was used to explore the high degree of parallelism that such platform can provide. The experimental results have shown that the HP-NDE can generate and evaluate new networks in average time constrained by a constant (O(1))

A modelagem em tempo real dos sistemas elétricos de potência (SEP) é extremamente importante para se obter uma operação em tempo real segura e confiável dos mesmos. O configurador de redes (CR) é uma ferramenta fundamental, para modelagem em tempo real dos SEP. A função do CR é determinar, em tempo real, a topologia atual da rede e a correspondente configuração de medidores, no modelo barra-ramo. Para isso, o configurador processa medidas lógicas, que consistem em estados de chaves e disjuntores, bem como dados armazenados em um banco de dados estático, que descreve a conexão dos equipamentos do sistema com as seções de barramento. Em razão de os CRs exigirem algoritmos de busca em um grafo, o desempenho desses algoritmos torna-se fortemente afetado pela forma com que as árvores são computacionalmente representadas. Propõe-se, neste trabalho, um CR tracking, para efeito de estimação de estado, que se baseia em uma nova forma de representar árvores, denominada representação nó-profundidade (RNP). A RNP permite um acesso direto para cada nó de um grafo e pode representar eficientemente árvores (grafos conexos e acíclicos) e florestas (um grafo com uma ou mais árvores). O CR proposto possui as seguintes características: (i) A RNP possibilita uma rápida atualização da topologia da rede, no modelo barra-ramo; (ii) Esta estrutura também permite a realização das etapas configuração de subestação e de rede ao mesmo tempo, diminuindo assim o tempo de processamento necessário para a obtenção do modelo barra-ramo. Para isso, o CR proposto representa cada seção de barramento do SEP como nó de um grafo e usa a RNP e outras duas estruturas de dados, que serão apresentadas no capítulo 5; (iii) Possibilita a associação dos medidores aos componentes do SEP, no modelo barra-ramo, de forma direta. Para isso, o CR proposto usa a RNP e cria barras fictícias para representar os componentes shunt do SEP. Testes realizados comprovam a eficiência e a robustez do configurador proposto tendo em vista os resultados coerentes obtidos para todos os testes, mesmo para os casos em que a mudança nos estados dos dispositivos seccionadores acarretava uma alteração drástica na rede elétrica. / On-line models of power system networks have a wide variety of critical uses, covering from security monitoring and control to market operation. Network topology processor (NTP) is a key tool in providing robust and reliable on-line model of power networks. The function of NTP is the determination of the bus/branch topology model (BBTM) of the network and the assignment of metering devices to the components of the BBTM. In order to do this, the NTP processes: logical measurements that consist of switching-device (breakers and switchers) status; as well as a static data-base describing the network connectivity in terms of bus-sections and switching-devices. Since NTPs require search algorithms for graphs, their performance can be drastically affected by the adopted computational graph representation. This work proposes a new tracking NTP for state estimation purposes, that uses a new graph representation named node-depth representation (NDR). This encoding enables a straightforward access to each one of the graph nodes and can efficiently represent trees (acyclic and connected graphs) and forests (a graph with one or more trees). The proposed tracking NTP has the following characteristics: (i) Using NDR for representation of a BBTM of the network, this NTP can track, over time, the changes of the network connectivity in a very direct and fast way; (ii) Processes both steps substation and network configurations in the same time, reducing the CPU time necessary to obtain the BBTM. In order to do this, the proposed NTP represents each bus-section as a graph node and uses NDR and other two data structures, which will be presented in the chapter 5; and (iii) To assign metering devices to the components of the BBTM, in a straightforward way, the proposed NTP creates additional buses, called fictitious buses, to represent shunt devices. The results of several tests have shown the proposed NTP is reliable, fast and suitable for real-time operation.

A modelagem em tempo real dos sistemas elétricos de potência (SEP) é extremamente importante para se obter uma operação em tempo real segura e confiável dos mesmos. O configurador de redes (CR) é uma ferramenta fundamental, para modelagem em tempo real dos SEP. A função do CR é determinar, em tempo real, a topologia atual da rede e a correspondente configuração de medidores, no modelo barra-ramo. Para isso, o configurador processa medidas lógicas, que consistem em estados de chaves e disjuntores, bem como dados armazenados em um banco de dados estático, que descreve a conexão dos equipamentos do sistema com as seções de barramento. Em razão de os CRs exigirem algoritmos de busca em um grafo, o desempenho desses algoritmos torna-se fortemente afetado pela forma com que as árvores são computacionalmente representadas. Propõe-se, neste trabalho, um CR tracking, para efeito de estimação de estado, que se baseia em uma nova forma de representar árvores, denominada representação nó-profundidade (RNP). A RNP permite um acesso direto para cada nó de um grafo e pode representar eficientemente árvores (grafos conexos e acíclicos) e florestas (um grafo com uma ou mais árvores). O CR proposto possui as seguintes características: (i) A RNP possibilita uma rápida atualização da topologia da rede, no modelo barra-ramo; (ii) Esta estrutura também permite a realização das etapas configuração de subestação e de rede ao mesmo tempo, diminuindo assim o tempo de processamento necessário para a obtenção do modelo barra-ramo. Para isso, o CR proposto representa cada seção de barramento do SEP como nó de um grafo e usa a RNP e outras duas estruturas de dados, que serão apresentadas no capítulo 5; (iii) Possibilita a associação dos medidores aos componentes do SEP, no modelo barra-ramo, de forma direta. Para isso, o CR proposto usa a RNP e cria barras fictícias para representar os componentes shunt do SEP. Testes realizados comprovam a eficiência e a robustez do configurador proposto tendo em vista os resultados coerentes obtidos para todos os testes, mesmo para os casos em que a mudança nos estados dos dispositivos seccionadores acarretava uma alteração drástica na rede elétrica. / On-line models of power system networks have a wide variety of critical uses, covering from security monitoring and control to market operation. Network topology processor (NTP) is a key tool in providing robust and reliable on-line model of power networks. The function of NTP is the determination of the bus/branch topology model (BBTM) of the network and the assignment of metering devices to the components of the BBTM. In order to do this, the NTP processes: logical measurements that consist of switching-device (breakers and switchers) status; as well as a static data-base describing the network connectivity in terms of bus-sections and switching-devices. Since NTPs require search algorithms for graphs, their performance can be drastically affected by the adopted computational graph representation. This work proposes a new tracking NTP for state estimation purposes, that uses a new graph representation named node-depth representation (NDR). This encoding enables a straightforward access to each one of the graph nodes and can efficiently represent trees (acyclic and connected graphs) and forests (a graph with one or more trees). The proposed tracking NTP has the following characteristics: (i) Using NDR for representation of a BBTM of the network, this NTP can track, over time, the changes of the network connectivity in a very direct and fast way; (ii) Processes both steps substation and network configurations in the same time, reducing the CPU time necessary to obtain the BBTM. In order to do this, the proposed NTP represents each bus-section as a graph node and uses NDR and other two data structures, which will be presented in the chapter 5; and (iii) To assign metering devices to the components of the BBTM, in a straightforward way, the proposed NTP creates additional buses, called fictitious buses, to represent shunt devices. The results of several tests have shown the proposed NTP is reliable, fast and suitable for real-time operation.

Diversos problemas do mundo real estão relacionados ao projeto de redes, tais como projeto de circuitos de energia elétrica, roteamento de veículos, planejamento de redes de telecomunicações e reconstrução filogenética. Em geral, esses problemas podem ser modelados por meio de grafos, que manipulam milhares ou milhões de nós (correspondendo às variáveis de entrada), dificultando a obtenção de soluções em tempo real. O Projeto de uma Rede é um problema combinatório, em que se busca encontrar a rede mais adequada segundo um critério como, por exemplo, menor custo, menor caminho e tempo de percurso. A solução desses problemas é, em geral, computacionalmente complexa. Nesse sentido, metaheurísticas como Algoritmos Evolutivos têm sido amplamente investigadas. Diversas pesquisas mostram que o desempenho de Algoritmos Evolutivos para Problemas de Projetos de Redes pode ser aumentado significativamente por meio de representações mais apropriadas. Este trabalho investiga a paralelização da Representação Nó-Profundidade (RNP) em hardware, com o objetivo de encontrar melhores soluções para Problemas de Projetos de Redes. Para implementar a arquitetura de hardware, denominada de HP-RNP (Hardware Parallelized RNP), foi utilizada a tecnologia de FPGA para explorar o alto grau de paralelismo que essa plataforma pode proporcionar. Os resultados experimentais mostraram que o HP-RNP é capaz de gerar e avaliar novas redes em tempo médio limitado por uma constante (O(1)) / Many problems related to network design can be found in real world applications, such as design of electric circuits, vehicle routing, telecommunication network planning and phylogeny reconstruction. In general, these problems can be modelled using graphs that handle thousands or millions of nodes (input variables), making it hard to obtain solutions in real-time. The Network Design is the combinatorial problem of finding the most suitable network subject to a evaluation criterion as, for example, lower cost, minimal path and time to traverse the network. The solution of those problems is in general computationally complex. Metaheuristics as Evolutionary Algorithms have been widely investigated for such problems. Several researches have shown that the performance of Evolutionary Algorithms for the Network Design Problems can be significantly increased through more appropriated dynamic data structures (encodings). This work investigates the parallelization of Node-Depth Encoding (NDE) in hardware in order to find better solutions for Network Design Problems. To implement the proposed hardware architecture, called HP-NDE (Hardware Parallellized NDE), the FPGA technology was used to explore the high degree of parallelism that such platform can provide. The experimental results have shown that the HP-NDE can generate and evaluate new networks in average time constrained by a constant (O(1))