Estágio orientado na empresa, pelo Eng. Nuno Filipe Correia de Melo Ferreira de Almeida / Tese de mestrado integrado. Engenharia Industrial e Gestão. Faculdade de Engenharia. Universidade do Porto. 2012

Submitted by EDUARDO BATISTA DE MORAES BARBOSA null (ebmb@yahoo.com) on 2016-07-22T20:43:38Z No. of bitstreams: 1 Thesis-Full.pdf: 4249671 bytes, checksum: 293e98d71cda47dab135797fedb06e6f (MD5) / Approved for entry into archive by Ana Paula Grisoto (grisotoana@reitoria.unesp.br) on 2016-07-25T17:18:40Z (GMT) No. of bitstreams: 1 barbosa_ebm_dr_guara.pdf: 4249671 bytes, checksum: 293e98d71cda47dab135797fedb06e6f (MD5) / Made available in DSpace on 2016-07-25T17:18:40Z (GMT). No. of bitstreams: 1 barbosa_ebm_dr_guara.pdf: 4249671 bytes, checksum: 293e98d71cda47dab135797fedb06e6f (MD5) Previous issue date: 2016-07-01 / A configuração de parâmetros de algoritmos, em especial, das meta-heurísticas, nem sempre é trivial e, frequentemente, é realizada ad hoc de acordo com o problema sob análise. A fim de resolver o problema de sintonização de meta-heurísticas, a presente pesquisa propõe uma metodologia que combina o uso de técnicas estatísticas robustas (ex.: Planejamento de Experimentos) e métodos eficientes de Inteligência Artificial (ex.: Algoritmos de Corrida). A ideia central desta metodologia é um método heurístico, denominado Algoritmo de Corrida Orientada por Heurística (HORA), capaz de explorar o espaço de busca para perseguir diferentes alternativas na vizinhança de uma configuração de parâmetros promissora e encontrar sistematicamente boas configurações candidatas para diferentes algoritmos. Em síntese, o método HORA concentra as buscas sobre configurações candidatas promissoras, criadas dinamicamente em um processo iterativo, e utiliza uma técnica estatística robusta para avaliar as diferentes alternativas e descartar aquelas de qualidade inferior, assim que reunir evidências estatísticas suficientes contra elas. A partir dos resultados de diversos estudos computacionais, em que diferentes meta-heurísticas foram aplicadas sobre dois problemas clássicos de otimização combinatória, apresentam-se evidências estatísticas que as sintonizações obtidas pelo HORA são competitivas em relação ao método de Corrida e seu tempo no processo de sintonização é amplamente vantajoso. Em um estudo complementar, um algoritmo já bem configurado da literatura foi sintonizado por meio da metodologia proposta e os resultados da nova sintonização foram comparados com a literatura. Os resultados demonstram que a sintonização obtida pelo HORA pode encontrar soluções de melhor qualidade em relação à sintonização original. Portanto, a partir dos resultados apresentados nesta pesquisa conclui-se que a metodologia para sintonização de meta-heurísticas por meio do método HORA é uma abordagem promissora que pode ser aplicada sobre diferentes meta-heurísticas para resolução de uma diversidade de problemas de otimização. / The fine-tuning of the algorithms parameters, specially, of the meta-heuristics, it is not always trivial and often is performed by ad hoc methods according to the problem under analysis. In order to solve the problem of tuning metaheuristics, this research proposes a methodology combining statistical robust techniques (e.g.: Design of Experiments) and efficient methods from Artificial Intelligence (e.g.: Racing Algorithms). The key idea of this methodology is a heuristic method, called Heuristic Oriented Racing Algorithm (HORA), which explores the search space looking for alternatives near of a promising candidate and consistently finds good candidates configuration for different algorithms. Briefly, HORA focuses its searches over the promising candidates configuration, dynamically created in an iterative process, and employs a robust statistical method to evaluate and discarding them, as soon as gather enough statistical evidence against them. The results of several studies, where different metaheuristics were applied to solve two classical combinatorial optimization problems, present statistical evidences that the settings obtained by HORA are competitive to the Racing Algorithms and its time in the fine-tuning process is widely advantageous. In a complementary study, an already well setting algorithm from the literature was tuned by means of the proposed methodology and the new settings were compared with the literature. The results show that the fine-tuning from HORA can find better quality solutions than the original ones. Therefore, from the results presented in this study it is concluded that the methodology for fine-tuning of metaheuristics by means of HORA is a promising approach, which can be applied on different metaheuristics to solve a diversity of optimization problems.

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

Made available in DSpace on 2015-04-11T14:02:44Z (GMT). No. of bitstreams: 1 aurelio.pdf: 7052556 bytes, checksum: 209649285da9d7e9789f5576368e72c7 (MD5) Previous issue date: 2013-03-26 / The quality of software design is directly related to the decisions taken during its execution, because wrong decisions may cause significant damage in a software project. Among the decisions to be performed by a software engineer, an important one would be the selection of technologies to be applied to software projects. Usually, these decisions are made taking into account the experience of the professionals involved in the task. Thus, we limit the exploration of other possibilities that could be most appropriate for such scenario, what could be offered by a scientific approach to support this decision making. This thesis presents a framework for instantiation of software technologies selection techniques by using search-based strategies. For this, the Software Technologies Selection Problem (STSP) was modeled as a combinatorial optimization problem (Minimum Dominanting Set) with the purpose of to attend different and real scenarios of Software Engineering. The proposed framework for the STSP was idealized as a mechanism to support software engineers who are not able to use other generic optimization frameworks in a software project due to tight deadlines and limited resources. It was designed to be integrated with the main meta-heuristic optimization frameworks, such as JMetal and Opt4J, that implement a large number of meta-heuristics. To analyze the feasibility of the proposed modeling and the developed framework, two case studies were conducted in complex and real optimization problems: (i) selection of model-based testing techniques; (ii) selection of requirements elicitation technique for critical embedded systems. The studies were performed using different meta-heuristics and their results indicate their feasibility to support the selection of software technologies. / A qualidade de um projeto de software está diretamente relacionada com as decisões tomadas durante suas diversas fases, pois decisões equivocadas podem causar danos significativos no projeto. Entre as decisões de um engenheiro de software, pode ser citada a escolha de tecnologias a serem aplicadas em um projeto de software. Geralmente estas decisões são tomadas levando-se em conta a experiência dos profissionais envolvidos nas tarefas. Assim, deixa-se de explorar outras soluções mais adequadas para tal cenário, algo que uma abordagem científica de apoio a tal seleção poderia oferecer. O trabalho apresenta um framework para instanciação de técnicas de seleção de tecnologias de software baseado em estratégias de busca. Para isso, o Problema de Seleção de Tecnologias de Software, do inglês Software Technologies Selection Problem (STSP) foi modelado como um problema de otimização combinatória (Conjunto Dominante Mínimo) com o objetivo de atender diferentes cenários reais de Engenharia de Software. O framework proposto para STSP foi idealizado como um mecanismo de apoio aos engenheiros de software que possuiriam dificuldades em usar outros frameworks de otimização genéricos durante um projeto de software, devido a prazos curtos e recursos limitados. Tal framework foi desenvolvido para ser integrado com os principais frameworks de meta-heurística de otimização identificados na literatura técnica, como JMetal e Opt4J, que implementam um grande número de meta-heurísticas. Para analisar a viabilidade da modelagem proposta para o STSP e do framework desenvolvido, foram realizados dois estudos de casos em problemas de otimização do mundo real: (i) seleção de técnicas de teste baseado em modelos; (ii) seleção de técnicas de elicitação de requisitos para sistemas embarcados. Os estudos foram realizados utilizando diferentes meta-heurísticas. Os resultados indicam sua viabilidade de apoio à seleção de tecnologias de software.

Uma hiper-heurística é uma heurística que pode ser utilizada para lidar com qualquer problema de otimização, desde que a ela sejam fornecidos alguns parâmetros, como estruturas e abstrações, relacionados ao problema considerado. As hiper-heurísticas têm sido aplicadas a alguns problemas práticos e apresentadas como métodos de grande potencial, no que diz respeito à capacidade de possibilitar o desenvolvimento, em tempo bastante reduzido, de algoritmos capazes de lidar satisfatoriamente, do ponto de vista prático, com problemas de otimização complexos e pouco conhecidos. No entanto, é difícil situar as hiper-heurísticas em algum nível de qualidade e avaliar a robustez dessas abordagens caso não as apliquemos a problemas para os quais existam diversas instâncias disponíveis publicamente e já experimentadas por algoritmos relevantes. Este trabalho procura dar alguns passos importantes rumo a essas avaliações, além de ampliar o conjunto das hiper-heurísticas, compreender o impacto de algumas alternativas naturais de desenvolvimento e estabelecer comparações entre os resultados obtidos por diferentes métodos, o que ainda nos permite confrontar as duas diferentes classes de hiper-heurísticas que identificamos. Com essas finalidades em mente, desenvolvemos 3 novas hiper-heurísticas e implementamos 2 das hiper-heurísticas mais importantes criadas por outros autores. Para estas últimas, experimentamos ainda algumas extensões e modificações. Os dois métodos hiper-heurísticos selecionados podem ser vistos como respectivos representantes de duas classes distintas, que aparentemente englobam todas as hiper-heurísticas já desenvolvidas e nos permitem denominar cada um desses métodos como \"hiper-heurística de busca direta por entornos\" ou como \"hiper-heurística evolutiva indireta\". Implementamos cada hiper-heurística como uma biblioteca (em linguagem C), de forma a evidenciar e estimular a independência entre o nível em que se encontra a hiper-heurística e aquele onde se apresentam as estruturas e abstrações diretamente relacionadas ao problema considerado. Naturalmente, essa separação é de ingente importância para possibilitar a reutilização imediata das hiper-heurísticas e garantir que nelas haja total ausência de informações relativas a um problema de otimização específico. / A hyperheuristic is a heuristic that can be used to handle any optimization problem, provided that the algorithm is fed with some parameters, as structures and abstractions, related to the problem at hand. Hyperheuristics have been applied to some practical problems and presented as methods with great potential to allow the quick development of algorithms that are able to successfully deal, from a practical standpoint, with complex ill-known optimization problems. However, it\'s difficult to position hyperheuristics at some quality level and evaluate their robustness without applying them to problems for which there are many instances available in the public domain and already attacked by worthy algorithms. This work aims to give some important steps towards that process of evaluation, additionally increasing the number of available hyperheuristics, studying the impact of some natural development alternatives and comparing the results obtained by different methods, what also enables us to confront the two classes of hyperheuristics that we have identified. With those purposes in mind, we have developed 3 original hyperheuristics and implemented 2 of the most important hyperheuristics created by other authors. For those latter two approaches, we have also experimented with some modifications and extensions. The two methods we have chosen for implementation may be seen as respectively representing two distinct classes, which seem to contain all hyperheuristics developed so far and that allow us to classify any of these methods as either being a \"direct neighbourhood search hyperheuristic\" or an \"indirect evolutive hyperheuristic\". We have implemented each hyperheuristic as a library (in the C language), so as to clearly show and estimulate the independence between the level where the hyperheuristic is and that to which the structures and abstractions directly related to the problem at hand belong. Obviously, this separation of concerns is extremely important to make the immediate reuse of hyperheuristics possible and enforce in them the complete absence of information from a specific optimization problem.

Submitted by Automação e Estatística (sst@bczm.ufrn.br) on 2018-08-01T21:05:14Z No. of bitstreams: 1 IslameFelipeDaCostaFernandes_DISSERT.pdf: 12085812 bytes, checksum: 11b3cc3f73ed5f2051b48e441b6ee204 (MD5) / Approved for entry into archive by Arlan Eloi Leite Silva (eloihistoriador@yahoo.com.br) on 2018-08-02T23:01:50Z (GMT) No. of bitstreams: 1 IslameFelipeDaCostaFernandes_DISSERT.pdf: 12085812 bytes, checksum: 11b3cc3f73ed5f2051b48e441b6ee204 (MD5) / Made available in DSpace on 2018-08-02T23:01:50Z (GMT). No. of bitstreams: 1 IslameFelipeDaCostaFernandes_DISSERT.pdf: 12085812 bytes, checksum: 11b3cc3f73ed5f2051b48e441b6ee204 (MD5) Previous issue date: 2018-07-06 / Conselho Nacional de Desenvolvimento Científico e Tecnológico - CNPq / O Problema da Árvore Geradora Multiobjetivo (AGMO) é uma extensão NP-Difícil da Árvore Geradora Mínima (AGM). Devido à sua habilidade em modelar inúmeros problemas reais onde objetivos conitantes devem ser otimizados simultaneamente, a AGMO tem sido intensamente estudada na literatura e muitos algoritmos exatos e heurísticos lhe foram propostos. Além disso, nos últimos anos, pesquisas têm demonstrado considerável desempenho dos algoritmos que combinam estratégias de várias meta-heurísticas. Estes algoritmos são chamados híbridos e trabalhos anteriores os aplicaram com sucesso a vários problemas de otimização. Neste trabalho, cinco novos algoritmos híbridos são propostos para duas versões da AGMO: três para a versão bi-objetivo (AG-Bi) baseada em dominância de Pareto e dois para a versão com muitos objetivos baseada no operador de média ponderada ordenada (AG-OWA). Esta pesquisa hibridizou diversas abordagens meta-heurísticas com respeito a diferentes categorias de hibridização. Experimentos computacionais avaliaram as novas abordagens com base no tempo computacional e na qualidade das soluções encontradas. Os resultados foram comparados com o estado da arte. / The Multi-objective Spanning Tree Problem (MSTP) is an NP-hard extension of the Minimum Spanning Tree (MST). Once the MTSP models several real-world problems in which conicting objectives need to be optimized simultaneously, it has been extensively studied in the literature and several exact and heuristic algorithms were proposed for it. Besides, over the last years, researchs have showed the considerable performance of algorithms that combine various metaheuristic strategies. They are called hybrid algorithms and previous works successfully applied them to several optimization problems. In this work, five new hybrid algorithms are proposed for two versions of the MSTP: three for the bi-objective version (BiST) based on Pareto dominance and two for the manyobjective version based on the ordered weighted average operator (OWA-ST). This research hybridized elements from various metaheuristics. Computational experiments investigated the potential of the new algorithms concerning computational time and solution quality. The results were compared to the state-of-the-art.

Submitted by Eliane Vendramini De Oliveira (eliane@fai.com.br) on 2018-07-13T03:04:17Z No. of bitstreams: 1 Tese - versão pós defesa - 120718 (2).pdf: 24296114 bytes, checksum: b4e157585cf2618ae6be232afa8e33e6 (MD5) / Approved for entry into archive by Cristina Alexandra de Godoy null (cristina@adm.feis.unesp.br) on 2018-07-13T18:36:58Z (GMT) No. of bitstreams: 1 oliveira_ev_dr_ilha.pdf: 24296114 bytes, checksum: b4e157585cf2618ae6be232afa8e33e6 (MD5) / Made available in DSpace on 2018-07-13T18:36:59Z (GMT). No. of bitstreams: 1 oliveira_ev_dr_ilha.pdf: 24296114 bytes, checksum: b4e157585cf2618ae6be232afa8e33e6 (MD5) Previous issue date: 2018-05-25 / O Problema de Corte Bidimensional não guilhotinado tem sua aplicação prática quando comparado a problemas de indústrias que trabalham com aço, madeira, vidro, entre outros materiais, os quais necessitam de um padrão de corte que lhes proporcione maior lucro entre as peças cortadas, usando-se como técnica de corte o laser, e não a guilhotina, por isso existem diversas propostas para a resolução desse problema. Em particular, as propostas de solução utilizando-se meta-heurísticas foram o foco desta pesquisa. Vários trabalhos relevantes nessa área foram analisados, servindo de base para que esta tese trouxesse contribuições para a resolução do problema. A pesquisa sobre o problema permitiu que se apresentasse uma nova forma de representação da proposta de solução para o problema de corte bidimensional não guilhotinado. Outro resultado importante que se apresenta neste trabalho foi o desenvolvimento de duas meta-heurísticas especializadas na resolução do problema de corte bidimensional não guilhotinado. A primeira delas é o algoritmo genético de chaves aleatórias viciadas, e a segunda meta-heurística implementada foi RVNS. Foram realizados vários testes, utilizando-se instâncias conhecidas na literatura especializada, e os resultados encontrados pelas metaheurísticas algoritmo genético e RVNS propostas pela autora foram de boa qualidade, principalmente se comparados com os resultados já conhecidos na literatura. Os resultados obtidos com o algoritmo genético especializado, em muitos casos, foram iguais aos encontrados na literatura, e em dois casos de testes apresentaram-se superiores, contribuindo novamente para a área especializada no problema. Outro comparativo de resultados realizados pela autora está relacionado aos resultados obtidos pelas meta-heurísticas especialistas, propostas nesta tese, aos resultados encontrados utilizando-se o software AMPL para modelagem matemática em conjunto com o solver CPLEX. Nesse caso, novamente as meta-heurísticas algoritmo genético e RVNS apresentaram resultados iguais ou muito próximos do ótimo encontrado pelo modelo matemático. Os algoritmos desenvolvidos pela autora, além de resolverem o problema de corte bidimensional não guilhotinado, apresentaram bons resultados, visto que promoveram melhorias em relação ao que já existe na literatura. Os algoritmos foram escritos na linguagem de programação Fortran. Foram utilizados casos de teste de pequeno, médio e grande número de peças. Concluiu-se que o problema de corte bidimensional não guilhotinado é complexo e apresenta diversas variantes, sendo que as meta-heurísticas implementadas, neste trabalho, atendem a essa demanda com eficiência. Evidências empíricas mostram que esses algoritmos podem ser apropriados para solucionar instâncias associadas a situações reais. / The two-dimensional non-guillotine cutting problem has its practical application when compared to problems in industries that work with steel, wood, glass, among other materials, which require a cut pattern that provides more profit among the cut pieces, using laser as a cut technique, not the guillotine. Thus, there are several potential answers for this question. In particular, the potential solutions using metaheuristics were the focus of this research. Several relevant papers in this area were analyzed, forming a base so that this dissertation can bring solutions for the problem. The research about this issue allowed us to present a new form of representation of the proposal of solution for the two-dimensional non-guillotine problem. Another important result presented in this paper is the development of two metaheuristics specialized in the resolution of the two-dimensional non-guillotine problem. The first is the biased random-key genetic algorithm. The second metaheuristics was the RVNS. Several tests were performed, using methods well-known in the specialized literature, and the results found by the metaheuristics genetic algorithm and the RVNS suggested by the author were of good quality, mainly if compared to the results already known in the literature. The results obtained by the specialized genetic algorithm, in many cases, were equal to the ones found in the literature, and, in two tests, they were superior, once more contributing to the specialized field of the problem. Another comparison between the results performed by the author is related to the outcomes obtained by the specialized metaheuristics, suggested in this dissertation, and the ones found using the AMPL software to the mathematical modeling together with the CPLEX solver. In this case, once more, the genetic algorithm and RVNS metaheuristics presented resulted identical or very similar to the optimum one found by the mathematical model. The algorithms developed by the author not just solved the two-dimensional non-guillotine cutting problem, but present good results, given that they promoted improvements, comparing to what already exists in the literature. The algorithms were written in the Fortran programming language. Small, medium and big number of pieces’ case-tests were performed. The conclusion was that the two-dimensional non-guillotine cutting problem is complex and presents several variants. However, the metaheuristics implemented by this research efficiently meet this demand. Empirical evidences show that these algorithms can be used to solve issues associated with real situations.

Orientador: Rubén Augusto Romero Lázaro / Resumo: O Problema de Corte Bidimensional não guilhotinado tem sua aplicação prática quando comparado a problemas de indústrias que trabalham com aço, madeira, vidro, entre outros materiais, os quais necessitam de um padrão de corte que lhes proporcione maior lucro entre as peças cortadas, usando-se como técnica de corte o laser, e não a guilhotina, por isso existem diversas propostas para a resolução desse problema. Em particular, as propostas de solução utilizando-se meta-heurísticas foram o foco desta pesquisa. Vários trabalhos relevantes nessa área foram analisados, servindo de base para que esta tese trouxesse contribuições para a resolução do problema. A pesquisa sobre o problema permitiu que se apresentasse uma nova forma de representação da proposta de solução para o problema de corte bidimensional não guilhotinado. Outro resultado importante que se apresenta neste trabalho foi o desenvolvimento de duas meta-heurísticas especializadas na resolução do problema de corte bidimensional não guilhotinado. A primeira delas é o algoritmo genético de chaves aleatórias viciadas, e a segunda meta-heurística implementada foi RVNS. Foram realizados vários testes, utilizando-se instâncias conhecidas na literatura especializada, e os resultados encontrados pelas metaheurísticas algoritmo genético e RVNS propostas pela autora foram de boa qualidade, principalmente se comparados com os resultados já conhecidos na literatura. Os resultados obtidos com o algoritmo genético especializado, em mui... (Resumo completo, clicar acesso eletrônico abaixo) / Abstract: The two-dimensional non-guillotine cutting problem has its practical application when compared to problems in industries that work with steel, wood, glass, among other materials, which require a cut pattern that provides more profit among the cut pieces, using laser as a cut technique, not the guillotine. Thus, there are several potential answers for this question. In particular, the potential solutions using metaheuristics were the focus of this research. Several relevant papers in this area were analyzed, forming a base so that this dissertation can bring solutions for the problem. The research about this issue allowed us to present a new form of representation of the proposal of solution for the two-dimensional non-guillotine problem. Another important result presented in this paper is the development of two metaheuristics specialized in the resolution of the two-dimensional non-guillotine problem. The first is the biased random-key genetic algorithm. The second metaheuristics was the RVNS. Several tests were performed, using methods well-known in the specialized literature, and the results found by the metaheuristics genetic algorithm and the RVNS suggested by the author were of good quality, mainly if compared to the results already known in the literature. The results obtained by the specialized genetic algorithm, in many cases, were equal to the ones found in the literature, and, in two tests, they were superior, once more contributing to the specialized field of the p... (Complete abstract click electronic access below) / Doutor

Made available in DSpace on 2014-06-11T19:22:32Z (GMT). No. of bitstreams: 0 Previous issue date: 2009-11-20Bitstream added on 2014-06-13T18:08:26Z : No. of bitstreams: 1 proto_ab_me_ilha.pdf: 2777482 bytes, checksum: ac3152da7c340dcf6ab04c187cabe418 (MD5) / Neste trabalho propõe-se o desenvolvimento de uma interface gráfica voltada para a resolução do problema de planejamento da expansão das linhas de transmissão, que utiliza-se de programas para a obtenção das soluções ótimas ou de boas soluções. A grande dificuldade encontrada por usuários ao interagir com estes programas, motivou o desenvolvimento de uma aplicação com interface gráfica, a qual disponibiliza ao usuário diversas metodologias para a resolução do problema do planejamento da expansão das linhas de transmissão de energia elétrica. Espera-se que software como este, agregado ao sistema de ensino tradicional que normalmente ´e utilizado num curso de engenharia elétrica, possa fortalecer o processo de aprendizagem do aluno. Assim, o software educacional Transmission Expansion Planning (TEP 1.0) está sendo desenvolvido visando propiciar um ambiente agradável para a realização de simulações e testes e favorecer a aprendizagem dos conceitos que envolvem o problema do planejamento da expansão da transmissão. É possível através deste software fazer simulações para os sistemas: Garver (6 barras/ 15 ramos), Sul brasileiro (46 barras/79 ramos) e Norte-Nordeste brasileiro (87 barras/179 ramos). O software se beneficia de recursos oferecidos por programas que são executados em background, bem como da utilização de meta-heurísticas e do ambiente de processamento de máquinas paralelas virtuais, as quais podem ser selecionadas para realização dos testes em determinado sistema / This work proposes the development of a computational tool aimed at solving the problem of the transmission expansion planning, which uses programs in the background to obtain optimal solutions or good solutions. The great difficulty for users to interact with these programs, motivated the development of an application with a graphical interface, which provides the user with various methodologies for solving the problem of expansion planning of transmission lines of electricity. It is expected that software like this, added to the traditional school system which is normally used in electrical engineering courses, can strengthen the process of student learning. Thus, the educational software Transmission Expansion Planning (TEP 1.0) is being developed to provide a pleasant environment for simulations and testing and promote the learning of concepts involving the issue of transmission expansion planning. It is possible using this software to do simulations for the systems: Garver (6 nodes / 15 branches), South Brazilian (46 nodes / 79 branches) and North-Northeast Brazilian (87 nodes / 179 branches). The software takes advantage of capabilities offered by programs that run on background, and using meta-heuristics and the processing environment, parallel virtual machine, which can be selected to test on a system

Submitted by Fernando Souza (fernandoafsou@gmail.com) on 2017-08-14T11:28:15Z No. of bitstreams: 1 arquivototal.pdf: 7134434 bytes, checksum: a99ec0d172a3be38a844f44b70616b16 (MD5) / Made available in DSpace on 2017-08-14T11:28:15Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 7134434 bytes, checksum: a99ec0d172a3be38a844f44b70616b16 (MD5) Previous issue date: 2017-02-17 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / Many computational problems are considered to be hard due to their combinatorial nature. In such cases, the use of exaustive search techniques for solving medium and large size instances becomes unfeasible. Some data clustering and image segmentation problems belong to NP-Hard class, and require an adequate treatment by means of heuristic techniques such as metaheuristics. Data clustering is a set of problems in the fields of pattern recognition and unsupervised machine learning which aims at finding groups (or clusters) of similar objects in a benchmark dataset, using a predetermined measure of similarity. The partitional clustering problem aims at completely separating the data in disjont and non-empty clusters. For center-based clustering methods, the minimal intracluster distance criterion is one of the most employed. This work proposes an approach based on the metaheuristic Continuous Greedy Randomized Adaptive Search Procedure (CGRASP). High quality results were obtained through comparative experiments between the proposed method and other metaheuristics from the literature. In the computational vision field, image segmentation is the process of partitioning an image in regions of interest (set of pixels) without allowing overlap. Histogram thresholding is one of the simplest types of segmentation for images in grayscale. Thes Otsu’s method is one of the most populars and it proposes the search for the thresholds that maximize the variance between the segments. For images with deep levels of gray, exhaustive search techniques demand a high computational cost, since the number of possible solutions grows exponentially with an increase in the number of thresholds. Therefore, metaheuristics have been playing an important role in finding good quality thresholds. In this work, an approach based on Quantum-behaved Particle Swarm Optimization (QPSO) were investigated for multilevel thresholding of available images in the literature. A local search based on Variable Neighborhood Descent (VND) was proposed to improve the convergence of the search for the thresholds. An specific application of thresholding for electronic microscopy images for microstructural analysis of cementitious materials was investigated, as well as graph algorithms to crack detection and feature extraction. / Muitos problemas computacionais s˜ao considerados dif´ıceis devido `a sua natureza combinat´oria. Para esses problemas, o uso de t´ecnicas de busca exaustiva para resolver instˆancias de m´edio e grande porte torna-se impratic´avel. Quando modelados como problemas de otimiza¸c˜ao, alguns problemas de clusteriza¸c˜ao de dados e segmenta¸c˜ao de imagens pertencem `a classe NP-Dif´ıcil e requerem um tratamento adequado por m´etodos heur´ısticos. Clusteriza¸c˜ao de dados ´e um vasto conjunto de problemas em reconhecimento de padr˜oes e aprendizado de m´aquina n˜ao-supervisionado, cujo objetivo ´e encontrar grupos (ou clusters) de objetos similares em uma base de dados, utilizando uma medida de similaridade preestabelecida. O problema de clusteriza¸c˜ao particional consiste em separar completamente os dados em conjuntos disjuntos e n˜ao vazios. Para m´etodos de clusteriza ¸c˜ao baseados em centros de cluster, minimizar a soma das distˆancias intracluster ´e um dos crit´erios mais utilizados. Para tratar este problema, ´e proposta uma abordagem baseada na meta-heur´ıstica Continuous Greedy Randomized Adaptive Search Procedure (C-GRASP). Resultados de alta qualidade foram obtidos atrav´es de experimentos envolvendo o algoritmo proposto e outras meta-heur´ısticas da literatura. Em vis˜ao computacional, segmenta¸c˜ao de imagens ´e o processo de particionar uma imagem em regi˜oes de interesse (conjuntos de pixels) sem que haja sobreposi¸c˜ao. Um dos tipos mais simples de segmenta¸c˜ao ´e a limiariza¸c˜ao do histograma para imagens em n´ıvel de cinza. O m´etodo de Otsu ´e um dos mais populares e prop˜oe a busca pelos limiares que maximizam a variˆancia entre os segmentos. Para imagens com grande profundidade de cinza, t´ecnicas de busca exaustiva possuem alto custo computacional, uma vez que o n´umero de solu¸c˜oes poss´ıveis cresce exponencialmente com o aumento no n´umero de limiares. Dessa forma, as meta-heur´ısticas tem desempenhado um papel importante em encontrar limiares de boa qualidade. Neste trabalho, uma abordagem baseada em Quantum-behaved Particle Swarm Optimization (QPSO) foi investigada para limiariza¸c˜ao multin´ıvel de imagens dispon´ıveis na literatura. Uma busca local baseada em Variable Neighborhood Descent (VND) foi proposta para acelerar a convergˆencia da busca pelos limiares. Al´em disso, uma aplica¸c˜ao espec´ıfica de segmenta¸c˜ao de imagens de microscopia eletrˆonica para an´alise microestrutural de materiais ciment´ıcios foi investigada, bem como a utiliza¸c˜ao de algoritmos em grafos para detec¸c˜ao de trincas e extra¸c˜ao de caracter´ısticas de interesse.