[pt] Esta dissertação investiga a utilização de Algoritmos Genéticos (AG) no processo de descoberta de conhecimento implícito em Banco de Dados (KDD - Knowledge Discovery Database). O objetivo do trabalho foi avaliar o desempenho de Algoritmos Genéticos no processo de classificação de registros em Bancos de Dados (BD). O processo de classificação no contexto de Algoritmos Genéticos consiste na evolução de regras de associação que melhor caracterizem, através de sua acurácia e abrangência, um determinado grupo de registros do BD. O trabalho consistiu de 4 etapas principais: um estudo sobre a área de Knowledge Discovery Database (KDD); a definição de um modelo de AG aplicado à Mineração de Dados (Data Mining); a implementação de uma ferramenta (Rule-Evolver) de Mineração de Dados; e o estudo de casos. O estudo sobre a área de KDD envolveu todo o processo de descoberta de conhecimento útil em banco de dados: definição do problema; seleção dos dados; limpeza dos dados; pré-processamento dos dados; codificação dos dados; enriquecimento dos dados; mineração dos dados e a interpretação dos resultados. Em particular, o estudo destacou a fase de Mineração de Dados e os algoritmos e técnicas empregadas (Redes Neurais, Indução de regras, Modelos Estatísticos e Algoritmos Genéticos). Deste estudo resultou um survey sobre os principais projetos de pesquisa na área. A modelagem do Algoritmo Genético consistiu fundamentalmente na definição de uma representação dos cromossomas, da função de avaliação e dos operadores genéticos. Em mineração de dados por regras de associação é necessário considerar-se atributos quantitativos e categóricos. Atributos quantitativos representam variáveis contínuas (faixa de valores) e atributos categóricos variáveis discretas. Na representação definida, cada cromossoma representa uma regra e cada gene corresponde a um atributo do BD, que pode ser quantitativo ou categórico conforme a aplicação. A função de avaliação associa um valor numérico à regra encontrada, refletindo assim uma medida da qualidade desta solução. A Mineração de Dados por AG é um problema de otimização onde a função de avaliação deve apontar para as melhores regras de associação. A acurácia e a abrangência são medidas de desempenho e, em alguns casos, se mantém nulas durante parte da evolução. Assim, a função de avaliação deve ser uma medida que destaca cromossomas contendo regras promissoras em apresentar acurácia e abrangência diferentes de zero. Foram implementadas 10 funções de avaliação. Os operadores genéticos utilizados (crossover e mutação) buscam recombinar as cláusulas das regras, de modo a procurar obter novas regras com maior acurácia e abrangência dentre as já encontradas. Foram implementados e testados 4 operadores de cruzamento e 2 de mutação. A implementação de uma ferramenta de modelagem de AG aplicada à Mineração de Dados, denominada Rule-Evolver, avaliou o modelo proposto para o problema de classificação de registros. O Rule-Evolver analisa um Banco de Dados e extrai as regras de associação que melhor diferenciem um grupo de registros em relação a todos os registros do Banco de Dados. Suas características principais são: seleção de atributos do BD; informações estatísticas dos atributos; escolha de uma função de avaliação entre as 10 implementadas; escolha dos operadores genéticos; visualização gráfica de desempenho do sistema; e interpretação de regras. Um operador genético é escolhido a cada reprodução em função de uma taxa preestabelecida pelo usuário. Esta taxa pode permanecer fixa ou variar durante o processo evolutivo. As funções de avaliação também podem ser alteradas (acrescidas de uma recompensa) em função da abrangência e da acurácia da regra. O Rule- Evolver possui uma interface entre o BD e o AG, necessária para tor / [en] This dissertation investigates the application of Genetic Algorithms (GAs) to the process of implicit knowledge discovery over databases (KDD - Knowledge Discovery Database). The objective of the work has been the assessment of the Genetic Algorithms (GA) performance in the classification process of database registers. In the context of Genetic Algorithms, this classification process consists in the evolution of association rules that characterise, through its accuracy and range, a particular group of database registers. This work has encompassed four main steps: a study over the area of Knowledge Discovery Databases; the GA model definition applied to Data Mining; the implementation of the Data Mining Rule Evolver; and the case studies. The study over the KDD area included the overall process of useful knowledge discovery; the problem definition; data organisation; data pre-processing; data encoding; data improvement; data mining; and results´ interpretation. Particularly, the investigation emphasied the data mining procedure, techniques and algorithms (neural Networks, rule Induction, Statistics Models and Genetic Algorithms). A survey over the mais research projects in this area was developed from this work. The Genetic Algorithm modelling encompassed fundamentally, the definition of the chromosome representation, the fitness evaluation function and the genetic operators. Quantitative and categorical attributes must be taken into account within data mining through association rules. Quantitative attribites represent continuous variables (range of values), whereas categorical attributes are discrete variable. In the representation employed in this work, each chromosome represents a rule and each gene corresponds to a database attribute, which can be quantitative or categorical, depending on the application. The evaluation function associates a numerical value to the discovered rule, reflecting, therefore, the fitness evaluation function should drive the process towards the best association rules. The accuracy and range are performance statistics and, in some cases, their values stay nil during part of the evolutionary process. Therefore, the fitness evaluation function should reward chromosomes containing promising rules, which present accuracy and range different of zero. Ten fitness evaluation functions have been implemented. The genetic operators used in this work, crossover and mutation, seek to recombine rules´clauses in such a way to achieve rules of more accuracy and broader range when comparing the ones already sampled. Four splicing operators and two mutation operators have been experimented. The GA modeling tool implementation applied to Data Mining called Rule Evolever, evaluated the proposed model to the problem of register classification. The Rule Evolver analyses the database and extracts association rules that can better differentiate a group of registers comparing to the overall database registers. Its main features are: database attributes selection; attributes statistical information; evaluation function selection among ten implemented ones; genetic operators selection; graphical visualization of the system performance; and rules interpretation. A particular genetic operator is selected at each reproduction step, according to a previously defined rate set by the user. This rate may be kept fix or may very along the evolutionary process. The evolutionary process. The evaluation functions may also be changed (a rewarding may be included) according to the rule´s range and accuracy. The Rule Evolver implements as interface between the database and the GA, endowing the KDD process and the Data Mining phase with flexibility. In order to optimise the rules´ search process and to achieve better quality rules, some evolutionary techniques have been implemented (linear rank and elitism), and different random initialisation methods have been used as well; global averag

[pt] O desenvolvimento da Nanociência e da Nanotecnologia dependem em grande parte do avanço da Química Computacional. Nesse contexto, um dos conceitos mais importantes é o conjunto de funções de base. Essas são combinações lineares de funções que produzem uma solução aproximada da equação de Schrödinger para átomo de muitos elétrons e sistemas moleculares. A construção de funções de base é uma tarefa complexa e influencia a rapidez e a precisão de cálculos de estrutura eletrônica. Esse trabalho propõe uma metodologia baseada em Algoritmos Co-Evolucionários para realizar a parametrização e buscar a melhor forma de se utilizar primitivas gaussianas utilizadas em cálculos de estrutura eletrônica. Esta pesquisa avaliou diferentes formas de realizar a construção de funções de base com o emprego de Algoritmos Evolucionários. O trabalho apresenta uma metodologia inédita para realizar a construção de funções de base, que parametriza e distribui as primitivas gaussianas dentre os orbitais especificados. Como estudo de caso a ferramenta desenvolvida foi aplicada para construir funções de base para os seguintes átomos: B, C, N, O, F, Ne, Na, Mg, Al, Si, P, S, Cl, Ar. Em todos os casos, os resultados da aplicação metodologia que usa algoritmos co-evolucionários, foram superiores aos presentes na literatura. Com base na metodologia, é construído um sistema que torna viável a busca de funções de base que satisfaçam a um critério previamente especificado, no qual o usuário pode definir uma determinada precisão e a metodologia procura o número mínimo de parâmetros e a respectiva distribuição que aproxima a meta estabelecida. / [en] The development of nanoscience and nanotechnology has a strong dependency on the advance of computational chemistry. In this context, one of the most important concepts is the basis functions set. This linear combination of functions provides an approximate solution to Schrödinger equation for many electron atoms and molecular systems. The construction of basis function is a complex task and influences on the speed and precision of the electronic structures calculus Conventional non-linear programming techniques have been extensively used in parameterization, but they cannot be used to build a set of basis functions. This work intends to propose a methodology based in Evolutionary Algorithms to parameterize and search for the best way of using Gaussian primitives in calculus of electronic structure. The advantage of using evolutionary techniques is the ability to obtain good solutions for the continuous non-linear programming problems, which are at the same time discrete. Also, there are no necessary previous knowledge of good(standard) solutions for a certain problem. This work had evaluated different ways of build basis functions with the use of evolutionary algorithms. This essay inserts an unprecedented methodology in literature to perform construction of atomic basis functions. The tool developed here was applied to build the basis functions for the following atoms: B, C, N, O, F, Ne, Na, Mg, Al, Si, P, S, Cl, Ar. All cases of the applied methodology, which uses coevolutionary algorithms, present better results than the ones described in literature.

[pt] No Brasil, o planejamento da operação energética do Sistema Interligado Nacional - SIN é realizado atualmente por meio de uma cadeia de modelos matemáticos concebidos para otimizar o planejamento segundo o critério de minimização do valor esperado do custo total de operação. No entanto, desde a crise ocorrida no Setor Elétrico Brasileiro entre os anos de 2001 e 2002, cujo ápice ocorreu no racionamento de energia, houve uma intensificação na busca por métodos de otimização que permitam a consideração explicita de critérios adicionais na otimização, tal como a segurança operativa. Neste contexto, este trabalho propõe uma modelagem utilizando algoritmos genéticos que permite a consideração de múltiplos objetivos no processo de otimização sem que a representação física do sistema e de suas incertezas se- jam comprometidas. A abordagem multicritério para o problema possibilita que diversos indicadores, dentre os quais destaca-se o risco anual de déficit, que atualmente são apenas resultados da otimização, se tornem controláveis a partir de sua consideração diretamente no processo de otimização. A modelagem proposta foi computacionalmente implementada na linguagem C# utilizando a biblioteca GAcom desenvolvida pelo ICA/PUC-Rio. O desempenho da metodologia proposta foi avaliado por meio de estudos de casos aplicados ao SIN. Os resultados obtidos, assim como as vantagens observadas ao se utilizar a otimização multicritério, são discutidos ao longo do texto. / [en] In Brazil, the planning of the energy operation of the National Interconnected Power System is currently done through a chain of mathematical models designed to optimise the planning according to criterion of minimisation of the expected value of the total operation`s cost. However, since the 2001-2002 energy supply crisis, there was an intensification in the search for methods of optimization allowing explicit consideration of additional criteria, such as the operative security. In this context, this work proposes a modelling using genetic algorithms that makes possible the consideration of multiple objectives in the optimisation process without compromising the physical representation of the system and its uncertainties. A multicriteria approach to the problem allows that various indicators, like, for instance, annual deficit, which currently are only results of the optimisation, become controllable from its consideration in the optimisation process. The modelling proposal was computationally implemented in language C# using the GAcom library developed by the ICA/PUC-Rio. The performance of the proposed methodology was evaluated through potential National Inter- connected Power System case studies. The results, as well as the benefits seen when using the multicriteria optimisation, are discussed throughout the text.

[pt] Neste trabalho apresentamos uma proposta para auxiliar o estudo de funções polinomiais no ensino médio por intermédio das Curvas de Bézier. Para isto introduzimos as curvas de Bézier utilizando o algoritmo de De Casteljau e discutimos suas propriedades. Em seguida aplicamos a formulação das curvas de Bézier não paramétricas para representar funções polinomiais e discutimos alguns resultados observados em sala de aula. / [en] In this work we present a proposal to assist the study of polynomial functions in high school through the Bezier curves. For this we introduce the Bezier curves using the De Casteljau algorithm and discuss its properties. Then apply the formulation of Bezier curves non-parametric to represent polynomial functions and discuss some results observed in the classroom.

[pt] Com o desenvolvimento tecnológico no setor de telecomunicações, o espectro radioelétrico está quase totalmente ocupado com um grande número de múltiplas atribuições para os muitos serviços sem fio de aplicação comercial e, também, não comercial, tais como defesa, controle de tráfego aéreo e exploração científica. O espectro eletromagnético é um recurso natural precioso e escasso, por isso, importantes esforços estão sendo direcionados para o desenvolvimento de rádios cognitivos, com capacidade de sensoriar o uso do espectro e utilizar frequências momentaneamente disponíveis de forma oportunista. O rastreamento e a utilização de intervalos espectrais, ou white spaces, através da tecnologia de rádios cognitivos, permitirá aumentar a eficiência de uso do espectro com a introdução de novos serviços de telecomunicações a serem explorados por usuários secundários, obrigados a não interferir ou a provocar interferência muito limitada nos usuários primários. O objetivo geral deste trabalho é avaliar os principais algoritmos de detecção dos intervalos espectrais (Detector de Energia, Detecção do Valor Absoluto de Covariância, Sensoriamento de Covariância Espectral) por meio de simulações com dados experimentais obtidos em campanhas de medições e testes em laboratório. Os algoritmos foram testados para avaliar o seu desempenho em termos de probabilidade de detecção dada uma probabilidade de falso alarme requerida, complexidade computacional e robustez quanto a relações sinal-a-ruído baixas. Os dados experimentais utilizados provêm de campanhas de medidas realizadas em ambiente urbano na faixa de 3.5 GHz. / [en] With the technological development of the telecommunications industry, the radio spectrum is almost fully occupied with a large number of multiple assignments for wireless services for both commercial and non-commercial applications, such as defense, air traffic control and scientific exploration. The electromagnetic spectrum is a precious and scarce natural resource. Therefore, a considerable effort is being directed at the development of cognitive radios, capable of sensoring the spectrum and using momentarily available frequency bands in an opportunistic way. The tracking and using of these spectral intervals, or white spaces, using cognitive radio technology will enhance the efficiency of the spectrum use and allow the introduction of new telecommunications services to be exploited by secondary users, obliged not to interfere or produce very limited interference to primary users. The aim of this study is to evaluate the main algorithms for detection of spectral intervals (Energy Detector, Detection of Covariance Absolute Value, Spectral Covariance Sensing) through simulations with experimental data obtained in field measurements campaigns. The algorithms were tested to evaluate their performance in terms of detection probability given a required false alarm probability, computational complexity and robustness in low signal-to-noise conditions. The experimental data used comes from the measurements campaigns in urban environments at the 3.5 GHz band.

[pt] A extração de entidades de páginas web é comumente utilizada para melhorar a qualidade de muitas tarefas realizadas por máquinas de busca como detecção de páginas duplicadas e ranking. Essa tarefa se torna ainda mais relevante devido ao crescente volume de informação da internet com as quais as máquinas de busca precisam lidar. Existem diversos algoritmos para detecção de conteúdo na literatura, alguns orientados a sites e outros que utilizam uma abordagem mais local e são chamados de algoritmos orientados a páginas. Os algoritmos orientados a sites utilizam várias páginas de um mesmo site para criar um modelo que detecta o conteúdo relevante da página. Os algoritmos orientados a páginas detectam conteúdo avaliando as características de cada página, sem comparar com outras páginas. Neste trabalho apresentamos um algoritmo, chamado NCE ( News Content Extractor), orientado a página e que se propõe a realizar extração de entidades em páginas de notícias. Ele utiliza atributos de uma árvore DOM para localizar determinadas entidades de uma página de notícia, mais especificamente, o título e o corpo da notícia. Algumas métricas são apresentadas e utilizadas para aferir a qualidade do NCE. Quando comparado com outro método baseado em página e que utiliza atributos visuais, o NCE se mostrou superior tanto em relação à qualidade de extração quanto no que diz respeito ao tempo de execução. / [en] The entity extraction of web pages is commonly used to enhance the quality of tasks performed by search engines, like duplicate pages and ranking. The relevance of entity extraction is crucial due to the fact that search engines have to deal with fast growning volume of information on the web. There are many algorithms that detect entities in the literature, some using site level strategy and others using page level strategy. The site level strategy uses many pages from the same site to create a model that extracts templates. The page level strategy creates a model to extract templates according to features of the page. Here we present an algorithm, called NCE (News Content Extractor), that uses a page level strategy and its objective is to perform entity extraction on news pages. It uses features from a DOM tree to search for certain entities, namely, the news title and news body. Some measures are presented and used to evaluate how good NCE is. When we compare NCE to a page level algorithm that uses visual features, NCE shows better execution time and extraction quality.

[pt] Materiais compósitos são a base de muitos produtos, devido à sua capacidade de aperfeiçoar certas propriedades. Recentemente, a utilização de nanocargas na fabricação de compósitos vem sendo amplamente estudada, pois a partir de concentrações baixas de nanocargas, as propriedades começam a melhorar, possibilitando a criação de materiais leves e com uma grande gama de propriedades. Uma das propriedades mecânicas mais estudadas é o módulo de Young, que mensura a rigidez de um material. Alguns dos modelos existentes para essa propriedade em nanocompósitos pecam na precisão ou são limitados em função da fração máxima de nanopartículas admissível no modelo. Outros se adequam apenas a uma determinada combina ção de matriz/carga preestabelecida. O objetivo deste trabalho é utilizar Redes Neurais Artificiais como um aproximador capaz de modelar tal propriedade para diversas matrizes/cargas, levando em consideração suas características, sem perder a precisão. A validação do aproximador é realizada comparando o resultado com outros modelos propostos na literatura. Uma vez validada, utiliza-se Algoritmos Genéticos em conjunto com tal rede para definir qual seria a configuração ideal para três casos de estudo: um que maximize o valor do módulo de Young, outro que maximize o módulo relativo e um terceiro que maximize o módulo relativo e minimize a quantidade de carga utilizada, diminuindo os custos de projeto. As técnicas de Inteligência Computacional empregadas na modelagem e síntese de materiais nanoestruturados se mostraram boas ferramentas, uma vez que geraram uma boa aproximação dos dados utilizados com erros inferiores a 5%, além de possibilitarem a determinação dos parâmetros de síntese de um material com o módulo de Young desejado. / [en] Composite materials became very popular due to its improvements on certain properties achieved from the mixture of two different components. Recently, the use of nanofillers in the manufacture of composites has been widely studied due to the improvement of properties at low concentrations of nanofillers, enabling the creation of lightweight materials. Some of the existing models for the Young modulus of the nanocomposites have low accuracy or are limited in terms of the maximum filler fraction possible. Others are appropriate only for a given combination of matrix and filler. The objective of this work is to use Artificial Neural Networks as a function approximation method capable of modeling such property for various matrix/nanofillers, taking into account their characteristics, without losing accuracy. The validation of this approximator is performed comparing its results with other models proposed in the literature. Once validated, a Genetic Algorithm is used with the Neural Network to define which would be the ideal setting for three case studies: one that maximizes the value of composite’s Young’s modulus, other that maximizes the relative modulus and a third one that maximizes the relative modulus and minimizes the amount of load used, reducing the cost of project. Computational Intelligence techniques employed on the modeling and synthesis of nanostructured materials proved to be adequate tools, since it generated a good approximation of the data with errors lower than 5%, and determined the material’s parameters for synthesis with the desired Young’s modulus.

[pt] A atividade de Planejamento de Suprimento de Petróleo é um elo importante para a integração da Cadeia de Suprimento de Petróleo na PETROBRAS, uma vez que é responsável por refinar as informações do planejamento estratégico a ser implementado no nível operacional. Nesta tese, esse problema é definido e explicado em detalhes e um modelo de programação Inteira Mista é proposto para resolvê-lo. Embora os resolvedores de problemas de programação Inteira Mista tenham evoluído de forma surpreendente na última década, para esta aplicação em particular, com o modelo inicial proposto não é possível obter soluções com qualidade satisfatória em tempo computacional aceitável. Desta forma, a linha de pesquisa desta tese consistiu em investigar, em detalhe, a estrutura deste problemaa fim de encontrar reformulações mais adequadas e novos algoritmos para a solução deste problema. O foco principal desta tese é resolver de forma eficiente o problema de planejamento de suprimento de petróleo na PETROBRAS, no entanto, como subprodutos desse esforço são propostos um novo algoritmo de decomposição e reformulações que podem ser aplicados a uma ampla gama de problemas. No que diz respeito à realização do objetivo principal, todos os casos testados foram resolvidos de maneira eficiente através dos desenvolvimentos propostos. O novo algoritmo de decomposição se mostrou o método mais adequado para resolver as instâncias com mais de duas classes de navios operando em cada plataforma. Já para os casos com uma ou duas classes de navios, a formulação denominada Hull Relaxation, que tem como base uma estrutura definida neste trabalho como Cascading Knapsack Inequalities, é a melhor alternativa de solução. Tendo em vista estas alternativas de soluções, é implementado um algoritmo geral que automaticamente escolhe a melhor opção de solução, em função da estrutura do problema. Para a situação onde o número de classes de navios operando nas diversas plataformas varia entre um e quatro, pode-se usar mais de uma abordagem em paralelo e considerar como solução a alternativa mais rápida ou com melhor resultado. Este modelo está sendo testado na PETROBRAS e tem-se mostrado uma ferramenta eficaz para a integração de sua cadeia de suprimentos de petróleo, bem como permitindo a análise de cenários para a obtenção de soluções alternativas até então não exploradas. / [en] The Petroleum Supply Planning activity is an important link for the integration of the Petroleum Supply Chain at PETROBRAS as it is responsible for refining the strategic supply planning information to be used at the operational level. In this thesis we set the ground for understanding this important problem and we propose a mathematical model to solve it. Although the solvers in the last decade have evolved enormously, for this particular application we cannot get solutions with satisfactory quality in reasonable computational time with only the initial proposed model. This directed the line of research of this thesis into investigating, in detail, the structure of this problem in order to find more suitable reformulations and algorithms to tackle it. Our primary goal is to solve efficiently the petroleum supply planning problem at PETROBRAS. Nevertheless as a by-product of this endeavor, we propose a novel decomposition algorithm and reformulations based on a cascading knapsack structures that turn out to be applicable in a wide range of problems. Concerning the achievement of the main objective, we obtain good results for all instances we tested. We show that the novel decomposition algorithm is the most fitted method to solve the petroleum supply planning problem if we consider more than two tankers to offload each platform. In the case of one or two tankers to offload each platform, the hull relaxation formulation based on the cascading knapsack structure introduced after an inventory reformulation at platforms is the best option if one is to solve this problem. For the real application, these solution alternatives allow to implement a general algorithm that automatically switches to the best solution option depending on the structure of the problem. For the mixed situation, i.e., number of tanker varying from one to four, one can use more than one approaches in parallel and take the fastest or the best result obtained. This model is being tested at PETROBRAS and is showing to be an effective tool to help integrate its petroleum supply chain as well as to do what-if analysis to look for alternative solutions never thought before.

[pt] Séries temporais são ferramentas importantes para análise de eventos que ocorrem em diferentes domínios do conhecimento humano, como medicina, física, meteorologia e finanças. Uma tarefa comum na análise de séries temporais é a busca por eventos pouco frequentes que refletem fatos de interesse sobre o domínio de origem da série. Neste trabalho, buscamos desenvolver técnicas para detecção de eventos raros em séries temporais. Formalmente, uma série temporal A igual a (a1, a2,..., an) é uma sequência de valores reais indexados por números inteiros de 1 a n. Dados dois números, um inteiro t e um real d, dizemos que um par de índices i e j formam um evento-(t, d) em A se, e somente se, 0 menor que j - i menor ou igual a t e aj - ai maior ou igual a d. Nesse caso, i é o início do evento e j o fim. Os parâmetros t e d servem para controlar, respectivamente, a janela de tempo em que o evento pode ocorrer e a magnitude da variação na série. Assim, nos concentramos em dois tipos de perguntas relacionadas aos eventos-(t, d), são elas: - Quais são os eventos-(t, d) em uma série A? - Quais são os índices da série A que participam como inícios de ao menos um evento-(t, d)? Ao longo desse trabalho estudamos, do ponto de vista prático e teórico, diversas estruturas de dados e algoritmos para responder às duas perguntas listadas. / [en] Time series are important tools for the anaylsis of events that occur in different fields of human knowledge such as medicine, physics, meteorology and finance. A common task in analysing time series is to try to find events that happen infrequently as these events usually reflect facts of interest about the domain of the series. In this study, we develop techniques for the detection of rare events in time series. Technically, a time series A equal to (a1, a2,..., an) is a sequence of real values indexed by integer numbers from 1 to n. Given an integer t and a real number d, we say that a pair of time indexes i and j is a (t, d)-event in A, if and only if 0 less than j - i less than or equal to t and aj - ai greater than or equal to d. In this case, i is said to be the beginning of the event and j is its end. The parameters t and d control, respectively, the time window in which the event can occur and magnitude of the variation in the series. Thus, we focus on two types of queries related to the (t, d)-events, which are: - What are the (t, d)-events in a series A? - What are the indexes in the series A which are the beginning of at least one (t, d)-event? Throughout this study we discuss, from both theoretical and practical points of view, several data structures and algorithms to answer the two queries mentioned above.

[pt] Esta tese investiga a utilização de computação evolutiva aplicada à síntese de circuitos eletrônicos. A computação evolutiva compreende uma classe de algoritmos que utilizam certos aspectos da evolução natural como metáforas. Particularmente, a seleção natural, a recombinação de material genético e a mutação são os mecanismos biológicos nos quais a maior parte destes algoritmos evolutivos buscam inspiração. Embora algoritmos evolutivos tenham encontrado em problemas de otimização o seu maior potencial de aplicação, a utilização dos mesmos na síntese de circuitos eletrônicos vem sendo intensamente investigada nos últimos anos, dando início à área de pesquisa denominada de Eletrônica Evolutiva. Esta tese enfoca a área de eletrônica evolutiva sob o ponto de vista de engenharia de circuitos, e seu maior objetivo é oferecer embasamento teórico e experimental para proposta de novas ferramentas de Computer Aided Design (CAD) de circuitos eletrônicos. Nesta pesquisa, a utilização de algoritmos evolutivos não se restringiu àqueles que empregam apenas os três operadores genéticos descritos anteriormente, isto é, seleção, recombinação e mutação. Investigou-se a inclusão de novos métodos e operadores ao fluxo básico dos algoritmos evolutivos, com o propósito de melhorar seu desempenho em problemas na área de Eletrônica Evolutiva. Particularmente, estudou-se a utilização de complexidade através de sistemas com representação variável sistemas evolutivos que utilizem como metáfora o conceito biológico de especiação. Além disso, uma nova metodologia para otimização com múltiplos objetivos, baseada em conceitos de aprendizado de Redes Neurais Artificiais, for também concebida nessa tese. Realizou-se um amplo estudo de casos, abrangendo eletrônica analógica, digital e microeletrônica. Uma grande variedade de circuitos de caráter prático foi sintetizada, tais como: filtros, amplificadores, osciladores, retificadores, receptores, comparadores, multiplexadores e portas digitais básicas. Novos paradigmas de eletrônica evolutiva foram também concebidos, com o intuito de tornar os circuitos projetados competitivos com aqueles convencionalmente utilizados; estes paradigmas referem-se à forma como os circuitos são avaliados ao longo do algoritmo evolutivo. A plataforma para realização dos experimentos consistiu de simuladores de circuitos e também de circuitos integrados reconfiguráveis. Os resultados mostram que esta nova classe de ferramentas de CAD pode chegar a circuitos mais eficientes do que os obtidos por ferramentas convencionais. Além disso, circuitos eletrônicos sintetizados por computação evolutiva são em geral bastante distintos daqueles projetados convencionalmente, o que contribui para a concepção de novas metodologias de projeto. / [en] This thesis investigates the application of evolutionary computing techniques in the synthesis of electronic circuits. Evolutionary computation encompasses a particular class of algorithm which employ some aspects of natural evolution as metaphors. Particularly, most of these algorithms borrow ideas from the natural selection, genetic material recombination and mutation biological mechanisms. Even though evolutionary algorithms have been intensively investigates recently, starting a new research area called Evolutionary Electronics. This work focuses on evolutionary electronics from a enginnering perspective and the main objective is the proposal of a new generation of a Computer Aided Design (CAD) tools. Many case studies have been analysed, covering digital and analog microelectronics. The work aimed the achievement of competitive results comparing to other CAD tools. The research has made use of evolutionary algorithms tailored to these application, by including other genetic operators besides the ones defined above. The following methods have been embedded in the evolutionary methodology: memory based genetic algorithms, use of variable length representation systems and the use of the biological speciation metaphor. Furthermore, a new multiple-objective optimization method, based on artificial neural networks learning algorithms, has also been employed in the case studies. A large number of circuits of practical interest have been sysnthesised, such as filters, amplifiers, oscillators, rectifiers, receptors, comparators refer to new approaches for circuits evaluation, particularly in the digital domain. Circuit simulators and analog the reconfigurable circuits have been used as platforms for the evolutionary process. The results show that the circuits synthesided through evolutionary computation are, in some cases, more efficient than the human designed ones. Besides, the evolved circuits are usually quite different from their human designed counterparts, which can contribute to the creation of new design methodologies. The author identified many promising ways of evolutionary algorithms application in analog and digital design, which may, in the future, overcome conventional design in terms of area, speed and power consumption.