PPGCC - Programa de Pós-graduação em Ciência da Computação

URI permanente desta comunidadehttp://www.hml.repositorio.ufop.br/handle/123456789/596

Navegar

Agora exibindo 1 - 20 de 151

Uma abordagem centrada em dados para reconhecimento de fala em português : modelo de língua e suas implicações.
(2023) Alvarenga, João Paulo Reis; Luz, Eduardo José da Silva; Luz, Eduardo José da Silva; Merschmann, Luiz Henrique de Campos; Silva, Rodrigo César Pedrosa
Os avanços mais recentes no Reconhecimento Automático de Fala permitem alcançar uma qualidade jamais antes vista em línguas com dados abundantes, tais como o inglês, e em línguas com dados limitados, como o português. Em particular, abordagens baseadas em modelos de Transformers permitem realizar a tarefa de reconhecimento de fala diretamente a partir da representação do sinal bruto. Alguns estudos já indicam que a qualidade da transcrição pode ser melhorada ainda mais com o uso de modelos de linguagem. No entanto, o impacto real destes modelos ainda não está claro para o português brasileiro, assim como a importância da qualidade dos dados usados para treinar os modelos. Por isso, este trabalho explora o impacto dos modelos de linguagem aplicados ao reconhecimento de fala para língua portuguesa, tanto em termos de qualidade de dados quanto de desempenho computacional, com uma abordagem centrada em dados. Uma abordagem para medir a similaridade entre conjuntos de dados é proposta para auxiliar na tomada de decisão durante o treinamento. Os resultados mostram que é possível reduzir o tamanho do modelo de linguagem em ~80% e ainda alcançar taxas de erro por palavra em torno de 7,17% para o conjunto de dados Common Voice.
Uma abordagem de particionamento hardware e software para design de wearables em hardware reconfigurável.
(2018) Guimarães, Rodolfo Labiapari Mansur; Oliveira, Ricardo Augusto Rabelo; Oliveira, Ricardo Augusto Rabelo; Silva Júnior, Diógenes Cecílio da; Nacif, José Augusto Miranda
As tecnologias em microeletrônica, sensores e comunicação móvel têm sido constantemente melhoradas a medida que a informação torna-se mais necessária. Tornam-se um estímulo para o desenvolvimento de sistemas computacionais inteligentes e conectados como sistemas embarcados, IoTs ou wearables, visto pelo rápido desenvolvimento desses para o mercado. Tais dispositivos utilizam vários sensores e necessitam de um servi co autônomo, o que implica numa grande demanda de desempenho somado com o baixo consumo de energia. Entretanto ainda com a dificuldade de satisfazer os requisitos de aumento de desempenho e redução de consumo energético das várias aplicações autônomas modernas. Análise de desempenho no uso de FPGA com particionamento em hardware para sistemas embarcados têm sido fortemente abordada pela comunidade acadêmica. Entretanto, não há trabalhos científicos que trabalham o particionamento para sistemas wearable. Esta pesquisa tem como objetivo o aprimoramento de desempenho de dispositivos computacionais wearables em hardwares reconfiguráveis, visando alocação de recursos em hardware e reduzindo o consumo energético, isso utilizando particionamento hardware e software como meio. Os resultados mostram que e possível obter maior desempenho em sistemas wearables utilizando plataforma FPGA apenas com a realocação de algoritmos candidatos em hardware.
Uma abordagem evolucionária para o problema escalonamento de tarefas em máquinas idênticas paralelas com limitações de ferramentas.
(2018) Soares, Leonardo Cabral da Rocha; Carvalho, Marco Antonio Moreira de; Carvalho, Marco Antonio Moreira de; Toffolo, Túlio Ângelo Machado; Arroyo, José Elias Claudio
O Problema de Escalonamento de Tarefas em Máquinas Flexíveis Paralelas Idênticas com Restrições de Ferramentas, consiste em alocar tarefas a um conjunto de máquinas flexíveis paralelas, com o objetivo de minimizar o tempo máximo de processamento das tarefas pelas máquinas. Especificamente, as tarefas possuem tempo de processamento igual em qualquer máquina, porém, possuem tempo de preparo prévio que depende de todas as tarefas anteriores sequenciadas na mesma máquina, devido a configurações de ferramentas nas máquinas flexíveis. Neste trabalho, este problema NP-Difícil é abordado utilizando-se a metaheurística paralela Algoritmo Genético de Chaves Aleatórias Viciadas hibridizada com procedimentos de busca local organizados em uma Descida em Vizinhança Variável. São apresentados resultados inéditos para um conjunto de 2880 instâncias da literatura, incluindo resultados ótimos para 12,31% entre as menores instâncias. O método proposto é comparado ao atual estado da arte e obtém 91,81% das melhores soluções. Novas melhores soluções são apresentadas para 52,75% do total de instâncias. Adicionalmente, o método proposto apresenta tempo de execução 92,69% menor, dominando assim o atual estado da arte.
Abordagem exata e heurísticas para o problema de planejamento de ordens de manutenção de longo prazo : um estudo de caso industrial de larga escala.
(2018) Aquino, Roberto Dias; Souza, Marcone Jamilson Freitas; Chagas, Jonatas Batista Costa das; Souza, Marcone Jamilson Freitas; Chagas, Jonatas Batista Costa das; Carvalho, Marco Antonio Moreira de; Souza, Sérgio Ricardo de
Este trabalho propõe uma modelagem de programação linear inteira mista e algoritmos meta-heurísticos para um problema real de planejamento de manutenção de longo prazo para uma planta de beneficiamento de minério de ferro no Brasil. Este é um problema complexo de programação de ordens de manutenção preventiva, para o qual é necessário atribuir ordens de manutenção preventiva para as equipes de trabalho disponíveis em um horizonte de 52 semanas. Foi desenvolvido um modelo de programação inteira mista e os resultados foram utilizados como um benchmark. Como o modelo não foi capaz de resolver a instância real, foram propostos algoritmos meta-heurísticos para resolvê-la. Esses algoritmos foram baseados nos métodos Simulated Annealing, Variable Neighborhood Search, Multi-Start, Biased Random-Key Genetic Algorithm e algoritmos meméticos. Os algoritmos heurísticos desenvolvidos foram capazes de resolver a instância real, assim como melhorar a maioria dos resultados das instâncias de dimensões menores, levando a novos benchmarks.
Uma abordagem híbrida para resolver o problema da escala de motoristas de ônibus urbano.
(2014) Souza, Danilo Santos; Silva, Gustavo Peixoto
A alocação da tripulação (motoristas e cobradores) é uma etapa muito importante no planejamento operacional do Sistema de Transporte Público visto que custo operacional representado pelas escalas de trabalho compõe uma parcela significativa nos custos totais de uma empresa de transporte público. A redução dos custos das escalas de trabalho afetam não são as empresas operadoras, mas também os usuários deste serviço, pois com esta redução há a possibilidade de um maior investimento na qualidade do transporte público e a redução dos preços dos bilhetes. Estes custos, estão estritamente relacionados as normas operacionais impostas pelas empresas e legislações trabalhistas que se retém na definição das jornadas de trabalho dos motoristas e cobradores. Esse trabalho tem a finalidade de propor um novo método computacional capaz de auxiliar o processo da programação da tripulação em empresas de transporte público de ônibus urbano. Os métodos apresentados nesta pesquisa são baseados no uso de um modelo de programação linear inteira, ainda inédito na literatura, se diferindo dos demais pelo fato de que cada jornada e gerada diretamente a partir das tarefas a serem alocadas. Uma metaheurística Late Acceptance Hill Climbing (LAHC) também foi utilizada com o objetivo de resolver problemas de maiores dimensões. Um método híbrido, utilizando o método exato e a metaheurística LAHC, é proposto com o objetivo de obter um refinamento das soluções obtidas pela metaheurística, de modo a reduzir os custos das jornadas geradas. Para avaliar as abordagens apresentadas foram utilizadas instâncias geradas a partir de dados reais de uma empresa do setor de transporte público da cidade de Belo Horizonte/MG. Os modelos computacionais propostos apresentaram resultados satisfatórios, sendo que os custos finais foram reduzidos para a maioria dos testes realizados. Por outro lado, há a necessidade de novos estudos sobre os métodos apresentados, afim de que os mesmos se tornem mais eficientes.
Uma abordagem para estimar a similaridade item-item baseada nos relacionamentos semânticos da Linked Open Data.
(2019) Pereira, Ítalo Magno; Ferreira, Anderson Almeida; Ferreira, Anderson Almeida; Pereira Junior, Álvaro Rodrigues; Rodrigues, Lívia Couto Ruback
A época atual está sendo vista como uma era de sobrecarga de informação, uma vez que mais dados são produzidos do que humanos podem processar. Este fato implica na melhoria constante de sistemas de recuperação e tratamento de informação. Inserido neste contexto, os sistemas de recomendação são ferramentas importantes aos usuários, por sugerir itens que possam ser interessantes. No entanto, os sistemas de recomendação baseados em filtragem colaborativa sofrem com o problema conhecido como cold start ou falta de dados iniciais. A opção para contornar esse problema é explorar outras fontes de dados, como a Linked Open Data (LOD), para enriquecer os dados. Contudo, muitas soluções baseadas na LOD não fazem uso dos relacionamentos semânticos e, quando o fazem, não ponderam corretamente seus relacionamentos e, assim, não exploram o seu potencial. Este trabalho visa apresentar uma abordagem para explorar os relacionamentos semânticos da Linked Open Data, por meio da descoberta de características relevantes e ponderação de tais características sem intervenção de um especialista de domínio de aplicação. Para avaliar a proposta, foram realizados experimentos em dois domínios de aplicação, domínio de filmes e museus. Os resultados mostraram-se competitivos comparados a outras abordagens, onde a seleção de propriedades relevantes é feita manualmente.
Um algoritmo baseado na metaheurística late acceptance hill-climbing para o planejamento operacional de lavra.
(2014) Silva, Arthur de Assis; Souza, Marcone Jamilson Freitas
Este trabalho trata um problema particular de planejamento de lavra de uma mineradora localizada no quadrilátero ferrífero do Estado de Minas Gerais, Brasil. Neste problema há um conjunto de frentes de lavra, um conjunto de equipamentos de carga de diferentes produtividades, um conjunto de caminhões de diferentes capacidades e um conjunto de pontos de descarga para o material lavrado. Cada frente de lavra é subdividida em blocos, os quais, por sua vez, são subdivididos em sub-blocos. Cada sub-bloco pode conter um dentre quatro tipos de material: hematita, canga, itabirito e estéril. Além disso, cada sub-bloco somente pode ser lavrado se os sub-blocos precedentes tiverem sido totalmente lavrados. A cada ponto de descarga está associada uma meta de produção e uma qualidade de material a ser atendida. O objetivo é determinar a alocação das carregadeiras aos blocos e o número de viagens que cada caminhão deve fazer a cada sub-bloco, saindo de um determinado ponto de descarga, de forma a atender as metas de produção e qualidade estabelecidas para cada descarga. Para resolvê-lo foi desenvolvido um algoritmo heurístico baseado nas metaheurísticas Greedy Randomized Adaptive Search Procedures (GRASP) e Late Acceptance Hill-Climbing (LAHC). O algoritmo explora o espaço de soluções usando busca locais autoadaptativas. Experimentos computacionais comparam os resultados do algoritmo proposto com aqueles do otimizador LINGO aplicado a um modelo de programação linear inteira mista e mostram a efetividade da proposta.
Um algoritmo de estimação de distribuição para otimização multiobjetivo baseado em colônia de abelhas e clusters.
(2013) Novais, Fabiano Tomás; Guimarães, Frederico Gadelha
Neste trabalho, propõem-se um novo algoritmo híbrido denominado Multiobjective Optimization Estimation of Distribution Algorithm Based on Bee Colonies and Clusters (MOEDABC) para resolução de problemas de otimização multiobjetivo de larga escala no domínio contínuo. Este algoritmo é inspirado na organização de uma colônia de abelhas e baseia-se nos algoritmos de estimação de distribuição. Como forma de gerar melhores soluções utiliza-se também técnicas de clusterização com a finalidade de aumentar a convergência local das soluções na fronteira Pareto. O algoritmo é baseado em quatro tipos de abelhas: as campistas, as observadoras, as nutrizes e as escoteiras, onde cada uma utiliza uma forma diferente de gerar as novas soluções. Combinando diferentes técnicas como clusterização, estimação de distribuição e algoritmos genéticos possibilitou-se um melhor aprendizado por meio de modelos probabilísticos baseados em distribuições Gaussianas e de Cauchy, obtendo assim soluções de maior qualidade. Em busca de obter maior flexibilidade do algoritmo na resolução de problemas foi introduzido um feromônio de controle responsável por controlar a proporção de cada tipo de abelhas na colônia. Comparado com outros algoritmos os resultados obtidos demonstram que o algoritmo proposto apresenta uma maior velocidade de convergência e uma melhor distribuição das soluções na fronteira Pareto conforme os indicadores utilizados.
Um algoritmo híbrido para resolução de problemas binários.
(2015) Rezende, Josiane da Costa Vieira; Souza, Marcone Jamilson Freitas; Martins, Alexandre Xavier; Souza, Sérgio Ricardo de
Este trabalho apresenta um método híbrido, denominado HGVPRLB, para resolver problemas lineares binários. O método combina os procedimentos Greedy Randomized Adaptive Search Procedures -- GRASP, Variable Neighborhood Descent -- VND, propagação de restrições, e cortes Local branching. Como em todo algoritmo GRASP, o método HGVPRLB apresenta duas fases, que interagem entre si até que o tempo limite seja atingido. A primeira fase visa a construção de uma solução inicial; a segunda, por sua vez, visa ao refinamento dessa solução construída. Na fase de construção, é utilizado o resolvedor CBC e um procedimento de propagação de restrições, de forma a gerar uma solução inicial para o problema. O resolvedor CBC relaxa as variáveis binárias, isto é, atribui o valor de cada variável no intervalo real [0,1]. O procedimento propagação de restrições possui a finalidade de verificar se existe solução viável ao se fixar uma determinada variável no valor 1. Se esta solução existir, ele poderá retornar, ainda, um conjunto de possíveis fixações das demais variáveis. Na fase de refinamento são utilizados cortes Local branching controlados pelo procedimento VND até que um tempo previamente definido seja atingido. Os cortes Local Branching utilizam um resolvedor de programação linear inteira como uma ferramenta caixa-preta para explorar eficientemente subespaços das soluções do problema. O método desenvolvido foi aplicado a um conjunto de problemas binários da biblioteca MIPLIB 2010 com o intuito de verificar sua capacidade de obter soluções viáveis de qualidade variando-se o tempo de processamento. Os experimentos computacionais realizados mostraram que, quando o tempo de processamento aumenta, o método consegue aumentar tanto o número de soluções viáveis quanto a qualidade delas. Além disso, o método desenvolvido se mostrou superior a outro método da literatura, bem como a dois outros resolvedores de código aberto nesses dois indicadores de avaliação.
Algoritmos de aprendizado de máquina para previsão de tempo da manutenção de vagões.
(2022) Felix, Josemar Coelho; Silva, Rodrigo César Pedrosa; Silva, Rodrigo César Pedrosa; Bianchi, Andrea Gomes Campos; Nucci, Edson Romano; Pereira, Robson Bruno Dutra
A análise do planejamento de manutenção, com o objetivo de criar predições sobre a capacidade produtiva, é uma importante aliada na gestão industrial. A Engenharia de Métodos dispõe da ferramenta denominada cronoanálise, utilizada desde 1856, para avaliar a capacidade industrial. Essa ferramenta tem como base a cronometragem e análise subjetiva de várias atividades envolvidas nas atividades de produção da manutenção. Contudo, o próprio processo de cronometragem tende a afetar o tempo de execução, comprometendo a sua estimativa. Nesse contexto, este trabalho investiga a aplicação de métodos baseados em aprendizado de máquina para a avaliação da capacidade de restaurar vagões em oficinas da MRS Logística, e, ainda, comparar com a aplicação da cronoanálise utilizada atualmente pela empresa. Para tal, foram disponibilizados dados de 2019 sobre a manutenção de vagões. Esses dados serviram para a construção dos modelos de predição desta pesquisa. Foram reservados os dados de nove meses para treinamento, de três meses para testes e também realizou-se a validação cruzada utilizando cinco subdivisões. Com o auxílio do planejamento de experimentos e testes estatísticos de Friedman e Nemenyi, foi possível constatar que, os algoritmos de aprendizado de máquina, são capazes de produzir modelos com melhor qualidade quando combinados com a cronoanálise na liberação de vagões restaurados, comprovado pelas métricas denominadas Erro Médio Absoluto e Raiz Quadrada do Erro Médio.
Algoritmos exatos e heurísticos para a resolução do problema da descoberta de cliques de peso máximo.
(2015) Vilas Boas, Matheus Guedes; Santos, Haroldo Gambini
O presente trabalho trata do projeto, implementação e avaliação de algoritmos exatos e heurísticos, sequenciais e paralelos, para a resolução do problema da enumeração de cliques com peso acima de um limiar (PECPL). Esse problema considera um grafo com vértices ponderados, onde o objetivo é encontrar todos os cliques maximais com peso acima de um limiar. Os algoritmos estudados neste trabalho são aplicados na separação de cortes no contexto de Programação Inteira. Encontrar todos os cliques acima de um dado peso é equivalente ao problema de encontrar todas as desigualdades violadas de clique. Foram desenvolvidas adaptações em algoritmos conhecidos na literatura para a resolução do problema. Para o algoritmo de Bron-Kerbosch, uma adaptação foi realizada para resolver o PECPL. Além disso, várias melhorias foram propostas a fim de melhorar a eficiência na resolução das instâncias do problema. Foram propostas uma versão iterativa do algoritmo, originalmente recursivo, e uma versão paralela. O algoritmo de Ostergard e a heurística busca tabu com multi-vizinhanças também foram implementados e modificados para refletir o problema abordado no presente trabalho. Porém, a metaheurística Simulated Annealing foi proposta e desenvolvida utilizando-se as mesmas estruturas de vizinhança utilizadas na heurística busca tabu com multivizinhanças. A diferença das duas técnicas está na estratégia de resolução do problema: enquanto a primeira utiliza-se do conceito de lista tabu, a ultima simula o processo de recozimento de metais. Nos experimentos computacionais, foram utilizadas 7292 instâncias, oriundas de quatro conjuntos referentes à separação de cortes em problemas formulados por meio do uso de programação inteira. Os experimentos foram conduzidos em duas partes: em um primeiro momento, as instâncias foram utilizadas para resolução do PECPL. Posteriormente, o foco foi a resolução do problema do clique de peso máximo (PCPM). Quanto à resolução do PECPL, os resultados obtidos comprovam a eficiência do algoritmo de Bron-Kerbosch, quando comparado aos demais algoritmos, ao encontrar a solução ótima para todas as instâncias e em um tempo consideravelmente menor do que as outras técnicas. Quando a análise dos resultados foi direcionada à resolução do PCPM, todas as técnicas implementadas obtiveram bons resultados, com destaque para a heurística busca tabu com multi-vizinhanças, a qual resolveu todas as instâncias de forma ótima, com o menor tempo computacional em relação às demais abordagens. Como trabalhos futuros, são sugeridos a adoção de operadores lógicos para a representação do grafo no algoritmo de Bron-Kerbosch, a melhoria da versão paralela do algoritmo e o estudo do projeto das metaheurísticas Simulated Annealing e busca tabu.
Algoritmos heurísticos híbridos para o problema de sequenciamento em máquinas paralelas não-relacionadas com tempos de preparação dependentes da sequência.
(Programa de Pós-Graduação em Ciência da Computação. Departamento de Ciência da Computação, Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto., 2012) Haddad, Matheus Nohra; Souza, Marcone Jamilson Freitas
Este trabalho aborda o problema de sequenciamento em máquinas paralelas não- relacionadas com tempos de preparação dependentes da sequência, dó inglês Unre- lated Parallel Machine Scheduling Problem with Sequence Dependent Setup Times, ou apenas UPMSPST. Neste problema há um conjunto de tarefas e máquinas e a cada tarefa está associado um tempo de processamento, que é diferente para cada máquina. Dadas duas tarefas, também existe um tempo de preparação dependente da sequência de lase da máquina utilizada. O objetivo considerado neste problema é minimizar o tempo máximo de conclusão do sequenciamento, o chamado makes pan. OUPMSPST é muito encontrado no âmbito industrial e pertence à classe NP- difícil. Visando a sua resolução, são propostos três algoritmos heurísticos híbridos. O primeiro, nomeado VP, combina os procedimentos heurísticos Iterated Local Search (ILS), Variable Neighborhood Descent (VND)e Path Relinking(PR). O segundo, nomeado GIVP, difere do primeiro pelo fato de gerar a solução inicial pela fase de construção Greedy Randomized AdaptiveS earch Procedure(GRASP), e não por um procedimento guloso. O terceiro algoritmo, nomeado GIVMP, diferedos outros em três estratégias: a fase PR utiliza a estratégia mix edrelinking ao invés de backward relinking, as vizinhanças que formam o VND são usada sem ordem aleatória a cada chamada e não em ordem previamente de nida; por m,o GIVMP inclui um módulo de busca local feita pelo resolvedor CPLEX12.1 de programação matemática. Este resolvedor é aplicado apenas à máquina gargalo do problema e utiliza um modelo de programação inteira mista base a dono problemado Caixeiro Viajante Assimétrico. Para explorar o espaço de soluções são utilizados movimentos de inserção e troca de tarefas entre máquinas. Para testar os algoritmos foram utilizados dois conjuntos de problemas-teste da literatura. Inicialmente eles foram comparados entre si em um conjunto reduzido de instâncias ,tendo- severi cado a superioridade do algoritmo GIVMP. Em seguida, este algoritmo foi compara do com outros seis da literatura, sendo dois no primeiro conjunto de problemas- teste e outros quatro no Segundo. No primeiro conjunto veri cou-se a superiorida de absoluta do GIVMP sobre os dois algoritmos genéticos da literatura, tendo-se encontra do desvios percentuais relativos médios menores e novas melhores soluções.No segundo conjunto de problemas-teste vericou-se que o GIVMP tem desempenho inferior a um dos algoritmos, mas superior em relação aos outros três. Observa-se,no entanto,que neste segundo conjunto de problemas, não foram disponibilizados os desvios percentuais relativos médios dos algoritmos, mas apenas os desvios dos melhores valores encontrados,impedindo uma comparação de robustez dos algoritmos.
Algoritmos heurísticos para o problema de roteamento de unidades móveis de mamografia.
(2021) Rosa, Otávio Augusto Souza; Souza, Marcone Jamilson Freitas; Penna, Puca Huachi Vaz; Souza, Marcone Jamilson Freitas; Penna, Puca Huachi Vaz; Coelho, Igor Machado; Carvalho, Marco Antonio Moreira de
Este trabalho introduz o Problema de Roteamento de Unidades Móveis de Mamografia (MMURP). Este problema consiste em roteirizar um conjunto de Unidades Móveis de Mamografia (MMU) para atender a demanda de localidades desprovidas de mamógrafos fixos ou com número insuficiente deles. O objetivo é maximizar a demanda atendida e minimizar a distância total percorrida pelas MMUs. Para tratar o problema, propomos os algoritmos Smart IGS-VND e Smart IGS-RVND, ambos baseados na metaheurística Iterated Greedy Search. Nestes algoritmos, uma solução inicial é gerada por meio de um procedimento de três passos. Para refinar uma solução, usamos os procedimentos Randomized Variable Neighborhood Descent (RVND) e Variable Neighborhood Descent (VND). Para não ficar preso em ótimos locais e explorar diferentes regiões do espaço de soluções do problema, aplicamos um procedimento para destruir a solução atual e outro para construí-la de forma gulosa. Para testar os algoritmos propostos, usamos instâncias com 579 localidades, dois depósitos, até 56 MMUs e 180 km entre dois locais no máximo. Realizamos os testes considerando três cenários diferentes. Esses cenários diferem entre si pelo número de localidades candidatas a serem atendidas, o número de MMUs disponíveis em cada depósito e a capacidade dessas MMUs. Os resultados mostraram que os dois algoritmos encontraram soluções que atendem integralmente a demanda da região estudada. O Smart IGS-VND obteve um melhor desempenho para encontrar um valor alvo de demanda previamente definido. No entanto, quando foram comparadas a distância total percorrida pelas MMUs com a cobertura de exames, o Smart IGS-RVND mostrou ser capaz de encontrar soluções de melhor qualidade, reduzindo a distância total percorrida pelos veículos. No último cenário, apresentamos um plano de serviço mensal para uma MMU, variando de um a doze meses.
Algoritmos meta-heurísticos para o problema dial-a-ride.
(2019) Souza, André Luyde da Silva; Penna, Puca Huachi Vaz; Souza, Marcone Jamilson Freitas; Penna, Puca Huachi Vaz; Souza, Marcone Jamilson Freitas; Santos, André Gustavo dos; Toffolo, Túlio Ângelo Machado
Este trabalho trata do problema Dial-a-Ride, que consiste em fazer rotas para veículos com a finalidade de transportar pacientes de diferentes locais para realizar exames médicos em unidades de tratamento de saúde. O Dial-a-Ride é uma extensão do Problema de Roteamento de Veículos, possuindo características do Problema de Roteamento de Veículos com Janela de Tempo e do Problema de Roteamento de Veículos com Coleta e Entrega, combinados com restrições relativas aos pacientes. O trabalho considera a forma estática do problema e utiliza dados obtidos da Prefeitura Municipal de Ouro Preto-MG para modelagem e contextualização do problema. Para resolvê-lo, propõe-se dois algoritmos heurísticos, MS-VNS1 e VNS2, ambos baseados na meta-heurística Variable Neighborhood Search (VNS). O primeiro, MSVNS1, é guiado pela meta-heurística Multi-Start tendo como busca local o VNS. O segundo, por sua vez, é guiado apenas pelo VNS. Nos dois algoritmos o método de busca local do VNS é o procedimento heurístico Randomized Variable Neighborhood Descent (RVND), o qual usa os movimentos de realocação, troca e cruzamento para explorar o espaço de soluções do problema. Os resultados computacionais foram obtidos pela aplicação dos algoritmos em um conjunto de instâncias da literatura e comparados com os das melhores soluções desta variante do problema. Apesar de simples, os algoritmos desenvolvidos foram capazes de encontrar a solução ótima para algumas instâncias e soluções de boa qualidade para as demais. Os algoritmos também foram testados em um conjunto de instâncias criadas a partir de dados fornecidos pela Prefeitura Municipal de Ouro Preto-MG. Ambos se mostraram capazes de atender as demandas da cidade de Ouro Preto de forma automatizada, proporcionando ao setor de transporte da prefeitura uma ferramenta que possibilita reduzir os custos com o transporte de pacientes e diminuir a alocação de funcionários para cumprir essa atividade.
Algoritmos multiobjetivos para o problema de sequenciamento de tarefas em uma máquina com tempo de preparação dependente da sequência e da família.
(Programa de Pós-Graduação em Ciência da Computação. Departamento de Ciência da Computação, Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto., 2013) Rego, Marcelo Ferreira; Souza, Marcone Jamilson Freitas
Este trabalho trata do Problema de Sequenciamento de Tarefas em Uma Máquina com Tempo de Preparação Dependente da Sequência e da Família. Nesse problema, um conjunto de tarefas devem ser processadas por uma máquina, sendo que antes da execução de cada tarefa é necessário um tempo para preparar a máquina, o qual é de nido de acordo com a sequência e a família da tarefa. Desta forma, o tempo de preparação da máquina é requerido, apenas, para executar duas tarefas consecutivas que pertencem a famílias diferentes. Consideram-se os objetivos de minimizar o makespan e o atraso total ponderado. Para resolvê-lo, foram analisados sete algoritmos de otimização multiobjetivo. O primeiro é o Multi-objective Variable Neighborhood Search (MOVNS), que é um método de otimização multiobjetivo baseado na metaheur ística Variable Neighborhood Search (VNS). O segundo e o terceiro são duas variantes do MOVNS encontradas na literatura, denominadas MOVNS_Ottoni e MOVNS_Arroyo, que consistem em adicionar um procedimento de intensi cação no MOVNS. O quarto é o Pareto Iterated Local Search (PILS), que é um algoritmo multiobjetivo de busca local com características semelhantes à metaheurística Iterated Local Search (ILS). O quinto é uma variante do PILS proposta neste trabalho, denominada PILS1, em que um novo procedimento de perturbação é desenvolvido. O sexto e o sétimo são o Nondominated Sorting Genetic Algorithm II (NSGA-II) e o Strength Pareto Evolutionary Algorithm 2 (SPEA2), os quais são métodos de otimização baseados no processo de evolução natural para problemas multiobjetivos. Entre os sete algoritmos, cinco são de busca local: MOVNS, MOVNS_Ottoni, MOVNS_Arroyo, PILS e PILS1, e outros dois são de busca populacional: NSGA-II e SPEA2. Esses algoritmos foram comparados em relação às métricas de cardinalidade, distância média, distância máxima, diferença de hipervolume e epsilon. Os resultados computacionais realizados em instâncias-teste geradas aleatoriamente mostraram que o algoritmo PILS1 é estatisticamente superior a todos os outros algoritmos em relação às métricas cardinalidade, distância média, diferença de hipervolume e métrica epsilon, em termos de resultados médios. O PILS1 conseguiu também o melhor resultado médio para a métrica distância máxima; entretanto, a partir da análise estatística não foi possível a rmar que a diferença observada entre ele o NSGA-II era signi cativa.
Alocação de canais em redes WLAN considerando a utilidade marginal total da conexão para usuários.
(2015) Luiz, Thiago Alcântara; Freitas, Alan Robert Resende de; Guimarães, Frederico Gadelha
Redes locais sem fio (WLAN) têm sido amplamente utilizadas nos últimos anos. A fim de atender um número crescente de usuários, estas redes têm cada vez um número maior de pontos de acesso (access points ou AP) que operam em uma área reduzida, sem atenção suficiente para a seleção do canal de operação. A sobreposição de canais entre APs vizinhos é o principal fator de degradação do desempenho da rede para os usuários. No entanto, o número limitado de canais não sobrepostos disponíveis torna o problema de alocação de canais difícil. Os modelos de alocação de canais encontrados na literatura geralmente ignoram a qualidade de conexão dos usuários, e adotam, por exemplo, apenas o nível de interferência total no ambiente ou percentual de usuários submetidos a algum nível de interferência. Neste trabalho, propomos um novo modelo de alocação que visa encontrar um mapeamento de canais para os APs que compõem uma rede WLAN, com o objetivo de maximizar a qualidade total de conexão dos usuários considerando a Utilidade Marginal. O conceito de utilidade envolve a satisfação de um usuário em relação a qualidade da sua conexão, estimado pela intensidade de sinal recebida pelo AP e as perdas causadas pela interferência. Os resultados obtidos utilizando Algoritmos Evolutivos, um algoritmo de busca local e Algoritmos Meméticos contrapõem os modelos de alocação que desconsideram a qualidade de conexão e priorizam alguns usuários gerando grande desequilíbrio na distribuição das velocidades de conexão, pois, não adotam a degradação causada pelos níveis de interferência na conexão dos usuários separadamente.
Análise de combinação de classificadores usando uma abordagem multiobjetivo baseada em acurácia e número de classificadores.
(Programa de Pós-Graduação em Ciência da Computação. Departamento de Ciência da Computação, Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto., 2013) Tinôco, Sandro Luiz Jailson Lopes; Gomes, David Menotti
O Sensoriamento Remoto é uma forma de obter informações sobre a Terra a partir do espaço, com a finalidade de melhorar a gestão dos recursos naturais, o uso da terra e a proteção do meio ambiente. Esse campo do conhecimento tem se beneficiado dos diversos avanços tecnológicos dentre os quais pode ser citada a imagem hiperespectral. Este tipo de imagem pode ser composto por centenas de bandas, cada uma delas correspondendo a uma determinada faixa do espectro eletromagnético. Pode-se perceber a riqueza de informação que tal imagem pode fornecer, conduzindo a uma análise mais precisa. No entanto, para tratar esse volume de informações, tanto em qualidade quanto em quantidade, é necessária a utilização de algoritmos e métodos que consigam tirar proveito de toda a informação fornecida. Uma tarefa comum na análise desses dados é a geração de mapas temáticos a partir da classificação da cobertura terrestre. Tradicionalmente, procura-se desenvolver diferentes algoritmos de classificação e depois aquele que apresenta o melhor desempenho, ou seja maior acurácia, é escolhido. Este tipo de metodologia pode acarretar em perdas de importantes informações contidas nos classificadores descartados. Uma forma de se evitar isso, que tem sido bastante estudada e utilizada atualmente, é a combinação de múltiplas abordagens de classificação e a consequente produção de mapas temáticos mais precisos. No presente trabalho, é feita a combinação de doze abordagens de classificação, obtidas usando três representações de dados e quatro algoritmos de aprendizagem diferentes. As representações de dados usadas são a Pixelwise, Extended Morphological Profiles (EMP) e Feature Extraction by Genetic Algorithms (FEGA), que foram classificadas com os algoritmos de aprendizagem Support Vector Machines (SVM) com kernel Radial Basis Function (RBF) e kernel Linear, K-Nearest Neighbor (KNN) e Multilayer Perceptron Neural Network (MLP). O método de combinação proposto é baseado em uma combinação linear ponderada, em que um Programa Linear Inteiro (PLI) encontra os pesos para cada abordagem de classificação utilizada e é denominado Weighted Linear Combination optimized by Integer Linear Programming (WLC-ILP). Para analisar os resultados obtidos, o método proposto foi comparado a outros métodos de combinação como o Weighted Linear Combination optimized by Genetic Algorithm (WLC-GA) e, os tradicionais, como Majority Vote (MV) e Average Rule. O (WLC-ILP) superou os resultados dos métodos (MV) e Average Rule e obteve resultados similares ao (WLC-GA), porém, dez vezes mais rápido que este. Uma questão ainda em aberto está relacionada a quantos e quais classificadores de um conjunto utilizar, de forma a obter uma acurácia mais precisa. Não se sabe ao certo o que faz uma combinação produzir resultados, ainda que não seja sempre garantido, melhores do que um único classificador. Alguns autores apontam a diversidade de um conjunto como fator principal de êxito de um combinador, no entanto, não existe uma definição formal, amplamente aceita do que seja diversidade. Uma vez que é desejável produzir melhores acurácias utilizando o menor número de classificadores possível, um Algoritmo Genético Multiobjetivo apresenta-se como meio adequado para realização desta tarefa.
Análise de receitas visando a descoberta de conhecimento sobre pratos gastronômicos.
(2015) Rodrigues, Edwaldo Soares; Pereira Junior, Álvaro Rodrigues; Pereira Junior, Álvaro Rodrigues; Merschmann, Luiz Henrique de Campos; Carvalho, José Renato; Paiva, Débora Maria Barroso
Nos dias atuais, a internet tem desempenhado um importante papel em toda a sociedade, facilitando a realização de serviços e tendo diversos fins. Um dos serviços que surgiram a partir da internet foram os sistemas colaborativos, onde diversos usuários criam o conteúdo dos sistemas por meio de experiências pessoais. Um dos vários sistemas colaborativos existentes atualmente são os de compartilhamento de receitas gastronômicas. A área da Recuperação da Informação na Web tem crescido o interesse no que diz respeito a recuperar as informações contidas nesse ambiente e estudá-las de forma a identificar relações como os principais ingredientes utilizados no preparo de um prato, que podem ser identificadas por meio do uso de técnicas de Mineração de Dados textuais. Nesse escopo, o presente trabalho propõe o desenvolvimento de uma metodologia de descoberta de conhecimento em receitas gastronômicas, usando receitas coletadas de diversas fontes de dados. Para isso, informações como os ingredientes, quantidades, unidades de medida, instruções de preparo e outras características associadas as receitas são descobertas. Com os resultados encontrados e avaliados por meio do estudo de caso e das experimentações apresentadas nesta dissertação, este trabalho representa um primeiro passo para o desenvolvimento de um servi co que, além de agregar receitas de diversas fontes, explora o conhecimento coletivo que pode ser descoberto ao se analisar centenas de milhares de receitas disponíveis na rede.
Análise e otimização do problema de roteamento de veículos com muitos objetivos e janelas de tempo flexíveis.
(2015) Matsueda, Lucas Carvalho Oliveira; Freitas, Alan Robert Resende de; Guimarães, Frederico Gadelha
Para explorar a interseção entre problemas de roteamento de veículos propostos na literatura, esta dissertação propõe um problema de roteamento de veículos com muitos objetivos e janelas de tempo flexíveis (MOPRV). É proposta uma abordagem baseada em dois algoritmos evolucionários multiobjetivo (NSGA-II e NSGA-III) e um método para a redução e visualização de objetivos (Árvores de Agregação) é proposta. Através de um estudo sobre a harmonia e conflito entre os objetivos do problema, foi observada a possibilidade de agregação entre os mesmos, reduzindo o problema de seis para três objetivos. Os experimentos demonstram que as soluções para o problema reduzido possuem bons valores para todos os objetivos quando comparado com as soluções do problema completo. Mais ainda, os resultados demonstram que é mais vantajoso visualizar a relação entre os objetivos do MOPRV e em seguida otimizar o problema com menos objetivos do que tentar otimizar diretamente o problema considerando todos os objetivos do MOPRV.
Aquisição de imagens digitais e identificação dos ovos do mosquito Aedes Aegypti baseado em um modelo de aprendizado profundo.
(2019) Garcia, Pedro Saint Clair; Cámara Chávez, Guillermo; Cámara Chávez, Guillermo; Ferreira, Anderson Almeida; Bianchi, Andrea Gomes Campos; Saúde, André Vital
O mosquito Aedes aegypti pode transmitir algumas doenças, o que faz o estudo da proliferação deste vetor uma tarefa necessária. Com o uso de armadilhas feitas em laboratório, denominadas ovitrampas, é possível mapear a deposição de ovos numa determinada comunidade. Uma máquina fotográfica acoplada a uma lupa foi utilizada para adquirir imagens contendo os elementos (ovos) a serem contados. Essas imagens foram processadas a partir de um sistema de cores com o objetivo de encontrar a cor negra, que corresponde `a cor dos ovos. A partir dessas imagens já trabalhadas, foi realizado um processo de transferência de aprendizado com uma rede neural convolucional (CNN). A intenção era separar os elementos que realmente eram ovos dos demais. Por meio desse método, foi possível identificar cada ovo como um simples objeto. Em 90% das imagens testadas a contagem realizada pelo modelo em relação ao número real de ovos foi considerada de correlação perfeita. Para as demais 10% das imagens de teste, a contagem foi considerada de forte correlação, isso aconteceu em imagens que continham uma alta densidade de ovos ou que continham elementos negros que se pareciam com ovos do mosquito.