Computação paralela e bio-inspirada: algoritmos genéticos multipopulação e autômatos celulares híbridos

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.