Automatic algorithm configuration : methods and applications

Abstract

The performance of algorithms is often highly sensitive to the values of their pa rameters. Therefore, algorithm configuration plays a pivotal role when designing or adapting algorithms for a given problem domain. Automatic algorithm configuration methods automate this process, reducing human effort and potential biases involved in error-prone manual configuration approaches. A more general and ambitious research field, called automatic algorithm design, applies automatic configuration methods to select, combine and calibrate algorithm components, producing high quality algorithms automatically for different problem domains. Despite the growing attention and substantial progress made in the last years, there are still open research directions on understanding, improving and exploring methods for the automatic design and configuration of algorithms. We present a comprehensive study on automatic algorithm configuration with the fol lowing contributions. First, we improve the efficiency of the automatic configuration of optimization algorithms. In particular, we propose a set of capping methods that use previous executions to build a performance envelope, which is used to identify poor-performing executions and stop them early. These methods considerably reduce the configuration time without loss of quality. Second, we improve the quality of automatic algorithm configuration by exploring parameter regression models. In stead of searching for parameter values, we calibrate models that set these values according to the instance size of the instance being solved, leading to expressive gains in algorithm performance when compared to using fixed configurations. Third, we provide a visualization tool to analyze and understand the automatic algorithm configuration process. The visualizations allow to identify different types of flaws and improve configuration scenarios. Finally, we propose a component-wise heuristic solver for a general class of binary optimization problems. This solver implements a set of heuristic components that can be selected and combined to produce complete algorithms. Given a problem, automatic configuration methods explore this design space and search for the best heuristic algorithm. We automatically produce new state-of-the-art algorithms for different binary problems using this solver.

O desempenho de algoritmos está geralmente associado aos valores dos seus parâ metros. Portanto, a configuração do algoritmo desempenha um papel fundamental ao projetar ou adaptar algoritmos para um dado domínio. Métodos de configuração automática de algoritmos automatizam esse processo, reduzindo o esforço humano e potenciais vieses envolvidos em abordagens de configuração manuais. Um campo de pesquisa mais geral e ambicioso, chamado projeto automático de algoritmos, aplica métodos de configuração automática para selecionar, combinar e calibrar compo nentes algorítmicos, produzindo algoritmos de alta qualidade automaticamente para diferentes problemas. Apesar da crescente atenção e substancial progresso feito nos últimos anos, ainda existem possibilidades de pesquisa em aberto relacionadas ao en tendimento, melhoria e exploração de métodos de projeto e configuração automáticos de algoritmos. Este trabalho apresenta um estudo abrangente sobre configuração automática de algoritmos com as seguintes contribuições. Primeiro, melhora-se a eficiência da configuração automática de algoritmos de otimização. Em particular, são propostos métodos de poda que usam execuções prévias para construir um envelope de desempe nho, o qual é usado para identificar execuções de baixo desempenho e interrompê-las antecipadamente. Esses métodos reduzem consideravelmente o tempo de configuração sem perda de qualidade. Segundo, melhora-se a qualidade da configuração automática de algoritmos explorando modelos de regressão de parâmetros. Em vez de buscar por valores de parâmetros, são calibrados modelos que determinam esses valores de acordo com o tamanho da instância a ser resolvida, levando a um ganho expressivo no desempenho dos algoritmos quando comparado ao uso de configurações fixas. Terceiro, este trabalho disponibiliza uma ferramenta de visualização para analisar e entender o processo de configuração automática de algoritmos. As visualizações permitem identificar diferentes tipos de falhas e melhorar cenários de configuração. Finalmente, este trabalho propõe um solver heurístico baseado em componentes para a classe geral de problemas binários de otimização. Esse solver implementa um conjunto de componentes heurísticos que podem ser selecionados e combinados para a produção de algoritmos completos. Dado um problema, métodos de configuração automática exploram esse espaço de componentes e buscam pelo melhor algoritmo heurístico. Foram produzidos novos algoritmos no estado-da-arte para diferentes problemas binários usando esse solver.