Geradores de referência, ou fontes de tensão de referência, são largamente empregados na composição de diversos circuitos eletrônicos, pois são responsáveis por gerar e manter uma tensão constante para o restante do circuito. Como se trata de um circuito analógico e que possui diversas condições a serem atendidas (baixo coeficiente de temperatura, baixa tensão de alimentação, baixa regulação de linha, dentre outras), sua complexidade é alta e isso se reflete no tempo/dificuldade de um projeto. Com a finalidade de aumentar a qualidade do circuito e diminuir o tempo de projeto, foi estudado o projeto de fontes de tensão de referência através da aplicação de metaheurísticas, que são métodos de otimização utilizados em problemas que não possuem solução analítica. As metaheurísticas aplicadas foram: algoritmos genéticos, simulated annealing e pattern search, todos disponíveis em uma toolbox de otimização do Matlab. A fonte projetada, utilizando uma topologia proposta neste trabalho, fornece uma tensão de referência de 0,302 V em 300 K a uma tensão mínima de operação de 1,01 V. O coeficiente de temperatura, no intervalo de -10°C a 90°C, é de 19 ppm/°C a 1,01 V e a regulação de linha, com tensão de alimentação no intervalo de 1,01 V a 2,5 V, é de 81 ppm/V a 300 K. O consumo de potência é de 4,2 \'mü\'W, também em 300 K e a 1,01 V e a área é de 0,061 \'MM POT.2\'. Como resultado, mostrou-se a eficiência da utilização destes métodos no dimensionamento de elementos do circuito escolhido e foi obtida uma fonte de tensão de referência que atende aos critérios estabelecidos e é superior quanto ao critério de regulação de linha, quando comparada a outras fontes da literatura. Neste trabalho, foi utilizada a tecnologia CMOS de 0,35 \'mü\'m da Austria Micro Systems (AMS). / Voltage references are widely employed to compose electronic circuits, since they are responsible for generating and maintaining a constant voltage to the rest of the circuit. As it is an analog circuit and it has several conditions to fulfill (low temperature coefficient, low supply voltage, low line regulation, among others), its complexity is high, which reflects at the time/difficulties of a design. In order to increase the quality of the circuit and to minimize the design time, it was studied voltage references design using metaheuristics, which are optimization methods used in problems with no analytical solution. The applied metaheuristics were: genetic algorithms, simulated annealing and pattern search, they are all available in an optimization toolbox at Matlab. The designed voltage reference, applying a topology proposed in this work, provides a reference voltage of 0.302 V at 300 K at a minimum supply voltage of 1.01 V. The temperature coefficient, from -10°C to 90°C, is 19 ppm/°C at 1.01 V and the line regulation, using a supply voltage from 1.01 V to 2.5 V, is 81 ppm/V at 300 K. The power consumption is 4.2 W also at 300 K and 1.01 V and the area is 0.061 \'MM POT.2\'. As a result, it was shown that those methods are efficient in sizing the devices of the chosen topology and it was obtained a voltage reference that fulfills all established criteria and that is superior at the line regulation criterion, when compared to other voltage reference of the literature. In this work, the 0.35-\'mü\'m CMOS technology provided by Austria Micro Systems (AMS) was used.

O presente documento tem por objetivo apresentar o desenvolvimento de uma ferramenta computacional para auxiliar profissionais da área de otimização na implementação de métodos e resolução de problemas. O projeto foi desenvolvido como tema de dissertação no Programa de Mestrado em Ciência da Computação e Matemática Computacional do ICMC/USP. A ferramenta pode ser enquadrada como um ambiente de desenvolvimento (framework) e será chamada de ProOF - Professional Optimization Framework. O ProOF tem como foco principal nortear a implementação computacional de métodos variados para problemas de otimização, utilizando como paradigma a programação orientada a objetos. Esse framework incorpora as principais características encontradas por outras ferramentas propostas na literatura. Além disso, procura facilitar a implementação de métodos e resolução de problemas ao permitir alto reuso de códigos, dar suporte a geração de códigos em diferentes linguagens de programação e gerar uma Graphical User Interface (GUI) automática para parametrização dos métodos inseridos pelo usuário. Alguns trabalhos publicados recentemente utilizaram versões em desenvolvimento do ProOF e serão citados como estudo de caso para atestar a robustez do framework proposto. Por fim, uma comparação será realizada entre o ProOF e outros frameworks existentes na literatura / This paper aims to present the development of a computational tool to assist professionals in the optimization field in implementation of methods and problem solving. The project was developed as dissertation topic in the Masters Program in Computer Science and Computational Mathematics at ICMC/USP. The tool can be considered as a development environment (framework) and will be called ProOF - Professional Optimization Framework. The ProOF is mainly focused on guiding the implementation of various computational methods for optimization problems using as a paradigm the object-oriented programming. This framework incorporating the principal features found in other tools proposed in the literature. Moreover, seeks to facilitate the implementation of methods and problem resolution by allowing high code reuse, give support to code generation in different programming languages and generate a Graphical User Interface (GUI) automatic for parameter setting of methods implemented by the user. Some recently published studies have used previous versions of the ProOF and they will be cited as a case study to attest the robustness of the proposed framework. Finally, a comparison will be made between the ProOF and other existing frameworks in the literature

Made available in DSpace on 2015-03-05T14:01:20Z (GMT). No. of bitstreams: 0 Previous issue date: 23 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Este trabalho aborda o problema da otimização relacionado ao ciclo de operação de uma insersora automática de componentes (pick-and-place) em máquinas do tipo multi-head. O objetivo consiste em desenvolver uma técnica computacional capaz de encontrar uma boa solução para o problema de otimização, associado ao processo de inserção de componentes. A otimização consiste em resolver de forma conjunta, os Problemas de Escalonamento das Ferramentas, de Escalonamento da Seqüência de Inserção de Componentes e por fim, o Problema da Alocação dos Componentes no Alimentador, visando a redução do tempo total de operação. Como resultados, a técnica computacional permite elevar a produtividade das máquinas onde a mesma é aplicada. Neste trabalho, foi desenvolvida uma aplicação híbrida das metaheurísticas Busca Tabu e Algoritmos Genéticos. Através do uso de uma abordagem diferenciada e utilizando metaheurísticas contemporâneas, bons resultados são apresentados ao longo do trabalho. / This work approaches the optimization Problem related to the operation cycle in an automatic multi-head SMT placement machine (pick-and-place). The objective of this work is developing a computational technique capable to find a good solution for the optimization problem associated with the component insertion process. The optimization process was planned to solve in a joint way the Tools Scheduling Problem, Schedule of Component Insertion Sequence Problem and finally the Component Feeder Allocation Problem. The main objective is to reduce the total operation time. As a result the computational technique can increase the productivity of the machines where it is applied. This study developed a hybrid application of Tabu Search and Genetic Algorithms. The use of a differentiated approach combined with modern metaheuristics, good results are presented in the work.

Orientador: Helenice de Oliveira Florentino Silva / Resumo: A escassez de combustíveis fósseis e a demanda por fontes alternativas de energia renovável e limpa são impulsionadores para o desenvolvimento de biocombustíveis, tais como o biohidrogênio. Este gás é conhecido por seu alto valor calorífico, extrema leveza e baixa densidade, além de, ao ser queimado, produzir apenas vapor d'água e calor. Dentre os modos de produção, destaca-se a fermentação escura, a qual gera biohidrogênio e subprodutos através do tratamento microbiológico de resíduos agroindustriais. O objetivo deste trabalho foi modelar matematicamente este bioprocesso, estudar suas propriedades à luz da teoria de estabilidade, além de propor um modelo de otimização que determine uma combinação das concentrações de substrato e bactérias, tais que maximizem o rendimento da produção de biohidrogênio. Foram propostas duas heurísticas para a resolução do modelo, Algoritmo de Busca em Vizinhança Variável e Algoritmo Memético. Os resultados das simulações numéricas mostraram que o modelo obtido corrobora com a dinâmica bioquímica e microbiológica do bioprocesso. / Abstract: The lack of fossil fuels and the demand of alternative, renewable and clean energy sources promote development in biofuels, as biohydrogen. It is known by its high heat, extreme lightness and low density and also when it burns, the products are only steam and energy. Among the productions ways, we highlight dark fermentation, which generates biohydrogen and subproducts through organic waste microbiological treatment. The aim of this work was to mathematical model this bioprocess, to study its properties via stability analysis, besides to propose a optmization model to determine a combination of substract and bacteria concentrations, in order to maximize biohydrogen production yield. To solve the mathematical model have been proposed two heuristics: Variable Neighboor Search Algorithm and Memetic Algorithm. Numeric simulations showed that the mathematical model corroborates with the bioprocess microbial and biochemical dynamics. / Mestre

Submitted by Fabricia Fialho Reginato (fabriciar) on 2015-08-26T00:27:58Z No. of bitstreams: 1 CarlosWEISSHEIMER.pdf: 1780174 bytes, checksum: 5713fcfb8f07d336d4ef9416f67e4735 (MD5) / Made available in DSpace on 2015-08-26T00:27:58Z (GMT). No. of bitstreams: 1 CarlosWEISSHEIMER.pdf: 1780174 bytes, checksum: 5713fcfb8f07d336d4ef9416f67e4735 (MD5) Previous issue date: 2012 / FINEP - Financiadora de Estudos e Projetos / A tecnologia Internet Protocol Television (IPTV) é um fator impactante na sociedade. Ela tem sido explorada por diferentes meios de transmissão para a entrega de conteúdo multimídia sobre serviço baseado em Internet Protocol (IP). Atualmente, o IPTV é alvo de várias pesquisas, pois pode trazer muitos benefícios para a sociedade, tais como o suporte à interatividade e o aumento da interoperabilidade com redes domésticas. Este trabalho apresenta o desenvolvimento e a implementação de um modelo computacional, baseado na aplicação de metaheurísticas, sobre uma plataforma IPTV, com o objetivo de desenvolver um algoritmo híbrido utilizando as metaheurísticas Busca Tabu (BT) e Algoritmo Genético (AG). Esse algoritmo permite que seja feita a análise e o estudo dos seguinte parâmetros: taxa de transmissão, qualidade de áudio, número de clientes e largura de banda, visando encontrar a melhor configuração dos mesmos para a transmissão IPTV dadas às características do cliente. Após a validação do algoritmo, foram realizados experimentos que auxiliaram a compreensão da dinâmica do sistema e viabilizaram encontrar uma boa solução, passível de simulação no simulador de rede Network Simulator 3 (NS3). / The Internet Protocol Television Technology (IPTV) is an impacting factor on society. It has been exploited by different means of transmission to the delivery of multimedia content over service based on Internet Protocol (IP). Currently, IPTV is the subject of several studies, since it can bring many benefits to society, such as interactivity support and increased interoperability with home networks. This paper presents the development and implementation of a computational model based on the application of metaheuristics on an IPTV platform in order to develop a hybrid algorithm using the metaheuristics Tabu Search (TS) and Genetic Algorithm (GA). This algorithm makes it possible to analysis and study of the following parameters: baud rate, audio quality, number of customers and network bandwidth in order to find the best setting for the IPTV transmission given the client characteristics. After validating the algorithm, experiments are performed to help understand the dynamics of the system and enable a good solution that can be simulated in the Network Simulator 3 (NS3).

Algoritmos meméticos são meta-heurísticas evolutivas voltadas intrinsecamente à exploração e incorporação de conhecimentos relacionados ao problema em estudo. Nesta dissertação, foi proposto um algoritmo memético multi populacional baseado em conhecimento para lidar com o problema de predição de estruturas tridimensionais de proteínas voltado à modelagem de estruturas livres de similaridades conformacionais com estruturas de proteínas determinadas experimentalmente. O algoritmo em questão, foi estruturado em duas etapas principais de processamento: (i) amostragem e inicialização de soluções; e (ii) otimização dos modelos estruturais provenientes da etapa anterior. A etapa I objetiva a geração e classificação de diversas soluções, a partir da estratégia Lista de Probabilidades Angulares, buscando a definição de diferentes grupos estruturais e a criação de melhores estruturas a serem incorporadas à meta-heurística como soluções iniciais das multi populações. A segunda etapa consiste no processo de otimização das estruturas oriundas da etapa I, realizado por meio da aplicação do algoritmo memético de otimização, o qual é fundamentado na organização da população de indivíduos em uma estrutura em árvore, onde cada nodo pode ser interpretado como uma subpopulação independente, que ao longo do processo interage com outros nodos por meio de operações de busca global voltadas a características do problema, visando o compartilhamento de informações, a diversificação da população de indivíduos, e a exploração mais eficaz do espaço de busca multimodal do problema O algoritmo engloba ainda uma implementação do algoritmo colônia artificial de abelhas, com o propósito de ser utilizado como uma técnica de busca local a ser aplicada em cada nodo da árvore. O algoritmo proposto foi testado em um conjunto de 24 sequências de aminoácidos, assim como comparado a dois métodos de referência na área de predição de estruturas tridimensionais de proteínas, Rosetta e QUARK. Os resultados obtidos mostraram a capacidade do método em predizer estruturas tridimensionais de proteínas com conformações similares a estruturas determinadas experimentalmente, em termos das métricas de avaliação estrutural Root-Mean-Square Deviation e Global Distance Total Score Test. Verificou-se que o algoritmo desenvolvido também foi capaz de atingir resultados comparáveis ao Rosetta e ao QUARK, sendo que em alguns casos, os superou. Corroborando assim, a eficácia do método. / Memetic algorithms are evolutionary metaheuristics intrinsically concerned with the exploiting and incorporation of all available knowledge about the problem under study. In this dissertation, we present a knowledge-based memetic algorithm to tackle the threedimensional protein structure prediction problem without the explicit use of template experimentally determined structures. The algorithm was divided into two main steps of processing: (i) sampling and initialization of the algorithm solutions; and (ii) optimization of the structural models from the previous stage. The first step aims to generate and classify several structural models for a determined target protein, by the use of the strategy Angle Probability List, aiming the definition of different structural groups and the creation of better structures to initialize the initial individuals of the memetic algorithm. The Angle Probability List takes advantage of structural knowledge stored in the Protein Data Bank in order to reduce the complexity of the conformational search space. The second step of the method consists in the optimization process of the structures generated in the first stage, through the applying of the proposed memetic algorithm, which uses a tree-structured population, where each node can be seen as an independent subpopulation that interacts with others, over global search operations, aiming at information sharing, population diversity, and better exploration of the multimodal search space of the problem The method also encompasses ad-hoc global search operators, whose objective is to increase the exploration capacity of the method turning to the characteristics of the protein structure prediction problem, combined with the Artificial Bee Colony algorithm to be used as a local search technique applied to each node of the tree. The proposed algorithm was tested on a set of 24 amino acid sequences, as well as compared with two reference methods in the protein structure prediction area, Rosetta and QUARK. The results show the ability of the method to predict three-dimensional protein structures with similar foldings to the experimentally determined protein structures, regarding the structural metrics Root-Mean-Square Deviation and Global Distance Total Score Test. We also show that our method was able to reach comparable results to Rosetta and QUARK, and in some cases, it outperformed them, corroborating the effectiveness of our proposal.

Les Problèmes d’Optimisation Combinatoire (COP) sont largement utilisés pour modéliser et résoudre un grand nombre de problèmes industriels. La résolution de ces problèmes pose un véritable défi en raison de leur inhérente difficulté, la plupart étant NP-difficiles. En effet, les COP sont difficiles à résoudre par des méthodes exactes car la taille de l’espace de recherche à explorer croît de manière exponentielle par rapport à la taille du problème. Les méta-heuristiques sont souvent les méthodes les plus efficaces pour résoudre les problèmes les plus difficiles. Malheureusement, bien des problèmes réels restent hors de portée des meilleures méta-heuristiques. Le parallélisme permet d’améliorer les performances des méta-heuristiques. L’idée de base est d’avoir plusieurs instances d’une méta-heuristique explorant de manière simultanée l’espace de recherche pour accélérer la recherche de solution. Les meilleures techniques font communiquer ces instances pour augmenter la probabilité de trouver une solution. Cependant, la conception d’une méthode parallèle coopérative n’est pas une tâche aisée, et beaucoup de choix cruciaux concernant la communication doivent être résolus. Malheureusement, nous savons qu’il n’existe pas d’unique configuration permettant de résoudre efficacement tous les problèmes. Ceci explique que l’on trouve aujourd’hui des systèmes coopératifs efficaces mais conçus pour un problème spécifique ou bien des systèmes plus génériques mais dont les performances sont en général limitées. Dans cette thèse nous proposons un cadre général pour les méta-heuristiques parallèles coopératives (CPMH). Ce cadre prévoit plusieurs paramètres permettant de contrôler la coopération. CPMH organise les instances de méta-heuristiques en équipes ; chaque équipe vise à intensifier la recherche dans une région particulière de l’espace de recherche. Cela se fait grâce à des communications intra-équipes. Des communications inter-équipes permettent quant a` elles d’assurer la diversification de la recherche. CPMH offre à l’utilisateur la possibilité d’ajuster le compromis entre intensification et diversification. De plus, ce cadre supporte différentes méta-heuristiques et permet aussi l’hybridation de méta-heuristiques. Nous proposons également X10CPMH, une implémentation de CPMH, écrite en langage parallèle X10. Pour valider notre approche, nous abordons deux COP du monde industriel : des variantes difficiles du Problème de Stable Matching (SMP) et le Problème d’Affectation Quadratique (QAP). Nous proposons plusieurs méta-heuristiques originales en version séquentielle et parallèle, y compris un nouvelle méthode basée sur l’optimisation extrémale ainsi qu’un nouvel algorithme hybride en parallèle coopératif pour QAP. Ces algorithmes sont implémentés grâce à X10CPMH. L’évaluation expérimentale montre que les versions avec parallélisme coopératif offrent un très bon passage à l’échelle tout en fournissant des solutions de haute qualité. Sur les variantes difficiles de SMP, notre méthode coopérative offre des facteurs d’accélération super-linéaires. En ce qui concerne QAP, notre méthode hybride en parallèle coopératif fonctionne très bien sur les cas les plus difficiles et permet d’améliorer les meilleures solutions connues de plusieurs instances. / Combinatorial Optimization Problems (COP) are widely used to model and solve real-life problems in many different application domains. These problems represent a real challenge for the research community due to their inherent difficulty, as many of them are NP-hard. COPs are difficult to solve with exact methods due to the exponential growth of the problem’s search space with respect to the size of the problem. Metaheuristics are often the most efficient methods to make the hardest problems tractable. However, some hard and large real-life problems are still out of the scope of even the best metaheuristic algorithms. Parallelism is a straightforward way to improve metaheuristics performance. The basic idea is to perform concurrent explorations of the search space in order to speed up the search process. Currently, the most advanced techniques implement some communication mechanism to exchange information between metaheuristic instances in order to try and increase the probability to find a solution. However, designing an efficient cooperative parallel method is a very complex task, and many issues about communication must be solved. Furthermore, it is known that no unique cooperative configuration may efficiently tackle all problems. This is why there are currently efficient cooperative solutions dedicated to some specific problems or more general cooperative methods but with limited performances in practice. In this thesis we propose a general framework for Cooperative Parallel Metaheuristics (CPMH). This framework includes several parameters to control the cooperation. CPMH organizes the explorers into teams; each team aims at intensifying the search in a particular region of the search space and uses intra-team communication. In addition, inter-team communication is used to ensure search diversification. CPMH allows the user to tune the trade-off between intensification and diversification. However, our framework supports different metaheuristics and metaheuristics hybridization. We also provide X10CPMH, an implementation of our CPMH framework developed in the X10 parallel language. To assess the soundness of our approach we tackle two hard real-life COP: hard variants of the Stable Matching Problem (SMP) and the Quadratic Assignment Problem (QAP). For all problems we propose new sequential and parallel metaheuristics, including a new Extremal Optimization-based method and a new hybrid cooperative parallel algorithm for QAP. All algorithms are implemented thanks to X10CPMH. A complete experimental evaluation shows that the cooperative parallel versions of our methods scale very well, providing high-quality solutions within a limited timeout. On hard and large variants of SMP, our cooperative parallel method reaches super-linear speedups. Regarding QAP, the cooperative parallel hybrid algorithm performs very well on the hardest instances, and improves the best known solutions of several instances.

Submitted by Secretaria Pós de Produção (tpp@vm.uff.br) on 2017-07-27T19:12:43Z No. of bitstreams: 1 D2016 - Frederico Galaxe Paes.pdf: 5062594 bytes, checksum: 6141e589af7945cfd88fe0b9b3d62443 (MD5) / Made available in DSpace on 2017-07-27T19:12:43Z (GMT). No. of bitstreams: 1 D2016 - Frederico Galaxe Paes.pdf: 5062594 bytes, checksum: 6141e589af7945cfd88fe0b9b3d62443 (MD5) / Este trabalho aborda os seguintes problemas: Problema Quadrático de Alocação (PQA), Problema de Leiaute de Facilidades com Áreas Diferentes (PLFAD) e o Problema Job Shop Sem Espera (PJSSE). O PQA é um clássico problema de otimização combinatória, cujo objetivo é minimizar a soma das distâncias entre pares de locais distintos, ponderadas pelos fluxos entre as facilidades neles alocadas. O objetivo desta parte do trabalho é investigar técnicas heurísticas da literatura com base num conjunto de instâncias de referência do PQA. Os experimentos relatadosenvolveramAlgoritmosMeméticos(AM),técnicasdediversidadeadaptativa,algoritmos ILS (Iterated Local Search), busca locais 2-exchange e cadeia de ejeção (Ejection Chain). Doze algoritmos foram testados em 37 instâncias de referência obtidas da QAPLIB levando à escolha da combinação de técnicas mais adequada ao problema. A partir das observações obtidas do estudo anterior, decidiu-se abordar o PLFAD, de natureza semelhante ao PQA. No PLFAD, o objetivo é dimensionar e localizar facilidades retangulares em um espaço ilimitado e contínuo, sem sobreposição, de modo a minimizar a soma das distâncias entre facilidades ponderada pelos fluxos de manuseio de material. Porém, a pesquisa mostrou que devido a estrutura amarrada apresentada pelas soluções do PLFAD, métodos tradicionais de busca local tornam o problema caro computacionalmente, principalmente pelo tratamento da inviabilidade, devido a sobreposição. Duas abordagens algorítmicas são então introduzidas para tratar o problema: um Algoritmo Genético (GA) básico e um GA combinado com uma estratégia de decomposiçãoviadesconstruçãoereconstruçãoparcialdasolução. Paradecomporeficientemente o problema, uma estrutura especial é imposta às soluções impedindo que as facilidade cruzem os eixos X ou Y. Embora esta restrição possa deteriorar o valor da melhor solução encontrada, ela também aumenta muito a capacidade de busca do método em problemas de médio e grande porte. Comomostradopelosexperimentos,oalgoritmoresultanteproduzsoluçõesdealtaqualidadepara doisgruposdeinstânciasclássicasdaliteratura,melhorando6das8melhoressoluçõesconhecidas do primeiro grupo e todas as instâncias de médio e grande porte do segundo grupo. Para algumas das maiores instâncias do segundo grupo, com 90 ou 100 facilidades, a melhora média das soluções ficou em torno de6%ou7%quando comparado aos algoritmos anteriores, com menor tempo de CPU. Para tais instâncias, métodos exatos atuais são impraticáveis. Finalmente é apresentado o PJSSE, escolhido devido às suas soluções apresentarem uma natureza semelhante àquelas do PLFAD. Uma algoritmo baseado em GA, cuja construção da solução é efetuada por um algoritmo guloso eficiente, é proposto para resolver instâncias de referência da literatura obtendo resultados promissores e com menor tempo computacional comparado com abordagens anteriores, principalmente em instâncias de grande porte. / This work address the following problems: Quadratic Assignment Problem (QAP), Unequal Area Facility Layout Problem (UA-FLP), and the Job Shop Problem No-Wait (JSPNW). The QAP is a classic combinatorial optimization problem, which aims to minimize the sum of distances between pairs of different locations, weighted by flows between facilities allocated in them. The objective of this part of the work is to investigate heuristic techniques of the literature based on a benchmark datasets of the QAP. We perform experiments with Memetic Algorithms (MA), adaptive diversity techniques, Iterated Local Search (ILS) algorithms, local searches 2−exchange andEjectionChains. Twelvealgorithmshavebeentestedin37benchmarkdatasets obtained from QAPLIB thus enabling to identify a combination of more suitable techiques for the problem. Based on the observations of the previous study, we decided to address the UA-FLP, of similar nature to QAP. The UA-FLP, aims to dimension and locate rectangular facilities in an unlimited floor space, without overlap, while minimizing the sum of distances among facilities weighted by “material-handling"flows. However, the research has shown that due to the tight structure of good UA-FLP solutions, traditional methods of local search make the problem expensive computationally, mainly by infeasibility treatment due to overlap. We introduce two algorithmic approaches to address this problem: a simple Genetic Algorithm (GA), and a GA combined with a decomposition strategy via partial solution deconstructions and reconstructions. To efficiently decompose the problem, we impose a solution structure where no facility should cross the X or Y axis. Although this restriction can possibly deteriorate the value of the best achievable solution, it also greatly enhances the search capabilities of the method on medium and large problems. As highlighted by our experiments, the resulting algorithm produces solutions of high quality for the two classic datasets of the literature, improving 6 out of the 8 best known solutions from the first set and all medium- and large-scale instances from the second set. For some of the largest instances of the second set, with 90 or 100 facilities, the average solution improvement goes as high as 6% or 7% when compared to previous algorithms, in less CPU time. For such instances, current exact methods are impracticable. Finally is presented the PJSSE, chosen because of its solutions present a nature similar to those of PLFAD. An algorithm based on GA, where the construction of the solution is made by an greedy eficient algorithm, is proposed to solve benchmark instances of the literature. Promising results have been achieved in less CPU-time than previous approaches, especially for larger scale instances.

L'optimisation topologique est une méthode de conception qui permet de définir de manière autonome la topologie, les formes et les dimensions d'un dispositif en vue de répondre de manière optimale à des critères de design. Initialement réservée au dimensionnement de pièces mécaniques, elle s'oriente aujourd’hui vers la conception de dispositifs plus complexes comme ceux rencontrés dans le domaine de l'électromécanique. C'est dans ce cadre que se situe notre travail. Un outil d'optimisation topologique étant formé de l'association d'un algorithme d'optimisation et d'un formalisme de distribution de matière, nous avons dans une première étape comparé différents couplages d'algorithmes métaheuristiques et de formalismes de distribution de matière en vue de choisir le couple qui semble le mieux adapté au problème traité. Cette comparaison nous a conduits à choisir comme outil d'optimisation l'association d'un algorithme génétique et d'une distribution de matière par cellules de Voronoï. Nous avons ensuite examiné comment améliorer les capacités d'exploration et d'exploitation de cet outil. Nous avons, à cet effet, étudié les aspects liés à la gestion de la taille de la population et à l'adaptation des mécanismes de reproduction au caractère graphique du problème. A l'issue de cette deuxième étape, nous avons finalisé un outil d'optimisation que nous avons testé sur des cas d'étude dont la complexité se rapproche de celle rencontrée au niveau industriel. Nous avons ainsi montré le potentiel de notre outil d'optimisation au niveau de la conception dans le cadre de l'électromécanique. / Topology optimization is a method of conception which is able to define the topology, the form and the dimensions of a device with the aim of responding optimally to given design criteria. Initially reserved to the sizing of mechanics parts, this method is directed today towards the conception of more complexes devices as those encountered in applied electromagnetic. It is in this context that our work was performed. A topology optimization tool is made of the combination of an optimization algorithm and a material distribution formalism. In a first step, we compared different couplings of metaheuristic algorithms and material distribution formalisms. This comparison led us to choose as optimization tool for the problem under study, the combination of a genetic algorithm and a distribution of material by Voronoi cells. In a second step, we discussed how to improve the exploration and exploitation capabilities of this tool. We have, for this purpose, studied aspects related to the management of the size of the population and to the adaptation of the mechanisms of reproduction to the graphical nature of the problem. After this second step, we builded our optimization tool that we tested on study cases whose complexity is similar to that encountered at industrial showing its potential of to design electromechanical devices.

Submitted by Rosivalda Pereira (mrs.pereira@ufma.br) on 2017-07-25T17:21:34Z No. of bitstreams: 1 RaphaelSantos.pdf: 3718930 bytes, checksum: df335fd5562e8156000972c282fe9724 (MD5) / Made available in DSpace on 2017-07-25T17:21:34Z (GMT). No. of bitstreams: 1 RaphaelSantos.pdf: 3718930 bytes, checksum: df335fd5562e8156000972c282fe9724 (MD5) Previous issue date: 2016-08-17 / Autonomous exploration, in robotics, can be defined as the act of moving into an unknown environment, at priori, while building up a map of the environment. A great deal of literature describes several problems that are relate to the strategy exploration: perception, location, trajectory control and mapping. This work aims to present an autonomous exploration algorithm based on metaheuristics. Therefore, the problem of autonomous exploration of mobile robots is formulated as an optimization problem, providing data for metaheuristics that are able to search points in the space of solutions that represent positions on the map under construction that best meet the objectives of the exploration. Metaheuristics are approximate methods that guarantee sufficiently good solutions to optimization problems. The proposal was implemented and incorporated as an optimization module in a simultaneous location and mapping system that was run on the Robot Operating System environment and proved to be able to guide a simulated robot without human intervention. Two optimization metaheuristics were implemented to guide target to simulated robot: Genetic Algorithm and Firefly Algorithm. Both algorithms have achieved good results, however the second one was able to guide robot by best trajectories. / Exploração autônoma, em robótica, pode ser definida como o ato de mover-se em um ambiente, a princípio desconhecido, enquanto constrói-se um mapa deste ambiente. Uma grande parte da literatura relata vários problemas que se relacionam com a estratégia de exploração: percepção, localização, trajetória, controle e mapeamento. Este trabalho visa apresentar um algoritmo de exploração autonoma baseado em metaheurísticas. Para tanto, o problema de exploração autônoma de robôs móveis é formulado como um problema de otimização, fornecendo dados para que metaheurísticas sejam capazes de buscar pontos no espaço de soluções que representam posições no mapa em construção que melhor satisfaçam os objetivos da exploração. Metaheuristicas são metodos aproximados que garantem soluções suficientemente boas para problemas de otimização. A proposta foi implementada e incorporada como um módulo de otimização em um sistema de localização e mapeamento simultâneos que foi executado em ambiente Robot Operating System e mostrou-se capaz de guiar um robô simulado sem intervenção humana. As metaheurísticas usadas foram o Algoritmo Genético e o Algoritmo de Vagalumes. Ambos os algoritmos obtiveram bons resultados, no entanto o Algoritmo de Vagalumes guiou o robô por trajetórias melhores.