Autômatos celulares não-uniformes, com conexões não-locais, na classificação de densidade

AUTOR(ES)

Fernando Faria

DATA DE PUBLICAÇÃO

2008

RESUMO

Cellular automata are discrete dynamical systems composed of simple, locally connected structures (the cells), general in terms of their computational power, and that display complex patterns of behaviour. The purpose of this work was to expand previous studies by Zanon (2006), on non-uniform, one-dimensional cellular automata with nonlocal neighbourhood, in order to verify the existence of rules of these kinds of automata to solve the density classification task, that is, the determination of the predominant bit in a binary string. Our concern here was to look for solutions of the problem mainly by evolutionary computation means, to solve it in a non-trivial fashion, i.e., without including in the solution the majority rule over the entire lattice, and, at the same time, with the target of inferring common features for the solutions that would be found. The results achieved led to an expansion in the quantity of perfect solutions available in the literature, but it became clear that all of them have at least one of the rules involved able to account for the entire lattice at once, an evidence that solutions without rules with global action may not exist. Furthermore, the following observations have been made for the type of automata we considered: even distinct automata may have the same temporal evolution; a certain degree of flexibility is allowed in the total balancing of the rules present in a solution of the density classification task; and, in principle, no common patterns seem to exist between solutions for lattices with 3 and 5 cells, thereby suggesting the impossibility of constructing a solution to the problem from another of a smaller lattice.

ASSUNTO(S)

non-uniform cellular automaton tarefa de classificação de densidade computação evolutiva genetic algorithm autômato celular autômato celular não-uniforme engenharia eletrica non-local cellular automaton evolutionary computation density classification task autômato celular não-local algoritmo genético cellular automaton

Documentos Relacionados

• Modelo de Heisenberg antiferromagnético com interações não-uniformes
• Influência de efeitos não-locais na dispersão de poluentes na camada linite planetária
• Leis de conservação não-locais, anomalias e matrizes-s exatas de modelos bidimensionais
• 5 - Estudo da difusão tecnológica por meio de autômatos celulares em arranjos produtivos locais
• Implementação de autômatos celulares com o uso de software livre.