Uma Interface de Programação de Aplicações para o BRKGA na plataforma CUDA

Eduardo Xavier

doi:10.5753/wscad.2019.8653

Eduardo Xavier State University of Campinas

DOI: https://doi.org/10.5753/wscad.2019.8653

Resumo

Neste artigo apresentamos o desenvolvimento de uma Interface de Programação de Aplicações (IPA) para o framework Biased Random-Key Genetic Algorithms (BRKGA), para execução na plataforma CUDA. Nós comparamos a performance da IPA para BRKGA proposta contra uma IPA padrão para BRKGA proposta por Toso e Resende, e mostramos que mesmo usando uma GPGPU de entrada, é possı́vel obter um speedup significativo. No mesmo espı́rito da IPA padrão para BRKGA, nós desenvolvemos a nossa IPA de tal forma que os aspectos lógicos principais do BRKGA são considerados na IPA e pouco esforço de um usuário é requerido para usar a IPA para implementar soluções para problemas especı́ficos. O trabalho do usuário é a implementação de uma função dependente do problema, que dado um vetor de chaves aleatórias computa uma solução para o problema sendo considerado. Nós apresentamos um exemplo de uso da IPA para o problema Traveling Salesman Problem (TSP) e mostramos que a execução da IPA em CUDA é mais rápida do que a execução da IPA padrão mesmo quando esta última é executada em paralelo com uso de OpenMP com várias threads de processamento.

Referências

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.

Czapiń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.

Czapiń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 Cá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 Cá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.

Gonçalves, J. F. and Resende, M. G. (2011). Biased random-key genetic algorithms for combinatorial optimization. Journal of Heuristics, 17(5):487–525.

Gonç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.

Gonç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.

Gonç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.

Gonç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, Sã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.