Doutorado em Modelagem Matemática e Computacional

URI Permanente para esta coleção

https://repositorio.cefetmg.br//handle/123456789/648

Navegar

Agora exibindo 1 - 8 de 8

Algoritmo GVNS aplicado ao problema das p-medianas capacitado abordagens determinística e robusta
(Centro Federal de Educação Tecnológica de Minas Gerais, 2022-12-20) Vasconcelos, Anderson Moreira; Souza, Marcone Jamilson Freitas; Souza, Sérgio Ricardo de; Sá, Elisângela Martins de; http://lattes.cnpq.br/4686246805500174; http://lattes.cnpq.br/6078945717558464; http://lattes.cnpq.br/6195947972246267; Souza, Marcone Jamilson Freitas; Souza, Sérgio Ricardo de; Sá, Elisângela Martins de; Silva, Maria Amélia Lopes; Haddad, Matheus Nohra; Wanner, Elizabeth Fialho; Menezes, Gustavo Campos
O Problema das p-Medianas Capacitado (PPMC) consiste em localizar p instalações em uma rede composta por n vértices e decidir qual mediana atenderá cada vértice, a fim de minimizar a soma das distâncias dos vértices à mediana a qual ele foi alocado e atender às restrições de capacidade de cada mediana. Considerando que as demandas dos clientes são incertas, é proposta a aplicação de uma abordagem de otimização robusta para lidar com a incerteza nestes parâmetros dando origem ao problema das p-Medianas Robusto Capacitado (PPMRC). Esta tese propõe algoritmos para resolução do PPMC e o PPMRC. Para resolver o PPMC, foram propostas quatro variantes da metaheurística General Variable Neighborhood Search (GVNS), que se diferem no método usado para construir uma solução inicial e nos métodos usados para realizar a busca local. Nas duas primeiras variantes, denominadas G-VND e G-RVND, a solução inicial é gerada de forma aleatória e os métodos de busca local são o Variable Neighborhood Descent (VND) e o Random Variable Neighborhood Descent (RVND), respectivamente. Nas duas últimas variantes, denominadas GG-VND e GG-RVND, a solução inicial é gerada através da fase de construção da metaheurística Greedy Randomized Adaptive Search Procedure (GRASP) e os métodos de busca local são o VND e o RVND, respectivamente. Os resultados de experimentos computacionais usando instâncias da literatura mostraram que o algoritmo GG-RVND apresentou melhor desempenho que os outros três algoritmos. Além disso, os resultados obtidos pelo algoritmo GG-RVND foram melhores do que aqueles da literatura, tanto em termos da qualidade das soluções geradas quanto em relação ao tempo de execução. Para o PPMRC, foi proposto um algoritmo baseado na metaheurística GVNS, com a solução inicial gerada através da fase construtiva do método GRASP e uma busca local realizada via VND. Os experimentos computacionais comparam os resultados do GVNS e as soluções do solver CPLEX. Para realizar esses experimentos computacionais, foram utilizadas instâncias da literatura, variando de 318 nós e cinco medianas a 4461 nós e 1000 medianas. Este estudo considera diversos cenários, valores variados dos parâmetros de robustez e de incerteza na demanda. Os resultados mostram que o Algoritmo GVNS tem um bom desempenho em encontrar boas soluções e supera o solver CPLEX, encontrando soluções melhores mesmo quando aplicado para resolver o conjunto de dados de menor dimensão.
Algoritmos para as versões determinística e robusta do problema de localização de concentradores com maximização do lucro
(Centro Federal de Educação Tecnológica de Minas Gerais, 2024-02-27) Oliveira, Fabricio Alves; Sá, Elisângela Martins de; Souza, Sérgio Ricardo de; http://lattes.cnpq.br/3677015295211434; http://lattes.cnpq.br/4686246805500174; http://lattes.cnpq.br/4686246805500174; Elisângela Martins de Sá; Sérgio Ricardo de Souza; Mateus, Geraldo Robson; Morabito Neto, Reinaldo; Souza, Marcone Jamilson Freitas; Menezes, Gustavo Campos
Esta tese estuda o problema de localização de concentradores, com objetivo direcionado para a maximização do lucro. Esse problema consiste em estabelecer a localização de concentradores, o projeto da rede e a alocação dos nós de demanda aos concentradores para maximizar o lucro total da rede. O problema considera que a rede de concentradores é incompleta, nenhuma estrutura topológica específica é requerida e é assumido que os concentradores e arcos entre concentradores possuem capacidade suficiente para lidar com o fluxo de demanda na rede. Este trabalho apresentou novas formulações e investigou suas propriedades. As formulações propostas assumem a estratégia de alocação múltipla; não impõem quaisquer restrições ao número de concentradores ou arcos entre concentradores instalados na rede; não permitem conexões diretas entre nós não concentradores e permitem que a demanda da rede seja parcialmente satisfeita, sendo atendida apenas quando for rentável. Essa última característica e o foco na maximização do lucro diferenciam o problema abordado nesta tese em relação aos problemas clássicos de localização de concentradores, nos quais a demanda completa entre todos os pares de origem e destino é atendida, e, além disso, os problemas são modelados sob o ponto de vista dos custos. Esta tese também investigou as propriedades e realizou uma análise comparativa das formulações propostas com outra da literatura. Para resolver o problema, foram desenvolvidos algoritmos baseados no método de decomposição de Benders, incluindo várias estratégias de aprimoramento. Uma vez que o problema aqui abordado é NP-difícil, também foram propostos dois algoritmos heurísticos baseados em busca local e troca sistemática de estruturas de vizinhança para solucionar instâncias do problema de grande porte. Para analisar a eficiência dos procedimentos de solução propostos, foram realizados extensivos experimentos computacionais com instâncias de referência na área de localização de concentradores. Os resultados desses testes mostraram que os algoritmos propostos possuem um bom desempenho. Em particular, com o método de decomposição de Benders, foram resolvidas até a otimalidade instâncias com até 150 nós. Por outro lado, com os algoritmos heurísticos, foram solucionadas instâncias contendo até 500 nós. Adicionalmente, foi realizada uma análise das estruturas de vizinhança consideradas nos algoritmos heurísticos e uma comparação estatística entre os dois algoritmos. Nesta tese também foi abordado o problema de localização de concentradores com maximização do lucro em que as demandas e os custos de instalação de concentradores e arcos entre concentradores são incertos. Uma formulação robusta, que permite controlar o grau de conservadorismo do modelo por meio de um budget de incerteza, é desenvolvida para este caso. São apresentadas discussões sobre a influência que a incerteza nos dados tem sobre a configuração da rede e sobre o lucro associado a ela. Para resolver o problema robusto, foram propostos um algoritmo exato baseado em decomposição de Benders e outro heurístico baseado na meta-heurística Iterated Local Search, adaptados dos melhores métodos identificados na resolução do problema determinístico. As soluções obtidas com o problema robusto possuem diferenças significativas em relação às soluções do problema determinístico, o que evidencia a importância de se estudar este tipo de problema, principalmente em aplicações reais. A incerteza nos dados pode levar a necessidade de um redesenho da rede de concentradores, o que influencia diretamente o lucro associado a ela.
Classificação e reconhecimento de padrões: novos algoritmos e aplicações / Emmanuel Tavares Ferreira Affonso
(Centro Federal de Educação Tecnológica de Minas Gerais, 2022-02-28) Affonso, Emmanuel Tavares Ferreira; Silva, Alisson Marques da; Moita, Gray Farias; http://lattes.cnpq.br/2550201329788172; http://lattes.cnpq.br/3856358583630209; http://lattes.cnpq.br/3453401178017064
Este trabalho visa o desenvolvimento de novos algoritmos para tarefas de classificação e reconhecimento de padrões. Inicialmente é proposto um método para seleção de atributos (FS, do inglês feature selection) para classificadores com treinamento offline. A abordagem de FS proposta, chamada de Mean Ratio for Feature Selection (MRFS), é baseada na razão das médias dos atributos em cada classe. MRFS possui baixo custo computacional pois utiliza apenas operações matemáticas básicas como adição, divisão e comparação e realiza apenas uma passagem nos dados para ranquear os atributos. O MRFS foi implementado e avaliado como método filter (MRFS-F) e como wrapper (MRFS-W). O desempenho dos métodos foram avaliados e comparados com o estado da arte. As comparações realizadas sugerem que os métodos propostos possuem um desempenho comparável ou superior aos métodos alternativos. Além dos métodos de FS foram propostos três classificadores evolutivos com treinamento online. O primeiro chamado de evolving Fuzzy Mean Classifier (eFMC) é baseado em um algoritmo de agrupamento fuzzy que realiza a classificação com base no grau de pertinência dos grupos. Novos grupos são criados sempre que uma nova classe é descoberta e a atualização do centro dos grupos é através das médias amostrais calculadas de forma incremental. O segundo classificador introduzido é o evolving Fuzzy Classifier (eFC) que de maneira análoga utiliza as médias amostrais para atualização dos centros dos grupos. Seu diferencial está na capacidade de gerar mais de um grupo associado a uma mesma classe para mapear diferentes regiões do espaço dos dados, criação de novos grupos aplicando o conceito de procrastinação, união de grupos redundantes e exclusão de grupos obsoletos. Por fim, foi proposto um classificador evolutivo com seleção de atributos denominado evolving Fuzzy Classifier with Feature Selection (eFCFS). Este classificador foi construído utilizando o mesmo algoritmo do eFC e incorporando o método MRFS de seleção de atributos. Os classificadores evolutivos propostos foram avaliados e comparados com três classificadores evolutivos alternativos. Os resultados experimentais e as comparações sugerem que os métodos baseados no MRFS para auxiliar modelos com treinamento offline e os 3 modelos evolutivos com treinamento online são promissores como alternativas para tarefas de classificação e reconhecimento de padrões, com boa acurácia e baixo custo computacional.
Desenvolvimento de matrizes de distâncias para representar interações de proteínas combinadas com algoritmos de agrupamento
(Centro Federal de Educação Tecnológica de Minas Gerais, 2023-08-24) Monteiro, Otaviano Martins; Rodrigues, Thiago de Souza; Dias, Sandro Renato; http://lattes.cnpq.br/5300421458375793; http://lattes.cnpq.br/4182923743939851; http://lattes.cnpq.br/5378637011361467; Rodrigues, Thiago de Souza; Dias, Sandro Renato; Gomes, Rogério Martins; Cruz, André Rodrigues da; Menezes, Gustavo Campos; Silva, Alisson Marques da
As proteínas são macromoléculas formadas por aminoácidos e estão presentes em todos os seres vivos. Várias proteínas tiveram suas estruturas tridimensionais resolvidas experimentalmente e foram armazenadas através de arquivos de texto em bancos de dados biológicos como o Protein Data Bank (PDB). Essas informações proteicas podem ser utilizadas por softwares, como o LSQKAB, que verificam similaridades tridimensionais de proteínas através de sobreposições entre os átomos das estruturas comparadas. No entanto, a realização de sobreposições atômicas requer um alinhamento preciso entre os átomos de duas estruturas por meio de movimentos de rotação e translação. Esse procedimento é computacionalmente intensivo, sendo classificado como NP-Completo. Portanto, a realização de múltiplas sobreposições atômicas, algo frequente em softwares que propõem mutações em proteínas, acarreta em um elevado custo computacional. Assim sendo, o propósito deste estudo consiste em elaborar abordagens fundamentadas em matrizes de distâncias, combinadas com algoritmos agrupamento (clustering) com o intuito de criar conjuntos de interações de proteínas que compartilham conformações tridimensionais semelhantes. O objetivo principal é alcançar soluções de alta precisão e desempenho notável, com o propósito de minimizar a necessidade de realizar sobreposições atômicas. Com o intuito de cumprir esses objetivos, foram desenvolvidas matrizes de distâncias baseadas em diferentes abordagens. A Matriz de Ângulos (MA) foi desenvolvida a partir dos ângulos dos átomos. A Matriz de Distâncias Completa Mista (MDCM) foi desenvolvida através da fusão de diferentes técnicas. A Matriz de Distâncias Reduzida cujos Centroides são Carbonos Alfa (MDRCCA), a Matriz de Distâncias Reduzida a partir de um Ponto entre os Carbonos Alfa (MDRPCA), além da Matriz de Pontos Médios (MPM) foram desenvolvidas a partir da importância dos átomos de carbonos alfa (CA). A concepção da MPM também foi influenciada pela importância das distâncias entre todos os átomos na estrutura, uma vez que essas distâncias são cruciais para o enovelamento da mesma. Essas estratégias foram integradas a algoritmos de agrupamento e os resultados subsequentes foram comparados com o método de busca da ferramenta RID, por ser uma ferramenta especialista em trabalhar com interações de proteínas, além da atomic Cutoff Scanning Matrix (aCSM) por ser uma das versões da Cutoff Scanning Matrix (CSM), que é considerada o estado da arte na geração de assinaturas em grafos proteicos, e com a Matriz de Distâncias Completa (MDC), que apresentou resultados superiores ao método de busca da RID e aCSM, nos primeiros trabalhos deste projeto. Os resultados foram satisfatórios, principalmente os alcançados pela MPM, que superou as demais técnicas na maioria dos experimentos.
Design configuration for MMAS algorithm applied for the travelling salesman problem with dynamic demands
(Centro Federal de Educação Tecnológica de Minas Gerais, 2022-06-24) Oliveira, Sabrina Moreira de; Souza, Sérgio Ricardo de; Wanner, Elizabeth Fialho; Bezerra, Leonardo César Teonácio; http://lattes.cnpq.br/2243256075052322; http://lattes.cnpq.br/0664132257054306; http://lattes.cnpq.br/3677015295211434; http://lattes.cnpq.br/9822253950704581; Souza, Sérgio Ricardo de; Wanner, Elizabeth Fialho; Bezerra, Leonardo César Teonácio; Marcelino, Carolina Gil; Stüzle, Thomas; Sá, Elisângela Martins de; Martins, Flávio Vinícius Cruzeiro
Os algoritmos Ant Colony Optimization (ACO) foram inicialmente desenvolvidos para problemas de otimização estática, em que os dados do problema são conhecidos a priori e não sofrem alterações durante a execução. No entanto, sua estrutura baseada em memória mostrou-se eficaz também em Problemas de Otimização Combinatória Dinâmicos (POCD), nos quais os dados podem mudar em tempo real, sem previsibilidade. A partir de uma revisão da literatura, identificaram-se adaptações para melhorar o desempenho do ACO em POCD, incluindo o algoritmo Population-Based ACO (P-ACO), projetado especificamente para essa classe de problemas. Embora o P-ACO tenha se destacado por seu processamento rápido, faltam estudos conclusivos sobre a eficácia dos métodos ACO em cenários dinâmicos. Neste trabalho, realiza-se uma extensiva campanha experimental para avaliar as principais versões do ACO aplicáveis a POCD: o MAX-MIN Ant System (MMAS) e o P-ACO. Utilizou-se como estudo de caso uma variação dinâmica do Problema do Caixeiro-Viajante (PCVDD), amplamente adotado na literatura. As principais contribuições incluem: (i) a proposta de um setup experimental pioneiro, com configuração automática de parâmetros para POCD; (ii) a introdução da métrica de hipervolume para avaliação de desempenho em horizontes temporais variáveis; e (iii) a comparação entre MMAS e P-ACO, demonstrando que o MMAS supera o P-ACO quando combinado com busca local, enquanto o inverso ocorre sem essa técnica. Os resultados também indicam que procedimentos adaptativos têm impacto significativo apenas quando a busca local é desativada.
k-in-a-TREE: an integer programming approach
(Centro Federal de Educação Tecnológica de Minas Gerais, 2024-10-16) Ferreira, Lucas Saldanha; Santos, Vinícius Fernandes dos; http://lattes.cnpq.br/6270626469557436; Santos, Vinícius Fernandes dos; Melo, Rafael Augusto de; Valle, Cristiano Arbex; Sá, Elisângela Martins de; Martins, Flávio Vinícius Cruzeiro
Chudnovsky e Seymour (2010) propuseram o algoritmo THREE-IN-A-TREE, que resolve o seguinte problema em tempo polinomial: dado um grafo simples e finito e três vértices fixos, verificar se existe uma árvore induzida contendo esses vértices. Neste trabalho, lidamos com uma generalização natural desse problema, denominada k-IN-A-TREE. Este problema pergunta se um grafo contém uma árvore induzida que abrange k vértices predeterminados. Quando k faz parte da entrada, o problema é conhecido por ser NP-completo, se k ≥ 4 é um número fixo, sua complexidade está aberta. Entretanto existem algoritmos eficientes para casos restritos, como grafos livres de garras, grafos com circunferência pelo menos k e grafos cordais. Neste trabalho apresentamos formulações de programação inteira mista para o problema em questão e mostramos que instâncias com até 25.000 vértices podem ser resolvidas em tempo computacional razoável. Também agregamos mais de três anos de tempo computacional em experimentos projetados para explorar quais variáveis impactam o tempo de execução das várias instâncias geradas; essas análises fornecem um perfil para o problema k-IN-A-TREE em sua forma mais genérica. As contribuições deste trabalho incluem demonstrar que o k-IN-A-TREE pode ser eficientemente resolvido usando Programação Linear Inteira (ILP), permitindo a solução de instâncias de tamanhos relativamente grandes. Além disso, apresentamos análise detalhada que foi conduzida para identificar e caracterizar as principais variáveis que influenciam a dificuldade computacional do problema, fornecendo dados valiosos sobre como a estrutura do grafo, tamanho, conectividade dos vértices e a distribuição dos elementos obrigatórios, afetam a dificuldade. Outra contribuição significativa é a demonstração de que o problema pode ser resolvido de forma eficaz em intervalos de tempo que seriam insuficientes para resolver outros problemas combinatórios complexos, como o Problema do Caixeiro Viajante (TSP). Isso destaca a tratabilidade computacional do problema em ambientes com restrições de tempo, onde outros problemas de complexidade semelhante permanecem mais desafiadores. Essas contribuições avançam o entendimento do problema, estabelecendo um novo marco para a habilidade de resolver o problema e abrindo caminho para futuras explorações teóricas e práticas.
Multi- and many-objective optimization some advances towards theoretical aspects in performance quality indicators and evolutionary frameworks
(Centro Federal de Educação Tecnológica de Minas Gerais, 2022-11-30) Lopes, Cláudio Lúcio do Val; Martins, Flávio Vinicius Cruzeiro; Wanner, Elizabeth Fialho; Deb, Kalyanmoy; http://lattes.cnpq.br/2243256075052322; http://lattes.cnpq.br/3199420233273400; http://lattes.cnpq.br/9356922762318218; Martins, Flávio Vinicius Cruzeiro; Wanner, Elizabeth Fialho; Deb, Kalyanmoy; Takahashi, Ricardo Hiroshi Caldeira; Fonseca, Carlos Manuel Mira de; Sá, Elisângela Martins de; Lisboa, Adriano Chaves
A otimização com muitos objetivos (MaO) refere-se a problemas com quatro ou mais objetivos, os quais introduzem desafios complexos, incluindo a ineficácia da dominância de Pareto, dificuldades no cálculo de indicadores de qualidade, visualização de conjuntos de soluções e equilíbrio entre convergência e diversidade. Um dos principais problemas nesse contexto é a comparação e avaliação de conjuntos de soluções gerados por algoritmos de otimização, já que tais conjuntos frequentemente contêm soluções incomparáveis. A seleção adequada de indicadores de qualidade é crucial para caracterizar a frente de Pareto de maneira precisa. Nesta tese, abordamos inicialmente o indicador Dominance Move (DoM), propondo novos métodos para seu cálculo, incluindo modelos de programação inteira mista (MIP) e uma abordagem aproximada baseada em aprendizado de máquina. O DoM demonstrou ser uma ferramenta eficaz para medir e comparar soluções em problemas MaO. Em seguida, apresentamos uma estrutura multiestágio que emprega algoritmos evolutivos baseados em vetores de referência para gerar conjuntos de soluções bem distribuídas e convergentes. Essa abordagem visa corrigir progressivamente deficiências em estágios anteriores, assegurando a obtenção de soluções Pareto-ótimas representativas. Os resultados desta pesquisa incluem a análise sistemática de métodos existentes e extensões inovadoras, tanto em indicadores de qualidade quanto em técnicas para equilibrar convergência e diversidade em algoritmos evolutivos.
Um estudo com abordagem heurística para problemas de roteamento de veículos com janelas de tempo e múltiplos depósitos
(Centro Federal de Educação Tecnológica de Minas Gerais, 2023-02-27) Bezerra, Sinaide Nunes; Souza, Marcone Jamilson Freitas; Souza, Sérgio Ricardo de; http://lattes.cnpq.br/5654731681042767; Souza, Marcone Jamilson Freitas; Souza, Sérgio Ricardo de; Ochi, Luiz Satoru; Penna, Puca Huachi Vaz; Sá, Elisângela Martins de; Wanner, Elizabeth Fialho
Este trabalho trata de alguns problemas de roteamento de veículos com janelas de tempo e múltiplos depósitos. Nesse conjunto estão problemas com roteamento fechado e aberto que objetivam a redução na distância ou na quantidade de veículos. Esse conjunto de problemas é NP-difícil, pois eles têm como subproblema, o Problema de Roteamento de Veículos (PRV), onde os clientes são atendidos por uma frota de veículos de mesma capacidade homogênea, em que os custos são dados pela distância total percorrida ou quantidade total de veículos utilizados no atendimento aos clientes. Para resolver esses problemas, o Smart General Variable Neighborhood Search com Busca Local Adaptativa (SGVNSBLA) é apresentado. O algoritmo alterna o mecanismo de busca local entre duas estratégias diferentes. Na primeira estratégia, o método Randomized Variable Neighborhood Descent (RVND) realiza a busca local e, ao aplicar essa estratégia, as vizinhanças com os melhores vizinhos recebem uma pontuação maior. Na segunda estratégia, o método de busca local é aplicado apenas em uma única vizinhança, escolhida pelo método da roleta. Assim, a aplicação da primeira estratégia de busca local serve como método de aprendizagem para aplicação da segunda estratégia. Para testar esses algoritmos, usamos instâncias de benchmark do MDVRPTW envolvendo até 960 clientes, 12 depósitos e 120 veículos, num total de 48 instâncias teste. Para fins de comparação, outros algoritmos baseados em vizinhança também foram implementados. Os resultados encontrados permitiram avaliar a contribuição das estruturas de vizinhanças utilizadas nas soluções que buscam a redução na quantidade de veículos. Os resultados mostram que o desempenho do SGVNSBLA superou o dos outros algoritmos implementados visando a redução da frota. Houve uma redução da frota de veículos em 91,18% das instâncias avaliadas e o tamanho da frota alcançou uma redução média de até 23,32% em problemas com janelas de tempo e múltiplos depósitos. Ao se avaliar essas instâncias com roteamento aberto, houve redução na quantidade de veículos em 100% das instâncias, com baixa variabilidade.

Navegar

Navegando Doutorado em Modelagem Matemática e Computacional por Assunto "Algoritmos"

Resultados por página

Opções de Ordenação