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.
|
