Implementações GPGPU do Algoritmo de Otimização por Enxame de Partı́culas para o Problema da Mochila Multidimensional

Bárbara S Munhão; Bianca A Dantas; Edson N Cáceres; Henrique Mongelli

doi:10.5753/wscad_estendido.2019.8703

Bárbara S Munhão Universidade Federal do Mato Grosso do Sul
Bianca A Dantas Universidade Federal do Mato Grosso do Sul
Edson N Cáceres Universidade Federal do Mato Grosso do Sul
Henrique Mongelli Universidade Federal do Mato Grosso do Sul

DOI: https://doi.org/10.5753/wscad_estendido.2019.8703

Resumo

Um dos problemas mais conhecidos de otimização combinatória, que possui diversas aplicações práticas, é o problema da mochila multidimensional (MKP). Apesar de sua popularidade e da demanda por soluções de alta qualidade, este é um problema N P-difı́cil, o que leva à necessidade de buscar estratégias alternativas para obtenção de boas soluções em tempo viável. Neste contexto, as metaheurı́sticas se destacam, visto que têm sido bem sucedidas na resolução de diferentes problemas difı́ceis, inclusive do MKP. Neste trabalho, são propostas duas implementações usando GPGPU do algoritmo de otimização por enxame de partı́culas (PSO). A redução nos tempos de execução dos programas GPGPU em comparação com a versão sequencial foi relevante, o que mostrou a eficácia do uso de estratégias de paralelizaçã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 Brévilliers, M. (2019). Gpu parallelization strategies for metaheuristics: a survey. International Journal of Parallel, Emergent and Distributed Systems, 34(5):497–522.

Fingler, H., Cá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.