PColorAnt3-RT: Um Algoritmo ACO Paralelo para Coloração de Grafos

Authors

  • Carla Negri Lintzmayer UNICAMP
  • Mauro Henrique Mulati Universidade Estadual de Maringá
  • Anderson Faustino da Silva Universidade Estadual de Maringá

DOI:

https://doi.org/10.22456/2175-2745.26274

Abstract

Em trabalhos anteriores foram apresentadas investigações de três diferentes algoritmos baseados em Ant Colony Optimization (ACO) aplicados ao problema de coloração de grafos com k cores. Os resultados obtidos demonstraram que ColorAnt_3-RT é o melhor dentreos três algoritmos ColorAnt-RT, sendocapaz de obter boas e até mesmo ótimas soluções para os melhores valores de k descritos na literatura, além de minimizar a quantidade de conflitos.Porém, em aplicações onde o tempo de execução é um fator crucial, algoritmos ACO não tem sido utilizados. Este artigo propõe e demonstra o uso de uma abordagem paralela para uma arquitetura de {\it hardware} com memória compartilhada com o objetivo de reduzir o tempo de execução de ColorAnt_3-RT, originando o algoritmo paralelo PColorAnt_3-RT que é capaz de encontrar boas e ótimas soluções em tempo de execução aceitável.

Downloads

Download data is not yet available.

Author Biographies

Carla Negri Lintzmayer, UNICAMP

Ciência da Computação

Otimização

Mauro Henrique Mulati, Universidade Estadual de Maringá

Informática

Otimização

Anderson Faustino da Silva, Universidade Estadual de Maringá

Informática

Sistemas de Computação

Published

2013-01-09

How to Cite

Lintzmayer, C. N., Mulati, M. H., & da Silva, A. F. (2013). PColorAnt3-RT: Um Algoritmo ACO Paralelo para Coloração de Grafos. Revista De Informática Teórica E Aplicada, 20(1), 65–86. https://doi.org/10.22456/2175-2745.26274

Issue

Section

Regular Papers