Nesta dissertação estudamos --- do ponto de vista algorítmico --- o seguinte problema, conhecido como problema da partição conexa balanceada. Dado um grafo conexo G com pesos atribuídos a seus vértices, e um inteiro q >= 2, encontrar uma partição dos vértices de G em q classes, de forma que cada classe da partição induza um grafo conexo e que, ao considerar as somas dos pesos dos vértices de cada classe, a menor das somas seja o maior possível. Em outras palavras, o objetivo é encontrar q classes cujos pesos sejam tão balanceados quanto possível. Sabe-se que este problema é NP-difícil. Mencionamos alguns resultados sobre complexidade computacional e algoritmos que são conhecidos para este problema. Apresentamos algumas heurísticas que desenvolvemos, todas elas baseadas no uso do algoritmo polinomial para árvores, devido a Perl e Schach, que apresentamos com detalhe. Implementamos quatro heurísticas e um algoritmo de 3/4-aproximação conhecido para o caso q=2. Exibimos os resultados obtidos com os vários testes computacionais conduzidos com instâncias aleatórias, com grafos de diferentes pesos e densidades. Os resultados computacionais indicam que o desempenho dessas heurísticas --- todas elas polinomiais --- é bem satisfatório. No caso especial em que q=2, observamos que a heurística mais onerosa sistematicamente produziu soluções melhores ou iguais às do algoritmo de aproximação / In this dissertation we study algorithmic aspects of the following problem, known as the balanced connected partition. Given a connected graph G with weights defined on its vertices, and an integer q >= 2, find a partition of the vertices of G into q classes such that each class induces a connected graph, and furthermore, when we consider the sum of the weights of the vertices in each class, the smallest sum is as large as possible. In other words, the q classes must have weights that are as balanced as possible. This problem is known to be NP-hard. We mention some computational complexity and algorithmic results that are known for this problem. We present some heuristics that we designed, all of them based on the use of the polynomial algorithm for trees, due to Perl and Schach, which we show in detail. We implemented four heuristics and a 3/4-approximation algorithm that is known for q=2. We run tests on many random instances, of graphs with different weights and densities. The computational results indicate that the performance of these heuristics --- all of polynomial time complexity --- are very satisfactory. For q=2, we observed that the most expensive heuristic produced solutions with values which are systematically better or equal to those produced by the approximation algorithm.

Esta tese aborda um problema de dimensionamento e sequenciamento de lotes de produção baseado em uma indústria alimentícia brasileira que opera por meio de diversas linhas de produção heterogêneas. Nesse ambiente produtivo, as linhas de produção compartilham recursos escassos, tais como, trabalhadores e máquinas e devem ser montadas (ativadas) em cada período produtivo, respeitando-se a capacidade disponível de cada recurso necessário para ativação das mesmas. Modelos de programação matemática inteira mista são propostos para representação do problema, bem como diversos métodos heurísticos de solução, compreendendo procedimentos construtivos e de melhoramento baseados na formulação matemática do problema e heurísticas lagrangianas. São propostas heurísticas do tipo relax-and-fix explorando diversas partições das variáveis binárias dos modelos e uma heurística baseada na decomposição do modelo para construção de soluções. Procedimentos do tipo fix-and-optimize e matheuristics do tipo iterative MIP-based neighbourhood search são propostas para o melhoramento das soluções iniciais obtidas pelos procedimentos construtivos. Testes computacionais são realizados com instâncias geradas aleatoriamente e mostram que os métodos propostos são capazes de oferecer melhores soluções do que o algoritmo Branch-and-Cut de um resolvedor comercial para instâncias de médio e grande porte. / This doctoral dissertation addresses the simultaneous lot sizing and scheduling problem in a real world production environment where production lines share scarce production resources. Due to the lack of resources, the production lines cannot operate all simultaneously and they need to be assembled in each period respecting the capacity constraints of the resources. This dissertation presents mixed integer programming models to deal with the problem as well as various heuristic approaches: constructive and improvement procedures based on the mathematical formulation of the problem and lagrangian heuristics. Relax-and-fix heuristics exploring some partitions of the set of binary variables of a model and a decomposition based heuristic are proposed to construct solutions. Fix-and-optimize heuristics and iterative MIP-based neighbourhood search matheuristics are proposed to improvement solutions obtained by constructive procedures. Computational tests are performed with randomly instances and show that the proposed methods can find better solutions than the Branch-and-Cut algorithm of a commercial solver for medium and large size instances.

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.

VIANA, Gerardo Valdíso Rodrigues. Técnicas para construção de árvores filogenéticas. 2007. 203 f. Tese (Doutorado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2007. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-20T12:05:20Z No. of bitstreams: 1 2007_tese_gvrviana.pdf: 3571043 bytes, checksum: 34853f08d8a8ac37e7c9e07dcf25de25 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-25T11:50:34Z (GMT) No. of bitstreams: 1 2007_tese_gvrviana.pdf: 3571043 bytes, checksum: 34853f08d8a8ac37e7c9e07dcf25de25 (MD5) / Made available in DSpace on 2016-07-25T11:50:34Z (GMT). No. of bitstreams: 1 2007_tese_gvrviana.pdf: 3571043 bytes, checksum: 34853f08d8a8ac37e7c9e07dcf25de25 (MD5) Previous issue date: 2007 / Phylogenetic tree structures express similarities, ancestrality, and relationships between species or group of species, and are also known as evolutionary trees or phylogenies. Phylogenetic trees have leaves that represent species (taxons), and internal nodes that correspond to hypothetical ancestors of the species. In this thesis we rst present elements necessary to the comprehension of phylogenetic trees systematics, then ef cient algorithms to build them will be described. Molecular biology concepts, life evolution, and biological classi cation are important to the understanding of phylogenies. Phylogenetic information may provide important knowledge to biological research work, such as, organ transplantation from animals, and drug toxicologic tests performed in other species as a precise prediction to its application in human beings. To solve a phylogeny problem implies that a phylogenetic tree must be built from known data about a group of species, according to an optimization criterion. The approach to this problem involves two main steps: the rst refers to the discovery of perfect phylogenies, in the second step, information extracted from perfect phylogenies are used to infer more general ones. The techniques that are used in the second step take advantage of evolutionary hypothesis. The problem becomes NP-hard for a number of interesting hypothesis, what justify the use of inference methods based on heuristics, metaheuristics, and approximative algorithms. The description of an innovative technique based on local search with multiple start over a diversi ed neighborhood summarizes our contribution to solve the problem. Moreover, we used parallel programming in order to speed up the intensi cation stage of the search for the optimal solution. More precisely, we developed an ef cient algorithm to obtain approximate solutions for a phylogeny problem which infers an optimal phylogenetic tree from characteristics matrices of various species. The designed data structures and the binary data manipulation in some routines accelerate simulation and illustration of the experimentation tests. Well known instances have been used to compare the proposed algorithm results with those previously published. We hope that this work may arise researchers' interest to the topic and contribute to the Bioinformatics area. / Árvores filogenéticas são estruturas que expressam a similaridade, ancestralidade e relacionamentos entre as espécies ou grupo de espécies. Conhecidas como árvores evolucionárias ou simplesmente filogenias, as árvores filogenéticas possuem folhas que representam as espécies (táxons) e nós internos que correspondem aos seus ancestrais hipotéticos. Neste trabalho, além das informações necessárias para o entendimento de toda a sistemática filogenética, são apresentadas técnicas algorítmicas para construção destas árvores. Os conceitos básicos de biologia molecular, evolução da vida e classificação biológica, aqui descritos, permitem compreender o que é uma Filogenia e qual sua importância para a Biologia. As informações filogenéticas fornecem,por exemplo, subsídios importantes para decisões relativas aos transplantes de órgãos ou tecidos de outras espécies para o homem e para que testes de reação imunológica ou de toxicidade sejam feitos antes em outros sistemas biológicos similares ao ser humano. Resolver um Problema de Filogenia corresponde à construção de uma árvore filogenética a partir de dados conhecidos sobre as espécies em estudo, obedecendo a algum critério de otimização. A abordagem dada a esse problema envolve duas etapas, a primeira, referente aos casos em que as filogenias são perfeitas cujos procedimentos desenvolvidos serão utilizados na segunda etapa, quando deve ser criada uma técnica de inferência para a filogenia num caso geral. Essas técnicas consideram de forma peculiar as hipóteses sobre o processo de evolução. Para muitas hipóteses de interesse o problema se torna NP-Difícil, justificando-se o uso de métodos de inferência através de heurísticas, meta-heurísticas e algoritmos aproximativos. Nossa contribuição neste trabalho consiste em apresentar uma técnica de resolução desse problema baseada em buscas locais com partidas múltiplas em vizinhanças diversificadas. Foi utilizada a programação paralela para minimizar o tempo de execução no processo de intensificação da busca pela solução ótima do problema. Desta forma, desenvolvemos um algoritmo para obter soluções aproximadas para um Problema da Filogenia, no caso, para inferir, a partir de matrizes de características de várias espécies, uma árvore filogenética que mais se aproxima da história de sua evolução. Uma estrutura de dados escolhida adequadamente aliada à manipulação de dados em binário em algumas rotinas facilitaram a simulação e ilustração dos testes realizados. Instâncias com resultados conhecidos na literatura foram utilizadas para comprovar a performance do algoritmo. Esperamos com este trabalho despertar o interesse dos pesquisadores da área de Computação, consolidando, assim, o crescimento da Bioinformática.

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

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.

Submitted by Lucienne Costa (lucienneferreira@ufcg.edu.br) on 2018-05-02T21:20:23Z No. of bitstreams: 1 DIMAS CASSIMIRO DO NASCIMENTO FILHO – TESE (PPGCC) 2017.pdf: 1879329 bytes, checksum: bda72914ec66d17611d9d0ab5b9ec6d5 (MD5) / Made available in DSpace on 2018-05-02T21:20:23Z (GMT). No. of bitstreams: 1 DIMAS CASSIMIRO DO NASCIMENTO FILHO – TESE (PPGCC) 2017.pdf: 1879329 bytes, checksum: bda72914ec66d17611d9d0ab5b9ec6d5 (MD5) Previous issue date: 2017-11-10 / Na era de Big Data, na qual a escala dos dados provê inúmeros desafios para algoritmos clássicos, a tarefa de avaliar a qualidade dos dados pode se tornar custosa e apresentar tempos de execução elevados. Por este motivo, gerentes de negócio podem optar por terceirizar o monitoramento da qualidade de bancos de dados para um serviço específico, usualmente baseado em computação em nuvem. Neste contexto, este trabalho propõe abordagens para redução de custos da tarefa de deduplicação de dados, a qual visa detectar entidades duplicadas em bases de dados, no contexto de um serviço de qualidade de dados em nuvem. O trabalho tem como foco a tarefa de deduplicação de dados devido a sua importância em diversos contextos e sua elevada complexidade. É proposta a arquitetura em alto nível de um serviço de monitoramento de qualidade de dados que emprega o provisionamento dinâmico de recursos computacionais por meio da utilização de heurísticas e técnicas de aprendizado de máquina. Além disso, são propostas abordagens para a adoção de algoritmos incrementais de deduplicação de dados e controle do tamanho de blocos gerados na etapa de indexação do problema investigado. Foram conduzidos quatro experimentos diferentes visando avaliar a eficácia dos algoritmos de provisionamento de recursos propostos e das heurísticas empregadas no contexto de algoritmos incrementais de deduplicação de dados e de controle de tamanho dos blocos. Os resultados dos experimentos apresentam uma gama de opções englobando diferentes relações de custo e benefício, envolvendo principalmente: custo de infraestrutura do serviço e quantidade de violações de SLA ao longo do tempo. Outrossim, a avaliação empírica das heurísticas propostas para o problema de deduplicação incremental de dados também apresentou uma série de padrões nos resultados, envolvendo principalmente o tempo de execução das heurísticas e os resultados de eficácia produzidos. Por fim, foram avaliadas diversas heurísticas para controlar o tamanho dos blocos produzidos em uma tarefa de deduplicação de dados, cujos resultados de eficácia são bastante influenciados pelos valores dos parâmetros empregados. Além disso, as heurísticas apresentaram resultados de eficiência que variam significativamente, dependendo da estratégia de poda de blocos adotada. Os resultados dos quatro experimentos conduzidos apresentam suporte para demonstrar que diferentes estratégias (associadas ao provisionamento de recursos computacionais e aos algoritmos de qualidade de dados) adotadas por um serviço de qualidade de dados podem influenciar significativamente nos custos do serviço e, consequentemente, os custos repassados aos usuários do serviço. / In the era of Big Data, in which the scale of the data provides many challenges for classical algorithms, the task of assessing the quality of datasets may become costly and complex. For this reason, business managers may opt to outsource the data quality monitoring for a specific cloud service for this purpose. In this context, this work proposes approaches for reducing the costs generated from solutions for the data deduplication problem, which aims to detect duplicate entities in datasets, in the context of a service for data quality monitoring. This work investigates the deduplication task due to its importance in a variety of contexts and its high complexity. We propose a high-level architecture of a service for data quality monitoring, which employs provisioning algorithms that use heuristics and machine learning techniques. Furthermore, we propose approaches for the adoption of incremental data quality algorithms and heuristics for controlling the size of the blocks produced in the indexing phase of the investigated problem. Four different experiments have been conducted to evaluate the effectiveness of the proposed provisioning algorithms, the heuristics for incremental record linkage and the heuristics to control block sizes for entity resolution. The results of the experiments show a range of options covering different tradeoffs, which involves: infrastructure costs of the service and the amount of SLA violations over time. In turn, the empirical evaluation of the proposed heuristics for incremental record linkage also presented a number of patterns in the results, which involves tradeoffs between the runtime of the heuristics and the obtained efficacy results. Lastly, the evaluation of the heuristics proposed to control block sizes have presented a large number of tradeoffs regarding execution time, amount of pruning approaches and the obtained efficacy results. Besides, the efficiency results of these heuristics may vary significantly, depending of the adopted pruning strategy. The results from the conducted experiments support the fact that different approaches (associated with cloud computing provisioning and the employed data quality algorithms) adopted by a data quality service may produce significant influence over the generated service costs, and thus, the final costs forwarded to the service customers.

Esta pesquisa trata do projeto de redes de distribuição de carga parcelada. Mais especificamente são tratados dois tipos de problemas que são comuns no planejamento desse tipo de sistema. O primeiro deles corresponde ao problema estratégico de configuração de redes do tipo hub-and-spoke, consistindo na definição simultânea da quantidade e localização de terminais para consolidação de carga (ou hubs), e na definição da alocação dos terminais aos hubs localizados. Uma vez determinada a configuração da rede, o segundo problema, no nível de decisão tático, corresponde na definição do caminho que cada carga parcelada deve percorrer desde sua origem até alcançar seu terminal de destino, a um mínimo custo, tendo a rede hub-and-spoke como um dado de entrada do problema. Um novo modelo matemático é proposto para representar o problema estratégico de configuração de uma rede hub-and-spoke, possuindo uma menor quantidade de variáveis e restrições, ao se comparar com outros modelos matemáticos comumente utilizados para representar o problema. Esse novo modelo matemático permitiu a obtenção de soluções ótimas para problemas em redes com até 100 terminais, sendo apresentada pela primeira vez a solução ótima para problemas utilizados como benchmark na literatura. Dado que problemas de grande porte ainda continuam muito difíceis de serem resolvidos, são propostas três variantes de uma heurística simples e eficiente utilizando técnicas de multi-início e busca tabu, bem como uma heurística integrada em dois estágios baseada em busca tabu para solução. Experimentos computacionais utilizando dados tradicionalmente utilizados na literatura para solução de problemas de configuração de redes hub-and-spoke (conjuntos de dados CAB e AP), bem como instâncias novas e modificadas, mostraram que a abordagem utilizada para solução do problema possibilitou a obtenção da solução ótima, ou a melhor solução conhecida, para esses problemas em um tempo de processamento muito curto, permitindo assim resolver de forma eficiente problemas de grande porte, nunca antes resolvidos em pesquisas anteriores. O segundo problema foi motivado por uma aplicação prática de uma empresa de transporte rodoviário de cargas parceladas no Brasil. O problema diz respeito ao planejamento de carregamentos a serem realizados em cada terminal, levando-se em consideração cada carga parcelada que precisa ser transportada, definindo o percurso que cada carga deve percorrer até chegar ao seu destino. É proposto um modelo matemático e, dada a dificuldade para se resolver problemas de tamanho como o encontrado na prática, é proposto também um método de solução utilizando metaheurística busca tabu. Experimentos computacionais realizados mostraram que a heurística proposta pôde efetivamente resolver problemas de tamanho como o encontrado na prática. / This research deals with problems related to distribution networks for less-than-truckload (LTL) freight transportation. More specifically, we deal with two relevant problems that arise. The first corresponds to the strategic problem of designing and configuring hub-and-spoke networks in terms of simultaneously determining the optimal number of consolidation terminals (hub) nodes, their locations and the allocation of the other terminals (spokes) to the hubs. . Once the network configuration is determined, the second problem, in the tactical level of decision, corresponds to defining the path that each LTL individual freight needs to follow from its origin to reach its destination terminal, at a minimum cost, having a hub-and-spoke network topology as a data entry to the problem. A new mathematical model is proposed to represent the strategic problem of designing a hub-and-spoke network, with fewer variables and constraints than previous formulations found in the literature This model allowed us to obtain optimal solutions for problems in transportation networks with up to 100 terminals, reporting for the first time the optimal solutions of benchmark problems in the literature. Since this problems still remains too hard to solve for larger instances, we propose we propose three variants of a simple and efficient multi-start tabu search heuristic as well as a two-stage integrated tabu search heuristic to solve it. Computational experiments using typical benchmark problems (CAB and AP data sets) as well as new and modified instances show that our approaches consistently return the optimal or best-known results in very short CPU times, thus allowing the possibility of efficiently solving larger instances of the USAHLP than those found in the literature. The second problem is motivated by a practical application of a LTL transportation company in Brazil. It deals with the planning of loads to be done at each terminal, taking into account each LTL freight that needs to be transported, defining the path that each good needs to follow to reach its destination. A new mathematical model is proposed, and, since real world problems are very hard to solve, a heuristic based on tabu search is also developed. Computational experiments show that our heuristic can effectively solve real-world instances from a trucking company in Brazil.

A avaliação do estado das estruturas é um tema de pesquisa muito importante para diversos campos da engenharia e, por isso, estão sendo desenvolvidas metodologias que permitem detectar dano em uma estrutura. O presente trabalho tem como objetivo verificar a aplicabilidade dos algoritmos genéticos (AG) na detecção de dano a partir das mudanças ocorridas, entre as condições com e sem dano, dos parâmetros dinâmicos da estrutura. Três tipos de AGs (binário, real e redundante implícita) são implementados com a finalidade de comparação do desempenho. Os parâmetros dinâmicos da estrutura, sadia e danificada, são determinados a partir do modelo de elementos finitos da estrutura. Medições incompletas e ruidosas foram consideradas visando simular as características da informação obtida por meio de um ensaio dinâmico real. Os AGs implementados são aplicados em estruturas de tipo viga, treliça e pórtico sob diferentes cenários de dano. Resultados mostram o bom desempenho dos AGs para detectar dano em uma estrutura. / The assessment of structural health is an important research topic in many engineering fields and, for that reason, damage detection methodologies are being developed. The goal of this dissertation is to verify the applicability of genetic algorithms (GAs) for detecting damage using dynamic parameters changes between undamaged and damaged condition of the structure. Three different GAs are implemented in order to compare the performance of the algorithms. Undamaged and damaged dynamic parameters are computed using the finite element model of the structure. Incomplete and noisy measurements are considered with the objective of simulating the real condition of the information in a real dynamic test. GAs are applied in some different structures: beam, truss and frame. The results indicate the good performance of the GAs for detecting damage in a structure.