Generating heuristics for the quadratic unconstrained binary optimization problem using automatic algorithm configuration
Fecha
2023Autor
Tutor
Nivel académico
Grado
Tipo
Otro título
Gerando heurísticas para o problema de otimização binária quadrática irrestrita usando configuração automática de algoritmos
Materia
Abstract
In this work, we study an automated approach to the design of heuristic algorithms to solve the Quadratic Unconstrained Binary Optimization Problem (QUBO). Our approach is an extension of the work of Souza and Ritt (2018), who represent a design space of algorithms by a context-free grammar which is later explored by an algorithm configurator. We extend this work by introducing a new platform for design space exploration of heuristics for QUBO with a modular architecture and new components. Usi ...
In this work, we study an automated approach to the design of heuristic algorithms to solve the Quadratic Unconstrained Binary Optimization Problem (QUBO). Our approach is an extension of the work of Souza and Ritt (2018), who represent a design space of algorithms by a context-free grammar which is later explored by an algorithm configurator. We extend this work by introducing a new platform for design space exploration of heuristics for QUBO with a modular architecture and new components. Using this platform and the grammar-based approach, we were able to find algorithms that are very competitive and sometimes better than the state of the art in commonly used instances in the literature ...
Resumo
Neste trabalho, estudamos uma abordagem automatizada para o projeto de algoritmos heurísticos para resolver o Problema de Otimização Binária Quadrática Ir restrita (QUBO). Nossa abordagem é uma extensão do trabalho de Souza and Ritt (2018), que representam um espaço de design de algoritmos por uma gramática li vre de contexto que posteriormente é explorada por um configurador de algoritmos. Estendemos este trabalho introduzindo uma nova plataforma para exploração do espaço de design de heurísti ...
Neste trabalho, estudamos uma abordagem automatizada para o projeto de algoritmos heurísticos para resolver o Problema de Otimização Binária Quadrática Ir restrita (QUBO). Nossa abordagem é uma extensão do trabalho de Souza and Ritt (2018), que representam um espaço de design de algoritmos por uma gramática li vre de contexto que posteriormente é explorada por um configurador de algoritmos. Estendemos este trabalho introduzindo uma nova plataforma para exploração do espaço de design de heurísticas para QUBO com uma arquitetura modular e no vos componentes. Usando essa plataforma e a abordagem baseada em gramática, conseguimos encontrar algoritmos muito competitivos e às vezes melhores do que o estado da arte em instâncias comumente usadas na literatura. ...
Institución
Universidade Federal do Rio Grande do Sul. Instituto de Informática. Curso de Ciência da Computação: Ênfase em Ciência da Computação: Bacharelado.
Colecciones
-
Tesinas de Curso de Grado (37272)
Este ítem está licenciado en la Creative Commons License