Algoritmo de evolução diferencial em GPU aplicado ao problema Quadrático de Alocação.

Abstract

A utilização de Unidades de Processamento Gráfico (GPUs) para solucionar problemas complexos tem recebido crescente atenção no ambiente acadêmico (e mais recentemente,mineradores de criptomoedas), obtendo resultados cada vez mais rápidos em relação às implementações que utilizam apenas processamento da Unidade Central de Processamento (CPU). Na literatura é comum encontrar relatos de acelerações de 30 vezes na execução de determinados algoritmos pela GPU, principalmente os algoritmos evolucionários. O objetivo deste estudo é verificar o desempenho da GPU para solucionar o Problema Quadrático de Alocação, a partir da utilização do Algoritmo de Evolução Diferencial.Para o desenvolvimento do algoritmo, emprega-se o framework Compute Unified Device Architecture (CUDA) e a técnica de representação Relative Positioning Index– Índice por Posição Relativa (RPI). Neste trabalho são realizados três experimentos baseados na comparação dos três algoritmos desenvolvidos, cada um com uma abordagem de paralelismo diferente, e nas técnicas de exploração de vizinhança implementadas. Por fim, são também comparados os resultados obtidos com os melhores resultados encontrados na literatura, que reforçam a importância de paralelizar algoritmos sempre que for válido, mesmo que estes algoritmos sejam executados apenas pela CPU. A partir de técnicas de paralelismo básicas foram obtidos resultados bem próximos aos que a literatura apresenta, sugerindo que o algoritmo é promissor, mesmo com a diferença entre as representações.