Use este identificador para citar ou linkar para este item: https://repositorio.unipampa.edu.br/jspui/handle/riu/4789
Tipo: Trabalho de Conclusão de Curso
Título: Uso de operações SIMD em uma biblioteca de algoritmos bio-inspirados
Autor(es): Lucca, Natiele
Primeiro Orientador: Schepke, Claudio
Resumo: Algoritmos de otimização buscam resolver problemas complexos. Uma estratégia para modelar algoritmicamente um problema é utilizar conceitos de computação natural, também conhecida como computação bio-inspirada. Os algoritmos bio-inspirados simulam a capacidade de aprendizado ou adaptação de um grupo de indivíduos inteligentes submetidos a um ambiente complexo e assim otimizam uma solução inicial com o objetivo de encontrar soluções ótimas. Dessa forma, neste trabalho é proposto uma biblioteca open source bio-inspirada e paralela. Constituem essa biblioteca os algoritmos Artificial Bee Colony (Colônia Artificial de Abelhas - ABC), Ant Colony Optimization (Otimização por Colônia de Formigas - ACO) e Particle Swarm Optimization (Otimização por Enxame de Partículas - PSO), desenvolvidos na linguagem de programação C++. O trabalho testa diretivas de execução paralela e vetorial, comparando o desempenho das diretivas individualmente e combinadas. A diretiva de execução vetorial obteve o maior número de testes com ganho de desempenho, sendo essa diretiva aplicada nos algoritmos selecionados para a biblioteca. Após a implementação paralela, os algoritmos foram submetidos às funções clássicas de teste Alpine, Booth, Easom, Griewank, Rastrigin, Rosenbrock e Sphere, sendo aplicados a uma população de 10 até 100 agentes. Os resultados obtidos mostraram que as versões sequencial e paralela obtiveram a mesma solução média e que para pelo menos um teste de população todas as funções obtiveram ganho de desempenho. Com isso, comprovou-se que a versão paralela dos algoritmos desenvolvidos mantém a qualidade da solução e reduz o tempo de execução.
Abstract: Optimization algorithms seeks to resolve complex problems. A strategy to algorithmically model a problem is to use concepts of Natural Computing, also known as Bio-inspired Computing. Bio-inspired algorithms simulate the ability of learn or adapt a smart group of individuals subjected to a complex environment and thus optimize initial solution in order to find optimal solutions in a polynomial time. In this way, this work proposes an open source, bio-inspired, and parallel library. This library is composed by Artificial Bee Colony (ABC), Ant Colony Optimization (ACO) and Particle Swarm Optimization (PSO) algorithms developed in C++ programming language. The OpenMP API was used for the parallelization of algorithms. The work tests parallel and vectorization directives execution by comparing the performance of individual and combined directives. The vectorization directive execution obtained the highest number of tests with performance gain. This directive was applied to the selected algorithms of the library. After the parallel implementation, the algorithms were submitted to the classic test functions Alpine, Booth, Easom, Griewank, Rastrigin, Rosenbrock and Sphere, being applied to a population of 10 to 100 agents. The results showed that the sequential and parallel versions obtained the same average solution and that, for at least one population test, all functions obtained performance gains. With this, we prove that the parallel version of the developed algorithms maintains the quality of the solution and reduces the execution time.
Palavras-chave: Ciência da computação
Algoritmos
Biblioteca
OpenMP
Otimização
Artificial Bee Colony
Ant Colony Optimization
Particle Swarm Optimization
Computer science
Algorithms
Library
CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA
Idioma: por
País: Brasil
Editor: Universidade Federal do Pampa
Sigla da Instituição: UNIPAMPA
Campus: Campus Alegrete
Citação: LUCCA, Natiele. Uso de operações SIMD em uma biblioteca de algoritmos bio-inspirados. Orientador: Claudio Schepke. 2019. 85 p. Trabalho de Conclusão de Curso (Bacharel em Ciência da Computação) - Universidade Federal do Pampa, Curso de Ciência da Computação, Alegrete, 2019.
Tipo de Acesso: Acesso Aberto
URI: http://dspace.unipampa.edu.br:8080/jspui/handle/riu/4789
Data do documento: 25-Nov-2019
Aparece nas coleções:Ciência da Computação

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
Natiele Lucca - 2019.pdf1.56 MBAdobe PDFVisualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.