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
13 resultados
Resultados da Pesquisa
Item 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 deEste 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.Item 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 ClaudioO 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.Item Discretizador heurístico para o contexto de classificação hierárquica.(2016) Galvão, Leandro Ribeiro; Merschmann, Luiz Henrique de Campos; Silla Júnior, Carlos Nascimento; Pappa, Gisele Lobo; Ferreira, Almeida FerreiraDiferentes tipos de problemas de classificação podem ser encontrados na literatura, cada qual possuindo seu nível de complexidade. Diversos algoritmos de aprendizado de máquina requerem atributos discretos e nesses casos o pré-processamento da base de dados né necessário. Na literatura, os trabalhos apresentam diversos métodos de discretização, porém até o momento, não há nenhum método de discretização supervisionado projetado para ser utilizada em conjunto com classificadores hierárquicos globais. Neste trabalho é proposto um método supervisionado de discretização capaz de lidar com bases do contexto de classificação hierárquica. Esse método corresponde a uma heurística, denominada Agglomerative Discretization Heuristic for Hierarchical Classification - ADH2C, que foi projetada para ser utilizada em conjunto com classificadores hierárquicos globais. A avaliação da qualidade da discretização realizada pela heurística ADH2C foi feita a partir de experimentos comparativos com métodos de discretização não-supervisionados Equal-Width (EW) e Equal-Frequency (EF). A qualidade da discretização foi medida por meio do desempenho preditivo pelo classificador hierárquico Global Model Naive Bayes (GMNB) utilizando-se 9 bases de dados de bioinformática pré-processadas pelos métodos de discretização EW, EF e ADH2C. Os experimentos realizados neste trabalho mostraram que para a maioria das bases de dados utilizadas, o classificador GMNB alcançou o melhor desempenho preditivo (hF) quando utilizou as bases de dados pré-processadas pela heurística ADH2C. A melhora no desempenho preditivo do GMNB, utilizando as bases de dados pré-processadas pela heurística ADH2C, evidencia sua aplicabilidade no contexto de classificação hierárquica monorrótulo.Item Desenvolvimento de técnicas de seleção de atributos no contexto da classificação hierárquica monorrótulo.(2015) Dias, Thieres Nardy; Merschmann, Luiz Henrique de CamposA seleção de atributos, tradicionalmente adotada como uma etapa de pré-processamento dos dados, tem como objetivo principal identificar os atributos relevantes para a tarefa de classificação. No entanto, para o cenário de classificação hierárquica, onde as classes a serem preditas estão estruturadas de acordo com uma hierarquia, poucos trabalhos na literatura apresentam propostas de técnicas de seleção de atributos. Mais especificamente, para problemas de classificação hierárquica monorrótulo, não foram encontradas na literatura técnicas de seleção de atributos que possam ser utilizadas em conjunto com classificadores hierárquicos globais, ou seja, classificadores que são treinados levando-se em consideração toda a hierarquia de classes de uma só vez. Desse modo, neste trabalho propomos uma adaptação da medida Incerteza Simétrica (Symmetrical Uncertainty { SU) para permitir que ela possa ser utilizada em técnicas de seleção de atributos para problemas de classificação hierárquica monorrótulo que usam classificadores hierárquicos globais. Posteriormente, utilizamos essa adaptação proposta, denominada Incerteza Simétrica Hierárquica (Hierarchical Symmetrical Uncertainty { SUH), em duas técnicas distintas de seleção de atributos: uma que faz uso da abordagem Filtro e outra que segue uma abordagem Híbrida (Filtro e Wrapper). A técnica que implementa a abordagem Híbrida corresponde a uma heurística que utiliza o classificador hierárquico Global-Model Naive Bayes (GMNB) para avaliar os subconjuntos de atributos. A partir das duas técnicas de seleção de atributos propostas neste trabalho, pudemos verificar a adequação da adaptação da medida SU para o cenário hierárquico. Além disso, o método heurístico proposto, nomeado como Hybrid Feature Selection for Hierarchical Classification (HFS4HC), apresentou resultados bastante promissores para o contexto da classificação hierárquica monorrótulo.Item 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 GambiniO 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.Item Grafo de conflitos : construção e aplicações em problemas de programação inteira.(2015) Brito, Samuel Souza; Santos, Haroldo GambiniEste trabalho explora a informação estrutural de relações entre variáveis binárias em problemas de Programação Inteira por meio de grafos de conflitos. Tal estrutura possui um papel fundamental na construção de métodos exatos e heurísticos de resolução. Nesse sentido, o presente trabalho propõe e desenvolve técnicas baseadas na análise de grafos de conflitos para obtenção de soluções factíveis e limites duais fortes para problemas de Programação Inteira. Foram desenvolvidas otimizações nas técnicas de detecção de conflitos, que permitiram a construção rápida de grafos densos mediante a análise de restrições. A obtenção de limites duais fortes para programas inteiros é realizada por uma rotina desenvolvida para geração de desigualdades válidas. Essa rotina é responsável por gerar cortes de clique e ciclo ímpar e inseri-los na relaxação linear, reforçando os limites duais e acelerando a convergência para a solução ótima. Para obter soluções factíveis para programas binários foi desenvolvido um resolvedor heurístico, que utiliza as relações lógicas entre variáveis para construir uma solução inicial e melhorá-la por meio de uma busca local. A busca local executa uma cadeia de movimentos a cada iteração, que permite corrigir a infactibilidade de uma solução ou, até mesmo, saltar de uma solução factível para outra. Considerando a produção de limites duais fortes, os resultados obtidos pela rotina de geração de desigualdades desenvolvida mostraram uma convergência mais rápida em relação à rotina de separação de cortes do resolvedor COINOR Branch-and-Cut. Em relação à obtenção de factibilidade, o resolvedor heurístico foi apto a gerar soluções para um número significativo de problemas de Programação Inteira Binária, considerando tempos restritos de execução.Item Novos algoritmos para o problema de sequenciamento em Máquinas Paralelas não relacionadas com tempos de preparação dependentes da sequência.(2014) Cota, Luciano Perdigão; Souza, Marcone Jamilson FreitasEste trabalho trata o Problema de Sequenciamento em Máquinas Paralelas Não- Relacionadas com Tempos de Preparação Dependentes da Sequência (UPMSPST, do inglês Unrelated Parallel Machine Scheduling Problem with Setup Times), objetivando minimizar o makespan. Para resolvê-lo foram desenvolvidos três algoritmos heurísticos e um algoritmo híbrido. O primeiro algoritmo heurístico, denominado HIVP, tem uma solução inicial gerada por um procedimento construtivo parcialmente guloso baseado no método Heuristic-Biased Stochastic Sampling e na regra Adaptive Shortest Processing Time { ASPT. Essa solução e, posteriormente, refinada pelo procedimento Iterated Local Search { ILS, tendo o Random Variable Neighborhood Descent como método de busca local. Além disso, periodicamente a busca é intensificada e diversificada por meio de um procedimento Path Relinking { PR. No segundo algoritmo heurístico, denominado GIAP, a solução inicial é criada por um procedimento inspirado no Greedy Randomized Adaptive Search Procedures. Nesse segundo algoritmo, a solução é refinada por um procedimento ILS que utiliza como método de busca local o procedimento Adaptive Local Search { ALS. A busca _e também intensificada e diversificada por meio de um procedimento PR. O terceiro e último algoritmo heurístico, denominado AIRP, tem sua solução inicial gerada por um procedimento construtivo guloso baseado na regra ASPT. Essa solução é refinada por um procedimento ILS que tem como busca local um procedimento chamado RIV. De forma análoga aos algoritmos anteriores, a busca também passa por uma intensificação ao e diversificação periodicamente por meio de um procedimento PR. O algoritmo híbrido, denominado AIRMP, tem o funcionamento similar ao do algoritmo heurístico AIRP, diferindo deste por acrescentar um módulo de programação linear inteira mista. Para a aplicação desse módulo são selecionados um par de máquinas e subconjuntos de tarefas nessas máquinas. Esses subconjuntos são combinados e passam por uma busca local que consiste em acionar um resolvedor de programação matemática aplicado a melhor das formulações de programação matemática dentre aquelas estudadas e desenvolvidas. Pelos experimentos computacionais foi possível concluir que o AIRP obteve os melhores resultados dentre os algoritmos heurísticos propostos, conseguindo superar vários outros algoritmos da literatura. Também foram realizados experimentos para comparar os algoritmos AIRMP e AIRP. Como o AIRMP necessita de um tempo maior para acionar o módulo de programação matemática, esses experimentos utilizaram um tempo maior de execução. Observou-se, no entanto, que a adição do módulo de programação matemática não melhorou o desempenho do AIRMP no tempo testado e na estrutura utilizada de subconjuntos de tarefas. Esses testes também mostraram que aumentando-se o tempo de processamento do AIRP, o algoritmo e capaz de encontrar melhores soluções.Item pRINS : uma matheurística para problemas binários.(2014) Gomes, Thiago Macedo; Souza, Marcone Jamilson FreitasUma importante técnica para resolver problemas de otimização é por meio de Programação Inteira Mista (MIP, do inglês Mixed Integer Programming). Uma formulação MIP de um problema envolve um conjunto de variáveis, um conjunto de restrições sobre estas variáveis, um conjunto de restrições de integralidade e uma função objetivo linear a otimizar. Aplicações em otimização inteira são encontradas em diversas àreas do conhecimento, incluindo-se roteamento de veículos, alocação de enfermeiros, programação de horários, entre outros. O uso de métodos heurísticos tem sido empregado na resolução de problemas MIP como uma forma de acelerar o processo de busca na árvore de branching. Este trabalho propõe uma adaptação da heurística MIP Relaxation Induced Neighborhood Search (RINS), que explora a ideia de fixar variáveis de mesmo valor na solução inteira e fracionária corrente. O método proposto, denominado pRINS, explora explicitamente técnicas de pré-processamento, procurando sistematicamente por um número ideal de fixações, visando a produzir sub-problemas de tamanho controlado. As variáveis a fixar são organizadas por meio de um vetor de prioridade, sendo propostas três maneiras de escolha destas variáveis, cada uma delas dando origem a uma variante do método. Em seguida, os problemas são criados e resolvidos de modo semelhante ao método Variable Neighborhood Descent até que um critério de parada seja satisfeito. Os resultados das variantes do método foram comparados com os do resolvedor COIN-OR e CBC stand-alone e com o método RINS original. Pelos resultados obtidos, o método proposto se mostrou com desempenho superior a essas duas técnicas.Item Um algoritmo baseado na metaheurística late acceptance hill-climbing para o planejamento operacional de lavra.(2014) Silva, Arthur de Assis; Souza, Marcone Jamilson FreitasEste 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.Item Metaheurísticas Busca Tabu para o problema de rodízio de tripulações de ônibus urbanos.(2013) Andrade, Suelaine Débora Gonçalves de; Silva, Gustavo PeixotoO Problema de Rodízio das Tripulações (PRT) do sistema de transporte público consiste em atribuir a cada tripulação uma sequência de jornadas para os dias do horizonte de planejamento. Como as jornadas diárias tem durações diferentes, as sequências das jornadas podem resultar em um acúmulo de horas extras ou de horas ociosas. Assim o objetivo do PRT é minimizar as horas extras da escala, compensando-as com ociosidades entre jornadas.Este é o princípio do banco de horas permitido pela legislação, desde que sejam respeitadas as restrições operacionais e leis trabalhistas. Neste trabalho o problema foi resolvido utilizando diferentes implementações do Algoritmo de Busca Tabu. Primeiramente é feita a geração da solução inicial através de uma heurística gulosa. A solução gerada é viável, no entanto os custos são altos. Depois são utilizadas as jornadas criadas e com base em trocas viáveis tenta diminuir o custo de cada rodízio com diferentes versões implementadas de Busca Tabu. Foram implementadas quatro versões: a primeira versão, BTMP, que possui menor tempo da busca local para quando encontra um vizinho melhor; a segunda, denominada BTMV, em que a busca local é efetuada sobre toda a vizinhança; a terceira, BTPV, que utiliza um critério de porcentagem variável para a busca pelo melhor vizinho e a quarta versão BTID, que utiliza critérios de intensificação e diversificação para a Busca Tabu. Ao montar um rodízio, devem ser consideradas as folgas das tripulações ao longo do período. Neste trabalho foi desenvolvido um modelo em dois cenários distintos: um que não considera a atribuição das folgas e outro que realiza esta atribuição. Posteriormente os resultados foram comparados aos obtidos no trabalho de Prates e Silva (2012) através da metaheurística VNS. Os resultados mostram que as implementações do modelo desenvolvido se aproveitam das características de cada etapa, gerando soluções mais econômicas.cada tripulação uma sequência de jornadas para os dias do horizonte de planejamento. Como as jornadas diárias tem durações diferentes, as sequências das jornadas podem resultar em um acúmulo de horas extras ou de horas ociosas. Assim o objetivo do PRT é minimizar as horas extras da escala, compensando-as com ociosidades entre jornadas. Este é o princípio do banco de horas permitido pela legislação, desde que sejam respeitadas as restrições operacionais e leis trabalhistas. Neste trabalho o problema foi resolvido utilizando diferentes implementações do Algoritmo de Busca Tabu. Primeiramente é feita a geração da solução inicial através de uma heurística gulosa. A solução gerada é viável, no entanto os custos são altos. Depois são utilizadas as jornadas criadas e com base em trocas viáveis tenta diminuir o custo de cada rodízio com diferentes versões implementadas de Busca Tabu. Foram implementadas quatro versões: a primeira versão, BTMP, que possui menor tempo da busca local para quando encontra um vizinho melhor; a segunda, denominada BTMV, em que a busca local é efetuada sobre toda a vizinhança; a terceira, BTPV, que utiliza um critério de porcentagem variável para a busca pelo melhor vizinho e a quarta versão BTID, que utiliza critérios de intensificação e diversificação para a Busca Tabu. Ao montar um rodízio, devem ser consideradas as folgas das tripulações ao longo do período. Neste trabalho foi desenvolvido um modelo em dois cenários distintos: um que não considera a atribuição das folgas e outro que realiza esta atribuição. Posteriormente os resultados foram comparados aos obtidos no trabalho de Prates e Silva (2012) através da metaheurística VNS. Os resultados mostram que as implementações do modelo desenvolvido se aproveitam das características de cada etapa, gerando soluções mais econômicas.