Uma Interface de Programação de Aplicações para o BRKGA na plataforma CUDA
Abstract
In this paper we present the development of an Application Programming Interface (API) for the algorithmic framework Biased Random-Key Genetic Algorithms (BRKGA) that executes in the CUDA platform. We compare the performance of our BRKGA API against the standard BRKGA API developed by Toso and Resende, and show that even using a simple entrance level GPGPU, significant speedup can be achieved. In the same spirit of the standard BRKGA API, we developed our API in such a way that all central aspects of the BRKGA logic are dealt by the API and little effort is required by an user of the API. The task of the user is to implement a problem-dependent procedure to convert vectors of random keys into a solution to the specific problem being solved. We provide an example of use of the API for the Traveling Salesman Problem (TSP) and show that the CUDA implementation outperforms the standard API even when this last one is executed in parallel using OpenMP with several threads.
References
Alba, E., Luque, G., and Nesmachnow, S. (2013). Parallel metaheuristics: recent advances and new trends. International Transactions in Operational Research, 20(1):1–48.
Arora, R., Tulshyan, R., and Deb, K. (2010). Parallelization of binary and real-coded genetic algorithms on gpu using cuda. In IEEE Congress on Evolutionary Computation, pages 1–8. IEEE.
Branke, J., Kaußler, T., Smidt, C., and Schmeck, H. (2000). A multi-population approach to dynamic optimization problems. In Evolutionary Design and Manufacture, pages 299–307. Springer.
Czapiński, M. (2013). An effective parallel multistart tabu search for quadratic assignment problem on cuda platform. Journal of Parallel and Distributed Computing, 73(11):1461–1468.
Czapiński, M. and Barnes, S. (2011). Tabu search with two approaches to parallel flowshop evaluation on cuda platform. Journal of Parallel and Distributed Computing, 71(6):802–811.
Dantas, B. D. A. and Cáceres, E. N. (2016). A parallelization of a simulated annealing approach for 0-1 multidimensional knapsack problem using gpgpu. In 2016 28th International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD), pages 134–140. IEEE.
de Almeida Dantas, B. and Cáceres, E. N. (2018). An experimental evaluation of a parallel simulated annealing approach for the 0–1 multidimensional knapsack problem. Journal of Parallel and Distributed Computing, 120:211–221.
Feo, T. A. and Resende, M. G. (1995). Greedy randomized adaptive search procedures. Journal of global optimization, 6(2):109–133.
Glover, F. and Laguna, M. (1998). Tabu search. In Handbook of combinatorial optimization, pages 2093–2229. Springer.
Gonçalves, J. F. and Resende, M. G. (2011). Biased random-key genetic algorithms for combinatorial optimization. Journal of Heuristics, 17(5):487–525.
Gonçalves, J. F. and Resende, M. G. (2012). A parallel multi-population biased randomkey genetic algorithm for a container loading problem. Computers & Operations Research, 39(2):179–190.
Gonçalves, J. F. and Resende, M. G. (2013). A biased random key genetic algorithm for 2d and 3d bin packing problems. International Journal of Production Economics, 145(2):500–510.
Gonçalves, J. F. and Resende, M. G. (2015). A biased random-key genetic algorithm for the unequal area facility layout problem. European Journal of Operational Research, 246(1):86–107.
Gonçalves, J. F., Resende, M. G., and Mendes, J. J. (2011). A biased random-key genetic algorithm with forward-backward improvement for the resource constrained project scheduling problem. Journal of Heuristics, 17(5):467–486.
Hoberock, J. and Bell, N. (2010). Thrust: A parallel template library. http://thrust.github.io/. Accessado: 11-09-2019.
Holland, J. H. (1992). Genetic algorithms. Scientific american, 267(1):66–73.
Kirkpatrick, S., Gelatt, C. D., and Vecchi, M. P. (1983). Optimization by simulated annealing. science, 220(4598):671–680.
Meffert, K., Rotstan, N., Knowles, C., and Sangiorgi, U. (2012). Jgap-java genetic algorithms and genetic programming package. URL: http://jgap. sf. net.
Noronha, T. F., Resende, M. G., and Ribeiro, C. C. (2011). A biased random-key genetic algorithm for routing and wavelength assignment. Journal of Global Optimization, 50(3):503–518.
Pospichal, P., Jaros, J., and Schwarz, J. (2010). Parallel genetic algorithm on the cuda architecture. In European conference on the applications of evolutionary computation, pages 442–451. Springer.
Takemoto, L. A., de Almeida Dantas, B., and Mongelli, H. (2018). A parallel approach of simulated annealing using GPGPU to solve the quadratic assignment problem. In Symposium on High Performance Computing Systems, WSCAD 2018, São Paulo, Brazil, October 1-3, 2018, pages 23–29.
Toso, R. F. and Resende, M. G. C. (2015). A c++ application programming interface for biased random-key genetic algorithms. Optimization Methods and Software, 30(1):81–93.
Zhang, S. and He, Z. (2009). Implementation of parallel genetic algorithm based on cuda. In International Symposium on Intelligence Computation and Applications, pages 24–30. Springer.
Arora, R., Tulshyan, R., and Deb, K. (2010). Parallelization of binary and real-coded genetic algorithms on gpu using cuda. In IEEE Congress on Evolutionary Computation, pages 1–8. IEEE.
Branke, J., Kaußler, T., Smidt, C., and Schmeck, H. (2000). A multi-population approach to dynamic optimization problems. In Evolutionary Design and Manufacture, pages 299–307. Springer.
Czapiński, M. (2013). An effective parallel multistart tabu search for quadratic assignment problem on cuda platform. Journal of Parallel and Distributed Computing, 73(11):1461–1468.
Czapiński, M. and Barnes, S. (2011). Tabu search with two approaches to parallel flowshop evaluation on cuda platform. Journal of Parallel and Distributed Computing, 71(6):802–811.
Dantas, B. D. A. and Cáceres, E. N. (2016). A parallelization of a simulated annealing approach for 0-1 multidimensional knapsack problem using gpgpu. In 2016 28th International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD), pages 134–140. IEEE.
de Almeida Dantas, B. and Cáceres, E. N. (2018). An experimental evaluation of a parallel simulated annealing approach for the 0–1 multidimensional knapsack problem. Journal of Parallel and Distributed Computing, 120:211–221.
Feo, T. A. and Resende, M. G. (1995). Greedy randomized adaptive search procedures. Journal of global optimization, 6(2):109–133.
Glover, F. and Laguna, M. (1998). Tabu search. In Handbook of combinatorial optimization, pages 2093–2229. Springer.
Gonçalves, J. F. and Resende, M. G. (2011). Biased random-key genetic algorithms for combinatorial optimization. Journal of Heuristics, 17(5):487–525.
Gonçalves, J. F. and Resende, M. G. (2012). A parallel multi-population biased randomkey genetic algorithm for a container loading problem. Computers & Operations Research, 39(2):179–190.
Gonçalves, J. F. and Resende, M. G. (2013). A biased random key genetic algorithm for 2d and 3d bin packing problems. International Journal of Production Economics, 145(2):500–510.
Gonçalves, J. F. and Resende, M. G. (2015). A biased random-key genetic algorithm for the unequal area facility layout problem. European Journal of Operational Research, 246(1):86–107.
Gonçalves, J. F., Resende, M. G., and Mendes, J. J. (2011). A biased random-key genetic algorithm with forward-backward improvement for the resource constrained project scheduling problem. Journal of Heuristics, 17(5):467–486.
Hoberock, J. and Bell, N. (2010). Thrust: A parallel template library. http://thrust.github.io/. Accessado: 11-09-2019.
Holland, J. H. (1992). Genetic algorithms. Scientific american, 267(1):66–73.
Kirkpatrick, S., Gelatt, C. D., and Vecchi, M. P. (1983). Optimization by simulated annealing. science, 220(4598):671–680.
Meffert, K., Rotstan, N., Knowles, C., and Sangiorgi, U. (2012). Jgap-java genetic algorithms and genetic programming package. URL: http://jgap. sf. net.
Noronha, T. F., Resende, M. G., and Ribeiro, C. C. (2011). A biased random-key genetic algorithm for routing and wavelength assignment. Journal of Global Optimization, 50(3):503–518.
Pospichal, P., Jaros, J., and Schwarz, J. (2010). Parallel genetic algorithm on the cuda architecture. In European conference on the applications of evolutionary computation, pages 442–451. Springer.
Takemoto, L. A., de Almeida Dantas, B., and Mongelli, H. (2018). A parallel approach of simulated annealing using GPGPU to solve the quadratic assignment problem. In Symposium on High Performance Computing Systems, WSCAD 2018, São Paulo, Brazil, October 1-3, 2018, pages 23–29.
Toso, R. F. and Resende, M. G. C. (2015). A c++ application programming interface for biased random-key genetic algorithms. Optimization Methods and Software, 30(1):81–93.
Zhang, S. and He, Z. (2009). Implementation of parallel genetic algorithm based on cuda. In International Symposium on Intelligence Computation and Applications, pages 24–30. Springer.
Published
2019-11-08
How to Cite
XAVIER, Eduardo.
Uma Interface de Programação de Aplicações para o BRKGA na plataforma CUDA. In: BRAZILIAN SYMPOSIUM ON HIGH PERFORMANCE COMPUTING SYSTEMS (SSCAD), 20. , 2019, Campo Grande.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2019
.
p. 13-24.
DOI: https://doi.org/10.5753/wscad.2019.8653.
