Quantum annealing (QA) is an optimization process in quantum computing similar to the probabilistic metaheuristic simulated annealing (SA). The QA process involves encoding an optimization problem into an energy landscape, which it then traverses in search for the point of minimal energy representing the global optimal state. In this thesis two different implementations of QA are examined, one run on a binary quadratic model (BQM) and one on a discrete quadratic model (DQM). These are then compared to their traditional counterpart: SA, in terms of performance and accuracy when solving the graph coloring problem (GCP). Regarding performance, the results illustrate how SA outperforms both QA implementations. However, it is apparent that these slower execution times are mostly due to various overhead costs that appear because of limited hardware. When only looking at the quantum annealing part of the process, it is about a hundred times faster than the SA process. When it comes to accuracy, both the DQM-implementation of QA and SA provided results of high quality, whereas the BQM-implementation performed notably worse, both by often not finding the optimal values and by sometimes returning invalid results. / Quantum annealing (QA) är en kvantbaserad optimeringsprocess som liknar den probabilistiska metaheuristiken simulated annealing (SA). QA går ut på att konvertera ett optimeringsproblem till ett energilandskap, som sedan navigeras för att hitta punkten med lägst energi, vilket då motsvarar den optimala lösningen på problemet. I denna uppsats undersöks två olika implementationer av QA: en som använder en binary quadratic model (BQM) och en som använder en discrete quadratic model (DQM). Dessa två implementationerna jämförs med deras traditionella motsvarighet: SA, utifrån både prestanda och korrekthet vid lösning av graffärgningsproblemet (GCP). När det gäller prestanda visar resultaten att SA är snabbare än båda QA implementationerna. Samtidigt är det tydligt att denna prestandaskillnad framförallt beror på diverse förberedelser innan exkueringen startar på kvantdatorn, vilka är krävande på grund av olika hårdvarubegränsningar. Om man endast betraktar kvantprocesserna visar vår studie att QA implementationerna är ungefär hundra gånger snabbare än SA. Gällande korrekthet gav både DQM-implementationen av QA och SA resultat av hög kvalitet medan BQM-implementationen presterade betydligt sämre. Den gjorde detta dels genom att inte skapa optimala resultat och genom att returnera otillåtna lösningar.

O projeto de amplificadores de baixo ruído (LNA) aparenta ser um trabalho simples pelos poucos componentes ativos e passivos que o compõe, porém a alta correlação entre os seus parâmetros de projeto dificulta muito esse trabalho. Esta dissertação apresenta uma proposta para contornar essa dificuldade: o uso de algoritmos metaheurísticos, em particular algoritmos genéticos e simulated annealing. Algoritmos metaheurísticos são técnicas avançadas que emulam princípios físicos ou naturais para resolver problemas com alto grau de complexidade. Esses algoritmos estão emergindo nos últimos anos porque têm mostrado eficiência e eficácia. São feitos neste trabalho os projetos de três LNAs, dois (LNA1 e LNA2) para sistemas com arquitetura homódine (LNA com carga capacitiva) e um (LNA3) para sistemas com arquitetura heteródine (LNA com carga resistiva) utilizando-se algoritmos genéticos e simulated annealing (recozimento simulado). Apresenta-se inicialmente a análise detalhada da configuração escolhida para os projetos (fonte comum cascode com degeneração indutiva FCCDI). A frequência de operação dos LNAs é 1,8 GHz e a fonte de alimentação de 2,0 V. Para o LNA1 e o LNA2 se atingiu uma figura de ruído de 2,8 dB e 3,2 dB, consumo de potência de 6,8 mW e 2,7 mW e ganho de tensão de 22 dB e 24 dB, respectivamente. Para LNA3 se atingiu uma figura de ruído de 3,5 dB, consumo de potência de 7,8 mW e ganho de tensão de 15,5 dB. Os resultados obtidos e comparações feitas com LNAs da literatura demonstram viabilidade e eficácia da aplicação de algoritmos metaheurísticos no projeto de LNA. Neste trabalho utilizaram-se as ferramentas ELDO (simulador de circuitos elétricos), versão 2009.1 patch1 64 bits, ASITIC (para projetar e simular os indutores), versão 03.19.00.0.0.0 e MATLAB (o toolbox fornece os algoritmos metaheurísticos), versão 7.9.0.529 R2009b. Além disso, os projetos foram desenvolvidos na tecnologia CMOS 0,35 m da AMS (Austria Micro Systems). / The design of low noise amplifiers (LNA) seems to be a simple work because the small number of active and passive device that they are composes, nevertheless the high trade off of LNA parameters complicates very much the work. This research presents a proposal to contour act the obstacle: to use metaheuristic algorithms, in special genetic algorithms and simulated annealing. The metaheuristic algorithms are advanced techniques that emulate physics or natural principles to solve problems with high grade of complexity. They have been emerging in the last years because they have shown effectiveness and efficiency. In this dissertation were designed three LNAs using genetic algorithms and simulated annealing: two (LNA1 and LNA2) to homódine architecture (LNA with capacitive load) and one (LNA3) to heteródine architecture (LNA with resistive load). First it is show the detailed analysis of configuration chosen to the designs (common source cascode with inductive degeneration). The operation frequency is 1.8 GHz and power supply is 2.0 V for all LNAs. LNA1 and LNA2 reached a noise figure of 2.8 dB and 3.2 dB, a dissipation power of 6.8 mW and 2.7 mW, and a voltage gain of 22 dB and 24 dB respectively. LNA3 reached 3.5 dB of noise figure, 7.8 mW of dissipation power, and 15.5 dB of voltage gain. The results obtained and the comparisons with LNAs from the literature demonstrate that the metaheuristic algorithms show efficiency and effectiveness in the design of LNA. This study was developed with the help of the tools ELDO (electric circuit simulator) version 2009.1 patch1 64 bits, ASITIC (to design and simulate the inductors) version 03.19.00.0.0.0, and MATLAB (the toolbox provides the metaheuristic algorithms) version 7.9.0.529 R2009b. Furthermore, the designs were developed on CMOS 0.35 AMS (Austria Micro Systems) technology.

Made available in DSpace on 2015-03-04T18:51:09Z (GMT). No. of bitstreams: 1 TeseFlavia.pdf: 12428230 bytes, checksum: 6fb8e9ea53da0aa51093c702fb32bc4a (MD5) Previous issue date: 2009-06-06 / Coordenacao de Aperfeicoamento de Pessoal de Nivel Superior / As the genome sequencing advances, the comprehension of protein structures becomes a crucial extension to these progresses. In spite of the numerous recent technological advances, experimental determination of protein terciary structures is still very slow compared to the accumulated data from amino acid sequences. That is what makes the protein folding a central problem to the development of the pots-genomic era. In this work we use an optimization method, the Generalized Simulated Annealing (GSA), which is based on Tsallis' generalized thermostatistics, to investigate the protein folding problem. Although GSA is a generic procedure, its efficiency depends not only on the appropriate choice of parameters, but also on topological characteristics of the energy hypersurface. By mapping all the GSA parameters, it can be possible to reduce the number of possible choices of them. That also allows an analysis of its effects on the algorithm behavior. As a initial step, we apply GSA to known structures, such as polyalanines. In sequence, we also apply GSA to three more peptides of ribosomal P proteins, which are of considerable importance on the comprehension of Chagas' heart disease. Each one contains 13 amino acids and differ only on the third residue by a non-conservative mutation. As these peptides do not have experimentally resolved structure, we analyze results obtained from GSA followed by Molecular Dynamics simulations. Validity of these results is studied such that, in the future, unknown structures can be determined by this technique with a higher degree of confidence. / Com os rápidos avanços no seqüenciamento do genoma, a compreensão da estrutura de proteínas torna-se uma extensão crucial a esses progressos. Apesar dos significativos avanços tecnológicos recentes, a determinação experimental da estrutura terciária de proteínas ainda é muito lenta se comparada com a taxa de acúmulo de dados das seqüências de aminoácidos. Isto torna o enovelamento de proteínas um problema central para o desenvolvimento da biologia pós-genômica. Em nosso trabalho, fazemos uso de um método de otimização, o Generalized Simulated Annealing (GSA), baseado na termoestatística generalizada por Tsallis. Embora o GSA seja um procedimento geral, sua eficiência depende não apenas da escolha apropriada de parâmetros, mas também das características topológicas da hiper--superfície de energia da função custo. Com o mapeamento dos parâmetros necessários à aplicação do GSA, pode-se reduzir significativamente o número de escolhas, além de tornar possível uma análise do efeito dos parâmetros no comportamento do algoritmo. Como passo inicial, usamos estruturas conhecidas, com as quais os resultados obtidos com o GSA possam ser comparados, como é o caso das polialaninas. Além disso, aplicamos, o GSA a três peptídeos de proteínas ribossomais da família P, de considerável importância no estudo da doença de Chagas. Cada um possui 13 aminoácidos, diferindo em apenas uma mutação não conservativa no terceiro aminoácido. Como os peptídeos não possuem estrutura experimentalmente resolvida, analisamos os resultados obtidos com GSA seguidos por simulações de Dinâmica Molecular. A validade destes resultados é estudada, de forma que, no futuro, estruturas desconhecidas possam ser determinadas com certo grau de confiabilidade.

Neste estudo, o novo algoritmo hibrido autoconfigurado PSOS (Particle Swarm Optimization - Simplex) para avaliação da integridade estrutural a partir de respostas dinâmicas é apresentado. A formulação da função objetivo para o problema de minimização definido emprega funções de resposta em freqüência e/ou dados modais do sistema. Uma nova estratégia para o controle dos parâmetros do algoritmo Particle Swarm Optimization (PSO), baseada no uso do método de Nelder - Mead é desenvolvida; conseqüentemente, a convergência do PSO fica independente dos parâmetros heurísticos e sua estabilidade e precisão são melhoradas. O método híbrido proposto teve melhor desempenho, nas diversas funções teste analisadas, quando comparado com os algoritmos simulated annealing, algoritmos genéticos e o PSO. São apresentados diversos problemas de detecção de dano, levando em conta os efeitos do ruído e da falta de dados experimentais. Em todos os casos, a posição e extensão do dano foram determinadas com sucesso. Finalmente, usando o PSOS, os parâmetros de um oscilador não linear (oscilador de Duffing) foram identificados. / In this study, a new auto configured Particle Swarm Optimization - Simplex algorithm for damage detection has been proposed. The formulation of the objective function for the minimization problem is based on the frequency response functions (FRFs) and the modal parameters of the system. A novel strategy for the control of the Particle Swarm Optimization (PSO) parameters based on the Nelder-Mead algorithm (Simplex method) is presented; consequently, the convergence of the PSOS becomes independent of the heuristic constants and its stability and accuracy are enhanced. The formulated hybrid method performs better in different benchmark functions than the Simulated Annealing (SA), the Genetic Algorithm (GA) and the basic PSO. Several damage identification problems, taking into consideration the effects of noisy and incomplete data, were studied. In these cases, the damage location and extent were determined successfully. Finally, using the PSOS, a non-linear oscillator (Duffing oscillator) was identified with good results.

Fundação Carlos Chagas Filho de Amparo a Pesquisa do Estado do Rio de Janeiro / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Neste trabalho, é proposta uma nova família de métodos a ser aplicada à otimização de problemas multimodais. Nestas técnicas, primeiramente são geradas soluções iniciais com o intuito de explorar o espaço de busca. Em seguida, com a finalidade de encontrar mais de um ótimo, estas soluções são agrupadas em subespaços utilizando um algoritmo de clusterização nebulosa. Finalmente, são feitas buscas locais através de métodos determinísticos de otimização dentro de cada subespaço gerado na fase anterior com a finalidade de encontrar-se o ótimo local. A família de métodos é formada por seis variantes, combinando três esquemas de inicialização das soluções na primeira fase e dois algoritmos de busca local na terceira. A fim de que esta nova família de métodos possa ser avaliada, seus constituintes são comparados com outras metodologias utilizando problemas da literatura e os resultados alcançados são promissores. / In this thesis, a new family of methods designed for multimodal optimization is introduced. In these techniques, first of all, initial solutions are generated in order to explore the search space. Secondly, these solutions are grouped in clusters using a fuzzy-clustering algorithm so that multiple optima are found. Finally, an instance of deterministic optimization method is triggered within each cluster to reach for the local optimum. This family of methods is formed by six variants combining three initialization schemes in the first phase with two local search algorithms in the third. These methods are compared against other techniques in the literature using benchmarks, obtaining promising results.

Fundação Carlos Chagas Filho de Amparo a Pesquisa do Estado do Rio de Janeiro / Neste trabalho é apresentado a aplicação de um método de otimização a fim de estimar parâmetros que normalmente estão presentes na modelagem matemática da dinâmica de espécies químicas na interface água-sedimento. O Problema Direto aqui consistiu na simulação das concentrações das espécies orgânicas e inorgânicas (amônia e nitrato) de nitrogênio, num ambiente idealizado, o qual foi fracionado em quatro camadas: uma camada de água (1 metro) e três camadas de sedimento (0-1 cm, 1-2 cm e 2-10 cm). O Problema Direto foi resolvido pelo Método de Runge Kutta, tendo sido gerada uma simulação de 50 dias. Na estimativa dos coeficientes de difusão e porosidade foi aplicado o Método Simulated Annealing (SA). A eficiência da estratégia aqui adotada foi avaliada através do confronto entre dados experimentais sintéticos e as concentrações calçadas pela solução do Problema Direto, adotando-se os parâmetros estimados pela SA. O melhor ajuste entre dados experimentais e valores calculados se deu quando o parâmetro estimado foi a porosidade. Com relação à minimização da função objetivo, a estimativa desse parâmetro também foi a que exigiu menor esforço computacional. Após a introdução de um ruído randômico às concentrações das espécies nitrogenadas, a técnica SA não foi capaz de obter uma estimativa satisfatória para o coeficiente de difusão, com exceção da camada 0-1 cm sedimentar. Para outras camadas, erros da ordem de 10 % foram encontrados (para amônia na coluna dágua, pro exemplo). Os resultados mostraram que a metodologia aqui adotada pode ser bastante promissora enquanto ferramenta de gestão de corpos dágua, especialmente daqueles submetidos a um regime de baixa energia, como lagos e lagoas costeiras. / This work presents the application of an optimization method to estimate parameters that are usually present in the mathematical modeling of chemical species dynamics in the water-sediment interface . Here, the Direct Problem was the simulation of organic and inorganic (ammonium and nitrate) nitrogen species concentrations in an idealized environment, which was fractionated into four layers: a layer of water (1 meter depth) and three layers of sediment (0-1 cm 1-2 cm and 2-10 cm). The Direct Problem was solved by the Runge Kutta method, yielding a 50 days simulation. Thus, the Simulated Annealing (SA) Method was applied to estimate diffusion coefficients and porosity. The strategy efficiency was evaluated by comparing synthetic experimental data with those yielded by the direct problem solution, adopting the parameters estimated by SA Method. The best fitting between experimental and calculated concentrations was achieved when the porosity was the estimated parameter. Regarding the Objective Function minimization, the estimative of this parameter also required lower computational effort. After introducing a random noise to the concentrations of nitrogenous species, SA technique was unable to obtain a satisfactory estimate for the diffusion coefficient, with the exception of sediment layer 0-1 cm. For the other layers, concentrations errors as high as 10% were found (for the ammonia concentration in the water layer, for example). The results showed that the methodology adopted here can be a quite promising tool in the water bodies management, especially in those submitted to low energy, as lakes and coastal lagoons.

Fundação Carlos Chagas Filho de Amparo a Pesquisa do Estado do Rio de Janeiro / Neste trabalho é apresentado a aplicação de um método de otimização a fim de estimar parâmetros que normalmente estão presentes na modelagem matemática da dinâmica de espécies químicas na interface água-sedimento. O Problema Direto aqui consistiu na simulação das concentrações das espécies orgânicas e inorgânicas (amônia e nitrato) de nitrogênio, num ambiente idealizado, o qual foi fracionado em quatro camadas: uma camada de água (1 metro) e três camadas de sedimento (0-1 cm, 1-2 cm e 2-10 cm). O Problema Direto foi resolvido pelo Método de Runge Kutta, tendo sido gerada uma simulação de 50 dias. Na estimativa dos coeficientes de difusão e porosidade foi aplicado o Método Simulated Annealing (SA). A eficiência da estratégia aqui adotada foi avaliada através do confronto entre dados experimentais sintéticos e as concentrações calçadas pela solução do Problema Direto, adotando-se os parâmetros estimados pela SA. O melhor ajuste entre dados experimentais e valores calculados se deu quando o parâmetro estimado foi a porosidade. Com relação à minimização da função objetivo, a estimativa desse parâmetro também foi a que exigiu menor esforço computacional. Após a introdução de um ruído randômico às concentrações das espécies nitrogenadas, a técnica SA não foi capaz de obter uma estimativa satisfatória para o coeficiente de difusão, com exceção da camada 0-1 cm sedimentar. Para outras camadas, erros da ordem de 10 % foram encontrados (para amônia na coluna dágua, pro exemplo). Os resultados mostraram que a metodologia aqui adotada pode ser bastante promissora enquanto ferramenta de gestão de corpos dágua, especialmente daqueles submetidos a um regime de baixa energia, como lagos e lagoas costeiras. / This work presents the application of an optimization method to estimate parameters that are usually present in the mathematical modeling of chemical species dynamics in the water-sediment interface . Here, the Direct Problem was the simulation of organic and inorganic (ammonium and nitrate) nitrogen species concentrations in an idealized environment, which was fractionated into four layers: a layer of water (1 meter depth) and three layers of sediment (0-1 cm 1-2 cm and 2-10 cm). The Direct Problem was solved by the Runge Kutta method, yielding a 50 days simulation. Thus, the Simulated Annealing (SA) Method was applied to estimate diffusion coefficients and porosity. The strategy efficiency was evaluated by comparing synthetic experimental data with those yielded by the direct problem solution, adopting the parameters estimated by SA Method. The best fitting between experimental and calculated concentrations was achieved when the porosity was the estimated parameter. Regarding the Objective Function minimization, the estimative of this parameter also required lower computational effort. After introducing a random noise to the concentrations of nitrogenous species, SA technique was unable to obtain a satisfactory estimate for the diffusion coefficient, with the exception of sediment layer 0-1 cm. For the other layers, concentrations errors as high as 10% were found (for the ammonia concentration in the water layer, for example). The results showed that the methodology adopted here can be a quite promising tool in the water bodies management, especially in those submitted to low energy, as lakes and coastal lagoons.

Esta dissertação apresenta um estudo da modelagem de experimentos aplicados a um processo industrial de tratamento térmico. A motivação deste trabalho surgiu diante das dificuldades associadas aos processos de recozimento industrial de aços do tipo baixa liga, na tentativa de encontrar temperaturas nas quais as durezas superficiais dos aços atingissem valores suficientemente baixos, adequados para etapas posteriores de fabricação, em especial a usinagem. Inicialmente forem realizados diversos experimentos com diferentes aços, onde a dureza superficial é obtida em função da temperatura de recozimento e dos teores de carbono e silício das amostras utilizadas. Em seguida propôs-se um modelo quadrático para modelar a dureza superficial como função dessas três variáveis. A estimação de parâmetros do modelo proposto foi realizada com o emprego do algoritmo Simulated Annealing, uma meta-heurística para otimização global que procura imitar o processo de recozimento de um material sólido. Finalmente, usando-se o modelo proposto, foi resolvido o chamado problema inverso, o qual consiste na estimação da temperatura de recozimento em função dos teores de carbono e silício e da dureza desejada. / This dissertation presents a study for experiments modeling applied for a heat treatment industrial process. The driving force to this work have raised from usual difficulties while low-alloy steels annealing industrial processes get on, trying to find out temperatures which the superficial hardness measurements reaches low values enough and suitable for the following stages, in special focus, the machining. At the first time, some experiments have been done with several steel grades, where superficial hardness is achieved as a function by annealing temperature, percent carbon content and percent silicon content of the samples. There was purposed a quadratic model for modeling the hardness as a function of that three parameters. The parameter estimation of the purposed model was done by the simulated annealing algorithm, a metaheuristic for global optimization which can be as the same as annealing of a solid material. Starting at the purposed model, the inverse problem was solved, where the estimated annealing temperature was achieved by the carbon and silicon percent contents and the suitable hardness.

Neste estudo, o novo algoritmo hibrido autoconfigurado PSOS (Particle Swarm Optimization - Simplex) para avaliação da integridade estrutural a partir de respostas dinâmicas é apresentado. A formulação da função objetivo para o problema de minimização definido emprega funções de resposta em freqüência e/ou dados modais do sistema. Uma nova estratégia para o controle dos parâmetros do algoritmo Particle Swarm Optimization (PSO), baseada no uso do método de Nelder - Mead é desenvolvida; conseqüentemente, a convergência do PSO fica independente dos parâmetros heurísticos e sua estabilidade e precisão são melhoradas. O método híbrido proposto teve melhor desempenho, nas diversas funções teste analisadas, quando comparado com os algoritmos simulated annealing, algoritmos genéticos e o PSO. São apresentados diversos problemas de detecção de dano, levando em conta os efeitos do ruído e da falta de dados experimentais. Em todos os casos, a posição e extensão do dano foram determinadas com sucesso. Finalmente, usando o PSOS, os parâmetros de um oscilador não linear (oscilador de Duffing) foram identificados. / In this study, a new auto configured Particle Swarm Optimization - Simplex algorithm for damage detection has been proposed. The formulation of the objective function for the minimization problem is based on the frequency response functions (FRFs) and the modal parameters of the system. A novel strategy for the control of the Particle Swarm Optimization (PSO) parameters based on the Nelder-Mead algorithm (Simplex method) is presented; consequently, the convergence of the PSOS becomes independent of the heuristic constants and its stability and accuracy are enhanced. The formulated hybrid method performs better in different benchmark functions than the Simulated Annealing (SA), the Genetic Algorithm (GA) and the basic PSO. Several damage identification problems, taking into consideration the effects of noisy and incomplete data, were studied. In these cases, the damage location and extent were determined successfully. Finally, using the PSOS, a non-linear oscillator (Duffing oscillator) was identified with good results.

Made available in DSpace on 2015-05-14T12:36:55Z (GMT). No. of bitstreams: 1 parte1.pdf: 1169586 bytes, checksum: 685986454ee5e2cc58d709e7d646732f (MD5) Previous issue date: 2009-08-28 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / This work presents a new heuristic, called Heurística 1, and the implementations of the GRASP, Simulated Annealing and Genetic Algorithms metaheuristics for the rectilinear Steiner minimum tree problem (RSMTP), talking about its theoretical aspects, like computational complexity, and practical ones, like pseudo-codes and implementation strategies. The new techniques for RSMTP presented, especially the Genetic Algorithms, have computational results of superior quality in comparison to the best heuristics in present litera / Este trabalho apresenta uma nova heurística, denominada Heurística 1, e a implementação das metaheurísticas GRASP, Simulated Annealing e Algoritmos Genéticos para o problema da árvore retilínea mínima de Steiner (RSMTP), discorrendo sobre seus aspectos teóricos, como a complexidade computacional; e práticos, como pseudocódigos e estratégias de implementação. As novas abordagens para o RSMTP apresentadas, em especial os Algoritmos Genéticos, ostentam resultados computacionais de qualidade superior às apresentadas pelas melhores heurísticas da literatura atual.