Melhorando o desempenho de um algoritmo genético paralelizado com OpenMP

Abstract

This work proposes two versions of a implementation using the Island Model of a Genetic Algorithm(GA). The difference between these two versions consist on the number of evolutions each island will perform. Each version is then applied to the Vehicle Routing Problem (VRP) and parallelized with OpenMP. The VRP is a combinatorial problem, where a vehicle with limited capacity must supply a number of neighborhoods or cities, requiring a return to the deposit to replenish when its capacity is exhausted. The solution of the problem is a path that meets all cities or neighborhoods and has the smallest total distance possible. To solve this problem, a GA is used, which consists on a type of metaheuristic that simulates the evolutionary behavior that each species go through. The Island Model is a variation of GA that utilizes multiple populations (islands), where on each one of these populations the species evolutionary behavior will be simulated. This GA is parallelized using the API (Application Interface) OpenMP. To the performance of the GA executions of the GA will be tested, where these tests will be divided in three moments. The first moment tests the overall performance of the GA and compares the new versions, one that uses the Island Model, and the conventional version of the GA. The second moment compares the efficiency of the executions realized on the architecture that is utilized, verifying which of the two versions of the GA applied to the Island Model obtained the best computational efficiency. The third moment realizes a comparison between the solutions obtained with the GA to better observe which of the two versions obtained a better quality of solution. After the tests, realized with the instances c50, c100, c120 and c150 a gain on speedup higher than 5 was obtained when 6 threads were used on an architecture with 6 processing cores , resulting on a higher performance when compared to past works, thus proving the efficiency of the Island Model as an alternative to increae the performance of the GA. Additionally, it was possible to verify that the Island Model allows the GA to reach solutions of good quality when compared to solutions obtained on previous works. Also, when comparing both versions of the Island Model it was possible to observe that while the Version 2 has better speedups on average and reaches better solutions, it suffers from a significant increase on the execution times, thus favoring the use of the Version 1, since their differences on speedup and quality of solution are not significant.