Per-instance algorithm configuration: from meta-learning to multi-objective decomposition
The 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...
| Autor principal: | Pavelski, Lucas Marcondes |
|---|---|
| Formato: | Tese |
| Idioma: | Inglês |
| Publicado em: |
Universidade Tecnológica Federal do Paraná
2022
|
| Assuntos: | |
| Acesso em linha: |
http://repositorio.utfpr.edu.br/jspui/handle/1/27906 |
| Tags: |
Adicionar Tag
Sem tags, seja o primeiro a adicionar uma tag!
|
| id |
riut-1-27906 |
|---|---|
| recordtype |
dspace |
| spelling |
riut-1-279062022-04-09T06:07:34Z Per-instance algorithm configuration: from meta-learning to multi-objective decomposition Configuração de algoritmos baseada em instância: do meta-aprendizado à decomposição multiobjetivo Pavelski, Lucas Marcondes Delgado, Myriam Regattieri de Biase da Silva https://orcid.org/0000-0002-2791-174X http://lattes.cnpq.br/4166922845507601 Kessaci, Marie Eleonore Pozo, Aurora Trinidad Ramirez https://orcid.org/ 0000-0001-5808-3919 http://lattes.cnpq.br/2815946827655352 Almeida, Carolina Paula de https://orcid.org/0000-0003-4939-6432 http://lattes.cnpq.br/8586489892942437 Dhaenens, Clarisse . Delgado, Myriam Regattieri de Biase da Silva https://orcid.org/0000-0002-2791-174X http://lattes.cnpq.br/4166922845507601 Luders, Ricardo https://orcid.org/ 0000-0001-6483-4694 http://lattes.cnpq.br/5158617067991861 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 CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO Engenharia Elétrica The 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. 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. 2022-04-08T13:52:33Z 2022-04-08T13:52:33Z 2021-12-13 doctoralThesis PAVELSKI, Lucas Marcondes. Per-instance algorithm configuration: from meta-learning to multi-objective decomposition. 2021. Tese (Doutorado em Engenharia Elétrica e Informática Industrial) - Universidade Tecnológica Federal do Paraná, Curitiba, 2021. http://repositorio.utfpr.edu.br/jspui/handle/1/27906 eng openAccess http://creativecommons.org/licenses/by/4.0/ application/pdf Universidade Tecnológica Federal do Paraná Curitiba Brasil Programa de Pós-Graduação em Engenharia Elétrica e Informática Industrial UTFPR |
| institution |
Universidade Tecnológica Federal do Paraná |
| collection |
RIUT |
| language |
Inglês |
| topic |
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 CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO Engenharia Elétrica |
| spellingShingle |
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 CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO Engenharia Elétrica Pavelski, Lucas Marcondes Per-instance algorithm configuration: from meta-learning to multi-objective decomposition |
| description |
The 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. |
| format |
Tese |
| author |
Pavelski, Lucas Marcondes |
| author_sort |
Pavelski, Lucas Marcondes |
| title |
Per-instance algorithm configuration: from meta-learning to multi-objective decomposition |
| title_short |
Per-instance algorithm configuration: from meta-learning to multi-objective decomposition |
| title_full |
Per-instance algorithm configuration: from meta-learning to multi-objective decomposition |
| title_fullStr |
Per-instance algorithm configuration: from meta-learning to multi-objective decomposition |
| title_full_unstemmed |
Per-instance algorithm configuration: from meta-learning to multi-objective decomposition |
| title_sort |
per-instance algorithm configuration: from meta-learning to multi-objective decomposition |
| publisher |
Universidade Tecnológica Federal do Paraná |
| publishDate |
2022 |
| citation |
PAVELSKI, Lucas Marcondes. Per-instance algorithm configuration: from meta-learning to multi-objective decomposition. 2021. Tese (Doutorado em Engenharia Elétrica e Informática Industrial) - Universidade Tecnológica Federal do Paraná, Curitiba, 2021. |
| url |
http://repositorio.utfpr.edu.br/jspui/handle/1/27906 |
| _version_ |
1805302272527171584 |
| score |
10,814766 |