Please use this identifier to cite or link to this item: https://repositorio.ufu.br/handle/123456789/31628
ORCID:  http://orcid.org/0000-0001-6709-7642
Document type: Dissertação
Access type: Acesso Aberto
Title: Computação paralela e bio-inspirada: algoritmos genéticos multipopulação e autômatos celulares híbridos
Alternate title (s): Parallel and bio-inspired computing: multipopulation genetic algorithms and hybrid cellular automata
Author: Morais, Bruno Well Dantas
First Advisor: Oliveira, Gina Maira Barbosa de
First member of the Committee: Miani, Rodrigo Sanches
Second member of the Committee: Delbem, Alexandre Cláudio Botazzo
Summary: This work consists of an investigation about the application of parallel computing techniques to bio-inspired models based on cellular automata (CA) and genetic algorithms (GA) in the context of their application to cryptography and the task scheduling problem, respectively. The Hybrid Cellular Automata (HCA) model features two algorithms that perform forward and backward evolution, where the states of a grid of cells are iteratively updated according to transition rules and nearby cells. This model is applied to cryptography, which aims for secure communication by encoding messages to prevent unintended access to the information. The Multipopulation Genetic Algorithm (MPGA) is a variation of GA intended for the application of parallel computing. This model consists of the evolution of multiple sets of solutions by means of stochastic operators for search and optimization applications. This algorithm is applied to the task scheduling problem, a computationally intractable problem that consists of minimizing the execution time of interdependent tasks assigned to a set of processors. Sequential and parallel implementations of these models were developed with the Python language, with implementations aimed to multicore processors (CPU) and graphics processing units (GPU) in the case of the HCA, and distributed memory and shared memory approaches for multicore processors in the case of the MPGA. With these implementations, experiments were conducted to quantify the performance gains of each parallel approach in comparison to the sequential implementations. The performance of the HCA algorithms was benefited by the parallel execution on GPU, while the parallel CPU implementations resulted in the loss of performance due to overhead. The experiments involving the parameterization of MPGA demonstrated a trade-off between the quality of solutions and execution time. In this case, a multiobjective analysis was employed, elucidating highly efficient configurations considering both of these performance metrics.
Abstract: This work consists of an investigation about the application of parallel computing techniques to bio-inspired models based on cellular automata (CA) and genetic algorithms (GA) in the context of their application to cryptography and the task scheduling problem, respectively. The Hybrid Cellular Automata (HCA) model features two algorithms that perform forward and backward evolution, where the states of a grid of cells are iteratively updated according to transition rules and nearby cells. This model is applied to cryptography, which aims for secure communication by encoding messages to prevent unintended access to the information. The Multipopulation Genetic Algorithm (MPGA) is a variation of GA intended for the application of parallel computing. This model consists of the evolution of multiple sets of solutions by means of stochastic operators for search and optimization applications. This algorithm is applied to the task scheduling problem, a computationally intractable problem that consists of minimizing the execution time of interdependent tasks assigned to a set of processors. Sequential and parallel implementations of these models were developed with the Python language, with implementations aimed to multicore processors (CPU) and graphics processing units (GPU) in the case of the HCA, and distributed memory and shared memory approaches for multicore processors in the case of the MPGA. With these implementations, experiments were conducted to quantify the performance gains of each parallel approach in comparison to the sequential implementations. The performance of the HCA algorithms was benefited by the parallel execution on GPU, while the parallel CPU implementations resulted in the loss of performance due to overhead. The experiments involving the parameterization of MPGA demonstrated a trade-off between the quality of solutions and execution time. In this case, a multiobjective analysis was employed, elucidating highly efficient configurations considering both of these performance metrics.
Keywords: Autômato celular
Algoritmo genético
Criptografia
Escalonamento de tarefas
Computação paralela
Cellular automata
Genetic algorithms
Cryptography
Task scheduling
Parallel computing
Computação
Area (s) of CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Subject: Computação
Language: eng
Country: Brasil
Publisher: Universidade Federal de Uberlândia
Program: Programa de Pós-graduação em Ciência da Computação
Quote: MORAIS, Bruno Well Dantas. Computação paralela e bio-inspirada: algoritmos genéticos multipopulação e autômatos celulares híbridos. 2020. 138 f. Dissertação (Mestrado em Ciência da Computação) - Universidade Federal de Uberlândia, Uberlândia, 2020. Disponível em: http://doi.org/10.14393/ufu.di.2021.29.
Document identifier: http://doi.org/10.14393/ufu.di.2021.29
URI: https://repositorio.ufu.br/handle/123456789/31628
Date of defense: 14-Dec-2020
Appears in Collections:DISSERTAÇÃO - Ciência da Computação

Files in This Item:
File Description SizeFormat 
ComputacaoParalelaBioInspirada.pdfDissertação21.42 MBAdobe PDFThumbnail
View/Open


This item is licensed under a Creative Commons License Creative Commons