Per-instance algorithm configuration: from meta-learning to multi-objective decomposition

• Ano de defesa: 2021
• Autor(a) principal: Pavelski, Lucas Marcondes
• Orientador(a): Delgado, Myriam Regattieri de Biase da Silva
• Banca de defesa: Pozo, Aurora Trinidad Ramirez , Almeida, Carolina Paula de , Dhaenens, Clarisse , Delgado, Myriam Regattieri de Biase da Silva , Luders, Ricardo
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: eng
• Instituição de defesa: Universidade Tecnológica Federal do Paraná; Curitiba
• Programa de Pós-Graduação: Programa de Pós-Graduação em Engenharia Elétrica e Informática Industrial
• País: Brasil
• Palavras-chave em Português: Algoritmos; Otimização matemática; Heurística; Aprendizado de máquinas; Algorítmos genéticos; Otimização combinatória; Algorithms; Mathematical optimization; Heuristic; Machine learning; Genetic algorithms; Combinatorial optimization
• Área do conhecimento CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
• Link de acesso: http://repositorio.utfpr.edu.br/jspui/handle/1/27906

A busca pelo melhor algoritmo e sua configuração é uma tarefa difícil na maioria dos cenários de otimização, especialmente em problemas NP-difíceis, uma vez que existem diferentes metaheurísticas propostas, e testar muitos parâmetros demanda um alto custo computacional. Além disso, o entendimento de tais parâmetros e sua relação com as instâncias do problema é de suma importância para a área de configuração de algoritmos. A literatura sobre Configuração Automática de Algoritmos (AAC do inglês Automatic Algorithm Configuration) propõe várias estratégias para encontrar a melhor configuração, embora o foco geralmente seja menos na explicabilidade e mais no desempenho dessas diferentes configurações. Com base em experiências anteriores obtidas a partir de dados, a área de Configuração Automática Baseada em Instância (PIAC, do inglês Per Instance Algorithm Configuration) foca no mapeamento construído para recomendar as melhores configurações. Este trabalho tem como objetivo propor e analisar duas abordagens PIAC. A primeira, chamada de MetaL PIAC, é uma extensão do problema de seleção de algoritmo e usa meta-aprendizado para recomendar meta-heurísticas e seus parâmetros de configuração. A segunda abordagem, chamada de MOAAC/D, é baseada em uma nova formulação multiobjetivo do problema AAC, que decompõe o espaço do problema e usa uma plataforma baseada em decomposição para fornecer configurações generalistas e especialistas ao mesmo tempo. Para cada objetivo, existe um conjunto de problemas relacionados a ele, e um algoritmo multiobjetivo baseado em decomposição é proposto para encontrar configurações com bons balanceamentos. Como estudo de caso principal, o trabalho considera problemas Flowshop. Experimentos extensivos realizados em mais de 6000 instâncias, consideram o MetaL PIAC para ajustar os parâmetros de diferentes meta-heurísticas, e o MOAAC/D para ajustar configurações da busca local iterativa e busca gulosa iterativa. Os resultados mostram que ambas as estratégias superam a solução generalista fornecida pelo irace – uma das abordagens de AAC mais conhecidas na área – com uma ligeira vantagem do MOAAC/D sobre o MetaL PIAC.