BrkgaCuda 2.0 [recurso eletrônico] : a library for the biased random-key genetic algorithm on GPUs = BrkgaCuda 2.0: uma biblioteca para o algoritmo genético de chave aleatória enviesado em GPUs
Bruno Almêda de Oliveira
DISSERTAÇÃO
Inglês
T/UNICAMP OL4b
[BrkgaCuda 2.0]
Campinas, SP : [s.n.], 2023.
1 recurso online (62p.) : il., digital, arquivo PDF.
Orientadores: Edson Borin, Eduardo Candido Xavier
Dissertação (mestrado) – Universidade Estadual de Campinas, Instituto de Computação
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 à...
Ver mais
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 à 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 para resolver 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 na maioria dos experimentos. Além disso, mostramos que é possível atingir esse ganho sem perda de qualidade das soluções encontradas
Ver menos
Abstract: Many 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 some viable solution, ideally close to or equal to the optimal solution. To...
Ver mais
Abstract: Many 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 some 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 to find an optimal solution, but it can take much time. A heuristic is the application of a trial-and-error methodology based on problem characteristics. The metaheuristic is a generic heuristic that can be used in several problems. To ease the usage of metaheuristics, some Application Programming Interfaces (APIs) were proposed to abstract the logic of the proposed methods, simplifying the development and allowing the reuse of the source code to solve another problem. In this context, the BrkgaCuda API was presented for the Biased Random-Key Genetic Algorithm (BRKGA) in the CUDA language, allowing the parallelization of its operations in the Graphics Processing Unit (GPU). BRKGA is an evolutionary algorithm based on the genetic algorithm, the main differences being the use of chromosomes with genes in the interval [0, 1] and a bias to select the genes of better chromosomes. Its great advantage is that the only dependency on the problem to be solved is a decoding method to convert the chromosome into a solution. Focused on achieving better performance, we propose several improvements for BrkgaCuda after evaluating its bottlenecks, in addition to implementing other methods already proposed in the literature. We aim to reduce the elapsed time and keep solutions as good as other APIs. In this work, we present a new version of the tool called Brkga-Cuda 2.0. In our experiments, this version has the lowest execution time compared to four other APIs, being about 20× faster in most experiments. Moreover, we show that it is possible to achieve this gain without loss of quality of the solutions found
Ver menos
Requisitos do sistema: Software para leitura de arquivo em PDF
Borin, Edson, 1979-
Orientador
Xavier, Eduardo Candido, 1979-
Coorientador
Frota, Yuri Abitdol de Menezes
Avaliador
Telles, Guilherme Pimentel, 1972-
Avaliador
BrkgaCuda 2.0 [recurso eletrônico] : a library for the biased random-key genetic algorithm on GPUs = BrkgaCuda 2.0: uma biblioteca para o algoritmo genético de chave aleatória enviesado em GPUs
Bruno Almêda de Oliveira
BrkgaCuda 2.0 [recurso eletrônico] : a library for the biased random-key genetic algorithm on GPUs = BrkgaCuda 2.0: uma biblioteca para o algoritmo genético de chave aleatória enviesado em GPUs
Bruno Almêda de Oliveira