ALGORITMO OTIMIZAÇÃO POR ENXAME DE PARTÍCULAS PARALELO

Resumo

O algoritmo otimização por Enxame de Partículas (do inglês Particle Swarm Optimization - PSO) foi modelado a partir do comportamento social do bando de aves. No algoritmo PSO, a população de indivíduos ou partículas são agrupados em um enxame que são um conjunto de possíveis soluções. Essas partículas simulam o comportamento de pássaros através do aprendizado próprio (componente cognitivo) e o aprendizado do bando (componente social), ou seja, imitam o seu próprio sucesso e o de indivíduos vizinhos. A partir desse comportamento as partículas assumem novas posições no espaço de busca que as direcionam para soluções ótimas (cálculo de aptidão). O objetivo deste trabalho é implementar uma versão paralela do algoritmo PSO clássico na linguagem de programação C++ e utilizar instruções OpenMP para o paralelismo. Os segmentos de código do algoritmo paralelizados foram o laço de repetição que atualiza as posições e a velocidade das partículas, e a função objetivo ou benchmark. Os métodos foram implementados no Atom e executados em uma máquina com dois processadores Intel®️ CoreTM Xeon CPU E5-2650, de 2.00 GHz de frequência, com 8 núcleos cada, memória RAM de 128 GB e com sistema operacional Ubuntu na versão 16.04 de 64 bits. Para avaliar o desempenho do algoritmo paralelo desenvolvido, seis funções de benchmark clássicas foram utilizadas, são elas: Alpine, Booth, Easom, Rastrigin, Rosenbrock e Sphere. Essas são funções de otimização global para minimização de funções. O primeiro teste realizado aplica a diretiva pragma simd nas funções objetivos dos benchmarks e a diretiva pragma simd na função que atualiza a posição e a velocidade das partículas. O segundo teste aplica a diretiva pragma simd nas funções objetivos e a diretiva pragma parallel for com 2 threads na função que atualiza a posição e a velocidade das partículas. Os testes foram repetidos 30 vezes para cada função, pois como os algoritmos utilizam valores aleatórios é importante realizar repetições para minimizar as chances de obtenção de resultados equivocados. Foram analisados para cada execução a solução final encontrada e o tempo de execução, os valores menores que 10 no expoente -100 foram arredondados para zero a fim de facilitar a interpretação dos dados. Analisando os resultados obtidos as funções Alpine, Rastrigin, Rosenbrock e Sphere obtiveram a média das soluções próximas da ótima com desvio padrão médio de 0,1 e tempos de execução inferior ao sequencial no primeiro teste realizado. Enquanto as funções Booth e Easom pioraram a solução média em ambos os testes e melhoram o tempo de execução no segundo teste. De acordo com os resultados podemos perceber que a diretiva simd possibilita a vetorização dos loops gerando um considerável ganho desempenho para problemas com pouco volume de dados.