Análise de um algoritmo paralelo de otimização por enxame de partículas semi-autônomas

Na área da engenharia é comum o aparecimento de problemas da classe NP-Difícil. Em razão da ambiguidade acerca da existência de algoritmos polinomiais para solucionar esses problemas, são utilizadas técnicas que demandam grande quantidade de recursos computacionais para encontrar respostas viáveis. Dependendo do cenário da aplicação, essas alternativas podem se mostrar impraticáveis devido o excessivo tempo de processamento que exigem. Nesse contexto, são propostas as meta-heurísticas, que se estabelecem como métodos estocásticos para otimização do processos de busca de soluções. Esses métodos são caracterizados pelo seu comportamento estocástico, por serem independentes do problema abordado e, para o caso de problemas não polinomiais, por conseguirem apresentar soluções factíveis com tempos de processamento inferiores aos de métodos exatos. Nessa classe de algoritmos, tem grande destaque o PSO (Particle Swarm Optimizer), um algoritmo bioinspirado que visa utilizar modelos abstratos de simulação do comportamento coletivo de animais para otimizar o processo de exploração do espaço de busca de um determinado problema. Esse modelo é notório em função da facilidade de implementação e baixo custo computacional. No entanto, o algoritmo em sua forma mais simples, apresenta certas desvantagens em relação ao modo com que navega o espaço de busca, o que pode influenciar o resultado final. Para tentar amenizar esses problemas, a literatura apresenta uma abundância de variações do PSO com diferentes tipos de operadores. Em trabalhos recentes, uma nova variação denominada SAPSO (Semi-Autonomous Particle Swarm Optimizer), que integra operadores de diversidade, cálculo de gradiente e atração e repulsão de partículas, tem apresentado bons resultados em relação a outros algoritmos conhecidos no meio acadêmico. Por se tratar de um trabalho recente, existem poucas pesquisas que explorem o potencial desse algoritmo em diferentes cenários. Tendo isso em mente, este trabalho se propõe a introduzir uma variação do SAPSO em um ambiente de processamento paralelo. Para tal, foi implementado um algoritmo, nomeado PSAPSO (Parallel Semi- Autonomous Particle Swarm Optimizer), utilizando a linguagem de programação C++ em conjunto com a API OpenMP. Para avaliar o algoritmo resultante, esse foi submetido a funções de teste que desafiam sua capacidade de exploração em diferentes aspectos. Para os cenários avaliados, os resultados evidenciam um bom ganho de velocidade e uma melhoria na capacidade de convergência do PSAPSO em relação ao SAPSO.