Automatic algorithm configuration : methods and applications

Detalhes bibliográficos
Ano de defesa: 2022
Autor(a) principal: Souza, Marcelo de
Orientador(a): Ritt, Marcus Rolf Peter
Banca de defesa: Não Informado pela instituição
Tipo de documento: Tese
Tipo de acesso: Acesso aberto
Idioma: eng
Instituição de defesa: Não Informado pela instituição
Programa de Pós-Graduação: Não Informado pela instituição
Departamento: Não Informado pela instituição
País: Não Informado pela instituição
Palavras-chave em Português:
Palavras-chave em Inglês:
Link de acesso: http://hdl.handle.net/10183/236350
Resumo: 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.