Use este identificador para citar ou linkar para este item: https://repositorio.unipampa.edu.br/jspui/handle/riu/1568
Tipo: Trabalho de Conclusão de Curso
Título: Aumentando a eficiência de um algoritmo genético através da paralelização com OpenMP
Autor(es): Gressler, Henrique de Oliveira
Primeiro Orientador: Cera, Márcia Cristina
Resumo: Este trabalho propõe a implementação e paralelização de um Algoritmo Genético (AG) para resolver o Problema do Roteamento de Veículos (PRV). O PRV é um problema combinatório pertencente à classe dos NP-Completos. Em sua forma canônica, consiste em rotear veículos que possuem uma capacidade de transporte para determinado produto. Os veículos devem atender as cidades distribuídas em um mapa, que possuem certa demanda para o produto transportado. A solução do problema passa pela determinação de rotas que minimizem a distância total percorrida e, que atenda todas as demandas das cidades do mapa, sendo que cada cidade deve ser visitada apenas uma vez. Resolver problemas combinatórios deste tipo traz avanços em várias áreas do conhecimento, como a concepção de circuitos integrados e a realização de testes combinatórios aplicados aos protocolos de redes de computadores. O objetivo geral deste trabalho é implementar um AG capaz de encontrar bons resultados para o PRV em um tempo de computação razoável e, através da paralelização com OpenMP, obter resultados compatíveis com os encontrados pela versão sequencial e, melhores se executado pelo tempo da versão sequencial. Nesse sentido, foram testados os diversos parâmetros de um AG, com objetivo de determinar qual combinação dos mesmos conduz a melhores resultados. Nesta busca ficou evidenciado que a variação do tamanho da população e do número de evoluções influencia significativamente no tempo necessário para encontrar uma solução e também na qualidade desta solução. Baseado na implementação sequencial, foi desenvolvida uma versão paralela usando a Application Program Interface (API) OpenMP. A paralelização consistiu em encontrar regiões que pudessem ser executadas em paralelo e eleger as diretivas de paralelização baseado nas características de cada região. Também foram testadas várias combinações de políticas de escalonamento e granularidade, para determinar quais as mais eficientes. Os melhores speedups foram obtidos pela versão com 4 threads, mantendo a qualidade das soluções compatível com o encontrado pela versão sequencial. Executar a versão paralela com 4 threads pelo tempo da versão sequencial, permitiu avaliar um número de indivíduos aproximadamente 100% maior, possibilitando encontrar melhores soluções.
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.
Palavras-chave: Computer science
Genetic algorithms
Parallelization
OpenMP
Meta-heuristic
Ciência da computação
Algoritmos genéticos
Paralelização
OpenMP
Meta-heurística
CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA
Editor: Universidade Federal do Pampa
Campus: Campus Alegrete
Tipo de Acesso: Attribution-NonCommercial-NoDerivs 3.0 Brazil
Licença: http://creativecommons.org/licenses/by-nc-nd/3.0/br/
URI: http://dspace.unipampa.edu.br/jspui/handle/riu/1568
Data do documento: 4-Mar-2013
Aparece nas coleções:Ciência da Computação

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
Aumentando a eficiência de um algoritmo genético através da paralelização com OpenMP.pdf2.4 MBAdobe PDFVisualizar/Abrir


Este item está licenciada sob uma Licença Creative Commons Creative Commons