Ciências Exatas e Tecnológicas
URI permanente desta comunidadehttps://locus.ufv.br/handle/123456789/4
Navegar
Item Abordagens heurísticas aplicadas ao Thief Orienteering Problem(Universidade Federal de Viçosa, 2022-07-15) Faêda, Leonardo Moreira; Faêda, Leonardo Moreira; http://lattes.cnpq.br/4917144810711752Este trabalho aborda o Thief Orienteering Problem, um problema multicomponente que combina dois problemas combinatórios conhecidos: o problema da mochila e o problema de orientação. Nesse problema, uma pessoa (denominada de ladrão) carrega uma mochila capacitada e possui um limite de tempo para coletar itens distribuídos em um conjunto de pontos. Os pontos de partida e chegada são fixos. O ladrão inicia sua trajetória com a mochila vazia e viaja com a velocidade inversamente proporcional ao peso da mochila. Enquanto tiver tempo, o ladrão pode passar pelos pontos coletando novos itens. O objetivo do problema é determinar qual rota e quais itens o ladrão deve coletar para maximizar o lucro da mochila. Dois métodos heurísticos baseados em metaheurísticas conhecidas são propostos para encontrar soluções boas que maximize o lucro obtido pelo ladrão em tempo hábil. O primeiro método heurístico é inspirado em algoritmos genéticos e os experimentos computacionais foram realizados com as instâncias de benchmark, a fim de comparar o desempenho do método desenvolvido com os algoritmos existentes na literatura. Os resultados mostraram que nosso método foi superior na maioria dos casos. Posteriormente uma novo método baseado na metaheurística de busca local iterada foi proposto e novos experimentos computacionais foram realizados. Os resultados mostraram que a abordagem superou os trabalhos existentes e o método inspirado em algoritmo genéticos em mais de 80% das instâncias do benchmark, com uma melhoria média de mais de 30%. Propomos também uma ampliação do problema para utilizar múltiplos ladrões. Nós descrevemos formalmente o problema apresentando uma formulação de programação não linear inteira mista e utilizamos adaptações dos métodos heurísticos propostos para gerar soluções iniciais para o problema. Os resultados mostram que, com a utilização de mais ladrões, o lucro total dos itens coletados aumentou em até 32% Palavras-chave: Metaheurísticas. Problemas Multicomponentes. Thief Orienteering ProblemItem Abordagens Heurísticas para otimização de um serviço de transporte reativo a demanda(Universidade Federal de Viçosa, 2016-06-10) Viana, Renan José dos Santos; Santos, André Gustavo dos; http://lattes.cnpq.br/2637804041805899Transporte reativo a demanda, na língua inglesa Demand Responsive Transport (DRT) é uma forma de prover transporte, seja para passageiros ou mercadorias, na qual o serviço é ativado sob demanda. Ao contrário dos serviços tradicionais de transporte público, os quais operam por meio de rotas, horários e pontos de atendimento fixos, os serviços DRT operam de formas flexíveis ou semi-flexíveis. Para utilização do serviço, passageiros devem enviar requisições, nas quais informam locais e horários desejados de embarque e desembarque. A partir das requisições, ocorre o processo de roteamento dos veículos e agendamento dos atendimentos. Usuários provenientes de requisições diferentes, mas com características em comum, seja área e/ou momento de atuação do serviço podem ser atendidos simultaneamente pelo mesmo veículo. Devido a esta forma de prover transporte, para alguns pesquisadores do tema, serviços DRT são conside- rados uma forma intermediária de transporte, situada entre os serviços de transporte público (caráter geral e compartilhado) e os táxis (personalizado e individual) e con- tribuem direta e indiretamente na redução de alguns dos principais problemas comuns em centros urbanos, tais como: excesso de veículos nas vias trafegando com baixa ocu- pação, poluição, congestionamentos, exclusão social relacionada ao acesso a meios de transporte público e etc. Neste trabalho, foram propostos modelos de programação linear mista, abordagens multiobjetivo e abordagens heurísticas para otimização de um serviço DRT introduzido na literatura, o qual foi explorado para os casos estático e dinâmico. As abordagens apresentadas foram avaliadas por meio de experimentos computacionais e testes estatísticos sobre conjuntos de instâncias com diferentes carac- terísticas, que indicaram as melhores abordagens para cada situação.Item Abordagens heurísticas para tratar o problema do Caixeiro Viajante Preto e Branco(Universidade Federal de Viçosa, 2015-12-08) Cazetta, Paôla Pinto; Gonçalves, Luciana Brugiolo; http://lattes.cnpq.br/9555452401257190O Problema do Caixeiro Viajante Preto e Branco (PCV-PB) é uma generalização do Problema do Caixeiro Viajante (PCV), definido sobre um grafo onde os vértices são classificados como pretos ou brancos. Assim como o clássico PCV, o objetivo do PCV-PB é encontrar um ciclo hamiltoniano de custo mínimo, entretanto, duas restrições adicionais são consideradas. Enquanto que a restrição de cardinalidade restringe o número de vértices brancos entre dois vértices pretos consecutivos, a restrição de comprimento restringe a distância máxima entre os mesmos. Apli- cações do PCV-PB podem ser observadas no escalonamento de aeronaves e em configurações de redes de telecomunicações. A proposta deste estudo é analisar diferentes estratégias heurísticas aplicadas para o PCV-PB. Heurísticas construtivas da literatura foram aperfeiçoadas e uma nova estratégia para a construção da solução foi apresentada. Neste contexto foi utilizado métodos como Lin kernighan e Inserção Específica de Brancos. Além disso, foram propostas abordagens heurísticas baseadas nas metaheurísticas GRASP, VND, ILS e SA. Diversos experimentos computacionais foram realizados para comparar a eficácia das abordagens. Os resultados garantem a aplicabilidade dos algoritmos propostos para o problema.Item Adequação do modelo formal da Associação Cartográfica Internacional e sua avaliação no desenvolvimento de infraestruturas de dados espaciais corporativas: estudo de caso IDE- Cemig(Universidade Federal de Viçosa, 2015-08-31) Oliveira, Italo Lopes; Lisboa Filho, Jugurta; http://lattes.cnpq.br/1270749431636054A International Cartographic Association (ICA) propôs um modelo para a descrição de Infraestrutura de Dados Espaciais (IDE) através de três das cincos perspectivas do framework RM-ODP (Reference Model for Open Distributed Processing). Posteriormente, este modelo foi estendido por outros pesquisadores para descrever de maneira mais adequada os atores e políticas da IDE, além de descreverem o relacionamento hierárquico entre as IDEs e as interações relacionadas com as políticas que regem o funcionamento da mesma. Entretanto, existem diferenças semânticas e terminológicas entre os atores e políticas do modelo da ICA e suas extensões. Além disso, o modelo da ICA não foi validado para IDEs de nível corporativo. O objetivo desta dissertação foi verificar se o modelo proposto pela ICA seria adequado para descrever IDEs de nível corporativo, utilizando como estudo de caso a IDE-Cemig. Inicialmente, os atores e políticas propostos pela ICA e pelos demais pesquisadores foram unificados, permitindo que os mesmos sejam utilizados por outros projetistas, sem que haja diferenças semânticas ou terminológicas entre eles. O modelo da ICA adaptado se mostrou adequado para descrever a IDE-Cemig, cujas diferenças apresentadas se devem às peculiaridades da IDE. Apesar de um único trabalho não ser capaz de validar o modelo da ICA para todo um nível de IDE, esta dissertação mostra que é possível utilizar o modelo da ICA para descrever IDEs corporativas. Outro resultado importante desta pesquisa é o próprio estudo de caso servir de exemplo para a especificação e implantação de novas IDEs, contribuindo principalmente para o fortalecimento da Infraestrutura Nacional de Dados Espaciais (INDE), uma vez que IDEs corporativas começam a ser implantadas e integradas à INDE.Item Agrupamento escalável de fluxos contínuos de dados com estimativa do número de grupos(Universidade Federal de Viçosa, 2018-12-21) Candido, Paulo Gustavo Lopes; Naldi, Murilo Coelho; http://lattes.cnpq.br/5249796751753792Avanços da tecnologia têm mudado a forma como dados são coletados, armaze- nados e analisados. Novas abordagens têm sido utilizadas para agrupamento não supervisionado de dados, tais como agrupamento de dados gerados em tempo real (fluxos contínuos de dados), e agrupamento escalável de dados. Ambas as abor- dagens descartam o armazenamento do conjunto completo de dados em memória principal devido a restrições físicas, utilizando técnicas como leitura linear e com- putação distribuída, respectivamente, para lidar com grande volume de dados. O agrupamento de fluxos contínuos de dados precisa lidar com características especí- ficas desse formato: são virtualmente e potencialmente ilimitados e possuem uma distribuição não-estacionária. Apesar de pouco exploradas, técnicas para estimação dinâmica do número de grupos mostraram ser eficazes na manutenção dos mode- los de agrupamento, uma vez que grupos podem surgir e desaparecer ao longo do tempo. Considerando ainda um cenário de aumento exponencial na quantidade de dados gerados em tempo real, surge a necessidade de algoritmos escaláveis (capazes de distribuir o processamento) para agrupamento de fluxos de dados, capazes de estimar o número de grupos, a fim de manter um alto nível de qualidade. Neste trabalho são apresentados cinco algoritmos com essa finalidade, dos quais quatro são baseados na computação evolutiva. O modelo funcional MapReduce é utilizado para prover escalabilidade por meio de um sistema distribuído, garantindo confiabilidade, resiliência e tolerância a falhas. Os algoritmos foram experimentados, analisados e comparados estatisticamente a fim de verificar sua qualidade e desempenho. Os resultados mostram que os algoritmos propostos são capazes de obter modelos de alta qualidade para fluxos de dados de alta velocidade que precisem ser escalados, mesmo com variações de distribuição e número de grupos.Item Algorithms for infrastructure design for electric vehicles with long-term planning(Universidade Federal de Viçosa, 2021-03-05) Corrêa, Victor Hugo Vidigal; Santos, André Gustavo dos; http://lattes.cnpq.br/2900950652690737The modernization of our lifestyle, originating from the Industrial Revolution in the XVIII century, has led to successive changes in the consumption patterns of the society, raising them to levels never seen before by facilitating the population’s access to various goods in increasingly distant markets from the production centers. With the surge of vehicles powered by fossil fuels, it was possible to dispose of products more quickly to markets all over the world, but with the consequence of the emission, over the years, of tons of CO 2 into the atmosphere, accumulating and causing the phenomenon called global warming which, if not tackled, could cause several negative impacts on the planet’s ecosystem. As one of several measures proposed to combat global warming, the use of electric vehicles has gained a lot of attention in recent years. Its use is particularly interesting for the transport sector, which is responsible for approximately 25% of global pollutant gas emissions. However, due to the particularities of the sector, the adoption of this means of transportation is still economically unattractive, especially due to the absence of an infrastructure network to efficiently operate its use. To optimize the construction of this infrastructure, this study aimed to present an algorithm aimed at reducing costs, considering a long-term planning of deliveries from a logistics company. Two algorithms are presented, one solves the short-term problem considering factors such as battery replacement, partial recharging, time windows and capacitated vehicles while the second, composed of 3 steps and based on the first, solves the problem considering long-term planning. The algorithms are tested with instances created based on real data from the United Kingdom and the State of Minas Gerais and, by the results obtained in the computational experiments, they were able to reduce the average costs in the long-term operational planning of deliveries by electric vehicles by 5.25% if compared to the algorithm for the problem that does not consider long-term planning. Keywords: Electric Vehicles. Logistics Infrastructure. Metaheuristics.Item Algoritmos de otimização multi-objetivo para o problema de Roteamento de Veículos com janelas de tempo(Universidade Federal de Viçosa, 2015-11-20) Aquino, Rafael de Freitas; Arroyo, José Elias Cláudio; http://lattes.cnpq.br/7457762561793045O Problema de Roteamento de Veículos com Janelas de Tempo (PRVJT) é uma variação do problema clássico de Roteamento de Veículos em que as demandas dos clientes devem ser atendidas dentro de uma janela de tempo estabelecida. Neste trabalho, aborda-se o PRVJT objetivando a otimização simultânea de múltiplos objetivos. Os objetivos a serem minimizados são: distância total de percurso dos veículos, desequilíbrio nas distâncias percorridas e desequilíbrio das cargas dos veículos. Já que o problema é NP-Difícil, para determinar uma aproximação das soluções Pareto-ótimas, propõe-se duas abordagens heurísticas. A primeira abordagem é baseada na meta-heurística Iterated Local Search, que utiliza uma etapa de intensificação a qual consiste na combinação de soluções dominantes. A segunda abordagem é um algoritmo genético com uma fase de intensificação baseada na heurística de busca local Iterated Greedy, que consiste em melhorar as soluções dominantes. Os desempenhos dos algoritmos heurísticos foram testados em um conjunto de instâncias disponíveis na literatura, denominado Solomon’s benchmarks, e os resultados foram comparados com os resultados de dois algoritmos multiobjetivos da literatura. Os resultados obtidos foram analisados estatisticamente e observou-se um desempenho superior dos algoritmos propostos.Item Algoritmos de posicionamento e roteamento baseados em travessia de grafo para arquiteturas reconfiguráveis de grão grosso (CGRA)(Universidade Federal de Viçosa, 2021-02-19) Canesche, Michael; Ferreira, Ricardo dos Santos; http://lattes.cnpq.br/2682801945729306A desaceleração da lei de Moore e o fim da escalabilidade de Dennard, criou no- vos desafios para prover desempenho, flexibilidade e eficiência energética na área de arquitetura de computadores. Processadores de propósito geral (CPUs), unidades de processamento gráfico (GPUs) e processadores de sinais digitais (DSPs) oferecem flexibilidade, mas possuem baixa eficiência energética. Circuitos integrados de apli- cação específicas (ASICs) possuem uma alta eficiência energética, mas uma baixa fle- xibilidade. Arranjos de portas programáveis (FPGAs) tem eficiência e flexibilidade, entretanto requerem a necessidade de conhecimento especializado em hardware e em linguagens de descrição e o tempo de compilação leva de minutos a horas. Por outro lado, arquiteturas reconfiguráveis de grão grosso (CGRAs) apresentam flexibilidade próxima a um FPGA e sua eficiência energética é próxima a um ASIC. Entretanto, ainda faltam ferramentas para a popularização dos CGRAs, dentre elas podemos ci- tar os algoritmos de posicionamento e roteamento (P&R). Esta dissertação apresenta dois algoritmos de P&R baseados em travessia de grafos para CGRA. O primeiro algo- ritmo introduz um novo percurso em Zigzag que explora a correlação entre as saídas, uma implementação em GPU e uma exploração sistemática do espaço de soluções. Os resultados mostraram uma aceleração de até 502x sem perda de qualidade em comparação ao estado da arte. O segundo algoritmo propõe uma nova abordagem de travessia capaz de explorar as reconvergências presentes nos grafos. Os resultados mostraram que a solução reduziu o comprimento dos fios em 7%, o tamanho máximo das filas em 2 vezes e melhorou o tempo de execução em até 4 vezes comparado com o primeiro algoritmo. Palavras-chave: Arquiteturas Reconfiguráveis. CGRAs. Posicionamento. Roteamento.Item Algoritmos exatos e heurísticos para o problema de roteamento duplo de veículos com múltiplas pilhas e demanda heterogênea(Universidade Federal de Viçosa, 2017-03-07) Chagas, Jonatas Batista Costa das; Santos, André Gustavo dos; http://lattes.cnpq.br/2185647848891762Este trabalho aborda dois problemas de roteamento de veículos de coleta e entrega com restrições de carregamento. Primeiramente foi tratado o Problema de Rotea- mento Duplo de Veículos com Múltiplas Pilhas (Double Vehicle Routing Problem with Multiple Stacks - DVRPMS). Posteriormente foi formulado e proposto o Problema de Roteamento Duplo de Veículos com Múltiplas Pilhas e Demanda Heterogênea (Double Vehicle Routing Problem with Multiple Stacks and Heterogeneous Demand - DVRPMSHD), se referindo a um caso mais realista do DVRPMS, quando os clientes têm demandas múltiplas e heterogêneas, sendo que toda a demanda de um mesmo cliente deve ser transportada por um único veículo. Em ambos os problemas, o objetivo é determinar rotas para uma frota de veículos a fim de atender a demanda de um conjunto de clientes de forma que a distância percorrida pelos veículos seja a mínima possível, respeitando algumas restrições de carregamento impostas pelas pilhas de armazenamento dos veículos. Todos os produtos localizados em uma região de coleta devem ser coletados e depois entregues em uma região de entrega pelos veículos. As regiões de coleta e entrega são largamente separadas, portanto todos os produtos devem ser carregados antes de qualquer descarregamento. O DVRPMS foi abordado principalmente por quatro métodos heurísticos, os quais foram testados em diversas instâncias e comparados aos métodos exatos e heurísticos já existentes na literatura. Os experimentos computacionais mostraram a eficiência dos algorit- mos propostos, obtendo soluções de melhor qualidade que as soluções apresentadas na literatura para a maioria dos casos de teste com baixo tempo computacional. Já o DVRPMSHD foi abordado de forma exata e heurística. Inicialmente, foi desen- volvido um método exato branch-and-price que apresentou maior eficiência quando comparado à formulação matemática também proposta para o problema. O método heurístico superou os resultados alcançados pelo branch-and-price para a maioria das instâncias de teste formuladas.Item Análise de sentimento por meio de aprendizado profundo aplicado a avaliações de hotéis(Universidade Federal de Viçosa, 2018-09-04) Souza, Joana Gabriela Ribeiro de; Oliveira, Alcione de Paiva; http://lattes.cnpq.br/9732055157884831Análise de Sentimentos é uma área ativa de pesquisa e tem apresentado resultados promissores. Existem na literatura diversas abordagens capazes de realizar diferentes tipos de classificação com boa precisão. Tivemos como objetivo principal deste trabalho o desenvolvimento de modelo que utilize redes neurais artificiais, mais especificamente modelos baseados nas arquiteturas relacionadas com o aprendizado profundo, para a tarefa de classificação de polaridade de avaliações de hotéis escritas em Língua Portuguesa. Dois modelos de redes neurais convolucionais foram desenvolvidos para realizar a tarefa de classificação de polaridades. O primeiro consistiu em uma rede convolucional que possuía 15 camadas alcançando precisão acima de 95% para as classificações das classes positiva e negativa isoladamente e mantendo o balanceamento entre as classes, e acima de 90%, 67% e 80% para as classes positiva, neutra e negativa, respectivamente. O segundo foi baseado no primeiro, porém com adequações de hiper-parâmetros, redução e realocação de camadas, utilização de um vetor representação de palavras maior (200 dimensões) e de um corpus cerca de 10 vezes maior em quantidade de reviews e com número de tokens por review também superior, com arquitetura com 10 camadas. Essas modificações na estrutura permitiram obter resultados ainda melhores do que os observados no primeiro modelo, na maioria dos casos. Diferente do primeiro modelo, neste segundo foi possível classificar as avaliações conforme as 5 classes do TripAdvisor e a partir de amostra recolhida do corpus classificada por voluntários, fizemos um comparativo entre os resultados alcançados utilizando nosso modelo e a classificação gerada pelas pessoas, apontando que apenas em um caso as pessoas obtiveram maior precisão do que o modelo desenvolvido.Item Análise espacial do grau de estadiamento do câncer de pulmão na região assistida pelo Hospital do Câncer de Muriaé(Universidade Federal de Viçosa, 2022-10-04) Barros, Myrian Nascimento de; Lisboa Filho, Jugurta; http://lattes.cnpq.br/2827034456534126O câncer é um dos problemas de saúde pública mais complexos que o sistema de saúde brasileiro enfrenta, dada a sua magnitude epidemiológica, social e econômica, sendo a segunda principal causa de morte no mundo. O câncer de pulmão, segundo estimativas de 2020, é o terceiro tipo mais comum em homens e o quarto em mulheres no Brasil e no mundo é o primeiro. O tabagismo e a exposição passiva ao tabaco são importantes fatores de risco para o desenvolvimento de câncer de pulmão. O diagnóstico tardio, com a doença em estágio avançado, diminui a expectativa de vida do paciente. Diante desse contexto, o presente trabalho objetiva a análise espacial de dados geográficos, das microrregiões assistidas pelo Hospital do Câncer de Muriaé (HCM), visando identificar o grau de estadiamento do câncer do pulmão, utilizando ferramentas de geoprocessamento, disponíveis no Sistema de Informação Geográfica (SIG), para a análise dos dados obtidos. Adicionalmente, foi realizada uma análise estatística das características demográficas e clínicas dos pacientes com câncer de pulmão. Para tanto, foram analisados os prontuários de pacientes atendidos no HCM, nos anos de 2019 e 2020, com diagnóstico clínico de câncer pulmonar. Para isso, o processo ETL (Extract, Transform and Load) apresentou-se como uma importante ferramenta na carga dos dados para o banco de dados, e na etapa de identificação das coordenadas geográficas (latitude e longitude), a partir de informações de bairro, cidade e estado, contidas na base de dados. No período do estudo foram identificados 351 casos de câncer de pulmão, em 90 cidades assistida pela instituição, sendo 84 municípios do estado de Minas Gerais, com 339 casos, e seis municípios do estado do Rio de Janeiro, com 12 casos. A partir do levantamento dos dados no HCM foi possível, por meio do georreferenciamento e uso de ferramentas de análise e mapeamento espacial, a geração de mapas temáticos apresentando diversas relações entre fatores geográficos e epidemiológicos da doença, configurando como um importante instrumento para apoio a ações de prevenção e controle epidemiológico da instituição de saúde. Palavras-chave: Câncer de Pulmão. Incidência. ETL. Análise Espacial. Estatística.Item Anotação semântica automática por meio de redes neurais profundas para corpora na língua inglesa(Universidade Federal de Viçosa, 2019-11-28) Silva, Roberta Caroline Rodrigues; Oliveira, Alcione de Paiva; http://lattes.cnpq.br/7236985482391957A anotação semântica permite que pessoas e dispositivos computacionais entendam mais facilmente o significado de uma sentença expressa em linguagem natural. Classificar textos de acordo com seu conteúdo é frequentemente uma das primeiras etapas realizadas por aplicativos voltados para o processamento de linguagem natural. E, apesar de ser um princípio básico, este passo é feito, geralmente, de forma manual, o que faz com que o processo seja lento, custoso e limitado. Para que a anotação seja realizada automaticamente, os métodos devem ser bem definidos por meio de um conjunto de características ou features, elaborado por especialistas, a fim de que o sistema possa atribuir probabilidades e fazer inferências. Nesta dissertação é apresentado um modelo de rede recorrente profunda que anota semanticamente textos escritos em inglês, e manipula como rótulo categorias de uma ontologia de nível topo. Os testes mostraram que é possível obter melhores resultados do que os encontrados em modelos que precisam do fornecimento prévio de features. Palavras-chave: PLN. Anotação Semântica. Rede Neural Recorrente. LSTM. Ontologia.Item Aplicação de heurísticas para solucionar cenários de média escala do problema do mochileiro viajante(Universidade Federal de Viçosa, 2017-03-08) Oliveira, Matheus Roberti Ribeiro; Santos, André Gustavo dos; http://lattes.cnpq.br/8377952874332914Nesta dissertação é apresentado o Problema do Mochileiro Viajante, sendo este um problema multicomponente composto da combinação de outros dois problemas bastante conhecidos e estudados pela comunidade acadêmica: o Problema do Caixeiro Viajante e o Problema da Mochila. Todo problema multicomponente possui duas características importantes: combinação e interdependência. A combinação existe porque um problema multicomponente deve ser composto de dois ou mais problemas individuais de otimização. A interdependência ocorre quando a combinação desses subproblemas torna- os capazes de afetar o resultado um do outro, como consequência, se forem resolvidos separadamente e suas melhores soluções individuais colocadas em união, não levarão, necessariamente, à melhor solução para o problema completo. Na definição do problema aqui tratado, a interdependência age através do impacto no tempo para percorrer a rota escolhida conforme diversos itens, com pesos específicos, são coletados (ou não) nas cidades onde estão localizados. Esse problema foi proposto através de uma discussão teórica sobre a distância encontrada entre os problemas enfrentados pelas indústrias e corporações, por vezes compostos por diversos subproblemas, e a maneira como, em geral, os pesquisadores tentam solucioná-los individualmente, impossibilitando assim uma visão maior do cenário onde se encontram e no impacto do relacionamento entre eles. Neste trabalho são realizados diversos estudos sobre a maneira como a interdependência dos componentes do PMV afeta o espaço de busca do mesmo, havendo propostas de heurísticas para solucioná-lo apenas com base em seus dados de entrada e de uma meta-heurística capaz de iniciar uma busca com uma solução inicial previamente fornecida e melhorá-la significativamente através de uma exploração de parte desse espaço de busca, sendo o percurso dessa exploração guiado por outra heurística que usa conhecimentos sobre a forma que os componentes do problema interagem entre si. Experimentos computacionais e análises estatísticas foram realizados para que as heurísticas aqui propostas pudessem ser melhor adaptadas para solucionar um conjunto de instâncias com as mais diversas características. Os resultados obtidos após esses experimentos são comparados com os resultados encontrados em outros três trabalhos presentes na literatura, revelando uma maior eficácia por parte das heurísticas aqui propostas quando cenários de pequeno e médio tamanho são selecionados.Item Aplicação de metaheurísticas para o problema de programação da produção em ambiente Assembly Flowshop com três estágios e tempos de preparação dependentes da sequência(Universidade Federal de Viçosa, 2015-02-25) Campos, Saulo Cunha; Arroyo, José Elias Claúdio; http://lattes.cnpq.br/6503693002598015Este trabalho aborda o problema Assembly flowshop de três estágios, onde existem m máquinas paralelas no primeiro estágio, uma máquina de transporte no segundo estágio e uma máquina de montagem no terceiro estágio. No primeiro estágio, diferentes partes do produto são fabricadas de forma independente nas máquinas paralelas. No segundo estágio, as peças fabricadas são coletadas e transferidas para o próximo estágio. No terceiro estágio as peças são montadas obtendo o produto final. Este problema possui muitas aplicações em indústrias de manufatura e pertence a classe de problemas de otimização combinatória NP-difícil. Para resolução deste problema é realizada uma abordagem mono-objetivo e uma multi-objetivo, onde a primeira visa encontrar uma sequência de n tarefas que minimize o atraso total, enquanto a segunda busca encontrar uma sequência de n tarefas para minimização simultânea do tempo total de fluxo e do atraso total. Para abordagem mono-objetivo são propostos quatro diferentes algoritmos baseados nas metaheurísticas: o GRASP-RVND, que corresponde a aplicação conjunta das metaheurísticas GRASP (Greedy Randomized Adaptive Search Procedure) e RVND (Random Variable Neighborhood Descent), o ILS (Iterated Local Search), o IG (Iterated Greedy) e o ILS-IG (que corresponde a aplicação conjunta das metaheurísticas ILS e IG). Foram realizados experimentos computacionais para comparar a eficiência dos algoritmos e os resultados obtidos são comparados com os resultados de um algoritmo PSA (Simulated Annealing Híbrido) da literatura. Nos experimentos foram usadas instâncias de pequeno e grande porte. Os resultados dos algoritmos também foram comparados com os resultados obtidos por um modelo de Programação Linear Inteira (MILP) para instâncias de pequeno porte. Os resultados foram analisados estatisticamente e os testes mostram que os algoritmos propostos foram superiores ao PSA em todas as classes de instâncias. Para a abordagem multiobjetivo são propostos dois algoritmos genéticos híbridos, obtidos a partir da aplicação combinada das metaheurísticas NSGA-II (Non-dominated Sorting Genetic Algorithm-II) e IG, sendo que, um deles utiliza uma busca local para melhorar as soluções dominantes. Os algoritmos foram comparados com o algoritmo tradicional NSGA-II. A análise estatística aplicada sobre os resultados obtidos mostra que houve grande melhoria em relação aos resultados gerados pelo NSGA-II.Item Aprendendo currículos para humanos com busca em árvore guiada por rede neural(Universidade Federal de Viçosa, 2021-12-17) Nova, João Gabriel Gama Vila; Lelis, Levi Henrique Santana de; http://lattes.cnpq.br/7972321254986061Este trabalho avalia Levin Tree Search (LTS) como um modelo para aprender currículos para pessoas. Nós hipotetizamos que a ordem em que LTS aprende a resolver um conjunto de problemas pode ser usada para formar um currículo que auxilia o aprendizado de humanos. Nós avaliamos LTS em dois esquemas de aprendizagem de currículos. Primeiro, ordenamos um pequeno conjunto de instâncias de problemas de acordo com a ordem em que LTS as resolve enquanto aprende uma política neural. Segundo, usamos LTS para ordenar um grande conjunto de instâncias de problemas e selecionamos um subconjunto deste para formar um currículo. Nós avaliamos o currículo que LTS gera através de um estudo com usuários em que os participantes aprendem a resolver uma classe de puzzles do jogo The Witness. Resultados computacionais mostram que a ordem que LTS encontra para o conjunto de instancias do jogo é a mesma ordem escolhida pelo game designer do jogo. O resultado do estudo com usuários sugere que o currículo que nosso sistema gera se compara favoravelmente com currículos de base em termos de retenção de usuário e número de tentativas para que se consiga resolver uma instância. Nossos experimentos computacionais e estudos com usuários sugerem que LTS utilizando uma política neural pode ser usada como um efetivo modelo de geração de currículos de ensino para auxiliar o aprendizado de pessoas em problemas de decisão sequencial. Palavras-chave: Educação. Busca em Árvore. Jogos.Item Aprendendo estratégias programáticas através de características comporta- mentais(Universidade Federal de Viçosa, 2023-02-24) Aleixo, David da Silva; Lelis, Levi Henrique Santana de; http://lattes.cnpq.br/3878423140335445Nos últimos anos, a pesquisa em síntese de estratégias programáticas tem despertado bastante interesse dos pesquisadores por gerar programas que podem ser interpretados por humanos, sendo até mesmo possível modificá-los manualmente. Entretanto, sinteti- zar estratégias programáticas é uma tarefa desafiadora devido à necessidade de realizar uma busca não diferenciável em um grande espaço de programas. Deste modo, utiliza-se atualmente uma abordagem de self-play para guiar a busca. No entanto, essa abordagem geralmente fornece um fraco sinal para guiar a busca, uma vez que o self-play só é ca- paz de avaliar o desempenho de um programa em relação a outros programas. Assim, enquanto pequenas mudanças em um programa podem não melhorar o seu desempenho, tais mudanças podem representar passos na direção de um programa mais eficiente. Nessa dissertação, apresentaremos duas abordagens que utilizam características comportamen- tais para guiar a busca. A primeira utiliza as características comportamentais provenien- tes de um oráculo através do processo de clonagem comportamental para aprender um sketch de uma estratégia programática. Em nossos experimentos, observamos que até mesmos oráculos fracos podem prover informações úteis, ajudando na síntese. Testamos nossa proposta de aprendizado de sketch juntamente com os algoritmos de busca Simu- lated Annealing e UCT como sintetizadores. Com isso, tentamos sintetizar as melhores respostas aproximadas para uma estratégia tradicional do Can’t Stop e para o vencedor da competição de 2020 do MicroRTS. Nosso método foi capaz de sintetizar estratégias programáticas mais fortes do que os oráculos originais e derrotaram as estratégias alvo. Em nossa segunda abordagem, propomos um algoritmo de busca de dois níveis que busca concorrentemente no espaço de programas e em um espaço de características comporta- mentais. Nossa hipótese é que um algoritmo de self-play em conjunto com uma função baseada em características pode gerar um forte sinal para auxiliar a síntese. Enquanto ambas as funções são usadas para guiar a pesquisa no espaço do programa, a função de self-play é usada para guiar a pesquisa no espaço de características, com o objetivo de permitir a seleção de características com maior probabilidade de levar a programas vitoriosos. Testamos nossa hipótese no MicroRTS, um jogo de estratégia em tempo real. Nossos resultados mostram que a busca de dois níveis sintetiza estratégias mais fortes do que métodos que buscam apenas no espaço do programa. Além disso, as estratégias que nosso método sintetiza obtiveram a maior taxa de vitórias em um torneio simulado com vários agentes, incluindo os melhores agentes das duas últimas competições do MicroRTS. Palavras-chave: Inteligência Artificial. Síntese de Programas. Algoritmo de Busca. Jogos.Item Arcabouço para detecção online de outliers para algoritmos de agrupamento em fluxos contínuos de dados(Universidade Federal de Viçosa, 2017-07-31) Pereira, Mariana Alves; Naldi, Murilo Coelho; http://lattes.cnpq.br/2723336078404906Avanços da tecnologia acarretam na geração rápida e contínua de massivas quantida- des de dados. Tal cenário requer a criação de algoritmos de agrupamento incremen- tais para extração de conhecimento. Entre as restrições impostas a esses algoritmos, os mesmos devem ser capazes de detectar e tratar possíveis outliers que chegam ao fluxo. O arcabouço desenvolvido nesse trabalho apresenta uma estratégia para a restrição de tratamento e detecção de outliers na componente online dos algoritmos de agrupamento de fluxo de dados. A principal contribuição da proposta em estudo é a capacidade de validar possíveis outliers detectados previamente, com o intuito de manter um modelo sempre atualizado e com qualidade. Para isso, todos os potenci- ais outliers são armazenados em uma memória auxiliar que de tempos em tempos é verificada, agrupando seus objetos, validando os micro-grupos formados por inliers e inserindo-os no modelo. Todos os objetos restantes que não foram validados, são mantidos na memória auxiliar até que se tornem válidos ou obsoletos. Em seguida, objetos obsoletos são removidos. Este trabalho também propõe o CluStreamOD, uma extensão do algoritmo de agrupamento CluStream, que aplica a estratégia em estudo em sua componente online, para tratar outliers. Os experimentos realizados mostram a eficácia do CluStreamOD para detecção e tratamento online de outliers do fluxo em comparação com CluStream, e a potencialidade da abordagem proposta para ser aplicada em outros algoritmos de fluxo de dados baseados em micro-grupos.Item Arquiteturas em hardware para monitoramento exato e apro- ximado do tempo de chegada entre pacotes em redes de computadores(Universidade Federal de Viçosa, 2016-10-05) Pacífico, Raycus Delano Garcia; Nacif, José Augusto MirandaO monitoramento de redes é um campo ativo em pesquisas na área de redes de computadores. Entretanto, com a propagação da Internet e a criação de novos serviços de rede, realizar tarefas de monitoramento de um grande volume de tráfego de ma- neira acurada e em tempo real tornou-se algo complexo e difícil de ser realizado. Isto ocorre devido a maioria das abordagens tradicionais de medição serem implementa- das em software na extremidade da rede. Esta abordagem gera alto custo e dificulta o monitoramento devido a configuração e implantação do software individualmente em cada nó. Medir de maneira acurada e em tempo real é importante, pois é pos- sível detectar falhas na rede, ataques e verificar a qualidade de serviços fornecidos pelos provedores de Internet em tempo real. Neste trabalho apresentamos duas ar- quiteturas de medição em hardware para o monitoramento exato e aproximado da métrica tempo de chegada entre pacotes. Ambas arquiteturas realizam tarefas de monitoramento em tempo real independente dos nos hospedeiros da rede e rodam sobre a plataforma NetFPGA 1G. 0 objetivo deste trabalho é comparar a acurácia e a escabilidade de ambas arquiteturas. Para o protótipo de monitoramento exato utilizamos o projeto OpenFlow. Estendemos este projeto e realizamos medições que não eram possíveis de ser realizadas em abordagens tradicionais, por exemplo, medição de regras com agregador de fluxo. Para o protótipo de monitoramento aproximado, estendemos o projeto Reference Nic. Este projeto foi transformado em um framework de medição que escala independente do número de fluxos. Com os resultados obtidos, a arquitetura de monitoramento exato apresenta uma diferença relativa de 28 fluxos quase nula em relação a um software na extremidade da rede. Isso significa, que a arquitetura mede de maneira acurada como uma aplicação na folha da rede, com a diferença de não ser necessário instrumentar os nós hospedeiros. A arquitetura de monitoramento aproximado, entretanto, apresenta uma diferença relativa de 1% a 20% de 2.000 fluxos em relação ao software. Esta arquitetura mede um volume de fluxos 70 vezes maior que a arquitetura exata sacrificando a acurácia pela escabilidade.Item Asymmetric Action Abstractions for Real-Time Strategy Games(Universidade Federal de Viçosa, 2019-02-08) Filho, Rubens de Oliveira Moraes; Lelis, Levi Henrique Santana de; http://lattes.cnpq.br/1137970319452572Action abstractions restrict the number of legal actions available for real-time plan- ning in zero-sum extensive-form games, thus allowing algorithms to focus their search on a set of promising actions. Optimal strategies derived from un-abstracted game trees are guaranteed to be no worse than optimal strategies derived from action-abstracted game trees. In practice, however, due to real-time constraints and the game tree size, one is only able to derive good strategies in un-abstracted trees in small-scale games. In this paper, we introduce an action abstraction scheme we call asymmetric abstraction. Asymmetric abstractions can retain the un-abstracted trees’ theoretical advantage over regularly abstracted trees while still allowing search algorithms to derive effective strategies, even in large-scale games. Further, asym- metric abstractions allow search algorithms to “pay more attention” in some aspects of the game by unevenly dividing the algorithm’s search effort amongst different as- pects of the game. In this paper we also introduce four algorithms that search in asymmetrically-abstracted game trees to evaluate the effectiveness of our abstrac- tion schemes. Two of those are greedy-search approaches and they are called Greedy Alpha-Beta Search and Stratified Alpha-Beta Search. The other two are versions of an algorithm we call Asymmetrically Action-Abstracted NaïveMCTS (A2N and A3N) and combine Monte Carlo Tree Search (MCTS) algorithms, naïve sampling strategy for select actions’ samples, and asymmetric abstraction scheme. In addi- tion to the search algorithms, we also introduce several strategies for generating asymmetric abstractions. An extensive set of experiments in a real-time strategy game developed for research purposes shows that search algorithms using asymmet- ric abstractions are able to outperform all other search algorithms tested.Item Atributos e métodos de qualidade para sistemas de informação geográfica voluntária(Universidade Federal de Viçosa, 2016-10-27) Câmara, Jean Henrique de Sousa; Lisboa Filho, Jugurta; http://lattes.cnpq.br/3434955624811089A difusão de dispositivos equipados com GPS como smartphones e tablets e a facilidade em manipular mapas online estão simplificando a produção e disseminação de informações geográficas fornecidas de forma voluntária (VGI) por meio da Internet. Os sistemas VGI coletam e distribuem este tipo de informação e podem ser usados, por exemplo, em casos de desastres naturais, mapeamento, gestão municipal etc. Em alguns casos, os sistemas VGI precisam ser implementados em um curto espaço de tempo, como no atendimento a emergências em casos de desastres naturais. Algumas ferramentas, como as plataformas Ushahidi e ClickOnMap, foram projetadas para possibilitar o desenvolvimento rápido de sistemas VGI. A qualidade dos dados coletados por estes sistemas pode ser questionada, mas em algumas situações não existem dados oficiais ou eles estão desatualizados. Assim, é necessário que estas plataformas ofereçam métodos que possam auxiliar o usuário a produzir ou informar dados voluntariamente com qualidade. Este trabalho apresenta um estudo sobre os principais atributos de qualidade que podem ser aplicados no contexto de VGI. Além disto, identifica-se na literatura os principais métodos que contribuem com o aumento da qualidade VGI. Este estudo resultou em um conjunto de 19 atributos e 26 métodos de qualidade relacionados à VGI. O trabalho ainda propõe seis métodos que podem auxiliar na obtenção de dados com melhor qualidade. Dez métodos de qualidade VGI foram implementados na plataforma ClickOnMap dando origem à plataforma ClickOnMap 2.0. Foi desenvolvido um sistema VGI, denominado Gota D’ Água, com o auxílio da ClickOnMap 2.0. O objetivo deste sistema foi coletar e disponibilizar informações voluntárias relacionadas ao desperdício de água como vazamentos, uso indevido, desvios ilegais dentre outros. Por meio do Gota D’ Água, verificou-se que os métodos propostos neste trabalho realmente podem ser aplicados em sistemas VGI para melhorar o nível de qualidade destas informações.