Aumentando a eficiência de um algoritmo genético através da paralelização com OpenMP

Abstract

This work proposes the implementation and parallelization of a Genetic Algorithm (GA) to solve the VRP. The VRP is a combinatorial problem wich belongs to the class of NP-Complete. The VRP in its canonical form, consists to route vehicles that have a carrying capacity for a particular product. Vehicles must get to the cities distributed on a map, which have certain demand for the carried product. The solution to the problem is to identify routes that minimize the total distance traveled, and that meets all the demands of the cities on the map, and each city must be visited only once. Solving this kind of combinatorial problems brings advances in various areas of knowledge such as the design of integrated circuits and combinatorial testing protocols applied to computer networks. This work showed that the variation in population size and number of evolutions significantly influences the time needed to find a solution and also in the quality of this solution. Based on the sequential implementation, we developed a parallel version using the OpenMP API. The parallelization was consisted on finding areas that could be executed in parallel and electing parallelization policies based on the characteristics of each region. We also tested several combinations of scheduling policies and granularity to determine the most efficient for the application. The best speedups were obtained by the version with 4 threads, which when executed by sequential version time, allowed to evaluate a number of individuals approximately 100% greater, enabling the finding of better solutions.