A geração de testes para circuitos combinacionais com fan-outs recovergentes é um problema NP-completo. Com o rápido crescimento da complexidade dos circuitos fabricados, a geração de testes passou a ser um sério problema para a indústria de circuitos integrados. Muitos algoritmos de ATPG (Automatic Test Pattern Generation) baseados no algoritmo D, usam heurísticas para guiar o processo de tomada de decisão na propagação n e na justificação das constantes de forma a aumentar sua eficiencia. Existem heurísticas baseadas em medidas funcionais, estruturais e probabilísticas. Estas medidas são normalmente referidas como observabilidade e controlabilidade que fazem parte de um conceito mais geral, a testabilidade. As medidas que o algoritmo utiliza podem ser calculadas apenas uma vez, durante uma etapa de pré-processamento (medidas de testabilidade estáticas - STM's), ou dinamicamente, recalculando estas medidas durante o processamento sempre que elas forem necessárias (medidas de testabilidade dinâmicas — DTM's). Para alguns circuitos, o use de medidas dinâmicas ao invés de medidas estáticas diminui o número de backtrackings pcir vetor gerado. Apesar disto, o tempo total de CPU por vetor aumenta. Assim, as DTM's só devem ser utilizadas quando as STM's não apresentam uma boa performance. Isto pode ser feito utilizando-se as medidas estáticas ate um certo número de backtrackings. Se o padrão de teste não for encontrado, então medidas dinâmicas são utilizadas. Entretanto, a necessário ainda buscar formas de melhorar o processo dinâmico, diminuindo o custo computacional. A proposta original do calculo das DTM's apresenta algumas técnicas, baseadas em selective tracing, com o objetivo de reduzir o custo computacional. Este trabalho analisa o use combinado de heurísticas e propõe técnicas alternativas, na forma das heurísticas de recalculo parcial e recalculo de linhas não free, que visam minimizar o overhead do calculo das DTM's. E proposta ainda a técnica de Pré-implicação que transfere a complexidade do algoritmo para a memória. Isto é feito através de um preprocessamento que armazena informações necessárias para a geração de todos os vetores de teste. De outra forma estas informações teriam de ser calculadas na geração de cada um destes vetores. A implementação do algoritmo D com as várias heurísticas permitiu a realização de um experimento pratico. Isto possibilitou a análise quantitativa da performance do algoritmo D para vários tipos de circuitos e demonstrou a eficiência de uma das heurísticas propostas neste trabalho. / The test generation for combinational circuits that contain reconvergence is a NP-complete problem. With the rapid increase in the complexity of the fabricated circuits, the generation of test patterns poses a serious problem to the IC industry. A number of existing ATPG algorithms based on the D algorithm use heuristics to guide the decision process in the D-propagation and justification to improve the efficiency. The heuristics used by ATPG algorithm are based on structural, functional and probabilistics measures. These measures are commonly referred to as line controllability and observability and they are combined under the , more general notion of testability. The measures used by ATPG algorithms can be computed only once, during a preprocessing stage (static testability measures - STM's) or can be calculated dinamically, updating the testability measures during the test generation process (dymanic testability measures - DTM's). For some circuits, replacing STM's by DTM's decreases the average number of backtrackings per generated vector. Despite these decrease, the total CPU time per generated vector is greater when using DTM's instead of STM's. So, DTM's only must be used if the STM's don't present a good performance. This can be done by STM's until a certain number of backtrackings. If a test pattern has still not been found, then DTM's are used. Therefore, it is yet necessary to search for ways to improve the dynamic process and decrease the CPU time requirements. In the original approach some techniques for reducing the computational overhead of DTM's based on the well-know technique of selective path tracing are presented. In this work, the combined use of heuristics are analised and alternative techniques — the heuristics of partial recalculus and not free lines recalculus — are proposed. These alternative techniques were developed in order to minimize the overhead of the DTM's calculus. It is yet proposed the pre-implication technique which transfers to memory the algorithm complexity. It includes a preprocessing stage which storages all necesary informations to the generation of all test vectors. So, these informations don't need be computed in the generation of each test vector. The implementation of the D-Algorithm with diferent heuristics has possibilited a practical experiment. It was possible to analise the performance of the D-Algorithm on diferent circuit types and to demonstrate the efficiency of one of the proposed heuristics.

[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

The Semantic Web is an extension of the current Web, where the availability of information is expected to enable the cooperation between man and, above all, machines. The creation of standards which express shared meaning enable the construction of applications to solve integration, collaboration and automation problems which were already been identified by scientific community and technology consumers. The use of Web Services has brought several advances in this sense, and their annotation in semantic terms, transforming them into Semantic Web Services, enables the Semantic Web intent. Several technologies also enable the creation of such elements and their inherent use as basic blocks of application development whose scope is embedded on Web. This way, due to the fast growing of the number of services, some approaches to effectively solve the problem of services integration and use become necessary. This work proposes a modeling of a software solution to the discovery and composition of Semantic Web Services problem through the use of a genetic algorithm based on abstract data types. It is also proposed a tool implementation using OWL, OWL-S and OWL-S API languages and frameworks as well as the formal problem definition along with the scientific community expectations to the given solution. / AWeb Semântica é uma ampliação da web atual onde a disposição da informação viabiliza a cooperação entre homens e, sobretudo, entre máquinas. O surgimento de padrões web que expressam significado compartilhado possibilitam a construção de aplicações que resolvem problemas de integração, colaboração e automação já identificados pela comunidade científica e mercado consumidor de tecnologias. A utilização de Serviços Web trouxe grandes ganhos neste sentido, e sua anotação em termos semânticos, tornando-os Serviços Web Semânticos, viabiliza a proposta da Web Semântica. Diversas tecnologias viabilizam a construção de tais elementos e sua conseqüente utilização como blocos básicos do desenvolvimento de aplicações cujo escopo é embarcado na web. Assim, dado o rápido crescimento da quantidade de serviços, tornam-se necessárias abordagens que resolvam de forma efetiva, com garantias de qualidade e tempo de resposta aceitável, a integração e posterior utilização destes. Este trabalho propõe a modelagem de uma solução de software para o problema da Descoberta e Composição de Serviços Web Semânticos através do uso do Algoritmo Genético Baseado em Tipos Abstratos de Dados. Também é proposta uma implementação utilizando OWL, OWL-S e a OWL-S API. São apresentadas a definição formal do problema, as expectativas da comunidade científica quanto às soluções elaboradas e os resultados obtidos com respeito à viabilidade da proposta.

Made available in DSpace on 2015-03-26T13:50:12Z (GMT). No. of bitstreams: 1 texto completo.pdf: 2283755 bytes, checksum: 7b17f9a16dc883593adc1fe443b6a654 (MD5) Previous issue date: 2013-03-20 / Conselho Nacional de Desenvolvimento Científico e Tecnológico / The performance of LSEMs (Land surface and ecosystem models) depends on the parameters of the equations representing the simulated process. However, the measurement of some parameters can be impractical or even impossible; therefore, they need to be estimated, or preferably optimized specifically for each ecosystem. When the parameters are calibrated to a single variable (mono-objective problem) they may not represent the reality, because the complexity of the model and its dependence on several variables (multi-objective problem). Thus, simultaneous multi-objective optimizations are indispensable. However, the optimization performance decreases as the number of variables to be optimized simultaneously increases. Furthermore, the study of simultaneous optimization using more than three objectives is a new area and not yet sufficiently studied. For simultaneous optimization of a large number of variables, there is a method that uses concepts of hierarchical systems theory in which the optimization occurs from the fastest (radiative fluxes) to the slowest process (carbon allocation). This study evaluates the performance of the hierarchical optimization using the index D (the average of the ratios between the individual outputs of multi-objective optimization and monoobjective). Understanding how the performance index D varies with respect to the number of objective functions optimized and to the number of hierarchical levels is important for the development of this research area. Two steps are necessary to achieve the study goals. First, a sensitivity analysis was performed to determine the output variables sensitivity to the model parameters. After, simulations were made using all possible combinations among the seven micrometeorological variables available (PARo, fAPAR, Rn, u *, H, LE, NEE) taking into account the hierarchy of processes. The results indicate that for up to three objective functions, hierarchical multi-objective optimization generates better results than the simultaneous multiobjective optimization (one hierarchical level), provided that the parameters distribution among hierarchical levels is consistent with the sensitivity analysis. Another important result shows that for the same number of outputs optimized, the greater the number of hierarchical levels the better the performance of the optimized model. However, the model performance falls quickly as the number of objective functions increases, evidencing that the power of hierarchy calibration that use a high number of objective functions is highly dependent on the removal of some constraints for model s performance. / O desempenho de um LSEM (Modelo de superfície terrestre e ecossistema) depende dos parâmetros das equações que representam os processos simulados. Contudo, a mensuração de alguns destes parâmetros pode ser impraticável ou até mesmo impossível; por isso, necessitam ser estimados ou, preferencialmente, otimizados para cada ecossistema. Quando os parâmetros são calibrados para uma única variável (problema mono-objetivo) eles podem não representar bem a realidade, dado a complexidade do modelo e sua dependência de diversas variáveis (problema multiobjetivo). Por isso, há a necessidade de uma otimização simultânea multiobjetiva. Porém, o desempenho da otimização diminui com o aumento do número de variáveis otimizadas simultaneamente e, além disso, o estudo da otimização simultânea de mais de três objetivos é uma área relativamente nova e não suficientemente estudada. Para a otimização simultânea de um grande número de variáveis, existe uma metodologia na qual se utiliza conceitos de teoria hierárquica de sistemas em que a otimização ocorre dos processos mais rápidos (fluxos radiativos) para os mais lentos (alocação de carbono). Este trabalho avalia o desempenho da otimização hierárquica do modelo, utilizando o índice D (a média das razões individuais entre as saídas das otimizações multiobjetiva e monoobjetiva). Entender como o índice de desempenho D do algoritmo de otimização hierárquico varia em relação ao número de funções objetivo otimizadas é de extrema importância para o desenvolvimento desta área de pesquisa. Para fazer atingir os objetivos, foram necessárias duas etapas. Primeiramente, foi feita uma análise de sensibilidade, a fim de conhecer a sensibilidade das variáveis de saída aos parâmetros do modelo. Depois, foram feitas simulações com todas as combinações possíveis entre as sete variáveis micrometeorológicas disponíveis (PARo, fAPAR, Rn, u*, H, LE, NEE) levando em consideração a hierarquia dos processos. Os resultados encontrados indicam que, para até três funções objetivo, a otimização multiobjetiva hierárquica pode gerar resultados melhores do que a otimização multiobjetiva tradicional (um único nível hierárquico), desde que a distribuição dos parâmetros entre as variáveis seja feita de forma coerente com a análise de sensibilidade. Outro resultado importante revela que para um mesmo número de saídas otimizadas, quanto maior o número de níveis hierárquicos melhor o desempenho do modelo otimizado. Porém, o desempenho do modelo diminui rapidamente quando o número de funções objetivo aumenta, evidenciando que o poder da calibração hierárquica para o uso de um grande número de funções objetivo é altamente dependente de algumas restrições que o modelo possui e um alto desempenho do modelo para muitas funções objetivo será possível somente após a remoção delas.

Apresentamos um novo algoritmo, baseado no algoritmo de inversão de matrizes de Leverrier-Fadeev, para extrair os autovalores e os coeficientes do polinômio característico da matriz (si+ A), não-simétrica, que surge em conexão com o método LTSN - o qual utiliza a transformada de Laplace para a solução da equação de ordenadas discretas S N. O algoritmo baseia-se em propriedades exibidas pela matriz, cuja estrutura e valores dos elementos fazem com que todos os seus autovalores sejam reais e simétricos em relação a zero. Evidências experimentais demonstram que, os autovalores do bloco superior esquerdo da matriz, de dimensão N /2, entrelaçam os autovalores negativos de -A. O algoritmo foi implementado em FORTRAN 77, usando algumas rotinas do BLAS e do LAPACK, e estruturado de forma a explorar a estrutura da matriz, permitindo efetuar os cálculos necessários em um menor tempo e com um menor gasto de menória. No entanto, apesar de ganhos obtidos em comparação com o algoritmo usualmente utilizado, proposto por Barichello, nossos experimentos demonstram a instabilidade numérica do algoritmo de Leverrier-Fadeev. / We present a new algorithm to compute the eigenvalues and the coefficients o f the characteristic polynomial o f a nonsymmetric matrix o f the form (sI+ A), which arises in connection with the LTSN method for the solution of thc discrete ordinates equations S N. Our algorithm is a modifi.cation of the matrix inversion Leverrier-Fadeev algorithm, exploiting the pattern existent in the matrix -A and some properties exhibited by its eigenvalues, which have been determined experimentally. More specifi.cally, its eigenvalues alllie on the real axis and are symmetrically distributed around zero. Also, -A has a block structure and the eigenvalues of the left-hand superior block interleave the negative eigenvalues of the matrix. The algorithm was designed to exploit these characteristics, computing only the nega:tive eigenvalues of -A (due to their symmetrical distribution) by means of the well-know bisection method to obtain the zeros of thc characteristic polynomial. Since the eigenvalues of the left-hand superior block of A interleave those of the matrix, it is possible to use intervals made of pairs of those eigenvalues which contain just a single eigenvalue of - A. Also, the structure of -A was used to develop optimized sections of code of thc algorithm to reduce the number of operations required. The whole algorithm was implementcd in FORTRAN 77, making use of some of the BLAS and LAPACK routines. The results obtained although presenting a better performance than that used currently, due to Barichello, show that the algorithm is susceptible to the ill-conditioning of the matrix.

Problemas de resfriamento de circuitos, presentes nas indústrias de eletrônicos e miniaturizados, têm sido amplamente estudados com o propósito de desenvolver mecanismos capazes de reduzirem a taxa de falha nos equipamentos devido às altas temperaturas. O presente trabalho utiliza o método Design Construtal associado com algoritmos de otimização, busca exaustiva e algoritmo genético, para realizar o estudo numérico de corpos sólidos com geração de calor uniforme onde são inseridos caminhos altamente condutivos em forma de “Y”, “Y-Y”, duplo “Y-Y” e “T”. O objetivo principal das otimizações realizadas consiste em minimizar a resistência ao fluxo de calor, quando as áreas ocupadas pelos materiais de alta e baixa condutividades são mantidas constantes, variando-se os comprimentos e espessuras dos caminhos condutivos. Para a solução numérica da equação da difusão do calor com as condições de contorno estabelecidas em cada caso, foi utilizado o PDETool do software MatLab. A formulação para o caminho condutivo em forma de “Y” apresenta a construção de volumes elementares, mantendo a mesma condutividade térmica para todo o caminho condutivo. Na configuração em forma de duplo “Y – Y” foi utilizado o método de busca exaustiva associado ao algoritmo genético (GA). Nas simulações realizadas com o caminho condutivo em forma de “T”, a configuração apresenta combinações de condutividade térmica diferentes para a base e para a parte superior, enfatizando que a geometria depende das condições impostas pelo ambiente. Para o caso com um volume elementar, a configuração em forma de “Y” degenera-se gerando um caminho condutivo em forma de “U” e com dois volumes, a variação ocorre no comprimento dos ramos do caminho condutivo. Para a configuração com quatro volumes, a configuração ótima tem a forma de “X”. No caso do caminho em forma de “T”, a configuração que minimiza a máxima temperatura em excesso tem a forma de um “I”. Como previsto no princípio da ótima distribuição das imperfeições, a geometria ótima para os casos estudados é aquela que melhor distribui as imperfeições do sistema. / Problems that embody cooling of circuits that appears in electronics and miniaturized industries, have been widely studied to develop mechanisms capable of reducing the failure rate of the equipment due to high temperatures. The present work applies the Constructal Design method associated with optimization algorithms, exhaustive search and genetic algorithm, to perform the numerical study of solid bodies with uniform heat generation in which are inserted high-conducting pathways with “Y”, “Y–Y”, double “Y–Y” and “T” shapes. The main goal of the performed optimizations consists in minimizing the resistance to the heat flux when the occupied areas of high and low conductivity materials are maintained constant, varying the lengths and thickness of conductive paths. For the numerical solution of the heat diffusion equation with the boundary conditions established in each case, it was used the PDETool from MatLab software. The formulation for the conductive pathway with "Y" shape presents the construction of elementary volumes, maintaining the same thermal conductivity across the entire conductive pathway. In the configuration in double “Y–Y” form it was used exhaustive search method associated with genetic algorithm (GA). In the simulations performed with the T-shaped conductive pathway, the configuration provides combinations of different thermal conductivity for the base and the top, emphasizing that the geometry depends on the conditions imposed by the environment. For the case with one elementary volume, the Y-shaped configuration degenerates producing a conductive pathway with U-shape; and with two volumes, the variation occurs in the length of branches of the conductive pathway. For the configuration with four volumes, the optimum configuration has the form of “X”. In the case of T-shaped pathway, the configuration that minimizes the maximal excess of temperature is I-shaped. As predicted by the principle of optimal distribution of the imperfections, the optimal geometry for the cases studied is the one that promotes the best distribution of the imperfections of the system.

[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.

Neste trabalho é desenvolvida uma metodologia de otimização multiobjetivo baseada no NSGA-II (Nondominated Sorting Genetic Algorithm), a qual visa a otimização do projeto de máquinas de indução pentafásicas. A escolha deste tipo de máquina se justifica pelo fato de que elas apresentam vantagens importantes quando comparadas com as trifásicas convencionais, tais como maior potência e maior torque para um mesmo volume de material ativo, além da possibilidade de operar na ocorrência de falhas (perda de uma ou duas fases). Na otimização de máquinas de indução vários objetivos podem ser definidos, sendo estes muitas vezes conflitantes. Neste contexto, este trabalho visa obter soluções que representam um compromisso entre dois objetivos: rendimento e custo do material ativo (ferro e material condutor). O algoritmo de otimização desenvolvido e implementado utiliza dois controles de diversidade da população, um baseado no fenótipo dos indivíduos, que é característico do NSGA-II, e outro adicional que é baseado no genótipo. A geometria do estator e do rotor da máquina e o seu modo de acionamento são parametrizados por 14 variáveis inteiras. O método desenvolvido foi implementado no Matlab R e aplicado a um caso prático de otimização de uma máquina de indução pentafásica considerando os dois objetivos citados. Os resultados práticos mostram que o método é capaz de obter projetos otimizados com maior rendimento e menor custo aproveitando as características particulares deste tipo de máquina. / In this work, it is developed a method of multiobjective optimization based on NSGAII (Nondominated Sorting Genetic Algorithm), which aims at optimizing the design of five-phase induction machines. The choice of this particular type of machine is justified by the fact that they have important advantages over conventional three-phase machines, such as higher power and higher torque for the same volume of material; in addition, they can operate under fault (loss of one or even two phases). When optimizing induction machines, several objectives can be defined, which are often conflicting. In this context, this work aims to obtain solutions that represent a trade-off between two objectives: efficiency and cost of active material (iron and conductor materials). The optimization algorithm that was developed and implemented uses two types of control for the diversity of the population, one based on the phenotype of the individuals, characteristic of the NSGA-II, and another one based on the genotype. The geometrical dimensions of the stator and rotor, together with the driving strategy, are parameterized by 14 integer variables. The developed method was implemented using Matlab R and applied to a practical case of a five-phase induction machine considering the aforementioned objectives. The practical results show that the method can lead to an optimized design with higher efficiency and at a lower cost, accounting for the special characteristics of this type of machine.

Esta tese tem foco no tema de otimização de carteiras de investimento modeladas para estratégia de investimento de index tracking. O conteúdo final é composto por três artigos. O primeiro artigo é intitulado “Index Tracking with Controlled Number of Assets Using a Hybrid Heuristic Combining Genetic Algorithm and Non-linear Programming”, e foi aceito para publicação na revista Annals of Operations Research. O segundo artigo é “Index Tracking and Enhanced Indexing using Cointegration and Correlation with Endogenous Portfolio Selection”, e foi aceito para publicação na revista Quarterly Review of Economics and Finance. Por fim, o terceiro artivo é “Investigating the Use of Statistical Process Control Charts for Index Tracking Portfolios”, o qual já foi submetido e está atualmente em processo de revisão. No primeiro artigo, discutimos a estratégia de investimento de index tracking usando programação matemática. Primeiro, usamos uma formulação de programação não linear para o problema de index tracking, considerando um número limitado de ações. Devido à dificuldade de solução do problema em um intervalo de tempo razoável por pacotes matemáticos comerciais, aplicamos uma abordagem de solução híbrida, combinando programação matemática e algoritmo genético. Com a aplicação de testes, demonstramos a eficiência da abordagem proposta comparando os resultados com soluções ótimas, com métodos previamente desenvolvidos, e com dados reais de índices de mercado. Os experimentos computacionais focam no Ibovespa (o mais popular índice do mercado brasileiro), e também apresentamos resultados para mercados consolidados tais quais S&P 100 (Estados Unidos), FTSE 100 (Reino Unido) and DAX (Alemanha). A estrutura proposta apresenta sua abilidade para obter ótimos resultados (resultados com gap em relação às soluções ótimas menores que 5% em 8 minutos de tempo de processamento) até mesmo para índices de mercado com alta volatilidade em um mercado em desenvolvimento. No segundo artigo, a atenção é voltada para a análise de dois métodos alternativos entre si para solução do problema de otimização de index tracking. Esse artigo investiga o desempenho “fora da amostra” dos métodos de correlação e cointegração para as estratégias de index tracking (IT) e enhanced indexing (EIT) aplicadas aos dados de mercado Brasileiro e Norte-americano. Nosso objetivo é comparar ambos os métodos na medida em que exploramos fortemente a cointegração em relação a estudos prévios: nós transformamos a seleção do portfólio endógena ao problema de otimização nessa abordagem. Os testes foram executados utilizando dados de 2004 a 2014 com amostras de 57 ações para dados brasileiros, e 96 ações para dados dos Estados Unidos; carteiras foram construídas usando combinações de no máximo 10 ações. Apesar da realização de testes extensivos, os resultados gerais demonstraram desempenho similar para ambos os métodos. Para IT no mercado brasileiro, foi verificado um trade-off entre melhor erro de tracking e maior turnover com cointegração (com resultados opostos para correlação), sendo que este mesmo padrão não foi encontrado para dados norte-americanos. Os resultados para EIT também não apresentação claro favorecimento para cointegração ou correlação. Por fim, o terceiro artigo é dedicado à discussão a respeito do uso de processo estatístico de gráficos de controle para regulação de carteiras de index tracking. Nesse artigo, nosso objetivo é introduzir uma abordagem baseada em gráficos de controle (SPC) para monitorar o processo de rebalanceamento de carteiras de index tracking. O método de SPC é derivado da Estatística e da Engenharia, como ferramenta para controle de processos de produção. Para cumprir os objetivos, aplicamos gráficos de controle EWMA (do inglês, exponentially weighted moving average) para monitorar carteiras de IT baseadas no uso combinado de dois gráficos de controle: desempenho de carteiras em termos de erro de tracking e em termos de volatilidade. Assim, visamos tornar endógeno o controle do processo de rebalanceamento das carteiras baseado em seu desempenho e em suas condições de risco ao longo do tempo. Testes computacionais foram realizados para avaliar a abordagem desenvolvida em comparação com a estratégia tradicional de rebalanceamento (que consiste no uso de janelas fixas de tempo para atualização das carteiras), usando dados dos mercados brasileiro e norte-americano de 2005 a 2014. Os métodos de cointegração e correlação foram aplicados para otimização das carteiras. Os resultados demonstraram que a abordagem com SPC pode ser uma alternativa viável para o processo de rebalanceamento de carteiras.

[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.