Análise de um algoritmo paralelo de otimização por enxame de partículas semi-autônomas
| dc.contributor.advisor-co1 | SANTOS FILHO, Reginaldo Cordeiro dos | |
| dc.contributor.advisor-co1Lattes | http://lattes.cnpq.br/9157422386900321 | pt_BR |
| dc.contributor.advisor1 | SALES JUNIOR, Claudomiro de Souza de | |
| dc.contributor.advisor1Lattes | http://lattes.cnpq.br/4742268936279649 | pt_BR |
| dc.creator | SILVA, Abner Cardoso da | |
| dc.creator.Lattes | http://lattes.cnpq.br/4858038825592872 | pt_BR |
| dc.date.accessioned | 2019-11-05T14:31:32Z | |
| dc.date.available | 2019-11-05T14:31:32Z | |
| dc.date.issued | 2019 | |
| dc.description.abstract | In the engineering field, NP-Hard problems are common. Because of the ambiguity about the existence of polynomial-time algorithms to solve these problems, techniques that require a great amount of computational resources are used to find practicable solutions. Depending on the application scenario, these alternatives may be impractical due to the excessive processing time they require. In this context, meta-heuristics are proposed, which are established as stochastic methods to optimize solution search processes. These methods are characterized by their stochastic behavior, because they are independent of the problem addressed and, in the case of non-polynomial problems, they can present feasible solutions with lower processing times than known solutions. In this class of algorithms the PSO (Particle Swarm Optimizer) stands out, which is a bioinspired algorithm that aims to use abstract models of simulation of the collective behavior of animals to optimize the process of exploring the search space of a given problem. This model is notorious for its ease of implementation and low computational cost. However, this algorithm, in its simplest form, has certain disadvantages in relation to the way it browses the search space, which can influence the final result. To try to mitigate these problems, the literature presents an abundance of variations of the PSO with different types of operators. In recent works, a new variation called SAPSO (Semi-Autonomous Particle Swarm Optimizer), which integrates operators of diversity, gradient calculation and attraction and repulsion of particles, has presented good results in relation to other algorithms known in the academic world. Because it is a recent work, there is little research that explores the potential of this algorithm in different scenarios. With this in mind, this paper proposes to introduce a variation of SAPSO in a parallel processing environment. For this, an algorithm, named PSAPSO (Parallel Semi-Autonomous Particle Swarm Optimizer), was implemented using the C++ programming language combined with the OpenMP API. In order to evaluate the resulting algorithm, it has been subjected to test functions that challenge its exploration capacity in different aspects. In the proposed scenarios, the results show improvements in processing speed and convergence capability of PSAPSO in relation to SAPSO. | pt_BR |
| dc.description.resumo | Na área da engenharia é comum o aparecimento de problemas da classe NP-Difícil. Em razão da ambiguidade acerca da existência de algoritmos polinomiais para solucionar esses problemas, são utilizadas técnicas que demandam grande quantidade de recursos computacionais para encontrar respostas viáveis. Dependendo do cenário da aplicação, essas alternativas podem se mostrar impraticáveis devido o excessivo tempo de processamento que exigem. Nesse contexto, são propostas as meta-heurísticas, que se estabelecem como métodos estocásticos para otimização do processos de busca de soluções. Esses métodos são caracterizados pelo seu comportamento estocástico, por serem independentes do problema abordado e, para o caso de problemas não polinomiais, por conseguirem apresentar soluções factíveis com tempos de processamento inferiores aos de métodos exatos. Nessa classe de algoritmos, tem grande destaque o PSO (Particle Swarm Optimizer), um algoritmo bioinspirado que visa utilizar modelos abstratos de simulação do comportamento coletivo de animais para otimizar o processo de exploração do espaço de busca de um determinado problema. Esse modelo é notório em função da facilidade de implementação e baixo custo computacional. No entanto, o algoritmo em sua forma mais simples, apresenta certas desvantagens em relação ao modo com que navega o espaço de busca, o que pode influenciar o resultado final. Para tentar amenizar esses problemas, a literatura apresenta uma abundância de variações do PSO com diferentes tipos de operadores. Em trabalhos recentes, uma nova variação denominada SAPSO (Semi-Autonomous Particle Swarm Optimizer), que integra operadores de diversidade, cálculo de gradiente e atração e repulsão de partículas, tem apresentado bons resultados em relação a outros algoritmos conhecidos no meio acadêmico. Por se tratar de um trabalho recente, existem poucas pesquisas que explorem o potencial desse algoritmo em diferentes cenários. Tendo isso em mente, este trabalho se propõe a introduzir uma variação do SAPSO em um ambiente de processamento paralelo. Para tal, foi implementado um algoritmo, nomeado PSAPSO (Parallel Semi- Autonomous Particle Swarm Optimizer), utilizando a linguagem de programação C++ em conjunto com a API OpenMP. Para avaliar o algoritmo resultante, esse foi submetido a funções de teste que desafiam sua capacidade de exploração em diferentes aspectos. Para os cenários avaliados, os resultados evidenciam um bom ganho de velocidade e uma melhoria na capacidade de convergência do PSAPSO em relação ao SAPSO. | pt_BR |
| dc.identifier.citation | SILVA, Abner Cardoso da. Análise de um algoritmo paralelo de otimização por enxame de partículas semi-autônomas. Orientador: Claudomiro de Souza de Sales Júnior. 2019. 52 f. Trabalho de Curso (Bacharelado em Ciência da Computação) – Faculdade de Computação, Instituto de Ciências Exatas e Naturais, Universidade Federal do Pará, Belém, 2019. Disponível em: http://bdm.ufpa.br/jspui/handle/prefix/2378. Acesso em:. | pt_BR |
| dc.identifier.uri | https://bdm.ufpa.br/jspui/handle/prefix/2378 | |
| dc.rights | Acesso Aberto | pt_BR |
| dc.source | 1 CD-ROM | pt_BR |
| dc.subject | Otimização por enxame de partículas | pt_BR |
| dc.subject | Paralelização | pt_BR |
| dc.subject | Meta-heurística | pt_BR |
| dc.subject.cnpq | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO | pt_BR |
| dc.title | Análise de um algoritmo paralelo de otimização por enxame de partículas semi-autônomas | pt_BR |
| dc.type | Trabalho de Curso - Graduação - Monografia | pt_BR |