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. |