Algoritmo genético paralelo: uma abordagem memética em ilhas

Abstract

This work investigates the application of parallel memetic genetic algorithms to solve the Capacitated Vehicle Routing Problem (CVRP), a classical combinatorial optimization problem widely studied in the literature. The proposed approach adopts the island model, in which multiple subpopulations evolve in a partially independent manner, periodically exchanging individuals through migration mechanisms in order to preserve genetic diversity and mitigate premature convergence. The developed algorithm incorporates genetic operators tailored for permutation-based problems, different selection strategies, and a local search operator based on the 2-opt method, characterizing a memetic approach. Parallelization is implemented in a shared-memory environment using the OpenMP library, allowing the evaluation of the impact of different communication topologies between islands, such as ring and mesh. The experimental results obtained from classical CVRP benchmark instances analyze both the quality of the solutions and the computational behavior of the parallel approach, considering metrics such as execution time, speedup, and efficiency in a complementary manner. The results indicate that the island model contributes positively to achieving higher-quality solutions, while also providing consistent computational gains in multicore environments.