30 Oct
09:30 Master's Defense IC3 Auditorium
Topics
BrkgaCuda 2.0: A Library for the Biased Random Key Genetic Algorithm on GPUs
Student
Bruno Almêda de Oliveira
Advisor / Teacher
Edson Borin - Co-supervisor: Eduardo Candido Xavier
Brief summary
Several problems in computer science are classified as NP-Hard, and unless P = NP, an optimal solution cannot be found in polynomial time. Such problems have great relevance in practice, and it is acceptable to find a viable solution, ideally close to or equal to the optimal solution. To search for such solutions, algorithms classified as exact or heuristic and meta-heuristic can be used. An exact algorithm guarantees finding an optimal solution, but it may require a lot of time. A heuristic is the application of a trial and error methodology based on characteristics of the problem. Metaheuristics are generic heuristics that can be used in a variety of problems. To facilitate the use of metaheuristics, some Application Programming Interfaces (API) were proposed to abstract the logic of the proposed methods, simplifying development and allowing code reuse to solve another problem. In this context, the BrkgaCuda API was proposed for the Biased Random-Key Genetic Algorithm (BRKGA) in the CUDA language, allowing the parallelization of its operations in Graphics Processing Units (GPU). Unit). BRKGA is an evolutionary algorithm based on the genetic algorithm, the main differences being the use of chromosomes with genes in the range [0, 1] and a bias to select genes from the best chromosomes. Its great advantage is that the only dependence on the problem to be solved is a decoder method to convert the chromosome into a solution. Focusing on achieving better performance, we propose several improvements to BrkgaCuda after evaluating its bottlenecks, in addition to adding other methods already proposed in the literature. Our goal is to reduce time spent and maintain solutions that are as good as other APIs. In this work, we present a new version of the tool called BrkgaCuda. In our experiments, this version has the shortest execution time when compared against four other APIs, being around 20× faster in most experiments. Furthermore, we show that it is possible to achieve this gain without losing the quality of the solutions found.
Examination Board
Headlines:
| Edson Borin | IC / UNICAMP |
| Yuri Abitbol de Menezes Frota | IC / UFF |
| Guilherme Pimentel Telles | IC / UNICAMP |
Substitutes:
| Fábio Luiz Usberti | IC / UNICAMP |
| Alfredo Goldman vel Lejbman | IME / USP |