BrkgaCuda 2.0: a framework for fast biased random-key genetic algorithms on GPUs

In this paper, we present the development of a new version of the BrkgaCuda, called BrkgaCuda 2.0, to support the design and execution of Biased Random-Key Genetic Algorithms (BRKGA) on CUDA/GPU-enabled computing platforms, employing new techniques to accelerate the execution. We compare the performance of our implementation against the standard CPU implementation and a previous GPU implementation. In the same spirit as the standard implementation, all central aspects of the BRKGA logic are dealt with in our framework, and little effort is required to reuse the framework on another problem. The user can also implement the decoder on the CPU in C++ or GPU in CUDA. Moreover, the BrkgaCuda 2.0 provides a decoder that receives a permutation created by sorting the indices of the chromosomes using the genes as keys. To evaluate our framework, we use a total of 54 instances of the Traveling Salesman Problem, the Set Cover Problem, and the Capacitated Vehicle Routing Problem, using two decoders in the last one. Our focus on this work is to improve the performance within the BRKGA logic. We show that the BrkgaCuda 2.0 is the fastest among similar frameworks while still providing solutions of similar quality.