ARTIGO AUTOMATO CELULAR 1

Prévia do material em texto

Autômatos celulares
Bruno Vinicius, César Augusto, Déborah Suellen, Elielton Carvalho,
Géssica Batista, Junior Tadeu, Wagner Gomes
Resumo. Esta pesquisa traz as utilização do autômato celular para o estudo de vários cenários fenômenos naturais, tais como terremotos, crescimento de bactérias, turbulências e dinâmica de populações. As características do Autômato Celular, como formato das células, como a células influência as células que estão as sua volta (vizinhança) que e as regras (condição para que o autômato celular possa fazer a simulação). Neste artigo demostraremos o modelo de Propagação de incêndio, a ferramenta utilizada para a simulação e WorldMaker.
Abstract. This research brings the use of cellular automata for the study of various senarios natural phenomena such as earthquakes, bacteria growth, turbulence and population dynamics. The Cellular Automata as you characterize the shape of the cells, such as cells influences the cells that are around the (neighborhood) and rules that (condition for the cellular automaton can do the simulation). In this article will demonstrate the model of fire spread, the tool used for the simulation and WorldMaker.
�
Introdução 
Com a utilização de equações diferenciais, podem-se estudar fenômenos naturais, tais como terremotos, crescimento de bactérias, turbulências e dinâmica de populações. Porém, a utilização dessas equações em um sistema com grande numero de variáveis, torna sua resolução muito difícil. Como alternativa, podemos limitar o numero de variáveis consideráveis, o que também torna seus resultados limitados em relação ao fenômeno estudado. Mesmo assim, essas equações só podem ser tratadas por métodos numéricos de integração, utilizando-se de recursos computacionais, o que ainda demanda longo tempo em sua resolução. Uma outra forma de se estudar esses fenômenos, é através de uma ferramenta chamada autômato celular. Quando um sistema contem um numero elevado de variáveis, ele é denominado sistema complexo. Para estuda-los, faz-se necessário a utilização dos autômatos celulares. 
Autômatos celulares
Autômatos celulares (ACs) são sistemas dinâmicos totalmente discretos (no espaço e no tempo) os quais são definidos através de regras locais, ou seja, trata-se de conjuntos de entidades (células) que interagem com as células vizinhas alterando seu comportamento (estado) ao longo do tempo de acordo com as mesmas. Mais formalmente, um autômato celular A é uma quadra A=(S,N,f,d), na qual S é um subconjunto dos números inteiros denominado conjunto de estados de A, N representa os vizinhos de uma célula, f é uma função local de transição que define como as células mudam de estado ao longo do tempo, e d é dimensão de A.
Isto é, um AC possui: um conjunto de estados, um conjunto de vizinhos, uma função local de transição e uma dimensão. Por exemplo, um autômato celular elementar (ACE) possui o conjunto de estados binário, seu conjunto de vizinhos é formado pela célula à sua esquerda, pela própria célula e pela a célula à sua direita; uma função local de transição que associa a cada sequência de 3 bits um valor binário (f:{0,1}³→{0,1}); e é unidimensional (d = 1). Sendo assim, um AC possui uma regra que determina qual será o estado da célula de acordo com seus vizinhos.
Autômatos Celulares de Von Neumann
“Autômatos celulares ganharam destaque nos anos 1950, quando John von Neumann estava tentando compreender a capacidade que a vida tem de se autocopiar” (Ian Stewart, 2014). O conceito de Autômato Celular está fortemente ligado ao grande cientista e matemático John von Neumann. De acordo com a história reescrita por Burks, Von Neumann estava interessado nas conexões entre biologia e a então nova ciência dos dispositivos computacionais chamada de Teoria dos Autômatos. Em seus estudos, predominava a idéia do fenômeno biológico da auto-reprodução (do inglês, self-reproducing). O autômato que foi construído por Von Neumann está embutido sobre um espaço celular bidimensional com regra de transição e configuração de estados iniciais particulares. O espaço bidimensional é considerado infinito, mas todas as células em quantidade finita iniciaram em um estado especial de repouso.
Autômatos Celulares de Stephen Wolfram
Stephen Wolfram (1983, p.603), um dos mais renomados teóricos sobre autômatos celulares, os define como, idealizações matemáticas de sistemas físicos, nos quais o espaço e o tempo são discretos, e os atributos assumem um conjunto de valores também discretos. Um autômato celular consiste de uma grade regular uniforme (ou “campo matricial”), comumente infinito em sua extensão, com uma variável discreta em cada localidade (“célula”). O estado de um autômato celular é completamente especificado pelos valores das variáveis em cada célula. Um autômato celular evolui em passos de tempo discretos, com o valor da variável em uma célula sendo afetado pelos valores das variáveis nas células vizinhas encontrados no passo de tempo anterior. A vizinhança de um célula é tipicamente formada pela própria célula em consideração e todas as demais células localizadas nas suas adjacências imediatas.
As variáveis em cada célula são atualizadas simultaneamente (“sincronicamente”), baseando-se nos valores das variáveis de sua vizinhança no passo de tempo precedente, e de acordo com um conjunto predefinido de “regras locais”. (Claudia M. A.; Gilberto C.; Antonio M.V.M., 2007).
Essa natureza discreta também permite a analogia com computadores digitais, pois os autômatos celulares podem ser vistos como computadores de processamento paralelo de construção simplificada.
Autômatos Celulares de John Conway
O Jogo da vida (Game oflife), de John Conway (Gardner, 1970), ou Life, como ficou conhecido, imortalizou o conceito de CA. Neste, o espaço celular é composto de uma grade quadrada regular bidimensional, em que a vizinhança das células consiste em seus oito vizinhos imediatos, isto é, quatro ortogonais e quatro diagonais. Essa vizinhança de oito células é chamada de “vizinhança de Moore”; por sua vez, uma vizinhança de apenas quatro células ortogonais adjacentes é conhecida como “vizinhança de von Neumann”. Qualquer célula pode estar viva (on) ou morta (off), e há apenas duas regras simples para que isso ocorra. Uma célula morta torna-se viva se há exatamente três células vivas imediatamente adjacentes a ela. Em contrapartida, uma célula permanece viva se há duas ou três células vivas em suas adjacências, senão ela morre. Isso significa que uma célula morre de isolamento ou superpopulação. Apesar da simplicidade das regras, esse jogo suporta a geração de inumeráveis padrões de comportamento dinâmico. É evidente que, mesmo nos mais simples CAs, padrões globais complexos emergem diretamente da aplicação de regras locais; é exatamente essa propriedade de complexidade emergente que torna os CAs tão fascinantes, e o uso de seus modelos tão atrativos.
Outra propriedade interessante do Life foi a possibilidade de apresentar certas configurações que se autoperpetuam. Um exemplo bem conhecido dessas configurações é o glider, o qual é feito de cinco células vivas. Os Gliders são estruturas que se modificam a cada ciclo do programa e se locomovem dentro da matriz.
Figura 1. A figura dos gliders que se modificam a cada ciclo do programa.
Estrutura de um Autômato Celular
Para aplicar um sistema de autômatos celulares a um dado problema faz se necessário a especificação de alguns pontos básicos, como a geometria do sistema, quais serão os vizinhos de um células sua dimensão, dentre outras características, etc.
6.1. Geometria
Em um sistema de autômatos celulares é necessário que se tenha uma geometria regular: ,ou seja, todas as células devem possuir o mesmo tamanho. A geometria do sistema pode ser classificada quanto à dimensão e/ou formato que as suas células assumem.
6.2. Dimensão
Podem-se construir modelos de sistemas de uma, duas ou três dimensões. No autômato unidimensional, as células estão distribuídas linearmente. No bidimensional, teremos uma distribuiçãono plano e no tridimensional, uma distribuição espacial.
6.2.1. Autômato Unidimensional
Ao ACs unidimensionais se desenvolvem ao longo de uma linha, como se fossem uma fila. Assim cada componente modifica seu estado de acordo com o estado de seu vizinho e de si mesmo. Dessa forma podemos ter vários tipos de desenvolvimentos ao longo do tempo. Para a construção de um AC é importante observar um problema típico que ocorre devido ao fato da fila ser constituída de um número finito de elementos também denominado de Vetor do AC. Esse problema é denominado Efeito de Borda que pode ser explicado com o exemplo: se o vetor tem 10 elementos o primeiro terá como vizinhança somente o segundo e o décimo terá como vizinhança somente o nono elemento.
Também acontece que em alguns ACs o seu desenvolvimento leva a um ciclo, ou seja, depois de algumas iterações ele apresenta uma configuração que aparece de tempos em tempos denominado de Período do Ciclo. Este período dependerá principalmente do comprimento da fila, ou seja, quanto maior o comprimento da fila maior será o período.
6.2.2. Autômato Bidimensional
Os autômatos celulares bidimensionais são formados por uma malha em duas dimensões. Essa malha pode ser quadrada, hexagonal ou triangular.
Figura 2. A figura do formato do autômatos celulares.
O autômato propriamente dito é representado por uma linha. A malha observada como evolução de uma regra, é na realidade um gráfico, pois cada linha representa um passo de tempo. Nos ACs bidimensionais, cada passo de tempo é representado por uma malha em duas dimensões no espaço. O autômato bidimensional possui um elevado numero de regras, por isso elas são divididas em grupos e numeradas independentemente dentro desses grupos. Dois grupos que são bastante utilizados são as totalísticas e as totalísticas exteriores.
6.2.3. Autômato Tridimensional
Os autômatos celulares tridimensionais são principalmente focados para encontrar uma regra de evolução em três dimensões, muitos dos resultados são quantitativos, baseados principalmente em simulando várias regras de evolução em espaços tridimensionais pequenos para encontrar estruturas que são semelhantes a aplicação jogo da vida. Este autômato celular é focado no estudo de campos estatísticos. Autômato celular tridimensional pode seguir os mesmos princípios do bidimensional, mas, dada a crescente complexidade dos cálculos e processamento, a sua implementação não é simples. No entanto, uma vez que podem ser considerados autômatos celulares tridimensional com as mesmas variáveis ​​tipo de limite no âmbito teórico, considere a representação dos autômatos celulares tridimensional considerando fronteira periódica é moldada.
6.3. Formato
As células podem ter várias formas (triangular, quadrangular, hexagonal, etc), desde que num mesmo autômato todas as células sejam de uma mesma forma.
6.4 Tamanho da Vizinhança
É importante em um sistema de autômato especificar quais serão os vizinhos de uma célula, pois as regras de transição serão aplicadas baseadas nos estados deles e da própria célula. A geometria do sistema de autômato celular está diretamente relacionada ao tamanho da vizinhança de uma célula. Existem diferentes tipos de vizinhas, entre eles a vizinhança de Von Neumann e de Moore.
Figura 3. As figuras mostram os diferentes tipos de vizinhança.
6.5. Condição de Limite (ou contorno)
Geralmente há uma necessidade de que o autômato seja infinito em todas as dimensões, mas é impossível que isso seja implementado em um computador, por depender de limitação do espaço da memória, então é necessário determinar condições de limite para que seja possível simular um autômato infinito. Essas condições são também necessárias para completar o conjunto de vizinhos das células que se encontram nas bordas do autômato. Como exemplos células que se encontram na extremidade esquerda não terão vizinhos à sua esquerda, sendo assim a condição de limite irá justamente simular o comportamento daquelas células, que não existem. Dentro das condições de limites há vários tipos de condições de limite, das quais citaremos três delas:
6.5.1. Limite periódico
São obtidos periodicamente estendendo-se o autômato. É como se autômato fosse copiado nas bordas, da maneira como ele se encontra num dado instante. Para um ganho de tempo e memória, não precisamos colocar o autômato inteiro, basta colocarmos um pedaço dele (que são r colunas ou r linhas mais próximas, e r é o raio da vizinhança).
Desenho: Esquema de um autômato unidimensional com raio de vizinhança 1 e condição de contorno periódica.
Figura 4. A figura é um esquema de autômato unidimensional.
6.5.2. Limite reflexivo
Está condição de contorno é obtida refletindo-se o autômato em cada limite.
6.5.3. Limites de valores fixos
Esta condição de limite é obtida, simplesmente descrevendo como serão os estados das células no contorno do autômato, e estes estados serão os mesmos em qualquer instante da simulação.Como exemplo, se um autômato tem 2 estados possíveis para um célula, PRETO e BRANCO, podemos determinar uma condição de limite onde todas as células no contorno são BRANCAS.
Figura 5. A figura do autômato em 2 estados possíveis para uma célula, preto e branco.
6.6. Condições Iniciais
Em uma implementação de um sistema de autômato celular tem se uma condição em que o sistema se encontra no tempo inicial (t0). Dependendo de como o sistema seja iniciado, diferentes evoluções são obtidas. E será a partir das observações que a evolução do sistema pode ser avaliada.
6.7. Conjunto de dados
Refere-se ao conjunto de valores possíveis que cada célula do sistema poderá obter. Todo autômato celular deve ter um conjunto de estados, que serão os possíveis estados em que as células poderão se encontrar. Como exemplo, o conjunto de estados pode ser um conjunto de cores (vermelho, verde e preto), representando os estados de um autômato simulando um incêndio florestal onde o verde seria as matas, o vermelho o fogo queimando as matas e o preto a mata já carbonizada, dentre outros, etc.
6.8. Regra de transição
São preceitos para determinar o estado da célula no próximo instante.
7. Aplicações
Modelos de autômatos Celulares (CA) possuem aplicações nas mais diversas áreas, que abrangem desde física teórica e empírica até mudanças de uso e cobertura do solo, engenharia e controle de tráfego, epidemiologia e biologia comportamental. A área de aplicação dos sistemas de autômatos celulares é bem ampla e vem obtendo grandes resultados como na área de medicina, quando se aplica os autômatos no controle das doenças, de viroses, evitando assim uma proliferação da doença e prevenção.Como exemplo de aplicações, temos: Sistemas Mecânicos, Reações Químicas, Formação de Cristais, Modelo de Crescimento Urbano, Tráfego Automóvel, Regulação Genética, Ecossistemas, Evolução de Epidemias, Colónias e Super-organismos, Simulação de Propagação de Fogo, Simulador de Padrões de Crime, Modelos de Reação-Difusão, Sistema de Encriptação Massivamente Paralelo.
7.1. Aplicação do software WorldMaker
Nesta seção será apresentados o trabalho prático, que demonstra a aplicação desenvolvida com Autômatos Celulares implementadas em propagação de incêndio. Este parte do trabalho ajudará a aprimorar o entendimento e a aplicabilidade de regras de transição e evolução das células nas mudanças de estados.
A ferramenta a ser utilizada será o WorldMaker, que possibilita a criação do autômato com diversas regras e estados como observado abaixo.
WorldMaker é uma forma de um sistema que se baseia num sistema de grade quadrada: ele é baseado nas interações de entidades que agem localmente. Cada célula pode ter duas entidades: um objeto e um fundo, que podem interagir em conjunto ou separadamente. Interações binárias (conforme definido pelas regras) são avaliadas entre a célula em questão e cada uma das células vizinhas, por sua vez no bairro de Moore (os oito células em torno de uma célula central em consideração). Enquanto que uma célula pode interagircom cada uma das suas células vizinhas, por sua vez, que, no entanto, não pode interagir com mais de uma célula a outra simultaneamente.
A definição de regra é definida em três partes: Condição A condição é a exigência de pré-requisito para a regra a ser executado; se isso não for satisfeito, esta regra não seria executada. As condições são baseadas nos primeiro e segundo plano objetos na célula a ser considerado, bem como o próximo a ele. Outras condições podem incluir a direção do objeto que está sendo considerado e os valores dos parâmetros para os primeiro e segundo plano, objetos da célula a ser considerado e a célula adjacente.
7.2. Autômato celular – Propagação de incêndio
O incêndio começa através de um foco e com o passar do tempo ele se espalha dentro de uma determinada área de acordo com a vegetação e o vento.
Esse autômato tem por objetivo simular a propagação do incêndio e prever qual será a situação dentro de um determinado período, para onde ele irá se espalhar, observando principalmente o vento que tem grande influência, dessa forma ajudando as pessoas na orientação sobre onde iniciar o combate ao incêndio.
Um incêndio além de causar um desastre econômico ele também gera principalmente um desastre ecológico, e seu combate gera ganhos nestes dois aspectos.
7.2.1. Possíveis estados
Célula verde –> vegetação (floresta)
Célula vermelha –>em chamas (fogo)
Célula preta –>queimada (carbonizada)
7.2.2 Transições
A transição entre os estados da célula será da seguinte forma:
Floresta-> fogo ->queimada
Passando de floresta para fogo, passando de fogo para queimada, nesta ordem sem retornar ao seu estado inicial.
7.2.3 Vizinhança
O autômato em estudo considerará apenas um formato de matriz bidimensional (2D), onde uma célula terá ação de raio 1 em relação a suas vizinhas, mantendo assim o formato de vizinhança x.As células serão representadas em formato quadrangular.
7.2.4 Regras
A floresta considerada possui uma vegetação verde, onde o incêndio se propaga de forma mais lenta e demora um certo tempo até que a vegetação se torne cinzas, pois as condições de clima favorecem a vegetação.
8. Simulação
A simulação terá início com poucos e pequenos focos de incêndio e corresponderá a um período.
Figura 6. A figura mostra a simulação da propagação de incêndio implementado no software WorldMaker 
9. Conclusão 
Este modelo, propagação de incêndio que simulamos neste artigo (foi utilizar o autômato celular desenvolvido por John Conway que seu modelo e conhecido como jogo da vida, sua vizinhança Moore que suas características é que espalha para em todos os lados inclusive na diagonal da células, a regra determinística ou seja a situação que foi proposto para realizar a simulação) nos permite ter condições mínimas para prever o comportamento do incêndio e assim diminuir os danos causados pelas chamas.
Referências
Almeida. Claudia Maria de; Camara. Gilberto; Monteiro. Antônio Miguel Vieira. “Aplicações Geo. informação em urbanismo: cidade real x cidade virtual.” Apresentação de Michael Batty. São Paulo: Oficina de Textos.2007.
Laboratório de Garagem.”Jogo da Vida de Conway em PYTHON.” Laboratório de Garagem 2014. Disponível em: http://labdegaragem.com/profiles/blogs/jogo-da-vida-de-conway-em-python>. Acesso em 02 nov 2014.
SOUSA. Sonia Alexandra F. S. “Autômato Celular”. Departamento de Ciência e Computação Faculdade de Ciências da Universidade do Porto 2001/2002. Disponível em: < HTTP://www.di.ubi.pt/~cbarrico/Disciplinas/VidaArtificial/Download/AutomatosCelulares.PDF>. Acesso em 02 nov 2014. 
STEWART, Ian. “Em busca do infinito :Uma história da Matemática dos primeiros números à teoria do caos.” 2014.
UFPE. “Especificações na Construção de um Sistema Autômato Celular”. UFPE 2014. Disponível em: <http://www.cin.ufpe.br/~if114/Monografias/Automatos%20Celulares/especificacoes.htm >. Acesso em 02 nov 2014.