Otimização de cache e paralelização de um algoritmo genético para o problema da mochila multidimensional
Resumo
O problema da mochila multidimensional é uma extensão do problema da mochila binária com ampla aplicação prática, como na alocação de recursos limitados. Por pertencer à classe NP-difícil, para a qual não se conhece algoritmo exato de tempo polinomial, a busca por métodos de resolução eficientes é recorrente na literatura. Este trabalho apresenta uma reformulação do algoritmo genético de Chu e Beasley orientada à localidade de cache, complementada por paralelização em OpenMP com modelo de ilhas. A proposta foi avaliada contra o algoritmo genético sequencial de referência sobre 335 instâncias clássicas da literatura, com validação por testes estatísticos. Os resultados mostram speedup médio de 5,6× (de 1,5× a 13,8×), em sua maior parte decorrente da reformulação sequencial, sem comprometer a qualidade das soluções obtidas.Referências
Chu, P. C. and Beasley, J. E. (1998). A genetic algorithm for the multidimensional knapsack problem. Journal of Heuristics, 4(1):63–86.
Dagum, L. and Menon, R. (1998). OpenMP: An industry-standard API for shared-memory programming. IEEE Computational Science and Engineering, 5(1):46–55.
Dantas, B. (2016). Metaheurísticas para o Problema da Mochila Multidimensional. PhD thesis, Faculdade de Computação, Universidade Federal de Mato Grosso do Sul, Campo Grande, MS.
Fréville, A. (2004). The multidimensional 0–1 knapsack problem: An overview. European Journal of Operational Research, 155(1):1–21.
Fréville, A. and Hanafi, S. (2005). The multidimensional 0–1 knapsack problem—bounds and computational aspects. Annals of Operations Research, 139(1):195–227.
Hennessy, J. and Patterson, D. (2017). Computer Architecture: A Quantitative Approach. Morgan Kaufmann, 6th edition.
Holm, S. (1979). A simple sequentially rejective multiple test procedure. Scandinavian Journal of Statistics, 6(2):65–70.
Mann, H. and Whitney, D. (1947). On a test of whether one of two random variables is stochastically larger than the other. Annals of Mathematical Statistics, 18(1):50–60.
Dagum, L. and Menon, R. (1998). OpenMP: An industry-standard API for shared-memory programming. IEEE Computational Science and Engineering, 5(1):46–55.
Dantas, B. (2016). Metaheurísticas para o Problema da Mochila Multidimensional. PhD thesis, Faculdade de Computação, Universidade Federal de Mato Grosso do Sul, Campo Grande, MS.
Fréville, A. (2004). The multidimensional 0–1 knapsack problem: An overview. European Journal of Operational Research, 155(1):1–21.
Fréville, A. and Hanafi, S. (2005). The multidimensional 0–1 knapsack problem—bounds and computational aspects. Annals of Operations Research, 139(1):195–227.
Hennessy, J. and Patterson, D. (2017). Computer Architecture: A Quantitative Approach. Morgan Kaufmann, 6th edition.
Holm, S. (1979). A simple sequentially rejective multiple test procedure. Scandinavian Journal of Statistics, 6(2):65–70.
Mann, H. and Whitney, D. (1947). On a test of whether one of two random variables is stochastically larger than the other. Annals of Mathematical Statistics, 18(1):50–60.
Publicado
03/09/2026
Como Citar
MARQUES, Henrique de Oliveira; BARROS, Janderson Souza; DANTAS, Bianca de Almeida.
Otimização de cache e paralelização de um algoritmo genético para o problema da mochila multidimensional. In: ESCOLA REGIONAL DE ALTO DESEMPENHO DO CENTRO-OESTE (ERAD-CO), 9. , 2026, Campo Grande/MS.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2026
.
p. 47-49.
DOI: https://doi.org/10.5753/eradco.2026.34581.
