Orientador: Ricardo Tokio Higuti / Resumo: O ultrassom pode ser utilizado para gerar imagens aplicadas aos ensaios não destrutivos (END) e diagnóstico médico, em que arrays são utilizados para obter imagens com melhor resolução lateral e contraste em relação a um único transdutor. No entanto, os arrays precisam ter o centro do seus elementos espaçados por uma distância (pitch) menor que λ/2, em que λ é o comprimento de onda gerado pelo transdutor, para que as imagens geradas por estes não apresente artefatos causados pelos lóbulos de espaçamento. Porém, para evitar circunstâncias como o aumento na complexidade eletrônica e tempo elevado para geração de imagens ultrassônicas, os arrays esparsos podem ser utilizados, os quais possuem os elementos espaçados por uma distância maior que λ/2 e as imagens geradas apresentam artefatos causados por lóbulos de espaçamento. Contudo, quando os arrays esparsos são utilizados, existem diversas combinações entre os pitches dos elementos para produzir imagens com diferentes qualidades, inviabilizando o teste de todas as combinações possíveis. Assim, neste trabalho, foi utilizado o algoritmo de busca genética para encontrar configurações de arrays esparsos que gerem imagens com boa qualidade, sendo proposto duas novas funções aptidão para avaliar os arrays esparsos. A primeiraé baseada no diagrama de radiação, e a segunda, na comparação entre PSFs (Point Spread Function). As configurações de arrays esparsos encontrados pelo algoritmo genético foram comparadas aos arrays esparsos dispo... (Resumo completo, clicar acesso eletrônico abaixo) / Abstract: Ultrasound can be used to generate images for nondestructive testing and medical diagnostic, in which arrays are used to generate images with better lateral resolution and contrast in comparison to a single transducer. In order to avoid artifacts in ultrasonic images caused by grating lobes, arrays need to have the center of their elements spaced by a distance (pitch) less than λ/2, where λ is the wavelength generated by the transducer. However, in order to avoid electronic complexity and high time to create an ultrasonic image, sparse arrays can be used, which their elements have a pitch greater than λ/2 that generates images with artifacts caused by grating lobes. Although, sparse arrays have their elements with different pitches that produce images with different qualities which it makes impossible to test all combinations. Thus, in this work, the genetic search algorithm was used to find sparse arrays that generate images with good quality. In addition, two new fitness functions were proposed. The first one based on the beam pattern and the second one in the comparison of two PSFs (Point Spread Function). The quality of the sparse arrays found by the genetic algorithm was then compared to the sparse arrays proposed by different authors using the beam pattern, PSF, and images generated from experimental data provided by CSIC (Consejo Superior de Investigaciones Científicas). In general, the images generated by the arrays obtained by the methodology developed in this work p... (Complete abstract click electronic access below) / Mestre

O objetivo de projetos de reforma agrária é redistribuir terras de grandes latifúndios para terrenos menores, com destino à agricultura familiar. Um dos principais problemas do Instituto Nacional de Colonização e Reforma Agrária (INCRA) é subdividir uma parcela grande de terra em lotes menores que são balanceados com relação a certos atributos. Este problema é difícil por que precisa considerar diversas restrições legais e éticas. As soluções atuais são auxiliadas por computador, mas manuais, demoradas e suscetíveis a erros, tipicamente produzindo lotes retangulares de áreas similares mas que são injustos com relação a critérios como aptidão do solo ou acesso a recursos hidrográficos. Nesta dissertação, nós propomos um algoritmo genético para gerar subdivisões justas de forma automática. Nós apresentamos um algoritmo construtivo guloso randomizado baseado em locação-alocação para gerar soluções iniciais, assim como operadores de mutação e recombinação que consideram especificidades do problema. Experimentos com 5 instâncias reais e 25 instâncias geradas artificialmente confirmam a efetividade dos diferentes componentes do método proposto, e mostram que ele gera soluções mais balanceadas que as atualmente usadas na prática. / The goal of agrarian reform projects is the redistribution of farmland from large latifundia to smaller, often family farmers. One of the main problems the Brazilian National Institute of Colonization and Agrarian Reform (INCRA) has to solve is to subdivide a large parcel of land into smaller lots that are balanced with respect to certain attributes. This problem is difficult since it considers several constraints originating from legislation as well as ethical considerations. Current solutions are computer-assisted, but manual, time-consuming and error-prone, leading to rectangular lots of similar areas which are unfair with respect to soil aptitude and access to hydric resources. In this thesis, we propose a genetic algorithm to produce fair land subdivisions automatically. We present a greedy randomized constructive heuristic based on location-allocation to generate initial solutions, as well as mutation and recombination operators that consider specifics of the problem. Experiments on 5 real-world and 25 artificial instances confirm the effectiveness of the different components of our method, and show that it leads to fairer solutions than those currently applied in practice.

Submitted by Automação e Estatística (sst@bczm.ufrn.br) on 2018-07-26T17:05:20Z No. of bitstreams: 1 FranciscoDasChagasBarbosaDeSena_TESE.pdf: 5493232 bytes, checksum: 378d23f978bc334f78243d8199a72e4d (MD5) / Approved for entry into archive by Arlan Eloi Leite Silva (eloihistoriador@yahoo.com.br) on 2018-07-26T19:31:37Z (GMT) No. of bitstreams: 1 FranciscoDasChagasBarbosaDeSena_TESE.pdf: 5493232 bytes, checksum: 378d23f978bc334f78243d8199a72e4d (MD5) / Made available in DSpace on 2018-07-26T19:31:37Z (GMT). No. of bitstreams: 1 FranciscoDasChagasBarbosaDeSena_TESE.pdf: 5493232 bytes, checksum: 378d23f978bc334f78243d8199a72e4d (MD5) Previous issue date: 2018-04-13 / Conselho Nacional de Desenvolvimento Científico e Tecnológico - CNPq / As antenas de microfita têm atraído a atenção de pesquisadores no mundo inteiro por possuírem características interessantes a diversas aplicações. Contudo, desvantagens como baixo ganho, estreita largura de banda e baixa eficiência de radiação podem limitar o seu uso em um determinado sistema. Além disso, esse tipo de antena pode excitar modos de ordem superior em adição ao fundamental. Essa característica é particularmente importante para sistemas que possuem múltiplas frequências de operação, nos demais casos, faz-se necessário o uso de filtros para eliminar os modos indesejados. Alternativamente, pode-se adicionar arranjos de defeitos ao plano de terra ou ao substrato da antena para cumprir esse mesmo objetivo, sendo tais estruturas denominadas de Defected Ground Structure (DGS) e Photonic Band Gap (PBG), respectivamente. Entretanto, o desenvolvimento de projetos eficientes envolvendo esses tipos de estruturas apresenta grande dependência da correta especificação dos parâmetros físicos do arranjo utilizado. Nesse contexto, objetivando eliminar e/ou atenuar os modos de ordem superior, sem afetar significativamente o desempenho da antena em operação para o modo fundamental, o presente trabalho estudou a aplicação de um Algoritmo Genético (AG) no desenvolvimento de novos modelos de estruturas DGS e PBG. Os modelos propostos são constituídos de furos circulares, preenchidos com ar, nos padrões hexagonal e retangular, para a configuração periódica, e com padrão micro estruturado, para a configuração quase periódica. O AG proposto foi responsável por especificar os seguintes parâmetros dos arranjos analisados: diâmetro dos furos, distância de separação entre os mesmo e o posicionamento do arranjo ao longo do comprimento da antena. Todas as antenas analisadas foram construídas manualmente, através do uso de uma fresadora e/ou corrosão por percloreto de ferro. Com base nos resultados simulados e medidos, verificou-se que o AG proposto foi capaz de otimizar as estruturas estudadas de maneira a preservar o modo fundamental, ao passo que os de ordem superior foram eliminados e/ou consideravelmente atenuados. Verificou-se que para o mesmo tipo de arranjo, as antenas com DGS apresentaram melhor desempenho em relação às com PBG, considerando o coeficiente de reflexão do modo fundamental. Além disso, as estruturas otimizadas não provocaram variações significativas no valor do ganho total ou na forma do diagrama de radiação e, no caso dos DGS, exibiram características importantes para miniaturização das antenas. Os resultados obtidos são particularmente importantes, partindo do pressuposto de que as estruturas otimizadas podem ser utilizadas para eliminar modos indesejados em aplicações com antenas de microfita passivas ou ativas, que operam também como ressoadores. / Microstrip antennas have attracted the attention of researchers worldwide because of their interesting features for various applications. However, disadvantages such as low gain, narrow bandwidth and low radiation efficiency can limit its use in a given system. Besides, this type of antenna can excite higher order modes in addition to the fundamental. This feature is particularly important for systems with multiple operating frequencies, in other cases, it is necessary to use filters to eliminate the unwanted modes. Alternatively, arrangement of defects can be added to the antenna‟s ground plane or substrate to achieve the same aim, such structures are called Defected Ground Structure (DGS) and Photonic Band Gap (PBG), respectively. However, the development of really efficient projects involving these types of structures presents great dependence on the correct specification of the physical parameters of the used arrangement. In this context, aiming at eliminating and/or attenuating higher order modes, without significantly affecting the performance of the antenna to the fundamental mode, the present work studied the application of a Genetic Algorithm (GA) in the development of new models of DGS and PBG structures. The proposed models consist of circular holes, filled with air, in the hexagonal and rectangular patterns, for the periodic configuration, and with micro structured pattern, for the quasi periodic configuration. The proposed AG was responsible for specifying the following parameters of the analysed arrangements: diameters of the holes, distance among them and the location of the arrangement along the length of the antenna. All the analysed antennas were constructed manually, by using a milling machine and/or corrosion by iron perchloride. Based on the simulated and measured results, was verified that the proposed GA was able to optimize the studied structures in order to preserve the fundamental mode, while the higher ones were eliminated and/or considerably attenuated. It was verified that for the same type of arrangement, the antennas with DGS presented better performance in relation to those with PBG, considering the reflection coefficient of the fundamental mode. In addition, the optimized structures did not cause significant changes in the total gain value or in the shape of the radiation pattern and, in the case of the DGS, exhibited important characteristics for miniaturization of the antennas. The obtained results are particularly important, assuming that the optimized structures can be used to eliminate unwanted modes in applications with passive or active microstrip antennas, which also operates as resonators.

No presente trabalho propõe-se empregar algoritmos genéticos em associação com o design construtal para a otimização de geometrias em problemas de transferência de calor. O objetivo principal de todos os estudos deste trabalho é minimizar a máxima temperatura que ocorre no domínio computacional. Investigou-se, inicialmente, uma cavidade isotérmica em forma de Y inserida em um sólido retangular com geração de calor uniforme a uma taxa volumétrica constante, onde foi feita uma comparação e validação do algoritmo genético frente à busca exaustiva para poucos graus de liberdade. Após, foi feita uma otimização usando somente algoritmos genéticos considerando todos os quatro graus de liberdade do problema e diferentes valores para suas restrições geométricas. O estudo seguinte foi feito considerando a mesma geometria anteriormente discutida, porém considerou-se as paredes da cavidade Y com uma condição de contorno convectiva. Da mesma forma anterior, foi feita uma validação do algoritmo genético frente à busca exaustiva e na sequência uma otimização de todos os quatro graus de liberdade e diferentes valores do parâmetro convectivo a, empregando somente algoritmos genéticos. No terceiro caso, estudou-se um caminho assimétrico em forma de V de um material de alta condutividade. A geometria tem sua base recebendo um fluxo de calor constante e o remove através das extremidades de dois braços ligados a um sumidouro de calor. Otimizou-se a forma pelo método exaustivo considerando quatro graus de liberdade e uma restrição constante . Após, usou-se algoritmos genéticos para otimizar a geometria considerando os mesmos graus de liberdade e diferentes valores para a restrição de ocupação do material condutivo. Similarmente ao caso da cavidade convectiva em forma de Y, por fim, estudou-se a otimização geométrica de um corpo cilíndrico onde cavidades convectivas retangulares com dois pares de braços são inseridas. Realizaram-se otimizações de até sete graus de liberdade e também se estudou a influência de um parâmetro convectivo e das frações de ocupação das áreas do corpo e braços da cavidade. Deste estudo, concluiu-se que quanto maior o número de cavidades, menores são as máximas temperaturas que ocorrem no domínio. Destaca-se, também, a dependência do parâmetro convectivo, que influenciou na forma da melhor geometria encontrada. Para todos os estudos feitos, os resultados mostraram que a busca por meio de algoritmos genéticos levou a uma redução significativa do número de simulações necessárias para obter a geometria ótima com resultados concordantes aos obtidos com busca exaustiva. Além disso, foi possível estender o estudo para problemas com mais graus de liberdade, restrições e propriedades térmicas. Conclui-se que o melhor design é altamente dependente dos graus de liberdade e restrições, este sendo alcançado de acordo com o princípio construtal da ótima distribuição das imperfeições. / In this work, we propose employing genetic algorithms in association with constructal design for geometry optimization in heat transfer problems. The main objective of all studies is to minimize the maximum temperature that occurs in the computational domain. It was investigated initially an isothermal Y-shaped cavity intruded into a rectangular solid conducting wall with heat generation uniformly at a volumetric rate, where a comparison and validation of genetic algorithm against exhaustive search for few degrees of freedom was made. Then, an optimization is performed by means of genetic algorithms considering all four degrees of freedom of the problem and different values for geometric constraints. The following study has been done considering the same geometry as previously discussed, but it is considered the walls of the Y-cavity with a convective boundary condition. Thus, a dimensionless heat transfer parameter to study (a) was added. Similarly, foregoing study, a genetic algorithm validation was performed comparing to the exhaustive search. After, all four degrees of freedom and different values of a parameter only using genetic algorithms were optimized. In the next investigation, an asymmetric V-shaped pathway of high conductivity material was studied. This geometry receives a constant heat transfer rate in its base and removes it by the end of the two branches that are in touch with the heat sink. The shape was optimized by exhaustive approach considering four degree of freedom and a constraint. After, we used genetic algorithms to optimize the geometry considering the same degrees of freedom and different values for the restriction. Finally, similar to the case of the Y-shaped convective cavity, rectangular convective cavities with two pairs of arms inserted into a cylindrical solid body were optimized. Optimizations of up to seven degrees of freedom were performed and the influence of the convective parameter and of the area fractions of the body and arms of the cavity, were also investigated. From this study, it was concluded that the higher the number of cavities, the lower the maximum temperatures occurring in the domain. Also, the dependence of the convective parameter, influenced in the form of the best geometry, is highlighted. For all studies carried out, the results showed that the search using genetic algorithms led to a significant reduction of the number of simulations required to obtain the optimal geometry. Moreover, it was possible to extend the study where it was considered other degrees of freedom, constraints and thermal properties. We concluded that the best design is highly dependent of degrees of freedom and constraints, and this has been achieved according to the constructal principle of optimal distribution of imperfections.

O objetivo de projetos de reforma agrária é redistribuir terras de grandes latifúndios para terrenos menores, com destino à agricultura familiar. Um dos principais problemas do Instituto Nacional de Colonização e Reforma Agrária (INCRA) é subdividir uma parcela grande de terra em lotes menores que são balanceados com relação a certos atributos. Este problema é difícil por que precisa considerar diversas restrições legais e éticas. As soluções atuais são auxiliadas por computador, mas manuais, demoradas e suscetíveis a erros, tipicamente produzindo lotes retangulares de áreas similares mas que são injustos com relação a critérios como aptidão do solo ou acesso a recursos hidrográficos. Nesta dissertação, nós propomos um algoritmo genético para gerar subdivisões justas de forma automática. Nós apresentamos um algoritmo construtivo guloso randomizado baseado em locação-alocação para gerar soluções iniciais, assim como operadores de mutação e recombinação que consideram especificidades do problema. Experimentos com 5 instâncias reais e 25 instâncias geradas artificialmente confirmam a efetividade dos diferentes componentes do método proposto, e mostram que ele gera soluções mais balanceadas que as atualmente usadas na prática. / The goal of agrarian reform projects is the redistribution of farmland from large latifundia to smaller, often family farmers. One of the main problems the Brazilian National Institute of Colonization and Agrarian Reform (INCRA) has to solve is to subdivide a large parcel of land into smaller lots that are balanced with respect to certain attributes. This problem is difficult since it considers several constraints originating from legislation as well as ethical considerations. Current solutions are computer-assisted, but manual, time-consuming and error-prone, leading to rectangular lots of similar areas which are unfair with respect to soil aptitude and access to hydric resources. In this thesis, we propose a genetic algorithm to produce fair land subdivisions automatically. We present a greedy randomized constructive heuristic based on location-allocation to generate initial solutions, as well as mutation and recombination operators that consider specifics of the problem. Experiments on 5 real-world and 25 artificial instances confirm the effectiveness of the different components of our method, and show that it leads to fairer solutions than those currently applied in practice.

Nesta dissertação, discute-se o problema de otimização de carteiras de investimento para estratégia passiva de Index Tracking. Os objetivos principais são (i) apresentar um modelo de otimização de Index Tracking e (ii) a solucionar esse modelo com uso do método heurístico de Algoritmos Genéticos (AG) para formação de carteiras com número reduzido de ativos. O índice de referência utilizado é o Ibovespa, para o período de Janeiro/2009 a Julho/2012, com um total de 890 observações diárias de preços. A partir de uma amostra de 67 ativos, são formadas carteiras sem limite de ativos e limitadas a 40, 30, 20, 10 e 05 ativos; os intervalos de rebalanceamento das carteiras são 20, 40 e 60 períodos (dias úteis), ou seja, rebalanceamento mensal, bimestral e trimestral. É verificado que, para essa amostra, não é possível formar carteiras de 20 ou menos ativos via otimização direta com o solver Cplex com menos de 1 hora de processamento e gap abaixo de 5%. Com uso da heurística de Algoritmos Genéticos, são formadas carteiras de 10 e 05 ativos com tempo de processamento em torno de 5 minutos; nesse caso, o gap médio fica abaixo de 10% para ambos os tipos de carteira. E, com tempo de processamento do AG um pouco maior, em torno de 8 minutos, o algoritmo fornece soluções para carteiras de 10 e 05 ativos com gap médio abaixo de 5%. / In this master’s thesis it is discussed the portfolio optimization problem using the passive investment strategy of Index Tracking. The main goals are (i) to present an optimization model for the Index Tracking problem and (ii) to solve this model using the heuristic approach of Genetic Algorithms (GA) to create portfolios with reduced amount of stocks. The benchmark used is the Ibovespa Index (main reference for the Brazilian Stock Market), during the period from January/2009 to July/2012 (using a total of 890 daily stock prices). The sample contains 67 assets, and the model is used to build portfolios without limit in the amount of assets and portfolios limited to 40, 30, 20, 10 and 05 assets; the ranges of time to rebalance the portfolios are 20, 40, and 60 trading days, which means to rebalance monthly, bimonthly and quarterly. The results show that, considering this sample, it is not possible to build portfolios with 20 stocks (or less than 20) through direct optimization using the solver Cplex with computational processing time less than 1 hour and results with gap below 5%. On the other hand, using the Genetic Algorithms heuristic approach, portfolios limited to 10 and 05 stocks are built with computational time close to 5 minutes; for both types of portfolio, the solutions provided by the GA have average gap below 10%. Also, with a computational time slightly bigger, close to 8 minutes, the algorithm provides solutions with average gap below 5% for portfolios limited to 10 and 05 stocks.

A experimentação e testes com o uso de protótipos físicos ou simulação em computadores é uma prática utilizada para o desenvolvimento de diversos produtos industriais. As indústrias aeronáutica, automobilística, mecânica, naval, petrolífera e microeletrônica, entre outras, há muito empregam uma ou ambas as técnicas citadas. No entanto, inexistem referências ou estudos sobre a aplicação prática e conceitual desse assunto dentro do ambiente bancário mundial. O propósito desta pesquisa é descrever e interpretar os modos de experimentação empregados atualmente para a formação de fundos de investimento no mercado financeiro brasileiro e propor novos procedimentos para o seu desenvolvimento em analogia ao processo industrial. A metodologia proposta foi demonstrada com a utilização de dados reais levantados durante quatro anos no mercado financeiro para o desenvolvimento de um fundo aberto referenciado DI fictício simulados com o auxílio de técnicas de Dinâmica de Sistemas e de Inteligência Artificial. Os resultados reforçam as possibilidades de analogia entre o desenvolvimento de produtos industriais tangíveis e serviços intangíveis, quebrando paradigmas e propondo novos conceitos sob uma ótica renovadora para o desenvolvimento de produtos financeiros. O problema de otimização apresentado representa um novo campo de aplicação para o uso integrado de Dinâmica de Sistemas com algoritmos inteligentes, sendo que os algoritmos genéticos provaram ser uma ferramenta de suporte à decisão adequada para um ambiente competitivo e globalizado. / Experimentation and tests using physical prototypes or computer simulation are practices used in the development of various industrial products. The aeronautical, automobile, mechanical, naval, petroleum and micro-electronics industries have been using one or both of the mentioned techniques for a very long time. However, this issue has not been studied in detail in the banking area. The aim of this research is to describe and interpret the experimentation modes currently used in the Brazilian financial market in order to propose new procedures to develop investment funds akin to the industrial process. The proposed methodology was tested using 4 years of real data of the Brazilian financial market in order to develop a fictional investment fund based on Dynamic Systems and Artificial Intelligence (genetic algorithms) simulation principles. The results strengthen the possible analogy between the development of tangible industrial products and intangible services and propose new concepts according to an innovative development methodology for financial products. The related optimization problem represents a new field of application for Dynamic Systems combined with intelligent algorithms and, particularly, the Genetic Algorithms (GA) based model provided an efficient decision-making tool to be used in a competitive and globalized environment.

Submitted by Isaac Francisco de Souza Dias (isaac.souzadias@ufpe.br) on 2016-03-30T17:14:18Z No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) ANTONIO.pdf: 1896299 bytes, checksum: 6648d14ae9c1893123a82366b851c19a (MD5) / Made available in DSpace on 2016-03-30T17:14:18Z (GMT). No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) ANTONIO.pdf: 1896299 bytes, checksum: 6648d14ae9c1893123a82366b851c19a (MD5) Previous issue date: 2015-02-27 / CAPES / Alinhamento Múltiplo de sequências (MSA) é uma das tarefas mais importantes em bioinformática. A MSA é uma técnica fundamental para o estudo da função, estrutura e evolução de biomoléculas. A partir do uso de métodos de MSA é possível a criação de modelos estatísticos para a classificação de famílias de proteína , análise filogenética e a previsão de estruturas secundárias de proteínas. Como trata-se de um problema do tipo NP-difícil, torna-se inviável o uso de métodos exatos para a busca da melhor solução. Por isso, é importante o uso de métodos de optimização baseado em heurística para resolver o problema de MSA. Nesta dissertação, propomos uma abordagem para alinhamento múltiplo de sequências por meio da otimização de uma função objetivo utilizando Evolução Diferencial. Embora a ideia de usar algoritmos evolutivos não seja nova, a abordagem apresentada difere pelo uso da Evolução Diferencial e pela definição do alinhamento como uma dispersão de lacunas ao longo das sequências, sem levar em consideração fenômenos biológicos, como os de inserção ou surgimento de bases, deleção ou mutação de bases. A solução proposta tem provado ser capaz de fazer melhorias significativas em alinhamentos quando comparadas com o método do estado da arte Clustal. / Multiple sequence alignment (MSA) is one of the most important tasks in bioinformatics. The MSA is a fundamental technique to the study of function, structure and evolution of biomolecules. By using of MSA methods it’s possible to create statistical models for classification of protein families, phylogenetic analysis and the prediction of secondary structures of proteins. Being a NPhard problem, it is infeasible due to its completely, the use of exact methods to search for optimal solutions. Because of this it is important to use heuristic-based optimization methods to solve the MSA problem. In this dissertation, we propose an approach to multiple sequence alignment by optimizing an objective function using Differential Evolution. Although the idea of using Evolutionary Algorithms is not new, the approach presented differs from the use of Differential Evolution and definition of alignment as a dispersion of gaps along the sequences, without considering biological events such as insertion or emergence of bases, deletion or mutation of bases. The proposed solution has proven to be able to make significant improvements in alignments when compared to the state-of-the art Clustal method.

Submitted by Rafael Santana (rafael.silvasantana@ufpe.br) on 2018-02-20T18:02:59Z No. of bitstreams: 2 license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5) Dissertacao TIAGO FRANCA BARRETO versao final revisada com ficha.pdf: 1881406 bytes, checksum: 12e01eebda9019e211cef41ad935a421 (MD5) / Made available in DSpace on 2018-02-20T18:02:59Z (GMT). No. of bitstreams: 2 license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5) Dissertacao TIAGO FRANCA BARRETO versao final revisada com ficha.pdf: 1881406 bytes, checksum: 12e01eebda9019e211cef41ad935a421 (MD5) Previous issue date: 2017-02-16 / CNPQ / Campos de produção de petróleo terrestres são compostos por um conjunto de poços de petróleo que, depois de certo tempo em operação, podem apresentar algum tipo de mau funcionamento e ter a produção interrompida. Quando isso ocorre, veículos especialmente equipados, também chamados sondas de manutenção, são utilizados para prestação de serviço nos poços e garantir que suas atividades sejam reestabelecidas. Dado um número limitado de sondas de manutenção e a grande quantidade de poços existentes no campo de petróleo, o problema das sondas de manutenção consiste em encontrar o melhor escalonamento para as mesmas de modo que a perda de produção total dos poços seja minimizada. O escalonamento dos poços considera alguns fatores como a taxa de perda de produção por poço, o nível de atendimento requerido e o horizonte de planejamento para o qual o escalonamento será executado. Este trabalho apresenta um algoritmo genético híbrido para a resolução do problema de sondas de manutenção com múltiplos objetivos, frota heterogênea e horizonte de planejamento finito. O algoritmo genético híbrido incorpora uma heurística de descida em vizinhança variável como método de busca local para aumentar a velocidade de convergência do conjunto de soluções. São considerados os objetivos de minimização da perda de produção e custo com frota associado ao aluguel das sondas de manutenção. A frota é mantida variável, portanto um depósito de sondas é incluído em uma posição estratégica no campo de produção de petróleo para garantir que as novas sondas de manutenção, além das já espalhadas no campo, possam ser incluídas no escalonamento quando requeridas. O algoritmo genético foi testado em um conjunto de instâncias com até 200 poços, 10 sondas de manutenção e horizonte de planejamento igual a 300. Os resultados demonstram um alto conflito entre os objetivos de minimização da perda de produção e o custo da frota para o problema das sondas de manutenção, além de importantes aspectos relacionados às soluções obtidas pelo algoritmo proposto aplicado ao problema. / Onshore oil fields are composed by a set of geographically distributed wells that, after some time of operation, might present some malfunction and have their production interrupted. When the oil production of some wells is interrupted, specially-equipped vehicles, also called workover rigs, are deployed to service the wells and guarantee that their activity is restored. Given the limited number of workover rigs and the large number of wells around the oil field, the workover rig problem consists in finding the best scheduling for the workover rigs so the total production loss of wells is minimized. The scheduling considers some factors such as the production loss rate of each well, the service level required and the planning time horizon in which the scheduling must be executed. This research presents a hybrid genetic algorithm to solve the multi-objective workover rig problem with a heterogeneous fleet and a finite time horizon. The hybrid genetic algorithm incorporates a variable neighborhood descent heuristic as a local search procedure to increase the convergence speed of the set of solutions. Both objectives of minimization of the production loss and fleet cost associated to the rent of workover rigs are taken in consideration. The fleet is held variable, so a workover rig depot is included at a strategic position on the oil field in order to guarantee that new workover rigs, besides the already existent ones on the oil field, might be included in the scheduling when required. The genetic algorithm was tested on a set of practical-sized instances up to 200 wells, 10 workover rigs and 300 period horizon. Results show a high conflict between the objectives of minimizing the production loss and fleet cost for the workover rig problem, besides important aspects of the solutions obtained by the proposed algorithm to solve the problem.

Submitted by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2017-02-01T18:20:32Z No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertação - Ivaneide Alves Protásio.pdf: 1710443 bytes, checksum: 890976db270d6fb66cc3f04a13cabf51 (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2017-02-01T18:20:47Z (GMT) No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertação - Ivaneide Alves Protásio.pdf: 1710443 bytes, checksum: 890976db270d6fb66cc3f04a13cabf51 (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2017-02-01T18:21:08Z (GMT) No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertação - Ivaneide Alves Protásio.pdf: 1710443 bytes, checksum: 890976db270d6fb66cc3f04a13cabf51 (MD5) / Made available in DSpace on 2017-02-01T18:21:08Z (GMT). No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertação - Ivaneide Alves Protásio.pdf: 1710443 bytes, checksum: 890976db270d6fb66cc3f04a13cabf51 (MD5) Previous issue date: 2014-03-21 / FAPEAM - Fundação de Amparo à Pesquisa do Estado do Amazonas / Several real-world problems can be modeled as combinatorial optimization problems. This is are usually complex and large scale problems can not be solved by exact methods , since they would require impractical computational time . Thus, meta-heuristics have been widely used for solving such problems. Two of the major difficulties of these methods are to escape from sub-optimal regions and to avoid premature convergence of the algorithm . To try to solving this problem , we use o hybrid techniques in order to develop strategies that are applicable to many optimization algorithms . This study investigates the efficiency of incorporating of data mining techniques to ant colony and genetic algorithm Population Metaheuristcs in order to guide them to generate new and better solutions. To validate the proposal, we use the Travelling Salesman Problem and the Problem Sets Cover and different versions of the hybrid meta-heuristics are tested and analyzed . The technique chosen to guide the search of new solutions , from the patterns obtained with the Data Mining , was grouping similar solutions in an attempt to reduce the search space in combinatorial optimization problems . The mining algorithms used are the K -means and Ward which use techniques of hierarchical and partitioning respectively. Computational experiments were performed in order to evaluate the use of MD in Meta-Population traditional heuristics . These experiments showed that the use of mined patterns can assist in obtaining good solutions . / Vários problemas do mundo real podem ser modelados como problemas de otimização combinatória. Em geral são problemas complexos e de larga escala, não podendo ser resolvidos por métodos exatos, pois os mesmos necessitariam de tempo computacional impraticável. Desse modo, as meta-heurísticas têm sido amplamente empregadas para a resolução de tais problemas. Duas das principais dificuldades destes métodos são escapar das regiões sub-ótimas e evitar a convergência prematura do algoritmo. Para tentar solucionar estes problema, propõe-se o uso de técnicas híbridas buscando desenvolver estratégias que sejam aplicáveis a diversos algoritmos de otimização. O presente trabalho investiga a eficiência da incorporação de técnicas de Mineração de Dados (MD) as Meta-heurísticas Populacionais Colônia de Formiga e Algoritmo Genético com o intuito de guiá-las a gerar novas e melhores soluções. Para a validação da proposta, serão utilizados o Problema do Caixeiro Viajante e diferentes versões das meta-heurísticas híbridas serão testadas e analisadas. A técnica escolhida para guiar a obtenção de novas soluções, a partir dos padrões obtidos com a Mineração de Dados, foi o de Agrupamento de soluções similares, na tentativa de reduzir o espaço de busca em problemas de otimização combinatória. O algoritmos de mineração utilizados são o K-Means e o Ward que utilizam técnicas de particionamento e hierárquico respectivamente. Experimentos Computacionais foram realizados com o objetivo de avaliar o uso de MD em Meta-heurísticas Populacionais tradicionais, atai como Algoritmo Genético e Colonia de Formiga. Estes experimentos mostraram que a utilização de padrões minerados podem auxiliar na obtenção de boas soluções em relação as técnicas tradicionais