PPGCC - Doutorado (Teses)
URI Permanente para esta coleção
Navegar
Submissões Recentes
Item Optimization algorithms for vehicle routing problems with multiple decision levels.(2023) Santos, Vinicius Gandra Martins; Carvalho, Marco Antonio Moreira de; Toffolo, Tulio Angelo Machado; Stevens, Nobby; Berghe, Greet Vanden; Carvalho, Marco Antonio Moreira de; Çalık, Hatice; Toffolo, Tulio Angelo Machado; Paternotte, Hande Yaman; Moniz, Martim Joyce; Meerbergen, Karl; Penna, Puca Huachi VazEm suas operações diárias, empresas de logística geralmente precisam resolver problemas com múltiplos níveis de decisão, além de uma vasta quantidade de aspectos práticos. Essas decisões não estão apenas relacionadas ao transporte, mas também podem envolver a determinação da localização de instalações, empacotamento de itens para envio ou escalonamento de pessoal. Incorporar todos esses níveis de decisão é crucial, dado que eles têm impacto direto no uso de recursos, custos e satisfação do cliente. Enquanto isso, alguns exemplos de aspectos práticos incluem janelas de tempo, várias opções de depósito e regulamentações de trabalho. Desenvolver métodos de solução para esses problemas extremamente complexos é frequentemente demorado e pode facilmente levar a uma explosão de complexidade. Em uma tentativa de ajudar a orientar pesquisadores e profissionais da indústria que enfrentam esse contexto de problema desafiador, nesta tese desenvolveremos uma metodologia geral para abordar problemas que apresentam múltiplos níveis de decisão interconectados com um problema de roteamento de veículos. Essa metodologia deve fornecer àqueles confrontados com tais problemas um conjunto geral de etapas que podem ser tomadas para simplificar e acelerar o processo de desenvolvimento de métodos de solução. Para chegar a essa metodologia geral, investigaremos os desafios enfrentados por um conjunto diversificado de empresas de logística e desenvolveremos métodos para resolver cada problema. Investigaremos como os diferentes níveis de decisão interagem entre si, como podemos aproveitar essas interações, que métodos podem reduzir e explorar efetivamente o espaço de busca do problema e como podemos minimizar o risco de uma explosão de complexidade para produzir rapidamente soluções de alta qualidade. Em última análise, em vez de começar focando no que diferencia esses problemas de múltiplos níveis, esperamos que esta tese incentive outros pesquisadores a primeiro explorar o que eles têm em comum.Item Revisitando o revenimento paralelo : computação de alto desempenho e aplicação em pesquisa operacional.(2024) Almeida, André Luis Barroso; Carvalho, Marco Antonio Moreira de; Lima, Joubert de Castro; Carvalho, Marco Antonio Moreira de; Lima, Joubert de Castro; Souza, Marcone Jamilson Freitas; Coelho, Igor Machado; Soares, Leonardo Cabral da Rocha; Martins, Simone de LimaNos últimos 35 anos, a computação paralela vem chamando a atenção da comuni- dade científica, especialmente para solucionar problemas complexos de otimização que necessitam de uma quantidade expressiva de poder computacional. A utilização de arquiteturas paralelas (multi-core e distribuídas) é uma alternativa natural e efetiva para acelerar as metaheurísticas e aumentar a qualidade das soluções geradas. Neste contexto, visando contribuir para a área de metaheurísticas paralelas, este estudo apresenta uma revisão sistemática de literatura ressaltando as particularida- des das publicações que adotam a computação de alto desempenho para projetar, implementar e experimentar metaheurísticas baseadas em trajetória. Ademais, essa revisão desempenhou um papel crucial para o desenvolvimento de uma nova me- taheurística paralela baseada no método conhecido como parallel tempering, pouco explorado na área de pesquisa operacional, que apresenta resultados expressivos na área de simulação e se integra de forma sinérgica com plataformas multiprocessadas modernas. Identificado durante a revisão, o parallel tempering revelou-se como uma metaheurística mais promissora para mitigar as lacunas identificadas na literatura. Assim, a nova metaheurística paralela desenvolvida foi minuciosamente avaliada em três estudos de caso envolvendo problemas difíceis de otimização abordados recentemente na literatura, tanto em termos de qualidade da solução quanto de tempo computacional. Além disso, uma API contendo a implementação do parallel tempering paralelo foi proposta e disponibilizada para facilitar futuras implementa- ções e popularizar sua utilização. Os resultados da avaliação ratificaram o potencial do parallel tempering, apresentando desempenho comparável ao estado da arte em um dos estudos de caso e superando-o nos outros dois, com redução de até 43,13% no valor das melhores soluções conhecidas. Quanto ao tempo computacional, os valores obtidos não se mostraram proibitivos em ambientes industriais reais, consolidando a eficácia da abordagem proposta.Item Inferencia gramatical : aplicações em composição algorítmica para modelagem de sequencia de acordes.(2024) Lopes, Henrique Barros; Moreira, Gladston Juliano Prates; Ribeiro, Rodrigo Geraldo; Moreira, Gladston Juliano Prates; Ribeiro, Rodrigo Geraldo; Silva, Ivair Ramos; Santos, Valéria de Carvalho; Wanner, Elizabeth Fialho; Ottoni, Amanda Gonçalves SaraivaInferência Gramatical é uma área amplamente estudada que utiliza algoritmos para inferir uma gramatica formal. As gramáticas inferidas podem ser aplicadas em uma grande vari- edade de áreas, como Linguística Computacional e Composição algorítmica. A literatura carece de algoritmos que tentam inferir Gramaticas Livres de Contexto Probabilísticas, ou mais expressivas. Para as primeiras, a literatura pode se beneficiar de algoritmos que tentam identificar as estruturas internas de uma gramatica. Na Composição Algorítmica, estudos re- centes mostraram que Modelos Ocultos de Markov podem superar Cadeias de Markov em termos de acurácia, porém não há diferenças significativas entre Modelos Ocultos de Markov e Gramaticas Livres de Contexto Probabilísticas (GLCPs). Nao há resultados na literatura que comprovam se inferir probabilidades sensíveis ao contexto podem superar ambas gramaticas. Este trabalho possui duas principais frentes, elaborar algoritmos de Inferência Gramatical e aplicar as gramaticas inferidas na área de Composição Algorítmica. Neste trabalho, desenvol- vemos um novo algoritmo para inferência de Gramáticas Livres de Contexto Probabilísticas chamado Pumping Inference. Ele foi capaz de inferir as linguagens Dyck-n e um subcon- junto da base de dados CoNLL-2003 com acurácia de predição melhor que a Amostragem de Gibbs. Na Composição Algorítmica, aplicamos um algoritmo de Amostragem de Gibbs para inferir Gramaticas (k, l)-Sensíveis ao Contexto Probabilísticas (G(k, l)CSPs) para mode- lar sequencia de acordes musicais. Nossos resultados mostram que a Amostragem de Gibbs e G(k, l)CSPs podem superar GLCPs e o algoritmo de busca de distribuição de probabilidades Metropolis-Hastings com perplexidades até 48% menores em media (valor-p 0,0026).Item Contributions to automating the analysis of conventional Pap smears.(2023) Diniz, Débora Nasser; Souza, Marcone Jamilson Freitas; Bianchi, Andrea Gomes Campos; Souza, Marcone Jamilson Freitas; Bianchi, Andrea Gomes Campos; Carneiro, Cláudia Martins; Luz, Eduardo José da Silva; Pessin, Gustavo; Souza, Jefferson Rodrigo de; Veras, Rodrigo de Melo SouzaThis thesis, organized as a compilation of articles, develops and presents contri- butions to the automated analysis of conventional Pap smear slides. A conventional Pap smear slide is a sample of cervical cells collected and prepared on a glass slide for subsequent cytopathological analysis. The main contributions are to detect and classify cervical cell nuclei to develop a decision support tool for cytopathologists. The first arti- cle resulting from this research utilizes a hierarchical methodology using Random Forest for the nucleus classification of the Herlev and Center for Recognition and Inspection of Cells (CRIC) Searchable Image Database databases based on 232 handcrafted fea- tures. In this article, we investigate balancing techniques, perform statistical analyses using Shapiro-Wilk and Kruskal-Wallis tests, and introduce the CRIC Searchable Image Database segmentation base. Our result defined the state-of-the-art in five metrics for nucleus classification in five and seven classes and the state-of-the-art in precision and F1-score for two-class classification. The second article introduces a method for nu- cleus detection in synthetic Pap smear images from the Overlapping Cervical Cytology Image Segmentation Challenge dataset proposed at the 11th International Symposium on Biomedical Imaging (ISBI’14). In this second article, we investigate clustering al- gorithms for image segmentation. We also explore four traditional machine learning techniques (Decision Tree (DT), Nearest Centroid (NC), k-Nearest Neighbors (k-NN), and Multi-layer Perceptron (MLP)) for classification and propose an ensemble method using DT, NC, and k-NN. Our result defined the state-of-the-art recall using this dataset. The third article proposes an ensemble method using EfficientNets B1, B2, and B6 to classify images from the CRIC Searchable Image Database dataset. Here, we investigate ten neural network architectures to choose those used in the ensemble method and present a data augmentation methodology using image transformation techniques. Our result de- fined the five state-of-the-art metrics for nucleus classification in two and three classes. Furthermore, we introduce results for six-class classification. Lastly, the fourth article introduces the Cytopathologist Eye Assistant (CEA), an intuitive and user-friendly tool that uses deep learning to detect and classify cervical cells in Pap smear images, support- ing cytopathologists in providing diagnoses. We investigate You Only Look Once (YOLO) v5 and YOLOR for performing both tasks (detection and classification) and also explore the combination of using YOLOv5 for detection and the ensemble of EfficientNets from the third article for classification. The article explores data balancing techniques, under- sampling, and oversampling using Python’s Clodsa library. The CRIC Cervix database was used for tool evaluation, considering four scenarios: original images, resized im- ages, augmented resized images, and balanced resized images. The application of CEA was validated by specialists with years of experience in cytopathology, highlighting the tool’s ease of use and potential to address specific queries.Item Wearable edge AI towards cyber-physical applications.(2023) Silva, Mateus Coelho; Oliveira, Ricardo Augusto Rabelo; Ribeiro, Sérvio Pontes; Bianchi, Andrea Gomes Campos; Oliveira, Ricardo Augusto Rabelo; Teixeira, Fernando Augusto; Silva, Jorge Miguel Sá; Correia, Luiz Henrique Andrade; Silva, Saul Emanuel Delabrida; Amorim, Vicente José Peixoto deThe creation of novel technologies to support field work and research has a major impact from technologies such as the Internet of Things (IoT), Edge Computing and wearable computing. In this context, Artificial-Intelligence-based systems became more common and a trend in recent work. Environments with low connectivity and high latency in data transmission enforce the usage of Edge Computing technologies in the treatment of acquired data. Nonetheless, there is no clarity in how to transport Artificial Intelligence (AI) to Edge Computing in extreme environments, given the complexity of the requirements. This gap is more clear in the context of wearable computing, where the systems restrictions for developing systems are even harder. Thus, this work presents a protocol for developing Edge AI appliances and some case-study applications in the context of wearable devices. This study helps to evaluate the creation of Wearable Edge AI context as a novel research field.Item Otimização de processos produtivos em sistemas de manufatura flexível.(2023) Soares, Leonardo Cabral da Rocha; Carvalho, Marco Antonio Moreira de; Carvalho, Marco Antonio Moreira de; Subramanian, Anand; Chaves, Antônio Augusto; Souza, Marcone Jamilson Freitas; Toffolo, Túlio Ângelo MachadoA complexidade geral do gerenciamento de produção de um sistema de manufatura flexível tem inspirado pesquisadores ao estudo de diversos problemas computacionais advindos de tais sistemas desde a década de 1980. Estudos recentes demonstram que o número de publicações em temas correlatos cresce constantemente desde o ano de 1988, reforçando a relevância e a atualidade do tema. Diante disto, neste trabalho são abordados alguns dos principais problemas advindos deste cenário. Todos os problemas abordados possuem publicações recentes em prestigiados veículos internacionais. Para cada problema abordado apresenta-se definição formal, revisão bibliográfica, método computacional para solução e análise comparativa dos resultados obtidos em relação ao atual estado da arte. Entre os métodos computacionais propostos há predominância da meta-heurística busca local iterada e do algoritmo genético de chaves aleatórias viciadas, entretanto, cada implementação foi cuidadosamente elaborada considerando-se as características individuais dos problemas abordados. Em síntese, inicialmente apresenta-se dois problemas fundamentais relacionados ao escalonamento de tarefas em máquinas flexíveis, o problema de minimização de trocas de ferramentas e o problema do escalonamento de tarefas em máquinas paralelas idênticas com restrições de ferramentas, visando fornecer um referencial teórico para embasar e direcionar o estudo dos demais problemas. Em seguida, são abordados o problema de minimização de blocos de uns consecutivos, o problema de minimização de trocas de ferramentas uniforme, o problema de sequenciamento de tarefas em máquinas paralelas com limitação de recursos e o problema de sequenciamento de tarefas em máquinas paralelas não-idênticas com restrições de ferramentas. Para cada problema abordado realizou-se uma ampla campanha experimental, analisando-se as instâncias disponíveis na literatura e os resultados gerados pelos métodos propostos e pelos métodos que compõem o estado da arte. Análises estatísticas foram realizadas e confirmaram a alta qualidade das soluções reportadas pelos métodos propostos.Item Blockchain é tudo que você precisa : a integração e comunicação descentralizada dos sistemas da Indústria 4.0.(2022) Garrocho, Charles Tim Batista; Oliveira, Ricardo Augusto Rabelo; Cavalcanti, Carlos Frederico Marcelo da Cunha; Oliveira, Ricardo Augusto Rabelo; Cavalcanti, Carlos Frederico Marcelo da Cunha; Loureiro, Antônio Alfredo Ferreira; Greve, Fabíola Gonçalves Pereira.; Silva, Jorge Miguel Sá; Correia, Luiz Henrique AndradeA Internet Industrial das Coisas é um novo marco que exigirá novos paradigmas e investimentos na indústria. Nesse contexto, os sistemas ciber-físicos são considerados a ponte para a quarta revolução industrial. Um exemplo disso é apresentado por diversos trabalhos recentes que aplicam novas tecnologias de hardware e software que permitem uma maior integração vertical dos sistemas de automação de processos industriais. Tais trabalhos geralmente possuem abordagens centralizadas e adicionam novos elementos na infraestrutura de rede que podem afetar as restrições de tempo na comunicação de processos industrias. Buscando uma decentralização na integração e comunicação entre dispositivos e sistemas industriais, o blockchain vem sendo amplamente aplicado, tornando os processos industriais mais seguros, automáticos, rastreáveis, imutáveis, e auditáveis. Entretanto, a utilização de tecnologias relacionadas a blockchain para o controle de processos também pode sofrer com problemas temporais que podem afetar os prazos de processos sensíveis ao tempo. Portanto, tornar a integração e comunicação dos processos industriais decentralizados que atendam os requisitos rigorosos de sistemas sensíveis ao tempo é um importante desafio que deve ser superado para o avanço da Indústria 4.0. Para enfrentar e superar esse desafio, é apresentado nessa tese diferentes arquiteturas de integração baseada em blockchain dos sistemas de automação de processos industriais. Essas arquiteturas aplicam contratos inteligentes baseados em blockchain como middleware na comunicação entre máquinas e dispositivos de monitoramento de chão de fábrica, permitindo uma decentralização do controle e o monitoramento de dispositivos industriais sem afetar os processos sensíveis ao tempo. Como provas de conceito, foram desenvolvidos sistemas de automação industrial baseado nas arquiteturas e implantados em dispositivos controladores sensíveis ao tempo. As avaliações de desempenho das provas de conceito permitiram a análise de viabilidade e o comportamento das arquiteturas propostas. Além disso, as discussões dessas experiências resultaram no desenvolvimento de metodologias e modelos que podem contribuir significamente no projeto, desenvolvimento, implantação e monitoramento de sistemas industriais baseados em tecnologias blockchain.Item Using Blockchain and Low Power in Smart Cities to internet of thigs applications : a Fog Computing approach.(2022) Ferreira, Célio Márcio Soares; Oliveira, Ricardo Augusto Rabelo; Silva, Jorge Sá; Oliveira, Ricardo Augusto Rabelo; Aquino, André Luiz Lins de; Cavalcanti, Carlos Frederico Marcelo da Cunha; Ramos Filho, Heitor Soares; Correia, Luiz Henrique Andrade; Silva, Saul Emanuel Delabrida; Silva, Jorge Miguel SáWith the advent and popularization of Internet of Things (IoT) devices, new possibilities for applications that use data extracted from the things we use in everyday life arise. Cars, wearables, health sensors, and home appliances will generate unprecedented amounts of data and bring insights that will revolutionize our daily routines. A potential scenario significantly impacted is Smart Cities (SC), which uses devices spread out on a large scale in an urban environment to extract traffic, weather, and equipment maintenance data to obtain insights acting on city management and disaster prevention. The network infrastructure currently available for these network applications uses proprietary communication technologies and is dependent on mobile phone companies. Their systems are proprietary, centralized, isolated from other databases, and constantly exposed to Single Point of Failure (SPOF). IoT applications are still primarily embryonic and do not provide reliable verification of the data source at the edge, as in the case of IoT devices, often with outdated firmware. Our work investigates the use in SC of a composition of Low Power Wide Area Networks (LPWAN) and the popular Personal Area Networks (PAN), independence of mobile network providers, and Low Power consumption. For this, we used development kits with LoRa and BLE to verify the feasibility and possible problems in this integration, and we evaluated the scalability of LoRa using a simulator. Security gaps in IoT Apps in Smart Cities mainly come from the difficulty of knowing and trusting edge devices. The problem of standardizing and updating these devices during their lifetime justifies our search for using tools that support transparency, scalability, reliability, resilience, and implicit requirements of decentralized Blockchain networks that support Smart Contracts. For this, we present a network architecture using Fog Computing and Smart Contracts Blockchain, which, through API gateways, authorizes and authenticates edge communication from IoT devices previously known by their metadata and firmware. To provide standard and link data from Blockchain with existing Web datasets, we use and add new components to ontologies that model Ethereum entities. This approach allows us to use the semantic web for data consumption and linking, which exposes data from Ethereum networks in soft-realtime through middleware. This work investigates the potential use of Fog Computing in SC in Low Power networks, strategies to identify and authenticate IoT devices at the edges using Blockchain and Smart Contract, and consumption and data link of Blockchain with the current web using the Semantic web. The set of these resources used in Fog computing allows searching for a composition of independent SC network infrastructures, Low Power, with reliable information coming from the edges and integrable with other pre-existing data sets. As the main results, we show the limits of the LoRa network, using a simulator in single-gateway and multi-gateway scenarios. We present scenarios of mixed use of traditional using Blockchain as authentication and validation background, by API gateway in Fog Computing architecture, and we present the times in transactions per second of this approach considering signatures and validation of payloads using Ethereum Blockchain. We present a middleware to expose Ethereum data in soft-realtime using ontologies that model Ethereum in the literature and extended by our EthExtras ontology, providing classes and properties for links and queries.The main advances of this work are the models using the Fog Computing paradigm for Smart Cities, where we present its use as a mixing point of LoRa and BLE and the Blockchain API Gateway to validate data from IoT devices. In addition to our Middleware for extracting and consuming Ethereum data in soft real-time using our EthExtras and EthOn vocabulary.Item Exploiting a loss and a synthetic dataset protocol for biometrics system.(2022) Silva, Pedro Henrique Lopes; Moreira, Gladston Juliano Prates; Luz, Eduardo José da Silva; Moreira, Gladston Juliano Prates; Luz, Eduardo José da Silva; Queiroz, Rafael Alves Bonfim de; Silva, Rodrigo César Pedrosa; Oliveira, Luciano Rebouças de; Santos, Thiago Oliveira dosOs sistemas biométricos são um assunto comum no cotidiano do ser humano. Os esforços para aumentar a segurança desses sistemas estão aumentando a cada ano devido à sua necessidade por robustez. Os sistemas baseados em uma modalidade biométrica não tem um desempenho próximo da perfeição em ambientes não cooperativos, o que exige abordagens mais complexas. Devido a isso, novos estudos são desenvolvidos para melhorar o desempenho de sistemas baseados em biometria, criando novas formas de ensinar um algoritmo de machine learning a criar novas representações. Atualmente, vários pesquisadores estão direcionando seus esforços para desenvolver novas abordagens de metric learning para arquiteturas de deep learning para uma ampla gama de problemas, incluindo biometria. Neste trabalho, propõe-se uma função de perda baseada em dados biométricos para criar representações profundas a serem utilizadas em sistemas biométricos, chamada de D-loss. Os resultados mostram a eficácia da função de perda proposta com a menor taxa de equal-error rate (EER) de 5,38%, 13,01% e 7,96% para MNIST-Fashion, CIFAR-10 e CASIA-V4. Uma estratégia diferente para aumentar a robustez de um sistema é a fusão de duas ou mais modalidades biométricas. No entanto, é impossível encontrar um conjunto de dados com todas as combinações de modalidades biométricas possíveis. Uma solução simples é criar um conjunto de dados sintéticos, embora a metodologia para criar um ainda seja um problema em aberto na literatura. Neste trabalho, propõe-se a criação de um critério para mesclar duas ou mais modalidades de tal forma a criar conjuntos de dados sintéticos semelhantes: o critério de Doddington Zoo. Várias estratégias de mesclagem são avaliadas: fusões ao nível de score (mínimo, multiplicação e soma) e nível de características (concatenação simples e metric learning). Um EER próximo a zero também é observado usando os critérios de fusão propostos com a fusão de soma de pontuação e as modalidades de Eletrocardiograma (CYBHi), olho e face (FRGC). Dois conjuntos de dados com mais de 1.000 indivíduos (UFPR-Periocular e UofTDB) são usados para avaliar os critérios de mesclagem junto com a D-loss e outras funções de metric learning. Os resultados mostram o aspecto do critério do Doddington Zoo de criar conjuntos de dados semelhantes (pequeno desvio padrão em relação ao critério randômico) e a robustez do D-loss (2,50% EER contra 2,17% da função de perda triplets e 5,74, da função de perda multi-similarity).Item A mathematical formulation and heuristic algorithms for minimizing the makespan and energy cost under time-of-use electricity price in an unrelated parallel machine scheduling problem.(2022) Rego, Marcelo Ferreira; Souza, Marcone Jamilson Freitas; Cota, Luciano Perdigão; Souza, Marcone Jamilson Freitas; Cota, Luciano Perdigão; Penna, Puca Huachi Vaz; Coelho, Igor Machado; Arroyo, José Elias Claudio; Batista, Lucas de SouzaEm muitos países, o preço da energia varia de acordo com a política time-of-use. Como regra geral, é vantajoso financeiramente para as indústrias planejarem sua produção considerando essa política. Esta tese apresenta um novo problema de sequenciamento de máquinas paralelas não-relacionadas bi-objetivo com tempos de preparação dependentes da sequência, no qual os objetivos são minimizar o makespan e o custo total de energia considerando máquinas com diferentes modos de operação e que o preço da eletricidade segue a política time-of-use. Introduzimos uma formulação de programação linear inteira mista e aplicamos o método da soma ponderada para obter uma fronteira Pareto. Também desenvolvemos métodos de otimização multiobjetivo, baseados no Multi-objective Variable Neighborhood Search com procedimento de intensificação (chamado MOVNS2) e o Non-dominated Sorting Genetic Algorithm II (NSGA-II), para tratar instâncias grandes, com pelo menos 50 tarefas, uma vez que a formulação não pode resolvê-las em um tempo computacional aceitável para a tomada de decisão. Comparamos o desempenho dos algoritmos NSGA-II e MOVNS2 com dois algoritmos de otimização multiobjetivo da literatura, o MOVNS1 e o NSGA-I, em relação às métricas de hipervolume e hierarchical cluster counting (HCC). Os resultados mostraram que os métodos propostos são capazes de encontrar uma boa aproximação para a fronteira Pareto comparado com os resultados do método de soma ponderada em instâncias pequenas, de até 10 tarefas. Quando consideramos apenas as instâncias grandes, o MOVNS2 é superior ao MOVNS1, o NSGA-I e o NSGA-II em relação à métrica de hipervolume. Além disso, o NSGA-II supera os métodos de otimização multiobjetivo NSGA-I, MOVNS1 e MOVNS2 em relaçãoo à métrica HCC. Ambos os resultados apresentam um nível de confiança de 95%. Assim, o MOVNS2 proposto é capaz de encontrar soluções não-dominadas com boa convergência e o NSGA-II com boa diversidade.Item Estratégias de otimização contínua Caixa-Cinza para problemas de larga escala.(2021) Costa, Rodolfo Ayala Lopes; Freitas, Alan Robert Resende de; Freitas, Alan Robert Resende de; Carvalho, Marco Antonio Moreira de; Toffolo, Túlio Ângelo Machado; Arroyo, José Elias Claudio; Guimarães, Frederico GadelhaA otimização caixa-cinza tem emergido como uma alternativa promissora aos tradicionais métodos de otimização caixa-preta, uma vez que esses métodos tradicionais deterioram seu desempenho ao lidar com problemas de larga escala. Embora trabalhos relacionados à otimização caixa-cinza tenham sido introduzidos na literatura nos últimos anos, há uma carência de estudos sobre essa abordagem no contexto de otimização contínua. Os problemas de otimização contínua representam uma importante subclasse de problemas práticos de otimização. Em particular, estudos sobre otimização contínua de problemas de larga escala vem recebendo especial atenção na última década. Nesse contexto, este trabalho se propõe a estudar e desenvolver diferentes abordagens caixa-cinza para lidar com essa subclasse de problemas. Para isso, definições matemáticas de separabilidade de problemas de otimização que são a base teórica para implementação das abordagens caixa-cinza são apresentadas e discutidas. Baseados nessas definições, diferentes algoritmos caixa-cinza foram propostos neste estudo. Um estudo experimental utilizando um conjunto de problemas de otimização contínua de larga escala foi proposto para investigar o desempenho das abordagens introduzidas. Os resultados demonstram um desempenho promissor das abordagens caixa-cinza em comparação com as versões caixa-preta. Em resumo, esses resultados demonstram a capacidade das estratégias caixa-cinza de melhorar as soluções encontradas e economizar tempo de processamento, explorando a estrutura do problema e avaliações parciais.Item Hybrid feature selection approaches using metaheuristics for hierarchical classification.(2021) Lima, Helen de Cássia Sousa da Costa; Souza, Marcone Jamilson Freitas; Merschmann, Luiz Henrique de Campos; Souza, Marcone Jamilson Freitas; Merschmann, Luiz Henrique de Campos; Toffolo, Túlio Ângelo Machado; Luz, Eduardo José da Silva; Cerri, Ricardo; Barril Otero, Fernando EstebanA seleção de atributos é uma etapa de pré-processamento amplamente difundida na área de mineração de dados. Um de seus objetivos é reduzir o número de atributos originais de uma base de dados para melhorar o desempenho de um modelo preditivo. No entanto, apesar dos benefícios da seleção de atributos para a tarefa de classificação, até onde sabemos, poucos estudos na literatura abordam a seleção de atributos para o contexto de classificação hierárquica. Este trabalho propõe duas abordagens principais de seleção híbrida de atributos supervisionada, combinando uma etapa filtro com uma wrapper, na qual um classificador hierárquico global avalia subconjuntos de atributos. A primeira abordagem usa a metaheurística Busca em Vizinhança Variável Geral com um ranqueamento de atributos construído com a medida Incerteza Simétrica Hierárquica. A segunda abordagem propõe uma adaptação da medida de seleção de atributos baseada em correlação adaptada para classificação hierárquica e utiliza o algoritmo Best First Search para pesquisar o espaço de subconjuntos de atributos. Doze bases de dados dos domínios de proteína e imagem foram usadas para realizar experimentos computacionais para validar o desempenho dos algoritmos propostos utilizando dois classificadores hierárquicos globais propostos na literatura. Testes estatísticos mostraram que o uso dos métodos de seleção de atributos propostos levaram a um desempenho preditivo consistentemente melhor ou equivalente ao obtido quando todos os atributos iniciais são utilizados, além do benefício de reduzir o número de atributos necessários, o que justifica a aplicação em cenários de classificação hierárquica.Item Mathematical models and heuristic algorithms for routing problems with multiple interacting components.(2021) Chagas, Jonatas Batista Costa das; Souza, Marcone Jamilson Freitas; Santos, André Gustavo dos; Souza, Marcone Jamilson Freitas; Santos, André Gustavo dos; Barboza, Eduardo Uchoa; Arroyo, José Elias Claudio; Vidal, Thibaut Victor Gaston; Toffolo, Túlio Ângelo MachadoMuitos problemas de otimização com aplicações reais têm vários componentes de interação. Cada um deles pode ser um problema pertencente à classe N P-difícil, e eles podem estar em conflito um com o outro, ou seja, a solução ótima para um componente não representa necessariamente uma solução ótima para os outros componentes. Isso pode ser um desafio devido à influência que cada componente tem na qualidade geral da solução. Neste trabalho, foram abordados quatro problemas de roteamento complexos com vários componentes de interação: o Double Vehicle Routing Problem with Multiple Stacks (DVRPMS), o Double Traveling Salesman Problem with Partial Last-InFirst-Out Loading Constraints (DTSPPL), o Traveling Thief Problem (TTP) e Thief Orienteering Problem (ThOP). Enquanto os DVRPMS e TTP já são bem conhecidos na literatura, os DTSPPL e ThOP foram recentemente propostos a fim de introduzir e estudar variantes mais realistas dos DVRPMS e TTP, respectivamente. O DTSPPL foi proposto a partir deste trabalho, enquanto o ThOP foi proposto de forma independente. Neste trabalho são propostos modelos matemáticos e/ou algoritmos heurísticos para a solução desses problemas. Dentre os resultados alcançados, é possível destacar que o modelo matemático proposto para o DVRPMS foi capaz de encontrar inconsistências nos resultados dos algoritmos exatos previamente propostos na literatura. Além disso, conquistamos o primeiro e o segundo lugares em duas recentes competições de otimização combinatória que tinha como objetivo a solução de uma versão bi-objetiva do TTP. Em geral, os resultados alcançados por nossos métodos de soluções mostraram-se melhores do que os apresentados anteriormente na literatura considerando cada problema investigado neste trabalho.Item Gathering data in wireless sensor networks by drone.(2020) Rezende, Josiane da Costa Vieira; Souza, Marcone Jamilson Freitas; Silva, Rone Ilídio da; Souza, Marcone Jamilson Freitas; Teixeira, Fernando Augusto; Coelho, Igor Machado; Ochi, Luiz Satoru; Penna, Puca Huachi Vaz; Coelho, Vitor Nazário; Silva, Rone Ilidio daThe benefits of using mobile sinks or data mules for data collection in Wireless Sensor Network (WSN) have been studied in several studies. However, most of them consider only the WSN limitations and sensor nodes having no more than one data packet to transmit. This paper considers each sensor node having a relatively larger volume of data stored in its memory. That is, they have several data packets to send to sink. We also consider a drone with hovering capability, such as a quad-copter, as a mobile sink to gather this data. Hence, the mobile collector eventually has to hover to guarantee that all data will be received. Drones, however, have a limited power supply that restricts their flying time. Hence, the drone’s energy cost must also be considered to increase the amount of collected data from the WSN. This work investigates the problem of determining the best drone tour for data gathering in a WSN. We focus on minimizing the overall drone flight time needed to collect all data from the WSN. We propose an algorithm to create a subset of sensor nodes to send data to the drone during its movement and, consequently, reduce its hovering time. The proposed algorithm guarantees that the drone will stay a minimum time inside every sensor node’s radio range. The computational experiments showed that our proposal significantly outperforms the state-of-the-art methods in finding drone tours in this type of scenario.Item Desenvolvimento de uma abordagem para reconhecimento contínuo da Língua Brasileira de Sinais utilizando imagens dinâmicas e técnicas de aprendizagem profunda.(2020) Escobedo Cárdenas, Edwin Jonathan; Cámara Chávez, Guillermo; Cámara Chávez, Guillermo; Ferreira, Anderson Almeida; Gomes, David Menotti; Luz, Eduardo José da Silva; Schwartz, William RobsonDurante os últimos anos, têm sido desenvolvidas diversas abordagens para o reconhecimento contínuo de línguas de sinais para melhorar a qualidade de vida das pessoas surdas e diminuir a barreira de comunicação entre elas e a sociedade. Analogamente, a incorporação do dispositivo Microsoft Kinect gerou uma revolução na área de visão computacional, fornecendo novas informações multimodais (dados RGB-D e do esqueleto) que podem ser utilizadas para gerar ou aprender novos descritores robustos e melhorar as taxas de reconhecimento em diversos problemas. Assim, nessa pesquisa de doutorado, apresenta-se uma metodologia para o reconhecimento de sinais contínuos da Língua Brasileira de Sinais (LIBRAS) utilizando como dados de entrada de um sinal as informações fornecidas pelo dispositivo Kinect. Diferentemente dos outros trabalhos na literatura, que utilizam arquiteturas de redes mais complexas (como as 3DCNN e BLSTM), o método proposto utiliza janelas deslizantes para procurar segmentos candidatos de serem sinais dentro de um fluxo continuo de video. Do mesmo modo, propõe-se o uso de imagens dinâmicas para codificar as informações espaço-temporais fornecidas pelo Kinect. Assim, pode-se reduzir a complexidade da arquitetura CNN proposta para o reconhecimento dos sinais. Finalmente, baseado no conceito de pares mínimos, um novo banco de dados da Língua Brasileira de Sinais chamado LIBRAS-UFOP é proposto. A base LIBRAS-UFOP possui tanto sinais isolados (56 classes de sinais) como sinais contínuos (37 classes); nós avaliamos nosso método usando essa base e o comparamos com os métodos propostos na literatura. Os resultados experimentais nos datasets LIBRAS-UFOP e LSA64 demostraram a validade do método proposto baseado em imagens dinâmicas como uma alternativa para o reconhecimento de língua de sinais.Item Contribuições para o desenvolvimento de uma teoria da dinâmica de sistemas espaciais.(2020) Amâncio, André Fonseca; Carneiro, Tiago Garcia de Senna; Carneiro, Tiago Garcia de Senna; Aguiar, Ana Paula Dutra; Monteiro, Antônio Miguel Vieira; Andrade Neto, Pedro Ribeiro de; Silva, Rodrigo César PedrosaEmbora o paradigma de modelagem Dinâmica de Sistemas (do termo em inglês System Dynamics - SD) venha sendo utilizado com frequência para modelar e simular sistemas geoespaciais, as atuais extensões desse paradigma ainda limitam ou dificultam a representação das componentes espaciais do comportamento desses sistemas. As simplificações e a diversidade de abordagens ameaçam a confiabilidade e a reprodutibilidade de muitos estudos ambientais fundamentados na SD. Elas permitem que um dado modelo conceitual de qualquer fenômeno produza resultados distintos quando implementados e simulados pela adoção de diferentes extensões/ferramentas. Não raramente, as ferramentas que implementam estas extensões da SD demandam que os modeladores codifiquem as estruturas de controle que garantirão coerência às simulações de fluxos simultâneos e, em geral, exigem que os modeladores sejam experts na construção de simuladores, pois é deles a responsabilidade de tratar incertezas intrínsecas aos algoritmos de integração numérica e de realizar o correto controle dos ciclos de retroalimentação. Este cenário justifica-se pela inexistência de consenso sobre quais seriam os conceitos e princípios básicos que especializariam a Dinâmica de Sistemas para o melhor entendimento das dinâmicas e dos padrões espaciais que emergem das interações entre os sistemas naturais e/ou sociais. É neste contexto que este trabalho apresenta uma análise crítica das extensões espaciais de SD encontradas na literatura e, em seguida, descreve o desenvolvimento de uma álgebra para a especificação formal de modelos dinâmicos espacialmente-explícitos baseados na Dinâmica de Sistemas. Esta álgebra possui tipos, operadores e regras sintáticas de rígida semântica que permitem que os aspectos espaciais do comportamento de modelos ambientais sejam simulados sem ambiguidade em diferentes linguagens de programação ou frameworks de modelagem, contribuindo para a reprodutibilidade dos avanços científicos no tema. Como uma prova de conceito, a especificação formal de um modelo hidrológico espacialmente-explícito é apresentada e os resultados de sua simulação analisados como uma maneira de ilustrar o uso e a expressividade desta álgebra e, principalmente, verificar a correção dos progressos alcançados. Então, a álgebra é utilizada para aprofundar o entendimento acerca dos impactos da espacialização de estoques, fluxos e feedbacks em arquétipos e modelos básicos da SD cujos comportamentos são previamente conhecidos. Estes estudos de caso contribuem para a criação de uma biblioteca de modelos e um guia de orientações que servem de suporte ao desenvolvimento um ambiente de aprendizado em modelagem, incentivando a reutilização e criação de modelos espaciais da SD a partir da composição de modelos e arquétipos cujos comportamentos são conhecidos e desejados. Os estudos de caso também evidenciam que a álgebra permite que os modeladores foquem seus esforços na modelagem conceitual da realidade, sem se preocuparem com detalhes de implementação dos modelos.Item Caracterização e análise de sensibilidade dos modelos de mobilidade veicular utilizando quantificadores de teoria da informação.(2020) Silva, Maurício José da; Oliveira, Ricardo Augusto Rabelo; Aquino, André Luiz Lins de; Aquino, André Luiz Lins de; Bianchi, Andrea Gomes Campos; Rosso, Osvaldo Anibal; Correia, Luiz Henrique AndradeNovas propostas de aplicações e protocolos para redes veiculares surgem todos os dias. É crucial avaliar, testar e validar estas propostas em larga escala antes de implantá-las no mundo real. Simulação ´e o método preferido pelos pesquisadores para avaliar suas propostas por permitir avaliações em larga escala e com baixo custo. É conhecido que, em simuladores para redes veiculares, modelos de mobilidade realistas são um requisito para produzir avaliações confiáveis. Porém, os modelos de mobilidade atuais são baseados em modelos aleatórios, normalmente o Random Waypoint, e eles não representam a mobilidade veicular real quando consideramos a variação de velocidade como elemento a ser avaliado. Neste trabalho apresentamos a caracterização global, por dia da semana e por hora do dia, do comportamento veicular utilizando informações de velocidades coletadas em diferentes cenários reais. Para realizar esta caracterização utilizamos a metodologia de Bandt-Pompe aplicada às séries temporais produzidas a partir das velocidades dos veículos. Em seguida, o histograma de probabilidade é atribuído aos seguintes quantificadores de Teoria da Informação: Entropia de Shannon, Complexidade Estatística e Medida de Informação de Fisher. Os resultados mostram que as velocidades veiculares possuem comportamento similar ao ruído colorido com espectro de potência f−k para k ≥ 0. Adicionalmente, utilizando a mesma metodologia, verificamos a fidelidade dos modelos de mobilidade usados nos principais simuladores de redes veiculares. A avaliação revelou que o modelo de Krauss é o modelo que mais se aproxima do comportamento veicular observado nos cenários reais. Em seguida, fizemos a análise de sensibilidade dos parâmetros do modelo de Krauss com o objetivo de identificar os parâmetros que mais influenciam para produzir comportamento correlacionado com o ruído colorido. Observamos que o parâmetro sigma, que utiliza o ruído branco (ruído branco, f−k para k = 0) para modelar o comportamento do motorista, é o que mais influencia no comportamento veicular. Assim, o parâmetro sigma precisa ser modificado para utilizar o ruído colorido f−k para k variando entre 0 < k ≤ 3.Item Conflict graphs in mixed-integer linear programming : preprocessing, heuristics and cutting planes.(2020) Brito, Samuel Souza; Santos, Haroldo Gambini; Santos, Haroldo Gambini; Fonseca, George Henrique Godim da; Mateus, Geraldo Robson; Aragão, Marcus Vinicius Soledade Poggi de; Toffolo, Túlio Ângelo MachadoThis thesis addresses the development of con ict graph-based algorithms for MixedInteger Linear Programming, including: (i) an e cient infrastructure for the construction and manipulation of con ict graphs; (ii) a preprocessing routine based on a clique strengthening scheme that can both reduce the number of constraints and produce stronger formulations; (iii) a clique cut separator capable of obtaining dual bounds at the root node LP relaxation that are 19.65% stronger than those provided by the equivalent cut generator of a state-of-the-art commercial solver, 3.62 times better than those attained by the clique cut separator of the GLPK solver and 4.22 times stronger than the dual bounds obtained by the clique separation routine of the COIN-OR Cut Generation Library; (iv) an odd-cycle cut separator with a new lifting module to produce valid odd-wheel inequalities; (v) two diving heuristics capable of generating integer feasible solutions in restricted execution times. Additionally, we generated a new version of the COIN-OR Branch-and-Cut (CBC) solver by including our con ict graph infrastructure, preprocessing routine and cut separators. The average gap closed by this new version of CBC was up to four times better than its previous version. Moreover, the number of mixed-integer programs solved by CBC in a time limit of three hours was increased by 23.53%.Item Decision trees for the algorithm selection problem : integer programming based approaches.(2019) Vilas Boas, Matheus Guedes; Santos, Haroldo Gambini; Blum, Christian Clemens; Merschmann, Luiz Henrique de Campos; Silva, Rodrigo César Pedrosa; Toffolo, Túlio Ângelo MachadoEven though it is well known that for most relevant computational problems different algorithms may perform better on different classes of problem instances, most researchers still focus on determining a single best algorithmic configuration based on aggregate results such as the average. In this thesis, we propose Integer Programming based approaches to build decision trees for the Algorithm Selection Problem. These techniques allow the automation of three crucial decisions: (i) discerning the most important problem features to determine problem classes; (ii) grouping the problems into classes and (iii) select the best algorithm configuration for each class. We tested our approach from different perspectives: (i) univariate approach, where for each branch node, only one cutoff point of a feature is chosen and (ii) multivariate approach, where for each branch node, weights for multiple features are used (oblique decision trees). Considering the current scenario where the number of cores per machine has increased considerably, we also propose a new approach based on recommendation of concurrent algorithms. To evaluate our approaches, extensive computational experiments were executed using a dataset that considers the linear programming algorithms implemented in the COIN-OR Branch & Cut solver across a comprehensive set of instances, including all MIPLIB benchmark instances. We also conducted experiments with the scenarios/- datasets of the Open Algorithm Selection Challenge (OASC) held in 2017. Considering the first dataset and a 10-fold cross validation experiment, while selecting the single best solver across all instances decreased the total running time by 2%, our univariate approach decreased the total running time by 68% and using the multivariate approach, the total running time is decreased by 72%. An even greater performance gain can be obtained using concurrent algorithms, something not yet explored in the literature. For our experiments, using three algorithm configurations per leaf node, the total running time is decreased by 85%. These results indicate that our method generalizes quite well and does not overfit. Considering the results obtained using the scenarios of the OASC, the experimental results showed that our decision trees can produce better results than less interpretable models, such as random forest, which has been extensively used for algorithm recommendation.Item CPPS retrofitting no contexto da indústria 4.0.(2020) Lins, Theo Silva; Oliveira, Ricardo Augusto Rabelo; Oliveira, Ricardo Augusto Rabelo; Silva Júnior, Diógenes Cecílio da; Ramos Filho, Heitor Soares; Silva, Jorge Miguel Sá; Kelner, Judith; Correia, Luiz Henrique AndradeA Indústria 4.0 ´e a nova revolução industrial, que envolve a introdução de novas tecnologias no âmbito industrial. No entanto, mudar o patamar tecnológico de uma indústria desatualizada não é uma tarefa simples. Ao invés de trocar todos equipamentos antigos por equipamentos novos nas indústrias, o conceito retrofitting surge como uma solução rápida e de baixo custo, que visa ao reaproveitamento do equipamento existente, com adição de novas tecnologias. Todavia, o retrofitting sofre variação de acordo com o tipo e modelo do equipamento industrial, dificultando a atualização de um equipamento industrial para um Sistema de Produção Ciber-físico ou Cyber-Physical Production System (CPPS). Nesta pesquisa, propomos métodos para utilização do retrofitting para transformação de um equipamento industrial ultrapassado tecnologicamente em um CPPS. A modernização é feita com o suporte de uma plataforma que possui recursos para integrar o equipamento industrial com a Indústria 4.0. Para implementar a plataforma, definimos os requisitos, componentes e tecnologias necessários para realização do retrofitting. Todo o procedimento é realizado com base no Modelo Arquitetural de Referência para Indústria 4.0 - Reference Architectural Model for Industrie 4.0 (RAMI 4.0), uma arquitetura já difundida da Indústria 4.0. Para validar o funcionamento da plataforma, foram realizados estudos de casos com um braço robótico muito comum em uma indústria automatizada e com uma planta didática automatizada. Como resultado, mostramos o impacto após o processo que chamamos de CPPS Retrofitting