Defesa de Tese de Doutorado de Raphael Gomes Santos – 14/03/2025, 14h, por videoconferência
Link para defesa: meet.google.com/etf-sqns-doa
Combining Heuristics and Data Mining for Continuous Optimization Problems
Resumo:
A hibridização de metaheurísticas com técnicas de mineração de dados tem sido aplicada com sucesso em problemas de otimização combinatória. Entre os exemplos desse tipo de estratégia estão DM-GRASP e MDM-GRASP, versões híbridas da metaheurística Greedy Randomized Adaptive Search Procedure (GRASP), que incorporam técnicas de mineração de dados. Esses métodos híbridos são chamados de Metaheurísticas orientada a Dados e visam extrair conhecimento útil dos dados gerados pelas metaheurísticas em seu processo de busca e usar esse conhecimento para melhorar a sua performance. Apesar do sucesso em problemas combinatórios, como o problema de empacotamento de conjuntos e o problema de diversidade máxima, propostas desse tipo para resolver problemas de otimização contínua ainda são escassas na literatura. Esta tese investiga a hibridização de metaheurísticas contínuas com Mineração de Dados. Seguindo esta ideia, propomos algoritmos de otimização híbridos baseados no conceito de metaheurística orientada a dados para resolver os problemas de otimização contínua global. Apresentamos uma versão híbrida de mineração de dados de uma metaheurística baseada em trajetórias C-GRASP, que é uma adaptação do GRASP para problemas com variáveis contínuas. Chamamos essa nova versão de DM-C-GRASP, que identifica padrões em soluções de alta qualidade e gera novas soluções guiadas por esses padrões. Realizamos experimentos computacionais com DM-C-GRASP em um conjunto de funções matemáticas de benchmark bem conhecidas. Os resultados mostraram que metaheurísticas para otimização contínua também podem se beneficiar do uso de padrões para orientar a busca por melhores soluções. Também propomos a hibridização de metódos de mineração de dados com um algoritmo evolucionário estado-da-arte, chamado L-SHADE. Chamamos esse algoritmo híbrido de DM-L-SHADE. A análise experimental do DM-L-SHADE mostra que ele é competitivo em comparação com heurísticas de última geração para otimização contínua.
Abstract:
The hybridization of metaheuristics with data mining techniques has been successfully applied to combinatorial optimization problems. This strategy includes DM-GRASP and MDM-GRASP, hybrid versions of the Greedy Randomized Adaptive Search Procedure (GRASP) metaheuristic incorporating data mining techniques. These hybrid methods are called Data-Driven Metaheuristics and aim to extract valuable knowledge from the data generated by the metaheuristics in their search process and improve its performance. Despite their success in combinatorial problems, such as the set packing problem and the maximum diversity problem, proposals of this type to solve continuous optimization problems are still scarce in the literature. This thesis investigates the hybridization of continuous metaheuristics with Data Mining. Following this idea, we propose hybrid optimization algorithms based on data-driven metaheuristics to solve global continuous optimization problems. We present a hybrid data mining version of the trajectory-based metaheuristic C-GRASP, which adapts GRASP for problems with continuous variables. We call this new version DM-C-GRASP, which identifies patterns in high-quality solutions and generates new solutions guided by these patterns. We perform computational experiments with DM-C-GRASP on well-known mathematical benchmark functions. The results show that metaheuristics for continuous optimization can also benefit from using patterns to guide the search for better solutions. We also propose hybridizing data mining methods with a state-of-the-art evolutionary algorithm called L-SHADE. We call this hybrid algorithm DM-L-SHADE. The experimental analysis of DM-L-SHADE shows that it is competitive compared to state-of-the-art heuristics for continuous optimization.
Banca examinadora:
Prof. Alexandre Plastino de Carvalho, UFF – Presidente
Prof. Simone de Lima Martins, UFF
Prof. Yuri Abitbol de Menezes Frota, UFF
Prof. Alexandre César Muniz de Oliveira, UFMA
Prof. Omar Andres Carmona Cortes, IFMA
Prof. Mauro Roisenberg, UFSC