Análise de um algoritmo paralelo de otimização por enxame de partículas semi-autônomas - SILVA, Abner Cardoso da (2019)
In the engineering field, NP-Hard problems are common. Because of the ambiguity about the existence of polynomial-time algorithms to solve these problems, techniques that require a great amount of computational resources are used to find practicable solutions. Depending on the application scenario, these alternatives may be impractical due to the excessive processing time they require. In this context, meta-heuristics are proposed, which are established as stochastic methods to optimize solution search processes. These methods are characterized by their stochastic behavior, because they are independent of the problem addressed and, in the case of non-polynomial problems, they can present feasible solutions with lower processing times than known solutions. In this class of algorithms the PSO (Particle Swarm Optimizer) stands out, which is a bioinspired algorithm that aims to use abstract models of simulation of the collective behavior of animals to optimize the process of exploring the search space of a given problem. This model is notorious for its ease of implementation and low computational cost. However, this algorithm, in its simplest form, has certain disadvantages in relation to the way it browses the search space, which can influence the final result. To try to mitigate these problems, the literature presents an abundance of variations of the PSO with different types of operators. In recent works, a new variation called SAPSO (Semi-Autonomous Particle Swarm Optimizer), which integrates operators of diversity, gradient calculation and attraction and repulsion of particles, has presented good results in relation to other algorithms known in the academic world. Because it is a recent work, there is little research that explores the potential of this algorithm in different scenarios. With this in mind, this paper proposes to introduce a variation of SAPSO in a parallel processing environment. For this, an algorithm, named PSAPSO (Parallel Semi-Autonomous Particle Swarm Optimizer), was implemented using the C++ programming language combined with the OpenMP API. In order to evaluate the resulting algorithm, it has been subjected to test functions that challenge its exploration capacity in different aspects. In the proposed scenarios, the results show improvements in processing speed and convergence capability of PSAPSO in relation to SAPSO.