Implementações GPGPU do Algoritmo de Otimização por Enxame de Partı́culas para o Problema da Mochila Multidimensional

  • Bárbara S Munhão Universidade Federal do Mato Grosso do Sul
  • Bianca A Dantas Universidade Federal do Mato Grosso do Sul
  • Edson N Cáceres Universidade Federal do Mato Grosso do Sul
  • Henrique Mongelli Universidade Federal do Mato Grosso do Sul

Resumo


Um dos problemas mais conhecidos de otimização combinatória, que possui diversas aplicações práticas, é o problema da mochila multidimensional (MKP). Apesar de sua popularidade e da demanda por soluções de alta qualidade, este é um problema N P-difı́cil, o que leva à necessidade de buscar estratégias alternativas para obtenção de boas soluções em tempo viável. Neste contexto, as metaheurı́sticas se destacam, visto que têm sido bem sucedidas na resolução de diferentes problemas difı́ceis, inclusive do MKP. Neste trabalho, são propostas duas implementações usando GPGPU do algoritmo de otimização por enxame de partı́culas (PSO). A redução nos tempos de execução dos programas GPGPU em comparação com a versão sequencial foi relevante, o que mostrou a eficácia do uso de estratégias de paralelização com a metaheurı́stica estudada.

Referências

Beasley, J. E. (1990). OR-Library: distributing test problems by electronic mail. Journal of the Operational Research Society, 41(11):1069–1072.

Chih, M., Lin, C.-J., Chern, M.-S., and Ou, T.-Y. (2014). Particle swarm optimization with time-varying acceleration coefficients for the multidimensional knapsack problem. Applied Mathematical Modelling, 38(4):1338 – 1350.

Chu, P. C. and Beasley, J. E. (1998). A genetic algorithm for the multidimensional knapsack problem. Journal of Heuristics, 4(1):63–86.

Essaid, M., Idoumghar, L., Lepagnot, J., and Brévilliers, M. (2019). Gpu parallelization strategies for metaheuristics: a survey. International Journal of Parallel, Emergent and Distributed Systems, 34(5):497–522.

Fingler, H., Cáceres, E. N., Mongelli, H., and Song, S. W. (2014). A cuda based solution to the multidimensional knapsack problem using the ant colony optimization. Procedia Computer Science, 29:84 – 94. 2014 International Conference on Computational Science.

Glover, F. and Kochenberger, G. (n.d.). Benchmarks for the multiple knapsack problem. http://hces.bus.olemiss.edu/tools.html.

Hembecker, F., Lopes, H. S., and Godoy, W. (2007). Particle swarm optimization for the multidimensional knapsack problem. In Beliczynski, B., Dzielinski, A., Iwanowski, M., and Ribeiro, B., editors, Adaptive and Natural Computing Algorithms, pages 358–365, Berlin, Heidelberg. Springer Berlin Heidelberg.

Jam, S., Shahbahrami, A., and Sojoudi Ziyabari, S. H. (2017). Parallel implementation of particle swarm optimization variants using graphics processing unit platform. International Journal of Engineering, 30(1):48–56.

Kennedy, J. and Eberhart, R. (1995). Particle swarm optimization. In Proceedings of ICNN’95 - International Conference on Neural Networks, volume 4, pages 1942–1948.

NVIDIA (2019). CUDA Zone. https://developer.nvidia.com/cuda-zone.

Veni, K. K. and Balachandar, S. R. (2010). A new heuristic approach for large size zero–one multi knapsack problem using intercept matrix. International Journal of Computational and Mathematical Sciences, 4(5):259–263.

Zan, D. and Jaros, J. (2014). Solving the multidimensional knapsack problem using a cuda accelerated pso. In 2014 IEEE Congress on Evolutionary Computation (CEC), pages 2933–2939.
Publicado
12/11/2019
MUNHÃO, Bárbara S; DANTAS, Bianca A; CÁCERES, Edson N; MONGELLI, Henrique. Implementações GPGPU do Algoritmo de Otimização por Enxame de Partı́culas para o Problema da Mochila Multidimensional. In: WORKSHOP DE COMPUTAÇÃO HETEROGÊNEA - SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (SSCAD), 20. , 2019, Campo Grande. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2019 . p. 96-107. DOI: https://doi.org/10.5753/wscad_estendido.2019.8703.