BUSCA EVOLUTIVA POR ESQUEMAS DE ATUALIZAÇÃO ASSÍNCRONA EM AUTÔMATOS CELULARES PARA SOLUÇÃO DA TAREFA DE CLASSIFICAÇÃO DE DENSIDADE
Abstract
O campo dos autômatos celulares tem crescido consideravelmente nos últimos anos. Podemos encontrar suas aplicações nas mais diversas áreas, um dos seus principais usos tem sido encontrado como framework para modelagem de sistemas reais. Podemos citar, entre eles, propagação de doenças, dinâmica de fluídos, modelos de crescimento urbano. Apesar de algumas regras apresentarem computabilidade universal, a codificação do problema e leitura da saída produzida por regras de transição demandam acesso global ao conjunto das células, denominado configuração. Sendo a Tarefa de Classificação de Densidade um problema clássico e utilizado como referência no estudo de tarefas globais que podem ser realizadas de maneira distribuída, baseando-se apenas em informações locais, seu interesse do ponto de vista teórico-computacional é inegável. Algoritmos evolutivos tem sido usados de maneira recorrente na TCD para buscar no espaço de regras. Um algoritmo genético é um tipo particular de algoritmo evolutivo, consistido de três etapas iteradas em gerações de indivíduos que exprimem as características necessárias para a resolução do problema: variação genética, seleção natural dos indivíduos e proliferação dos espécimes através de cruzamento. Este projeto demonstra como a utilização de algoritmos genéticos para realizar buscar no espaço de esquemas de atualização resulta em soluções melhores para aquelas já encontradas na literatura para o problema da DCT.
