Automatic configuration of generalized constructive heuristics

Abstract

Constructive algorithms represent one of the three fundamental approaches of metaheuristics, along with the modification and recombination strategies. In this context, the goal is to develop, step by step, a solution within a feasible solution space for a given problem. Examples of heuristics that employ this strategy include the Greedy Algorithm, Beam Search, Ant Colony Algorithm, among others. The diversity of available constructive algorithms, coupled with the nuances of metaheuristics, which are often stochastic, frequently complicates the selection of the most suitable algorithm for a specific problem. The same applies to design options, such as the definition of the neighborhood to be explored and the appropriate structures for efficient implementation. In light of these challenges, the field of automatic algorithm configuration emerges with the purpose of combining multiple heuristics to achieve more effective and comprehensive solutions, using various techniques to select the best heuristics and the best parameters for a given scenario. This work proposes the use of automatic configuration techniques to combine multiple constructive heuristics, aiming to achieve the best possible combination for specific problems. Additionally, it intends to compare the results obtained with other solutions found in the literature, employing different problems for the evaluation of these metrics.

Os algoritmos construtivos representam uma das três abordagens fundamentais das metaheurísticas, juntamente com as estratégias de modificação e recombinação. Nesse contexto, o objetivo é desenvolver, passo a passo, uma solução num espaço de soluções viáveis para um problema. Exemplos de heurísticas que empregam essa estratégia incluem o Algoritmo Guloso, a Busca por Raio, o Algoritmo de Colônia de Formigas, entre outros. A diversidade de algoritmos construtivos disponíveis, aliada às nuances das metaheurísticas, que muitas vezes são estocásticas, frequentemente dificulta a escolha do algoritmo mais adequado para um problema específico. O mesmo acontece com as opções de projeto, como a definição da vizinhança a ser explorada e das estruturas adequadas para uma implementação eficiente. Diante desses desafios, a área de configuração automática de algoritmos surge com o propósito de combinar várias heurísticas para alcançar soluções mais eficazes e abrangentes, empregando diversas técnicas para selecionar as melhores heurísticas e os melhores parâmetros para um determinado cenário. Este trabalho propõe a utilização de técnicas de configuração automática para combinar múltiplas heurísticas construtivas, visando alcançar a melhor combinação possível para problemas específicos. Além disso, pretende-se comparar os resultados obtidos com outras soluções encontradas na literatura, empregando diferentes problemas para a avaliação dessas métricas.