O alinhamento de seqüências biológicas é uma operação básica em Bioinformática, já que serve como base para outros processos como, por exemplo, a determinação da estrutura tridimensional das proteínas. Dada a grande quantidade de dados presentes nas seqüencias, são usadas técnicas matemáticas e de computação para realizar esta tarefa. Tradicionalmente, o Problema de Alinhamento de Seqüências Biológicas é formulado como um problema de otimização de objetivo simples, onde alinhamento de maior semelhança, conforme um esquema de pontuação, é procurado. A Otimização Multi-Objetivo aborda os problemas de otimização que possuem vários critérios a serem atingidos. Para este tipo de problema, existe um conjunto de soluções que representam um "compromiso" entre os objetivos. Uma técnica que se aplica com sucesso neste contexto são os Algoritmos Evolutivos, inspirados na Teoria da Evolução de Darwin, que trabalham com uma população de soluções que vão evoluindo até atingirem um critério de convergência ou de parada. Este trabalho formula o Problema de Alinhamento de Seqüências Biológicas como um Problema de Otimização Multi-Objetivo, para encontrar um conjunto de soluções que representem um compromisso entre a extensão e a qualidade das soluções. Aplicou-se vários modelos de Algoritmos Evolutivos para Otimização Multi-Objetivo. O desempenho de cada modelo foi avaliado por métricas de performance encontradas na literatura. / The Biological Sequence Alignment is a basic operation in Bioinformatics since it serves as a basis for other processes, i.e. determination of the protein's three-dimensional structure. Due to the large amount of data involved, mathematical and computational methods have been used to solve this problem. Traditionally, the Biological Alignment Sequence Problem is formulated as a single optimization problem. Each solution has a score that reflects the similarity between sequences. Then, the optimization process looks for the best score solution. The Multi-Objective Optimization solves problems with multiple objectives that must be reached. Frequently, there is a solution set that represents a trade-off between the objectives. Evolutionary Algorithms, which are inspired by Darwin's Evolution Theory, have been applied with success in solving this kind of problems. This work formulates the Biological Sequence Alignment as a Multi-Objective Optimization Problem in order to find a set of solutions that represent a trade-off between the extension and the quality of the solutions. Several models of Evolutionary Algorithms for Multi-Objetive Optimization have been applied and were evaluated using several performance metrics found in the literature.

Este trabalho verifica a possibilidade de se aplicar Algoritmos Evolutivos no aprendizado on-line de jogos. Alguns autores concordam que Algoritmos Evolutivos não são aplicáveis na prática para se atingir o objetivo em questão. É com a intenção de contestar a veracidade desta afirmação que foi desenvolvido o presente trabalho. Para atingir o objetivo proposto, foi desenvolvido um jogo de computador, no qual o algoritmo de aprendizado gera estratégias inteligentes e adaptativas para os caracteres não controlados pelo jogador através de um algoritmo evolutivo. Desta forma, a função do algoritmo evolutivo é fazer com que a estratégia utilizada pelo computador se adapte à estratégia utilizada pelo usuário a cada vez que joga. É apresentada uma revisão bibliográfica a respeito de Computação Evolutiva e as técnicas utilizadas para implementar comportamentos inteligentes para os caracteres controlados por computador nos jogos atuais, esclarecendo suas vantagens, desvantagens e algumas possíveis aplicações. São também explicados o jogo e os algoritmos implementados, assim como os experimentos realizados e seus resultados. Por fim, é feita uma comparação do algoritmo evolutivo final com uma outra técnica de adaptação, chamada Dynamic Scripting. Assim, este trabalho oferece contribuições para o campo de Computação Evolutiva e Inteligência Artificial aplicada a jogos / The goal of this work is to verify if it is possible to apply Evolutionary Algorithms to online learning in computer games. Some authors agree that evolutionary algorithms do not work properly in that case. With the objective of contesting this affirmation, this work was performed. To accomplish the goal of this work, a computer game was developed, in which the learning algorithm must create intelligent and adaptive strategies to control the non-player characters using an evolutionary algorithm. Therefore, the aim of the evolutionary algorithm is to adapt the strategy used by the computer according to the player\'s actions during the game. A review on Evolutionary Computation and the techniques used to produce intelligent behaviors for the computer controlled characters in modern game is presented, exposing the advantages, the problems and some applications of each technique. The proposed game is also explained, together with the implemented algorithms, the experiments and the obtained results. Finally, it is presented a comparison between the implemented algorithm and the Dynamic Script technique. Thus, this work offers contributions to the fields of Evolutionary Computation and Artificial Intelligence applied to games

Nesta tese, são estudados algoritmos para agrupamento de dados, com particular ênfase em Agrupamento de Dados com Restrições, no qual, além dos objetos a serem agrupados, são fornecidos pelo usuário algumas informações sobre o agrupamento desejado. Como fundamentação para o agrupamento, são considerados os modelos de mistura finitos, em especial, com componentes gaussianos, usualmente chamados de modelos de mistura de gaussianas. Dentre os principais problemas que os algoritmos desenvolvidos nesta tese de doutorado buscam tratar destacam-se: (i) estimar parâmetros de modelo de mistura de gaussianas; (ii) como incorporar, de forma eficiente, restrições no processo de aprendizado de forma que tanto os dados quanto as restrições possam ser adicionadas de forma online; (iii) estimar, via restrições derivadas de conceitos pré-determinados sobre os objetos (usualmente chamados de classes), o número de grupos destes conceitos. Como ferramenta para auxiliar no desenvolvimento de soluções para tais problemas, foram utilizados algoritmos evolutivos que operam com mais de uma solução simultaneamente, além de utilizarem informações de soluções anteriores para guiar o processo de busca. Especificamente, foi desenvolvido um algoritmo evolutivo baseado na divisão e união de componentes para a estimação dos parâmetros de um modelo de mistura de gaussianas. Este algoritmo foi comparado com o algoritmo do mesmo gênero considerado estado-da-arte na literatura, apresentando resultados competitivos e necessitando de menos parâmetros e um menor custo computacional. Nesta tese, foram desenvolvidos dois algoritmos que incorporam as restrições no processo de agrupamento de forma online. Ambos os algoritmos são baseados em algoritmos bem-conhecidos na literatura e apresentaram, em comparações empíricas, resultados melhores que seus antecessores. Finalmente, foram propostos dois algoritmos para se estimar o número de grupos por classe. Ambos os algoritmos foram comparados com algoritmos reconhecidos na literatura de agrupamento de dados com restrições, e apresentaram resultados competitivos ou melhores que estes. A estimação bem sucedida do número de grupos por classe pode auxiliar em diversas tarefas de mineração de dados, desde a sumarização dos dados até a decomposição de problemas de classificação em sub-problemas potencialmente mais simples. / In the last decade, researchers have been giving considerable attention to the field of Constrained Clustering. Algorithms in this field assume that along with the objects to be clustered, the user also provides some constraints about which kind of clustering (s)he prefers. In this thesis, two scenarios are studied: clustering with and without constraints. The developments are based on finite mixture models, namely, models with Gaussian components, which are usually called Gaussian Mixture Models (GMMs). In this context the main problems addressed are: (i) parameter estimation of GMMs; (ii) efficiently integrating constraints in the learning process allowing both constraints and the data to be added in the modeling in an online fashion; (iii) estimating, by using constraints derived from pre-determined concepts (usually named classes), the number of clusters per concept. Evolutionary algorithms were adopted to develop solutions for such problems. These algorithms analyze more than one solution simultaneously and use information provided by previous solutions to guide the search process. Specifically, an evolutionary algorithm based on procedures that perform splitting and merging of components to estimate the parameters of a GMM was developed. This algorithm was compared to an algorithm considered as the state-of-the-art in the literature, obtaining competitive results while requiring less parameters and being more computationally efficient. Besides the aforementioned contributions, two algorithms for online constrained clustering were developed. Both algorithms are based on well known algorithms from the literature and get better results than their predecessors. Finally, two algorithms to estimate the number of clusters per class were also developed. Both algorithms were compared to well established algorithms from the literature of constrained clustering, and obtained equal or better results than the ones obtained by the contenders. The successful estimation of the number of clusters per class is helpful to a variety of data mining tasks, such as data summarization and problem decomposition of challenging classification problems.

Orientador: Jose Raimundo de Oliveira / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-09T17:11:57Z (GMT). No. of bitstreams: 1 Campos_TatianeJesusde_D.pdf: 4875626 bytes, checksum: 36e6cf7484aa1c689c28b67404d977e5 (MD5) Previous issue date: 2007 / Resumo: Na última década os algoritmos evolutivos vem sendo aplicados na síntese e projeto de circuitos eletrônicos criando uma nova área de pesquisa denominada Hardware Evolutivo. Esta tese propõe o uso de Hardware Evolutivo como uma ferramenta para geração automática de circuitos aplicados ao controle de um pêndulo amortecido não linear. Inicialmente um amplo estudo sobre a utilização de computação evolutiva aplicada à síntese de circuitos eletrônicos foi realizado, de modo a identificar os principais benefícios, motivações, aplicações e desafios da área de Hardware Evolutivo. A seguir foi realizado um estudo de caso com o objetivo de realizar uma comparação experimental dos principais pontos que afetam o desempenho de um sistema de Hardware Evolutivo na evolução de circuitos digitais básicos. Após a realização destas etapas foi desenvolvido um Hardware Evolutivo para controle de um pêndulo não linear. O objetivo desta implementação foi apresentar comparações de desempenho entre diferentes abordagens para projetos de controladores. O uso do Hardware Evolutivo para obtenção do controlador tem como objetivo modelar o comportamento não linear do sistema e sintetizá-lo em um circuito digital combinacional criando assim uma alternativa de projeto automático para sistemas de controle. A análise e simulação do pêndulo não linear demonstra que a aplicação desta nova técnica de projeto de hardware apresenta resultados promissores / Abstract: In the last decade evolutionary algorithms application in electronic circuits synthesis have been intensively investigated, starting a new research area called Evolvable Hardware. This thesis considers the use of Evolvable Hardware as a tool for automatic design of circuits applied to the control of a nonlinear damped pendulum. Initially a study on the use of applied evolutionary algorithms to the synthesis of electronic circuits was carried out, in order to identify the main benefits, motivations, applications and challenges of the field of Evolvable Hardware. A case study was carried out with the objective to provide an experimental comparison of the main points that affect the performance of a system in the evolution of basic digital circuits. Finally a Evolvable Hardware controller unit for control a nonlinear damped pendulum was evolved. The objective of this implementation was to present performance comparisons between two different controllers designs. The analysis and simulation of nonlinear pendulum demonstrate that the application of this new technique of design provides excellent results / Doutorado / Engenharia de Computação / Doutor em Engenharia Elétrica

Esta dissertação apresenta uma metodologia de otimização do fluxo de potência em sistemas elétricos de subtransmissão utilizando duas técnicas da Computação Evolutiva, os Algoritmos Genéticos e as Estratégias Evolutivas. A metodologia decompõe o problema em duas partes e o trata seqüencialmente. A primeira parte procede com a otimização do fluxo de potência ativa e a segunda com a otimização do fluxo de potência reativa. São apresentadas as características e estruturas básicas dos Algoritmos Genéticos e das Estratégias Evolutivas. A técnica dos Algoritmos Genéticos é implementada no modelo de otimização do fluxo de potência ativa e a técnica das Estratégias Evolutivas no modelo de otimização do fluxo de potência reativa. As variáveis de controle dos modelos desenvolvidos são, respectivamente, os estados dos dispositivos de seccionamento e os níveis de tensão dos barramentos dos pontos de fronteira, associadas ao sistema analisado. Analisam-se os sistemas elétricos de subtransmissão que contêm múltiplos pontos de fronteira (conexão) com a Rede Básica e diversas possibilidades de configuração operativa. A metodologia proposta é aplicada a um sistema elétrico de subtransmissão real a fim de minimizar o custo dos encargos de uso dos sistemas de transmissão. Os resultados obtidos mostram a eficácia dos algoritmos desenvolvidos na busca das soluções desejadas. / This dissertation presents a power flow optimization methodology on subtransmission electric systems using two techniques of Evolutionary Computation, namely the Genetic Algorithms and the Evolution Strategies. The methodology splits the problem into two parts and treats it separately. On the first step it proceeds to optimize the active power flow and on the second step to optimize the reactive power flow. Characteristics and basic structures of the Genetic Algorithms and the Evolution Strategies are shown. The Genetic Algorithms technique is implemented on the active power flow optimization model and the Evolution Strategies technique on the reactive power flow optimization model. The control variables of developed models are, respectively, the switch states and the border point bar voltage levels, associated to the analyzed system. The subtransmission electric systems that have multiple border (connection) points to the Basic Network and many operative configuration possibilities are analyzed. The proposed methodology is applied to a real subtransmission electric system in order to minimizes the transmission system use duty costs. The obtained results show the efficacy of the developed algorithms in the search of desired solutions.

ALGORITMOS de Estimação de Distribuição (EDAs) compõem uma frente de pesquisa em Computação Evolutiva que tem apresentado resultados promissores para lidar com problemas complexos de larga escala. Nesse contexto, destaca-se o Algoritmo de Otimização Bayesiano (BOA) que usa um modelo probabilístico multivariado (representado por uma rede Bayesiana) para gerar novas soluções a cada iteração. Baseado no BOA e na investigação de algoritmos de detecção de estrutura de comunidades (para melhorar os modelos multivariados construídos), propõe-se dois novos algoritmos denominados CD-BOA e StrOp. Mostra-se que ambos apresentam vantagens significativas em relação ao BOA. O CD-BOA mostra-se mais flexível que o BOA, ao apresentar uma maior robustez a variações dos valores de parâmetros de entrada, facilitando o tratamento de uma maior diversidade de problemas do mundo real. Diferentemente do CD-BOA e BOA, o StrOp mostra que a detecção de comunidades a partir de uma rede Bayesiana pode modelar mais adequadamente problemas decomponíveis, reestruturando-os em subproblemas mais simples, que podem ser resolvidos por uma busca gulosa, resultando em uma solução para o problema original que pode ser ótima no caso de problemas perfeitamente decomponíveis, ou uma aproximação, caso contrário. Também é proposta uma nova técnica de reamostragens para EDAs (denominada REDA). Essa técnica possibilita a obtenção de modelos probabilísticos mais representativos, aumentando significativamente o desempenho do CD-BOA e StrOp. De uma forma geral, é demonstrado que, para os casos testados, CD-BOA e StrOp necessitam de um menor tempo de execução do que o BOA. Tal comprovação é feita tanto experimentalmente quanto por análise das complexidades dos algoritmos. As características principais desses algoritmos são avaliadas para a resolução de diferentes problemas, mapeando assim suas contribuições para a área de Computação Evolutiva / ESTIMATION of Distribution Algorithms represent a research area which is showing promising results, especially in dealing with complex large scale problems. In this context, the Bayesian Optimization Algorithm (BOA) uses a multivariate model (represented by a Bayesian network) to find new solutions at each iteration. Based on BOA and in the study of community detection algorithms (to improve the constructed multivariate models), two new algorithms are proposed, named CD-BOA and StrOp. This paper indicates that both algorithms have significant advantages when compared to BOA. The CD-BOA is shown to be more flexible, being more robust when using different input parameters, what makes it easier to deal with a greater diversity of real-world problems. Unlike CD-BOA and BOA, StrOp shows that the detection of communities on a Bayesian network more adequately models decomposable problems, resulting in simpler subproblems that can be solved by a greedy search, resulting in a solution to the original problem which may be optimal in the case of perfectly decomposable problems, or a fair approximation if not. Another proposal is a new resampling technique for EDAs (called REDA). This technique results in multivariate models that are more representative, significantly improving the performance of CD-BOA and StrOp. In general, it is shown that, for the scenarios tested, CD-BOA and StrOp require lower running time than BOA. This indication is done experimentally and by the analysis of the computational complexity of the algorithms. The main features of these algorithms are evaluated for solving various problems, thus identifying their contributions to the field of Evolutionary Computation

O problema reconstrução filogenética têm como objetivo determinar as relações evolutivas das espécies, usualmente representadas em estruturas de árvores. No entanto, esse problema tem se mostrado muito difícil uma vez que o espaço de busca das possíveis árvores é muito grande. Diversos métodos de reconstrução filogenética têm sido propostos. Vários desses métodos definem um critério de otimalidade para avaliar as possíveis soluções do problema. Porém, a aplicação de diferentes critérios resulta em árvores diferentes, inconsistentes entre sim. Nesse contexto, uma abordagem multi-objetivo para a reconstrução filogenética pode ser útil produzindo um conjunto de árvores consideradas adequadas por mais de um critério. Nesta tese é proposto um algoritmo evolutivo multi-objetivo, denominado PhyloMOEA, para o problema de reconstrução filogenética. O PhyloMOEA emprega os critérios de parcimônia e verossimilhança que são dois dos métodos de reconstru ção filogenética mais empregados. Nos experimentos, o PhyloMOEA foi testado utilizando quatro bancos de seqüências freqüentemente empregados na literatura. Para cada banco de teste, o PhyloMOEA encontrou as soluções da fronteira de Pareto que representam um compromisso entre os critérios considerados. As árvores da fronteira de Pareto foram validadas estatisticamente utilizando o teste SH. Os resultados mostraram que o PhyloMOEA encontrou um número de soluções intermediárias que são consistentes com as soluções obtidas por análises de máxima parcimônia e máxima verossimilhança realizados separadamente. Além disso, os graus de suporte dos clados pertencentes às árvores encontradas pelo PhyloMOEA foram comparadas com a probabilidade posterior dos clados calculados pelo programa Mr.Bayes aplicados aos quatro bancos de teste. Os resultados indicaram que há uma relação entre ambos os valores para vários grupos de clados. Em resumo, o PhyloMOEA é capaz de encontrar uma diversidade de soluções intermediárias que são estatisticamente tão boas quanto as melhores soluções de máxima parcimônia e máxima verossimilhança. Tais soluções apresentam um compromisso entre os dois objetivos / The phylogeny reconstruction problem consists of determining the evolutionary relationships (usually represented as a tree) among species. This is a very complex problem since the tree search space is huge. Several phylogenetic reconstruction methods have been proposed. Many of them defines an optimality criterion for evaluation of possible solutions. However, different criteria may lead to distinct phylogenies, which often conflict with each other. In this context, a multi-objective approach for phylogeny reconstruction can be useful since it could produce a set of optimal trees according to mdifficultultiple criteria. In this thesis, a multi-objective evolutionary algorithm for phylogenetic reconstruction, called PhyloMOEA, is proposed. PhyloMOEA uses the parsimony and likelihood criteria, which are two of the most used phylogenetic reconstruction methods. PhyloMOEA was tested using four datasets of nucleotide sequences found in the literature. For each dataset, the proposed algorithm found a Pareto front representing a trade-off between the used criteria. Trees in the Pareto front were statistically validated using the SH-test, which has shown that a number of intermediate solutions from PhyloMOEA are consistent with solutions found by phylogenetic methods using one criterion. Moreover, clade support values from trees found by PhyloMOEA was compared to clade posterior probabilities obtained by Mr.Bayes. Results indicate a correlation between these probabilities for several clades. In summary, PhyloMOEA is able to find diverse intermediate solutions, which are not statistically worse than the best solutions for the maximum parsimony and maximum likelihood criteria. Moreover, intermediate solutions represent a trade-off between these criteria

Técnicas de agrupamento de dados usualmente assumem que o conjunto de dados é de tamanho fixo e pode ser alocado na memória. Neste contexto, um desafio consiste em aplicar técnicas de agrupamento em bases de dados de tamanho ilimitado, com dados gerados continuamente e em ambientes dinâmicos. Dados gerados nessas condições originam o que se convencionou chamar de Fluxo Contínuo de Dados (FCD). Em aplicações de FCD, operações de acesso aos dados são restritas a apenas uma leitura ou a um pequeno número de acessos aos dados, com limitações de memória e de tempo de processamento. Além disso, a distribuição dos dados gerados por essas fontes pode ser não estacionária, ou seja, podem ocorrer mudanças ao longo do tempo, denominadas de mudanças de conceito. Nesse sentido, algumas técnicas de agrupamento em FCD foram propostas na literatura. Muitas dessas técnicas são baseadas no algoritmo das k-Médias. Uma das limitações do algoritmo das k-Médias consiste na definição prévia do número de grupos. Ao se assumir que o número de grupos é desconhecido a priori e que deveria ser estimado a partir dos dados, percorrer o grande espaço de soluções possíveis (tanto em relação ao número de grupos, k, quanto em relação às partições possíveis para um determinado k) torna desafiadora a tarefa de agrupamento de dados - ainda mais sob a limitação de tempo e armazenamento imposta em aplicações de FCD. Neste contexto, essa tese tem como principais contribuições: (i) adaptar algoritmos que têm sido usados com sucesso em aplicações de Fluxo Contínuo de Dados (FCD) nas quais k é conhecido para cenários em que se deseja estimar o número de grupos; (ii) propor novos algoritmos para agrupamento que estimem k automaticamente a partir do FCD; (iii) avaliar sistematicamente, e de maneira quantitativa, os algoritmos propostos de acordo com as características específicas dos cenários de FCD. Foram desenvolvidos 14 algoritmos de agrupamento para FCD capazes de estimar o número de grupos a partir dos dados. Tais algoritmos foram avaliados em seis bases de dados artificiais e duas bases de dados reais amplamente utilizada na literatura. Os algoritmos desenvolvidos podem auxiliar em diversas áreas da Mineração em FCD. Os algoritmos evolutivos desenvolvidos mostraram a melhor relação de custo-benefício entre eficiência computacional e qualidade das partições obtidas. / Several algorithms for clustering data streams based on k-Means have been proposed in the literature. However, most of them assume that the number of clusters, k, is known a priori by the user and can be kept fixed throughout the data analysis process. Besides the dificulty in choosing k, data stream clustering imposes several challenges to be dealt with, such as addressing non-stationary, unbounded data that arrives in an online fashion. In data stream applications, the dataset must be accessed in order and that can be read only once or a small number of times. In this context, the main contributions of this thesis are: (i) adapt algorithms that have been used successfully in data stream applications where k is known to be able to estimate the number of clusters from data; (ii) propose new algorithms for clustering to estimate k automatically from the data stream; (iii) evaluate the proposed algorithms according to diferent scenarios. Fourteen clustering data stream algorithms were developed which are able to estimate the number of clusters from data. They were evaluated in six artificial datasets and two real-world datasets widely used in the literature. The developed algorithms are useful for several data mining tasks. The developed evolutionary algorithms have shown the best trade-off between computational efficiency and data partition quality.

Problemas de projeto de redes (PPRs) são muito importantes uma vez que envolvem uma série de aplicações em áreas da engenharia e ciências. Para solucionar as limitações de algoritmos convencionais para PPRs que envolvem redes complexas do mundo real (em geral modeladas por grafos completos ou mesmo esparsos de larga-escala), heurísticas, como os algoritmos evolutivos (EAs), têm sido investigadas. Trabalhos recentes têm mostrado que estruturas de dados adequadas podem melhorar significativamente o desempenho de EAs para PPRs. Uma dessas estruturas de dados é a representação nó-profundidade (NDE, do inglês Node-depth Encoding). Em geral, a aplicação de EAs com a NDE tem apresentado resultados relevantes para PPRs de larga-escala. Este trabalho investiga o desenvolvimento de uma nova representação, baseada na NDE, chamada representação nó-profundidade-grau (NDDE, do inglês Node-depth-degree Encoding). A NDDE é composta por melhorias nos operadores existentes da NDE e pelo desenvolvimento de novos operadores de reprodução possibilitando a recombinação de soluções. Nesse sentido, desenvolveu-se um operador de recombinação capaz de lidar com grafos não-completos e completos, chamado EHR (do inglês, Evolutionary History Recombination Operator). Foram também desenvolvidos operadores de recombinação que lidam somente com grafos completos, chamados de NOX e NPBX. Tais melhorias tem como objetivo manter relativamente baixa a complexidade computacional dos operadores para aumentar o desempenho de EAs para PPRs de larga-escala. A análise de propriedades de representações mostrou que a NDDE possui redundância, assim, foram propostos mecanismos para evitá-la. Essa análise mostrou também que o EHR possui baixa complexidade de tempo e não possui tendência, além de revelar que o NOX e o NPBX possuem uma tendência para árvores com topologia de estrela. A aplicação de EAs usando a NDDE para PPRs clássicos envolvendo grafos completos, tais como árvore geradora de comunicação ótima, árvore geradora mínima com restrição de grau e uma árvore máxima, mostrou que, quanto maior o tamanho das instâncias do PPR, melhor é o desempenho relativo da técnica em comparação com os resultados obtidos com outros EAs para PPRs da literatura. Além desses problemas, um EA utilizando a NDE com o operador EHR foi aplicado ao PPR do mundo real de reconfiguração de sistemas de distribuição de energia elétrica (envolvendo grafos esparsos). Os resultados mostram que o EHR possibilita reduzir significativamente o tempo de convergência do EA / Network design problems (NDPs) are very important since they involve several applications from areas of Engineering and Sciences. In order to solve the limitations of traditional algorithms for NDPs that involve real world complex networks (in general, modeled by large-scale complete or sparse graphs), heuristics, such as evolutionary algorithms (EAs), have been investigated. Recent researches have shown that appropriate data structures can improve EA performance when applied to NDPs. One of these data structures is the Node-depth Encoding (NDE). In general, the performance of EAs with NDE has presented relevant results for large-scale NDPs. This thesis investigates the development of a new representation, based on NDE, called Node-depth-degree Encoding (NDDE). The NDDE is composed for improvements of the NDE operators and the development of new reproduction operators that enable the recombination of solutions. In this way, we developed a recombination operator to work with both non-complete and complete graphs, called EHR (Evolutionary History Recombination Operator). We also developed two other operators to work only with complete graphs, named NOX and NPBX. These improvements have the advantage of retaining the computational complexity of the operators relatively low in order to improve the EA performance. The analysis of representation properties have shown that NDDE is a redundant representation and, for this reason, we proposed some strategies to avoid it. This analysis also showed that EHR has low running time and it does not have bias, moreover, it revealed that NOX and NPBX have bias to trees like stars. The application of an EA using the NDDE to classic NDPs, such as, optimal communication spanning tree, degree-constraint minimum spanning tree and one-max tree, showed that the larger the instance is, the better the performance will be in comparison whit other EAs applied to NDPs in the literatura. An EA using the NDE with EHR was applied to a real-world NDP of reconfiguration of energy distribution systems. The results showed that EHR significantly decrease the convergence time of the EA

El aprendizaje de máquinas ha ganado terreno utilizándose en casi todas las áreas de la vida cotidiana, ayudando a tomar decisiones en las finanzas, la medicina, el comercio y el entretenimiento. El desarrollo continuo de nuevos algoritmos y técnicas de aprendizaje automático, y la amplia gama de herramientas y conjuntos de datos disponibles han traído nuevas oportunidades y desafíos para investigadores y profesionales tanto del mundo académico como de la industria. Seleccionar la mejor estrategia posible para resolver un problema de aprendizaje automático es cada vez más difícil, en parte porque requiere largos tiempos de experimentación y profundos conocimientos técnicos. En este escenario, el campo de investigación Automated Machine Learning (AutoML) ha ganado protagonismo, proponiendo estrategias para automatizar progresivamente tareas usuales durante el desarrollo de aplicaciones de aprendizaje de máquina. Las herramientas de AutoML más comunes permiten seleccionar automáticamente dentro de un conjunto restringido de algoritmos y parámetros la mejor estrategia para cierto conjunto de datos. Sin embargo, los problemas prácticos a menudo requieren combinar y comparar algoritmos heterogéneos implementados con diferentes tecnologías subyacentes. Un ejemplo es el procesamiento del lenguaje natural, un escenario donde varía el espacio de posibles técnicas a aplicar ampliamente entre diferentes tareas, desde el preprocesamiento hasta la representación y clasificación de textos. Realizar AutoML en un escenario heterogéneo como este es complejo porque la solución necesaria podría incluir herramientas y bibliotecas no compatibles entre sí. Esto requeriría que todos los algoritmos acuerden un protocolo común que permita la salida de un algoritmo para ser compartida como entradas a cualquier otro. En esta investigación se diseña e implementa un sistema de AutoML que utiliza técnicas heterogéneas. A diferencia de los enfoques de AutoML existentes, nuestra contribución puede combinar técnicas y algoritmos de diferentes bibliotecas y tecnologías, incluidos algoritmos de aprendizaje de máquina clásicos, extracción de características, herramientas de procesamiento de lenguaje natural y diversas arquitecturas de redes neuronales. Definimos el problema heterogéneo de optimización de AutoML como la búsqueda de la mejor secuencia de algoritmos que transforme datos de entrada específicos en la salida deseada. Esto proporciona un enfoque teórico y práctico novedoso para AutoML. Nuestra propuesta se evalúa experimentalmente en diversos problemas de aprendizaje automático y se compara con enfoques alternativos, lo que demuestra que es competitiva con otras alternativas de AutoML en los puntos de referencia estándar. Además, se puede aplicar a escenarios novedosos, como varias tareas de procesamiento de lenguaje natural, donde las alternativas existentes no se pueden implementar directamente. El sistema está disponible de forma gratuita e incluye compatibilidad incorporada con una gran cantidad de marcos de aprendizaje automático populares, lo que hace que nuestro enfoque sea útil para resolver problemas prácticos con relativa facilidad y esfuerzo. El uso de la herramienta propuesta en esta investigación permite a los investigadores y profesionales desarrollar rápidamente algoritmos de referencia optimizados en diversos problemas de aprendizaje automático. En algunos escenarios, la solución proporcionada por nuestro sistema podría ser suficiente. Sin embargo, los sistemas AutoML no deben intentar reemplazar a los expertos humanos, sino servir como herramientas complementarias que permitan a los investigadores obtener rápidamente mejores prototipos y conocimientos sobre las estrategias más prometedoras en un problema concreto. Las técnicas de AutoML abren las puertas a revolucionar la forma en que se realiza la investigación y el desarrollo del aprendizaje automático en la academia y la industria.