Hibridizações entre métodos exatos e meta-heurísticas : estratégias para otimização global com restrições

Abstract

Resumo: A otimização numérica global tem sido amplamente utilizada na modelagem de problemas em diversas áreas do conhecimento. Este processo consiste em encontrar uma valoração para variáveis reais que minimize uma função de custo. Embora os métodos propostos pelas comunidades de programação matemática, métodos exatos e meta-heurísticas apresentem desempenho satisfatório em alguns subconjuntos de instâncias, variantes com restrições, nãoconvexidade, não-linearidade ou alta dimensionalidade ainda representam desafios significativos. Nesse contexto, métodos híbridos surgem como alternativas promissoras, combinando vantagens e características complementares de diferentes abordagens. Com o objetivo de abrir novas perspectivas e metodologias em otimização numérica global mono-objetivo com restrições, esta tese propõe três otimizadores híbridos que combinam técnicas de contração do espaço de busca, típicas de métodos exatos, com a meta-heurística Evolução Diferencial (DE), destacada na literatura recente. O primeiro otimizador, BBDE, baseia-se em DE e incorpora diversas estratégias de resolvedores recentes e técnicas de consistência local, melhorando substancialmente seu desempenho. Em seguida, o HIDE integra uma versão intervalar de DE com técnicas de consistência local e uma derivação do BBDE, resultando em um desempenho superior ao da abordagem anterior. Por último, o HIBB combina um método híbrido de Branch & Bound (B&B) com consistência local e uma meta-heurística baseada em BBDE, avaliando diferentes formas de exploração do espaço de busca para melhor aproveitamento dos recursos computacionais disponíveis. As abordagens híbridas propostas apresentaram resultados significativamente superiores às suas versões originais, explorando de maneira eficaz as vantagens individuais de métodos exatos e meta-heurísticas.

Abstract: Global numerical optimization has been widely used in modeling problems across various fields of knowledge. This process involves finding a valuation for real variables that minimizes a cost function. Although the methods proposed by the communities of mathematical programming, exact methods, and metaheuristics show satisfactory performance in some subsets of instances, variants with constraints, non-convexity, non-linearity, or high dimensionality still pose significant challenges. In this context, hybrid methods emerge as promising alternatives, combining different approaches’ advantages and complementary characteristics. Aiming to introduce newperspectives and methodologies in single-objective global numerical optimization with constraints, this thesis proposes three hybrid optimizers that combine search space contraction techniques, typical of exact methods, with the Differential Evolution (DE) metaheuristic, highlighted in recent literature. The first optimizer, BBDE, is based on DE and incorporates various strategies from recent solvers and local consistency techniques, substantially improving its performance. Next, the HIDE integrates an interval version of DE with local consistency techniques and a derivation of BBDE, resulting in superior performance compared to the previous approach. Finally, the HIBB combines a hybrid Branch and Bound (B&B) method with local consistency and a BBDE-based metaheuristic, evaluating different ways of exploring the search space to utilize the available computational resources better. The proposed hybrid approaches presented significantly superior results to their original versions, effectively leveraging the individual advantages of exact methods and metaheuristics.