30out2023
09:30 Defesa de Mestrado Auditório do IC3
Tema
BrkgaCuda 2.0: Uma Biblioteca Para o Algoritmo Genético de Chave Aleatória Enviesado em GPUs
Aluno
Bruno Almêda de Oliveira
Orientador / Docente
Edson Borin - Coorientador: Eduardo Candido Xavier
Breve resumo
Vários problemas em ciência da computação são classificados como NP-Hard e, a menos que P = NP, uma solução ótima não pode ser encontrada em tempo polinomial. Tais problemas possuem grande relevância na prática, sendo aceitável encontrar alguma solução viável, idealmente próxima ou igual a solução ótima. Para realizar a busca de tais soluções, podem ser utilizados algoritmos classificados como exatos ou heurísticos e meta-heurísticos. Um algoritmo exato garante encontrar uma solução ótima, mas pode exigir bastante tempo. Uma heurística é a aplicação de uma metodologia de tentativa e erro com base em características do problema. Já a metaheurística é uma heurística genérica que pode ser utilizada em diversos problemas. Para facilitar o uso de metaheurística, foram propostas algumas Interfaces de Programação de Aplicações (API, do inglês Application Programming Interface) para abstrair a lógica dos métodos propostos, simplificando o desenvolvimento e permitindo a reutilização de código na solução de outro problema. Nesse contexto, a API BrkgaCuda foi proposta para o Algoritmo Genético de Chave Aleatória Enviesado (BRKGA, do inglês Biased Random-Key Genetic Algorithm) na linguagem CUDA, permitindo a paralelização de suas operações nas Unidades de Processamento Gráfico (GPU, do inglês Graphics Processing Unit). O BRKGA é um algoritmo evolucionário baseado no algoritmo genético, sendo as principais diferenças o uso de cromossomos com genes no intervalo [0, 1] e um viés para selecionar os genes dos melhores cromossomos. Sua grande vantagem é que a única dependência do problema a ser resolvido é um método decodificador para converter o cromossomo em uma solução. Com foco em atingir um melhor desempenho, propomos diversas melhorias para o BrkgaCuda após avaliar seus gargalos, além de adicionarmos outros métodos já propostos na literatura. Nosso objetivo é reduzir o tempo gasto e manter soluções tão boas quanto em outras APIs. Neste trabalho, apresentamos uma nova versão da ferramenta chamada BrkgaCuda. Em nossos experimentos, essa versão possui o menor tempo de execução quando comparado contra outras quatro APIs, sendo cerca de 20× mais rápida em grande parte dos experimentos. Além disso, mostramos que é possível atingir esse ganho sem perda de qualidade das soluções encontradas.
Banca examinadora
Titulares:
| Edson Borin | IC/UNICAMP |
| Yuri Abitbol de Menezes Frota | IC/UFF |
| Guilherme Pimentel Telles | IC/UNICAMP |
Suplentes:
| Fábio Luiz Usberti | IC/UNICAMP |
| Alfredo Goldman vel Lejbman | IME/USP |