Método para calibração de parâmetros com abordagem adaptativa de busca por agrupamento e modelos estocásticos

Abstract

Finding a solution to an optimization problem involves looking for good results in a solution space. This task is computationally very costly, as it handles efficiently and robustly. The use of meta-heuristics falls into the category of methods used to solve these problems. Therefore, an appropriate adjustment of the metaheuristic parameters becomes important. This task is considered difficult, as there are differences between the nature of the parameters. To solve this tuning problem, this research developed the Bayesian Network Tuning (BNT). A method to tuning meta-heuristic parameters, using stochastic and adaptive strategies, which use statistical information of dependence between different parameters with a cluster search technique. Thus, it is intended to develop an efficient parameter tuning method based on the methodology of Distribution Estimation Algorithms, to assist meta-heuristics in solving optimization problems. Two validations were performed. The first, using AClib to compare with other tuning methods in different scenarios. In the second validation, a case study of the proposed method was carried out on the meta-heuristic Biased Random-Key Genetic Algorithm (BRKGA) to solve the 1D Packaging Problem (BPP 1D). In both results, BNT was competitive and robust compared to other tuning methods found in the literature.

Encontrar uma solução para um problema de otimização envolve buscar bons resultados em um espaço de soluções. Essa tarefa é computacionalmente muito custosa, pois lida com eficiência e robustez. A utilização de meta-heurísticas se enquadra na categoria de métodos empregados para a resolução desses problemas. Com isso torna-se importante um ajuste apropriado dos parâmetros da meta-heurística. Essa tarefa é considerada difícil, visto que existem diferenças entre as naturezas dos parâmetros. De modo a resolver esse problema de ajuste, esta pesquisa desenvolveu o \textit{Bayesian Network Tuning} (BNT). Um método para calibrar parâmetros de meta-heurísticas, utilizando estratégias estocásticas e adaptativas, que utilizam a informações estatísticas de dependência entre diferentes parâmetros com uma técnica de busca por agrupamento. Desta forma, pretende-se desenvolver um método de ajuste de parâmetros eficiente com base na metodologia dos Algoritmos de Estimação de Distribuição, para auxiliar meta-heurísticas na resolução de problemas de otimização. Foram realizadas duas validações. A primeira, com o uso do AClib para o comparativo com outros calibradores em cenários diversificados. Na segunda validação, realizou-se um caso de estudo do método proposto sobre a meta-heurística \textit{Biased Random-Key Genetic Algorithm} (BRKGA) para resolver o Problema de Empacotamento 1D (BPP 1D). Em ambos os resultados, o BNT mostrou-se competitivo e robusto em comparação a outros métodos encontrados na literatura.