O impacto da paralelização com OpenMP no desempenho e na qualidade das soluções de um Algoritmo Genético

  • Henrique de Oliveira Gressler Unipampa
  • Márcia Cristina Cera Unipampa
Palavras-chave: Algoritmos Genéticos, Qualidade das Soluções, OpenMP, Desempenho,

Resumo

O Problema do Roteamento de Veículos (PRV) é um problema combinatório de difícil solução, aplicável tanto para logística de empresas de transporte quanto para melhor ocupação das vias públicas. Resolvê-lo testando todas as combinações possíveis (método de força bruta) torna-se inviável à medida que o problema escala, pois demanda um tempo de computação muito grande. Os Algoritmos Genéticos (AG) são meta-heurísticas capazes de encontrar soluções em um tempo computacional aceitável. Entretanto, mesmo os AG podem demandar um elevado tempo de processamento, dependendo das configurações utilizadas. Com a evolução das arquiteturas computacionais e a difusão das arquiteturas multicore, o uso da programação multithread torna-se uma alternativa para reduzir o tempo envolvido na solução de problemas combinatórios. Este artigo objetiva acelerar a resolução do PRV por meio da paralelização do AG com OpenMP, que é um padrão amplamente difundido para programação multithread. Nossos resultados atingiram um speedup acima de 2, utilizando 4 threads em um processador quadcore. Esse ganho está limitado à forma como o AG está implementado. Além do impacto no desempenho do AG também comprovou-se que o uso do OpenMP não afeta a qualidade das soluções. Adicionalmente, o uso do OpenMP permitiu que o AG encontrasse melhores soluções devido ao aumento do número de evoluções computadas num mesmo intervalo de tempo.

Downloads

Não há dados estatísticos.

Biografia do Autor

Henrique de Oliveira Gressler, Unipampa
Ciência da Computação
Publicado
2014-08-15
Como Citar
[1]
Gressler, H. e Cera, M. 2014. O impacto da paralelização com OpenMP no desempenho e na qualidade das soluções de um Algoritmo Genético. Revista Brasileira de Computação Aplicada. 6, 2 (ago. 2014), 35-47. DOI:https://doi.org/10.5335/rbca.2014.3660.
Seção
Artigo Original
Share |