Algoritmos genéticos para famílias de autómatos celulares em dimensão 1

Abstract

Os autómatos celulares são sistemas dinâmicos e discretos que podem ser interpretados como programas simples que desempenham funções computacionais ou como organismos digitais que exibem comportamentos característicos. De um ponto de vista biológico, cada autómato celular é caracterizado por um código similar ao código genético biológico - o genótipo - código esse que vai definir as regras para a realização do autómato celular, tal como acontece com os organismos biológicos. O genótipo do autómato celular vai definir as regras de transição do autómato celular, sendo que a concretização destas regras vai resultar na realização do autómato celular, que é representada num diagrama espaço-tempo. Esta realização vai apresentar, visualmente, padrões e características únicas dependendo do genótipo e das condições iniciais, sendo que esta realização pode também ser, analogamente, relacionada com a biologia, sendo definida como o fenótipo do autómato celular. O presente trabalho tem como principal objetivo estudar as dinâmicas evolutivas dos autómatos celulares quando sujeitos a operações genéticas, como mutação, replicação e recombinação. Para este estudo foi necessário implementar em Python um algoritmo que permitisse gerar e comparar fenótipos de diferentes autómatos celulares (a partir dos genótipos) para perceber de que forma as operações genéticas influenciam a estabilidade do fenótipo, ou seja, de que forma os padrões e características visuais são afetadas quando sujeitas a estas operações genéticas. Foi também implementado um algoritmo para estudar a evolução de populações de autómatos celulares que utiliza a operação genética de recombinação para evoluir uma determinada população e que permite perceber de que forma os genótipos e fenótipos evoluem em determinadas populações com diferentes características. Estas diferentes características de populações estão associadas à proximidade inicial dos genótipos, ou seja, podem existir populações em que os genótipos vão ser muito próximos inicialmente e populações em que os genótipos vão ser muito variados, sendo posteriormente analisado de que forma as características das populações subsistem e evoluem. Nesta dissertação vão ser estudados estes dois casos de populações e também um caso em que os genótipos na população são muito próximos inicialmente mas que contém um invasor, ou seja, foi introduzido um genótipo muito diferente dos existentes na população e é estudado como os genótipos e fenótipos dos descendentes são afetados; Abstract: Genetic algorithms for cellular automata families in dimension 1 - Cellular automata are dynamic, discrete systems that can be interpreted as simple programs that perform computational functions or as digital organisms that exhibit characteristic behaviors. From a biological point of view, each cellular automaton is characterized by a code similar to the biological genetic code - the genotype - code that will define the rules for the realization of the cellular automaton, as with biological organisms. The genotype of the cellular automaton will define the transition rules of the cellular automaton, and the realization of these rules will result in the realization of the cellular automaton, which is represented in a space-time diagram. This realization will visually present unique patterns and characteristics depending on the genotype and the initial conditions, and this realization can also be, analogously, related to biology, being defined as the phenotype of the cellular automaton. The main objective of this work is to study the evolutionary dynamics of cellular automata when subjected to genetic operations, such as mutation, replication and recombination. For this study it was necessary to implement in Python an algorithm that would allow to generate and compare phenotypes of different cellular automata (from the genotypes) in order to understand how the genetic operations influence the stability of the phenotype, that is, how the patterns and visual characteristics are affected when subjected to these genetic operations. An algorithm was also implemented to study the evolution of populations of cellular automata that uses the genetic operation of recombination to evolve a given population and that allows us to understand how genotypes and phenotypes evolve in certain populations with different characteristics. These different characteristics of populations are associated with the initial proximity of the genotypes, that is, there may be populations in which the genotypes will be very close initially and populations in which the genotypes will be very different from each other, being later analyzed how the characteristics of the populations subsist and evolve. In this dissertation will be studied these two cases of populations and also a case in which the genotypes in the population are very close initially, but that contains an invader, that is, a genotype very different from those existing in the population was introduced and it is studied how the genotypes and phenotypes of the descendants are affected.