Jornal Internacional de Swarm Intelligence e Computação Evolutiva

Abstrato

Análise de desempenho e ajuste para paralelização da otimização de colónias de formigas usando Open MP

Ahmed A Abouelfarag, Walid Mohamed Aly e Ashraf G Elbialy

Resumo O algoritmo de otimização de colónias de formigas (ACO) é uma heurística de computação suave que pertence aos métodos de inteligência de enxame. O ACO provou um bom desempenho na resolução de certos problemas NP-difíceis em tempo polinomial. Este artigo apresenta a análise, design e implementação de ACO como uma Me-heurística Paralela utilizando o framework Open MP. Para melhorar a eficiência da paralelização ACO, são examinados diferentes aspetos relacionados, incluindo o escalonamento de threads, os riscos de corrida e o ajuste eficiente do número efetivo de threads. É apresentado um caso de estudo de resolução do problema do caixeiro viajante (TSP) utilizando diferentes configurações para avaliar o desempenho da abordagem proposta. Os resultados experimentais mostram uma aceleração significativa no tempo de execução em mais de 3 vezes em relação à implementação sequencial.