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

Autores

  • Henrique de Oliveira Gressler Unipampa
  • Márcia Cristina Cera Unipampa

DOI:

https://doi.org/10.5335/rbca.2014.3660

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 conï¬guraçõ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

Os dados de download ainda não estão disponíveis.

Biografia do Autor

  • Henrique de Oliveira Gressler, Unipampa
    Ciência da Computação

Downloads

Publicado

15-08-2014

Edição

v. 6 n. 2 (2014)

Seção

Artigo Original

Licença

Licença Creative Commons
Todos os artigos estão licenciados com a licença Creative Commons Atribuição-NãoComercial-SemDerivações 4.0 Internacional. Autores que publicam nesta revista concordam com os seguintes termos:
a) Autores mantém os direitos autorais e concedem à revista o direito de primeira publicação, com o trabalho simultaneamente licenciado sob a Licença Creative Commons Attribution que permite o compartilhamento do trabalho com reconhecimento da autoria e publicação inicial nesta revista.
b) Autores têm autorização para assumir contratos adicionais separadamente, para distribuição não-exclusiva da versão do trabalho publicada nesta revista (ex.: publicar em repositório institucional ou como capítulo de livro), com reconhecimento de autoria e publicação inicial nesta revista.
c) Autores têm permissão e são estimulados a publicar e distribuir seu trabalho online (ex.: em repositórios institucionais ou na sua página pessoal) a qualquer ponto antes ou durante o processo editorial, já que isso pode gerar alterações produtivas, bem como aumentar o impacto e a citação do trabalho publicado (Veja O Efeito do Acesso Livre).

Como Citar

[1]
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.