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

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorDelgado, Myriam Regattieri de Biase da Silva-
Autor(es): dc.contributorhttps://orcid.org/0000-0002-2791-174X-
Autor(es): dc.contributorhttp://lattes.cnpq.br/4166922845507601-
Autor(es): dc.contributorKessaci, Marie Eleonore-
Autor(es): dc.contributorPozo, Aurora Trinidad Ramirez-
Autor(es): dc.contributorhttps://orcid.org/ 0000-0001-5808-3919-
Autor(es): dc.contributorhttp://lattes.cnpq.br/2815946827655352-
Autor(es): dc.contributorAlmeida, Carolina Paula de-
Autor(es): dc.contributorhttps://orcid.org/0000-0003-4939-6432-
Autor(es): dc.contributorhttp://lattes.cnpq.br/8586489892942437-
Autor(es): dc.contributorDhaenens, Clarisse-
Autor(es): dc.contributor.-
Autor(es): dc.contributorDelgado, Myriam Regattieri de Biase da Silva-
Autor(es): dc.contributorhttps://orcid.org/0000-0002-2791-174X-
Autor(es): dc.contributorhttp://lattes.cnpq.br/4166922845507601-
Autor(es): dc.contributorLuders, Ricardo-
Autor(es): dc.contributorhttps://orcid.org/ 0000-0001-6483-4694-
Autor(es): dc.contributorhttp://lattes.cnpq.br/5158617067991861-
Autor(es): dc.creatorPavelski, Lucas Marcondes-
Data de aceite: dc.date.accessioned2022-08-04T20:16:48Z-
Data de disponibilização: dc.date.available2022-08-04T20:16:48Z-
Data de envio: dc.date.issued2022-04-08-
Data de envio: dc.date.issued2022-04-08-
Data de envio: dc.date.issued2021-12-12-
Fonte completa do material: dc.identifierhttp://repositorio.utfpr.edu.br/jspui/handle/1/27906-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/capes/705963-
Descrição: dc.descriptionThe search for the best algorithm and its configuration is a difficult task on most optimization scenarios, especially on NP-hard problems, since different proposed metaheuristics exist, and testing many parameters demands high computational costs. Moreover, the understanding of such parameters and their relation to problem instances is of great importance in the field of algorithm configuration. The literature on Automatic Algorithm Configuration (AAC) proposes several strategies to find out the best configuration, although the focus is usually less on explainability and more on the performance of the different configurations. Based on past experience obtained from data, Per-Instance Algorithm Configuration (PIAC) focuses on the mapping built to recommend the best configurations. This work aims at proposing and analyzing two PIAC approaches. The first, namely MetaL PIAC, is an extension of the algorithm selection problem and uses meta-learning to recommend metaheuristics and their configuration parameters. The other, namely MOAAC/D is based on a brand new multi-objective formulation of the AAC problem, that decomposes the problem space and uses a decomposition-based framework to provide generalist and specialist configurations at the same time. For each objective, there is a set of problems related to it, and a decomposition based multi-objective algorithm is proposed to find good trade-off configurations. As the main study case, the work addresses flowshop problems. Extensive experiments performed on more than 6000 instances, consider MetaL PIAC to tune the parameters of different metaheuristics, and MOAAC/D to tune iterated local search and iterated greedy configurations. The results show that both strategies outperform the generalist solution provided by irace – one of the best well-known AAC – with a slight advantage of MOAAC/D over MetaL PIAC.-
Descrição: dc.descriptionA 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.-
Formato: dc.formatapplication/pdf-
Idioma: dc.languageen-
Publicador: dc.publisherUniversidade Tecnológica Federal do Paraná-
Publicador: dc.publisherCuritiba-
Publicador: dc.publisherBrasil-
Publicador: dc.publisherPrograma de Pós-Graduação em Engenharia Elétrica e Informática Industrial-
Publicador: dc.publisherUTFPR-
Direitos: dc.rightsopenAccess-
Direitos: dc.rightshttp://creativecommons.org/licenses/by/4.0/-
Palavras-chave: dc.subjectAlgoritmos-
Palavras-chave: dc.subjectOtimização matemática-
Palavras-chave: dc.subjectHeurística-
Palavras-chave: dc.subjectAprendizado de máquinas-
Palavras-chave: dc.subjectAlgorítmos genéticos-
Palavras-chave: dc.subjectOtimização combinatória-
Palavras-chave: dc.subjectAlgorithms-
Palavras-chave: dc.subjectMathematical optimization-
Palavras-chave: dc.subjectHeuristic-
Palavras-chave: dc.subjectMachine learning-
Palavras-chave: dc.subjectGenetic algorithms-
Palavras-chave: dc.subjectCombinatorial optimization-
Palavras-chave: dc.subjectCNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO-
Palavras-chave: dc.subjectEngenharia Elétrica-
Título: dc.titlePer-instance algorithm configuration: from meta-learning to multi-objective decomposition-
Título: dc.titleConfiguração de algoritmos baseada em instância: do meta-aprendizado à decomposição multiobjetivo-
Tipo de arquivo: dc.typelivro digital-
Aparece nas coleções:Repositorio Institucional da UTFPR - RIUT

Não existem arquivos associados a este item.