Embed Size (px)
Citation preview
UNIVERSIDADE CATOLICA DE PELOTASESCOLA DE INFORMATICA
PROGRAMA DE POS-GRADUACAO EM INFORMATICA
Um Estudo sobre a Aplicacao deAutomatos Celulares na Simulacao de
Fenomenos Ambientais e AspectosDinamicos
porAndre Luiz Silva de Moraes
Trabalho Individual 1TI-2007/2-01
Orientador: Prof. Dr. Marilton Sanchotene de Aguiar
Pelotas, dezembro de 2007
A Deus. . . por iluminar o caminho trilhado, a meus meus pais por me darem a educacaoe ensinarem a dar valor ao que e pouco mas e suficiente, a minha namorada por me
acompanhar em todos os momentos de dificuldade ate o momento e conseguir alimentara energia de acreditar que os desafios sempre podem ser vencidos com o esforco e fe
dedicados, a meus colegas de trabalho por segurarem as dificuldades de tempo ausenciada minha parte e dedico tambem a aqueles que nao mais estao presentes hoje para
dividirem comigo os momentos de minha vida.
AGRADECIMENTOS
Agradeco a todos os amigos, colegas e professores que me ajudaram a con-cluir este trabalho tambem a todos os que me acompanharam na jornada de dificulda-des. Agradeco em especial ao professor e orientador Marilton Sanchotene pelo empenhoe consideracao dedicado em nossos trabalhos desenvolvidos ate o momento e por meguiar durante as dificuldades passadas e atuais enfrentadas na conclusao deste trabalho.Agradeco tambem aos novos e antigos colegas que de uma forma ou de outra tornaram-senovos amigos e que nao serao esquecidos nunca.
”‘Nem mesmo a biologia garante que a recriacao da terra seria completamenteperfeita e com os mesmos atributos atuais se existissem formas para faze-lo”’.
— ANDRE MORAES
SUMARIO
LISTA DE FIGURAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
LISTA DE ABREVIATURAS E SIGLAS . . . . . . . . . . . . . . . . . . . . . 8
RESUMO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
ABSTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1 INTRODUCAO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111.1 Motivacao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121.2 Metodologia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2 AUTOMATOS CELULARES . . . . . . . . . . . . . . . . . . . . . . . . . 142.1 Automatos Celulares de John Von Neumann . . . . . . . . . . . . . . . . 142.2 Automatos Celulares de Stephen Wolfram . . . . . . . . . . . . . . . . . 142.3 Automatos Celulares de John Conway . . . . . . . . . . . . . . . . . . . 152.4 Estrutura de um Automato Celular . . . . . . . . . . . . . . . . . . . . . 162.4.1 Celulas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.4.2 Grade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.4.3 Vizinhanca . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172.4.4 Bordas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182.4.5 Estados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192.4.6 Regras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192.4.7 Evolucao ou Interacao . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212.4.8 Padroes de Comportamentos de Automatos Celulares . . . . . . . . . . . 212.4.9 Generalizacoes de Regras de Evolucao . . . . . . . . . . . . . . . . . . . 232.4.10 Self-Similarity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242.4.11 Self-Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3 ESTADO-DA-ARTE DA APLICACAO DE AUTOMATOS CELULARESPARA MODELAGEM DE FENOMENOS DINAMICOS . . . . . . . . . . 28
3.1 Modelagem de Celulas Biologicas . . . . . . . . . . . . . . . . . . . . . . 283.2 Modelagem Dinamica de Plantas . . . . . . . . . . . . . . . . . . . . . . 293.2.1 Introducao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293.2.2 Funcionamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303.2.3 Regras de Transicao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323.3 Modelagem de Epidemias: Simulacao de Dengue Urbana . . . . . . . . 34
3.3.1 Funcionamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4 CONSIDERACOES FINAIS . . . . . . . . . . . . . . . . . . . . . . . . . . 404.1 Introducao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
5 CONCLUSAO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
REFERENCIAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
LISTA DE FIGURAS
Figura 2.1 Jogo da Vida de Conway . . . . . . . . . . . . . . . . . . . . . . . . 16Figura 2.2 Celulas de um Automato . . . . . . . . . . . . . . . . . . . . . . . . 17Figura 2.3 Grade Bidimensional . . . . . . . . . . . . . . . . . . . . . . . . . . 17Figura 2.4 Grade Celular e suas Dimensoes . . . . . . . . . . . . . . . . . . . . 18Figura 2.5 Vizinhanca de Von Neumann r=1 . . . . . . . . . . . . . . . . . . . 18Figura 2.6 Vizinhanca de Moore r1 . . . . . . . . . . . . . . . . . . . . . . . . 19Figura 2.7 Vizinhanca de Moore Extendida r1 . . . . . . . . . . . . . . . . . . . 19Figura 2.8 Vizinhanca de Moore Extendida r2 . . . . . . . . . . . . . . . . . . . 20Figura 2.9 Tratamento de Bordas - Limite Fixo . . . . . . . . . . . . . . . . . . 20Figura 2.10 Tratamento de Bordas - Limite Periodico . . . . . . . . . . . . . . . 21Figura 2.11 Evolucao de um Automato Celular . . . . . . . . . . . . . . . . . . . 21Figura 2.12 Esquema tipico de um Automato Celular . . . . . . . . . . . . . . . 22Figura 2.13 Regra aplicada com poucas Evolucoes . . . . . . . . . . . . . . . . . 22Figura 2.14 Evolucao da Regra aplicada anteriormente com 255 passos . . . . . . 23Figura 2.15 Regra aplicada com estado inicial desordenado . . . . . . . . . . . . 23Figura 2.16 Grafo de Transicao de Estados para o automato celular com 12 celulas 24Figura 2.17 Classe 1 - Aplicacao da Regra 160 com 100 passos . . . . . . . . . . 24Figura 2.18 Classe 2 - Aplicacao da Regra 164 com 100 passos . . . . . . . . . . 25Figura 2.19 Classe 3 - Aplicacao da Regra 146 com 100 passos . . . . . . . . . . 25Figura 2.20 Classe 4 - Aplicacao da Regra 18 com 100 passos . . . . . . . . . . . 26Figura 2.21 Propriedade de Auto Similaridade . . . . . . . . . . . . . . . . . . . 27Figura 2.22 Propriedade de Auto Organizacao . . . . . . . . . . . . . . . . . . . 27
Figura 3.1 Ciclo de Vida de um Dictyostelium . . . . . . . . . . . . . . . . . . 29Figura 3.2 Grade Celular utilizada pela Modelagem de Celulas Biologicas . . . . 29Figura 3.3 Vizinhanca de Von Neumann Esq. e de Moore Dir. . . . . . . . . . . 30Figura 3.4 Configuracao de Populacao Inicial . . . . . . . . . . . . . . . . . . . 34Figura 3.5 Visualizacao de Funcionamento da Dinamica Populacional . . . . . . 34Figura 3.6 Modelo Esquematico da Dengue . . . . . . . . . . . . . . . . . . . . 36Figura 3.7 Demonstracao das interacoes Globais e Locais para a simulacao. . . . 36Figura 3.8 Interacao entre as grades de mosquitos e humanos vista de cima . . . 38Figura 3.9 Interacao entre as grades de humanos e mosquitos vista em perspectiva 39Figura 3.10 Simulacao do Modelo de Dengue sobre a cidade de Santos reprodu-
zida digitalmente . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
LISTA DE ABREVIATURAS E SIGLAS
ACs Automatos Celulares
SIGs Sistemas de Informacoes Geograficas
IPE Information Processing Environment
SPMD Single Program Multiple Data
ABNT Associacao Brasileira de Normas Tecnicas
RESUMO
Este trabalho tem por objetivo realizar um estudo sobre a origem e as carac-terısticas de automatos celulares, abordando conceitos sobre dinamica populacional,simulacao de comportamentos biologicos e analise e segmentacao de imagens de satelite.Dentre os objetivos especıficos, serao abordados automatos celulares com comportamentoestatico e em seguida aplicacoes modeladas dinamicamente para simulacao de compor-tamentos tanto ambientais quanto biologicos. Ainda, este trabalho apresenta modelosdinamicos baseados em automatos celulares, que e objeto de estudo na linha de pesquisaem Inteligencia Artificial, no contexto de um Projeto maior, denominado Projeto IPE (In-formation Processing Environment). O objetivo do Projeto IPE e o desenvolvimento deuma arquitetura computacional para o processamento de alto desempenho computacionalcom o objetivo de gerar uma ferramenta capaz de dar respostas ageis e concretas para asdiversas areas de estudo.
Palavras-chave: Automatos celulares, biologia.
ABSTRACT
TITLE: “A STUDY ON THE APPLICATION OF CELULAR AUTOMATA IN THESIMULATION OF DYNAMIC POPULATION AND ENVIRONMENTAL PHENOM-ENA”
This work aims to undertake a study on the origin and characteristics of cellularautomatons, addressing concepts on population dynamics, simulation and analysis of bio-logical behavior and targeting of satellite imagery. Among the specific objectives, will bedealt with automatons cellular behavior static and then modeled applications dynamicallyto both environmental simulation of behavior as organic. Still, this work presents dynamicmodels based on cellular automatons, which is the subject of study in the line of researchin Artificial Intelligence, in the context of a larger project, called Project IPE (InformationProcessing Environment). The goal of Project IPE is the development of a computationalarchitecture for the processing of high-performance computing with the goal of creatinga tool capable of giving practical and flexible responses to the various areas of study.
Keywords: ACs, Dinamic Models.
11
1 INTRODUCAO
Atualmente, a tecnologia devido ao fato das aplicacoes computacionais serem fre-quentemente viabilizadas atraves da paralelizacao de sua execucao em agregados de com-putadores ou grades computacionais, reduzindo o impacto do uso de recursos como tempoe espaco. Embora existam muitas ferramentas que possibilitem acessar remotamente da-dos e informacoes, a tecnologia se depara em uma realidade onde possui dados em excessoporem nao consegue recuperar as informacoes referentes a esses dados de forma rapida esegura por ainda nao existirem metodos consolidados que permitam faze-lo.
Diversas areas das ciencias enfrentam hoje a dificuldade como exemplo no quese refere ao processamento de imagens em larga escala e extracao de informacoes resul-tantes de analises dinamicas, ou seja, resultados que reconhecam modificacoes quandose utilizam elementos em grande quantidade para serem examinados. Um exemplo queconcretiza esta afirmacao e a analise de imagens medicas como tomografias computado-rizadas, que sao documentos graficos que necessitam ser analisados em larga escala comnecessidade de respostas rapidas e objetivas.
Descobre-se ser vital a importancia na area ambiental para o desenvolvimento deferramentas computacionais que auxıliem a analise combinada de todos os aspectos quepossam ser levados em consideracao quando da realizacao dos estudos que visam , porexemplo, para a determinacao de areas prioritarias para conservacao ambiental.
No processamento de imagens geograficas, os sistemas de informacoes ge-ograficas existentes nao sao suficientemente expressivos para analises desse tipo, prin-cipalmente quando se desejam levar em conta aspectos dinamicos. Muitas areas podemser identificadas e incluıdas como prioritarias a conservacao considerando-se apenas suacomposicao florıstica, mas careceriam de levantamentos precisos sobre sua fauna, florae comunidades humanas inseridas no seu contexto. Outras tem sido estabelecidas comounidades, mas carecem de informacoes que subsidiem a elaboracao dos seus planos demanejo.
O advento da criacao de metodologias utilizando o sensoriamento remoto e, poste-riormente, o desenvolvimento dos sistemas de informacao geografico, tem permitido quea integracao dos dados seja concatenada em um contexto espacotemporal. Por ser umatecnologia nova, requer o desenvolvimento contınuo de procedimentos, metodologias eestrategias, ampliando seu potencial de integracao e analise de dados. O seu uso tem sidoempregado em avaliacoes do potencial turıstico de unidades de conservacao, zoneamentode unidades de conservacao e a sua insercao na paisagem de entorno, elaboracao de planosde manejo e elaboracao de planos de gestao de sistemas de unidades de conservacao.
Os SIGs tem sido empregados, entre outras atividades, em zoneamento e gestao
12
de unidades de conservacao e a sua insercao na paisagem de entorno. Entretanto, osSIGs nao sao suficientemente expressivos para analises dos aspectos que devem ser le-vados em consideracao na realizacao das analises que visam a determinacao de areaspara conservacao ambiental, principalmente quando se quer levar em conta aspectosdinamicos.
Estes aspectos inseridos na proposta do ambiente IPE servirao ao estabelecimento,por exemplo, de estrategias de conservacao e os resultados das simulacoes tambem po-derao ser aplicados ao gerenciamento ambiental. Em andamento, no grupo de pes-quisa, tem-se um estudo de modelos dinamicos baseados em automatos celulares paraa simulacao de incendios em florestas (do ingles, Forest Fire Model), dentre os quais estao de Chopard, e a proposta de estende-los para atender a condicoes mais detalhadas detipo de vegetacao e outros aspectos climaticos e em parte abrangida pelo Projeto IPE. Aseguir, apresentam-se algumas aplicacoes de Automatos Celulares em fenomenos ambi-entais e biologicos.
1.1 MotivacaoA necessidade de metodos e de ferramentas computacionais que auxiliem a
concretizacao de tarefas de analise de imagens com alto desempenho e que levem emconsideracao todos os atributos necessarios possıveis e um desafio e pode ser contornadocom os metodos estudados neste trabalho. A tecnologia existente como linguagens deprogramacao dinamicas e a possibilidade de conceber tarefas de processamento de ima-gens com uma computacao paralelizada de alto desempenho motivam os objetivos destetrabalho e ate mesmo a continuidade deste em trabalhos futuros.
1.2 MetodologiaEste trabalho individual esta sendo desenvolvido no contexto do Projeto IPE
(Projeto IPE: um ambiente baseado em algoritmos evolutivos para o processamento deinformacoes e simulacao de modelos dinamicos) em desenvolvimento no Grupo de Pes-quisa em Fundamentos e Matematica da Computacao (GMFC).
O projeto tem como objetivo principal o desenvolvimento de um ambiente compu-tacional para o processamento de informacoes e simulacao de aspectos dinamicos base-ado em algoritmos evolutivos com alto desempenho de carater generico e fornecera umaarquitetura computacional para o desenvolvimento de aplicacoes dinamicas demandadaspor diversas areas do conhecimento.
O presente Trabalho Individual compreendeu inicialmente o estudo e revisao bibli-ografica da fundamentacao teorica do Projeto IPE, incluindo especificamente o estudo deAutomatos Celulares e de bibliografia, relacionada com o comportamento da propagacaode especies vegetais em florestas, modelagem da dinamica de experimentos biologicos.
No capıtulo 2 apresenta-se o conceito de automatos celulares (ACs)fundamentadoem varios artigos utilizados para pesquisa como (AGUIAR; COSTA, 2000), (AGUIARet al., 2004) e (AGUIAR; ROCHA COSTA, 2001) e em secoes subsequentes serao deta-lhados os elementos que o constituem bem como o funcionamento de cada um.
No capıtulo 3 serao apresentados estudos sobre artigos ( (DZWINEL, 2004), (FU;MILNE, 2004), (REY; WHITE; SANCHEZ, 2006), (BANDINI; PAVESI, 2004), (BAG-
13
NOLI et al., 1999))com aplicacoes de automatos celulares descrevendo pesquisas ja con-cluıdas e publicadas.
No capıtulo 4 descreve-se o Projeto IPE, o seu funcionamento, suas expectativase aplicacoes em areas de conhecimento especıficas e tambem pesquisas futuras que seraotemas para a estruturacao de uma dissertacao de mestrado a partir deste trabalho.
No captıtulo 5 e 6 estarao os projetos futuros e a conclusao, bem como o parecerfinal do autor deste trabalho.
14
2 AUTOMATOS CELULARES
Segundo (AGUIAR; COSTA, 2000), ACs sao modelos matematicos simples desistemas naturais. Eles sao constituıdos de uma malha, ou reticulado, de celulas (doingles, site) identicas e discretas, onde cada celula tem seu valor sobre um conjunto finito,por exemplo, de valores inteiros. Os valores evoluem, em passos de tempo discretos, deacordo com regras determinısticas que especificam os valores de cada celula em termosdos valores das celulas vizinhas.
2.1 Automatos Celulares de John Von NeumannO conceito original de Automato Celular esta fortemente associado ao grande ci-
entista e matematico John von Neumann. De acordo com a historia reescrita por Burks,Von Neumann estava interessado nas conexoes entre biologia e a entao nova ciencia dosdispositivos computacionais chamada de Teoria dos Automatos. Nos seus estudos, predo-minava a ideia do fenomeno biologico da auto-reproducao (do ingles, self-reproducing).
Ainda, a questao que ele apresentava era: ”‘Que tipo de organizacao logica e sufi-ciente para um automato ser capaz de reproduzir a si proprio?”’ Von Neumann acreditavaque uma teoria geral de computacao em redes complexas de automatos, como ACs, se-ria essencial para o entendimento de sistemas complexos da natureza e, tambem, para odesenvolvimento de sistemas artificiais complexos.
O detalhamento da solucao que Von Neumann deu a sua questao foi apresentadano seu livro Theory of Self-Reproducing Automata. O manuscrito estava incompletona epoca da morte de Von Neumann (1957) e foi editado e completado por Burks. Oautomato auto-reprodutor tem um certo grau de complexidade e Von Neumann requereuque o automato em questao fosse equivalente em poder computacional a maquina deTuring universal. O automato que foi construıdo por Von Neumann esta embutido sobreum espaco celular bidimensional com regra de transicao e configuracao de estados iniciaisparticulares. O espaco bidimensional e considerado infinito, mas todas as celulas emquantidade finita iniciam em um estado especial de repouso.
2.2 Automatos Celulares de Stephen WolframPara Stephen Wolfram os Automatos Celulares podem ser considerados como
idealizacoes discretas das equacoes diferenciais parciais frequentemente utilizadas paradescrever sistemas naturais. Essa natureza discreta tambem permite a analogia com com-putadores digitais, pois os ACs podem ser vistos como computadores de processamento
15
paralelo de construcao simplificada.Ele afirma ainda que um automato celular consiste em uma grade regular e uni-
forme com uma variavel discreta em cada local (celula). A grade e vetorial se for uni-dimensional ou denominada por ”‘grid”’ se for bidimensional. As variaveis das celulaspodem adquirir qualquer valor dentro de um dado conjunto de valores possıveis. O estadodo automato celular e definido pelos valores das variaveis em cada celula.
Essa natureza discreta tambem permite a analogia com computadores digitais, poisos automatos celulares podem ser vistos como computadores de processamento paralelode construcao simplificada.
2.3 Automatos Celulares de John ConwayJohn Conway, um matematico da universidade de Cambridge que era afficionado
pelo desenvolvimento de jogos matematicos, desenvolveu na decada de 1960 um jogochamado de ”‘Jogo da Vida”’ (do ingles, Game of Life). Onde simulava um automatobidimensional com estados binarios e utilizada a vizinhanca de Moore, comentada maisadiante neste trabalho.
Constitui ”‘um jogo sem jogador”’, o que significa que sua evolucao e determinadapelo seu estado inicial, nao necessitando de nenhuma entrada de jogadores humanos. Seufuncionamento da-se em um conjunto de celulas quadradas que seguem ao infinito emtodas as direcoes. Cada celula tem oito ”‘vizinhos”, que sao celulas adjacentes, incluindoas diagonais. Cada celula pode estar em dois estados de ”‘viva”’ ou ”‘morta”’. O estadodo tabuleiro se modifica em pequenas passagens de tempo. Os estados de todas as celulasem um instante sao considerados para calcular o estado de todas as celulas no instanteseguinte.
Para este trabalho, Conway pretendia satisfazer tres desejos principais:
• Como regra, nao deveria existir populacao inicial para que a populacao conseguissecrescer sem limite;
• Mesmo definindo padroes iniciais, a populacao tambem deveria conseguir crescersem limites;
• Devem haver imagens iniciais simples que crescam e mudem por um perıodo detempo consideravel antes de chegar a um fim das possıveis formas:
1. Sumindo completamente (por superpopulacao ou por ficarem muito distantes);
2. Estacionando em uma configuracao estavel que se mantem imutavel para sempre,ou entrando em uma fase de oscilacao na qual sao repetidos os ciclos infinitos dedois ou mais perıodos.
Na pratica, as regras do jogo deveriam permitir que este nao fosse previsıvel emqualquer que fosse a sua configuracao inicial e que gerasse uma populacao infinitamente.O jogo possuıa a seguinte regra de transicao:
• Qualquer celula viva com menos de dois vizinhos morre de solidao;
• Qualquer celula viva com mais de tres vizinhos morre de superpopulacao;
16
• Qualquer celula morta com exatamente tres vizinhos vivos se torna uma celula viva;
O Life interage sobre um reticulado bidimensional infinito, partindo de umaconfiguracao inicial com um numero finito de 1’s e todas as outras celulas com valor 0 euma caracterıstica interessante do Jogo e a de que sua regra de transicao e muito simplese ao mesmo tempo conseguir levar a padroes bastante complexos no espaco celular.
Conway ainda se fazia a seguinte pergunta: ”‘A populacao, ou seja, as celulascom valor 1, de uma configuracao do Life pode crescer sem limite?”’ em experimentosposteriores William Gosper responde a questao em 1970 com a invencao de um disparadorde gliders, uma estrutura estacionaria que emite um novo glider a cada 30 passos detempo.
Figura 2.1: Jogo da Vida de Conway
2.4 Estrutura de um Automato CelularNesta secao serao detalhados os componentes de um Automato Celular de acordo
com (PASCOAL, 2005), permitindo avaliar aplicacoes com as ferramentas desenvolvidasno futuro deste trabalho.
2.4.1 CelulasUma celula de um AC pode ser considerado um elemento de memoria que arma-
zena dados celulares. Em experimentos com imagens, por exemplo, pode-se considerarcomo uma celula os pixels de uma imagem analisada por um automato celular.
2.4.2 GradeA grade constitui o plano espacial onde as celulas estarao dispostas no AC. Pode
estar disposta em dimensoes diferentes com uma duas ou ate mesmo tres dimensoes.Um modelo de grade que apresenta grande facilidade de analise e a unidimensional, querepresenta fielmente uma exemplificacao de uma maquina de estados.
A grade de um Automato pode estar dispostas em ate tres dimensoes, podendovariar na sua utilizacao dependendo da finalidade em questao.
17
Figura 2.2: Celulas de um Automato
Figura 2.3: Grade Bidimensional
2.4.3 Vizinhanca
A vizinhanca determina a fronteira que cada celula tera dentro da grade celular.Em outras palavras o processo evolutivo do automato celular seguira regras que determi-nam em que direcao e quais celulas sofrerao a mudanca na evolucao.
O tamanho e a configuracao das vizinhancas podem variar em modelos utiliza-dos embora na maioria dos sistemas observados percebe-se que esta e tratada de formaestacionaria possuindo seus vizinhos dispostos em direcoes norte, sul, leste e oeste.
Mais especificamente, as variaveis nas celulas podem adquirir qualquer valor den-tro de um dado conjunto de valores possıveis e a vizinhanca e formada pelas celulasadjacentes a celula atual e pela propria celula em questao.
Alguns exemplos de modelos de vizinhancas conforme (PASCOAL, 2005) sao:Neumann, Moore, Moore Estendida e Aleatoria que seguem abaixo.
2.4.3.1 Vizinhanca de Neumann
A Vizinhanca de Von Neumann ocorre com quatro celulas: acima, abaixo, dadireita e da esquerda. Na figura 2.5, o modelo demonstrado contem uma configuracao deraio de alcance 1, desconsiderando as outras camadas.
2.4.3.2 Vizinhanca de Moore
Constitui uma ampliacao da vizinhanca de Neumann, onde as diagonais agora saotambem consideradas na grade e entao constituem celulas vizinhas.
18
Figura 2.4: Grade Celular e suas Dimensoes
Figura 2.5: Vizinhanca de Von Neumann r=1
2.4.3.3 Vizinhanca estendida de Moore
A vizinhanca estendida de Moore e equivalente vizinhanca de Moore citada ante-riormente e demonstrada , porem com uma configuracao de raio r=2.
2.4.3.4 Vizinhanca Aleatoria
Constitui um metodo de vizinhanca onde as bordas ficam espalhadas de forma naoordenada. Conforme (PASCOAL, 2005) a grade do AC pode ser finita ou infinita. Namaioria dos casos, em simulacoes computacionais e considerada finita. As grades infinitaspodem ser analisadas em nıvel matematico, pois nao possuem limitacoes laterais.
Entretanto as grades finitas devem definir condicoes de limite, ou seja, na malha aser analisada deve existir um momento em que esta analise seja interrompida com o fimda area percorrida. Neste caso, a situacao resultante e que existirao celulas na regiao deborda que possuirao vizinhancas incompletas.
2.4.4 BordasEm (PASCOAL, 2005) apud (Pfeifer, Kuns e Weber, 2002) existem tres possibi-
lidades de resolver o problema das bordas:
• Supor que existam celulas invisıveis ao redor da grade com um estado predefi-nido(Limite Fixo);
• A segunda e supor que as celulas da borda sao vizinhas das celulas da borda oposta(Limite Periodico);
• A terceira e assumir que as celulas da borda sao refletidas internamente a grade(Limite Reflexivo);
19
Figura 2.6: Vizinhanca de Moore r1
Figura 2.7: Vizinhanca de Moore Extendida r1
1. Limite Fixo - E obtido descrevendo como serao os estados das celulas no contornoda grade, estes estados serao mantidos durante todo o instante da interacao.
2. Limite Periodico - E representado quando ha uma extensao da grade de forma quecada celula tenha uma celula vizinha.
3. Limite Reflexivo - E representado quando cada celula da borda difunde interna-mente a grade, de forma a simular uma vizinhanca completa.
2.4.5 EstadosOs estados constituem os possıveis valores assumidos pelas celulas e podem ser
representados na forma de numeros, cores,propriedades como ligado e desligado, etc.Normalmente, os estados devem ser pre-definidos pelo modelo adotado de interacao paraque se possam obter respostas em analises e ate mesmo poder prever as evolucoes seguin-tes.
Os estados que as celulas assumem podem tambem ser considerados como umaresultante final de uma funcao matematica onde o proprio resultado da funcao nao seriaimportante no calculo de transicao.
2.4.6 RegrasE o componente mais importante em um sistema utilizando Automatos Celulares,
os possıveis estados que as celulas podem assumir no AC serao definidos pelas regrasimpostas no modelo utilizado que resultarao em uma tabela de transicao.
As regras de transicao podem ser divididas de acordo com a sua finalidade e abaixoseguem alguns dos modelos de regras de transicao possıveis (PASCOAL, 2005)
20
Figura 2.8: Vizinhanca de Moore Extendida r2
Figura 2.9: Tratamento de Bordas - Limite Fixo
• Especificacao Direta
• Regras Totalısticas
• Especificacao Implıcita e Multi-Passos
• Regras Probabilısticas
1. Especificacao Direta - Consiste na definicao de todos os possıveis estados dascelulas vizinhas, da propria celula e do proximo estado. As variaveis da funcao detransicao neste caso sao 2n e, em determinados modelos de automatos de grandeporte, existira uma quantidade de entradas bastante elevado.
2. Regras Totalısticas - Consistem na analise nao so de um unico vizinho da celulaem questao, mas sim de um conjunto de duas ou mais celulas simultaneamente paraque uma interacao ocorra. Em modelos como o Game of Life (Jogo da Vida) estetipo de regra e bastante utilizado.
3. Especificacao Implıcita e Multi-Passos - A especificacao explıcita pode ser de-terminada por uma formula onde as variaveis representam os estados das celulasvizinhas ou o estado da propria celula, por exemplo, tome-se como exemplo o es-tado de uma celula r dado atraves da formula C(r) = (Celula r-1 esta ativa ou celular+1 esta inativa). A explicitacao multi-passos consiste na forma de como a funcaode transicao e avaliada. As variaveis das formulas podem ser avaliadas em pas-sos diferentes, ou seja, por exemplo, pode-se avaliar na formula anterior primeiroquais as celulas inativas para todas as celulas do automato e depois as celulas ativas,contanto que sejam seguidas as definicoes de automatos celulares.
21
Figura 2.10: Tratamento de Bordas - Limite Periodico
Figura 2.11: Evolucao de um Automato Celular
4. Regras Probabilısticas - Constitui uma regra onde pode-se atingir diferentes saıdaspara a funcao de transicao, porem, para a determinacao de qual possıvel repostaseja resultante atribui-se propabilidades a essas saıdas. Uma forma de aplicar estaregra e definir que uma celula pode inicialmente partir de um estado ou de outrocom probabilidade definida em funcao de seus atuais vizinhos. Este tipo de regranecessita que a soma total das probabilidades seja 1.
2.4.7 Evolucao ou InteracaoEvolucao pode ser considerada de fato a acao em um automato celular. Ocorre
quando a celula faz a leitura de suas celulas vizinhas e, atraves de regras especıficas quelhes foram aplicadas, evolui em passos de tempo discretos.
2.4.8 Padroes de Comportamentos de Automatos CelularesNesta secao serao apresentados os padroes de comportamentos que um AC pode
atingir, os padroes resultantes sao gerados inicialmente pela definicao de uma regra deevolucao e de analise as celulas vizinhas.
Em sistemas que seguem a termodinamica convencional, a segunda lei da termo-dinamica implica numa degradacao progressiva de uma estrutura inicial e uma tendenciauniversal de evoluir com o tempo a estados de maxima entropia e maxima desordem.Enquanto muitos sistemas tendem a desordem, uma grande classe de sistemas mostramuma tendencia inversa: eles espontaneamente geram uma estrutura com o passar dotempo, mesmo iniciando a partir de estados desordenados ou desestruturados. Existemconfiguracoes especıficas de ACs exemplos de sistemas que possuem a propriedade de seauto-organizar.
Como exemplo de automato celular, considera-se uma linha (vetor) de celulas com
22
valores de 0 e 1, conforme a figura 2.12, o valor de uma celula na posicao i no tempo t ea(t)i.
Figura 2.12: Esquema tipico de um Automato Celular
Uma regra muito simples para a evolucao no tempo dos valores das celulas e
a(t+1)i = a
(t)i−1 + a
(t)i+1mod2
onde mod2 indica que e tomado o resto de 0 ou 1 da divisao por 2. De acordo comesta regra, o valor de uma celula em particular e dada pela soma modulo 2 (equivalente-mente ao OU exclusivo da algebra Booleana) dos valores da celulas vizinhas a esquerdae a direita no passo de tempo anterior.
A figura 2.13 mostra o padrao gerado pela evolucao em poucos passos utilizando aregra anterior a partir de uma semente (do ingles, seed) consistindo de apenas uma celulacom o valor 1 e todas as demais com o valor 0. A figura 2.14 mostra o padrao geradoapos 255 passos de tempo. A geracao deste padrao requer a aplicacao da regra anterior acerca de 250 mil valores de celulas.
Figura 2.13: Regra aplicada com poucas Evolucoes
A base matematica deste comportamento e revelada pela consideracao da propri-edades globais de um AC. Ao inves de seguir a evolucao a partir de um estado inicial emparticular, segue-se a evolucao em sua totalidade de uma configuracao de varios estadosiniciais diferentes.
Ao investigar as propriedades globais e conveniente considerar automatos celu-lares finitos que contenham um numero finito N de celulas cujos valores estao sujeitosa certas condicoes. Por exemplo, tal automato celular pode ser representado por celulasarranjadas ao redor de um cırculo. Se cada celula tem dois valores possıveis, existe umtotal de 2N estados possıveis, ou configuracoes, para o automato celular finito completo.
A evolucao global do automato celular pode ser representada por um grafo detransicao de estados finitos indicando o espaco de estados no automato celular. Cada um
23
Figura 2.14: Evolucao da Regra aplicada anteriormente com 255 passos
Figura 2.15: Regra aplicada com estado inicial desordenado
dos 2N estados possıveis do automato celular completo (como o estado 110101101010para um automato celular com 12 celulas) e representado por uma unica aplicacao daregra.
A trajetoria apontada no espaco de estados pelas linhas que conectam um nodoparticular ao seu sucessor corresponde a evolucao no tempo do automato celular a partirdo estado inicial representado pelo nodo particular. O grafo da figura 2.16 mostra todasas possıveis trajetorias no espaco de estados para um automato celular com 12 celulas.
As trajetorias que podem ser observadas na figura 2.16 estao unindo-se com otempo, demonstrando que uma celula tem um tempo t pode ter varios antecessores ounenhum. De forma a caracterizar uma evolucao irreversıvel, uma vez que a informacaode estados anteriores e perdida em sua evolucao sem poder determinar um historico deestados anteriores.
2.4.9 Generalizacoes de Regras de EvolucaoDe acordo com (AGUIAR; COSTA, 2000) diversas generalizacoes permitem cada
celula no automato celular ter um valor dentre um numero arbitrario k de valores e, ainda,permitir que o valor de uma celula dependa de valores que estejam rcelulas distantes, talque:
a(t+1)i = F (a(t)i−r , ..., a(t)t+r .
24
Figura 2.16: Grafo de Transicao de Estados para o automato celular com 12 celulas
O numero de regras diferentes com dados k e r cresce kk2r+1 e, portanto, torna-seimenso mesmo para k e r pequenos.
As regras definidas norlmalmente levam a padroes que diferem em detalhes. En-tretanto todos os padroes tendem a seguir apenas 4 classes de comportamentos:
• Classe 1 - A evolucao leva a estados homogeneos
• Classe 2 - A evolucao leva a um conjunto de estruturas estaveis e periodicas quesao separadas e simples
• Classe 3 - A evolucao leva a padroes caoticos
• Classe 4 - A evolucao leva a estruturas complexas, e algumas vezes, de longa vida.
Figura 2.17: Classe 1 - Aplicacao da Regra 160 com 100 passos
2.4.10 Self-SimilarityUma das propriedades fundamenteais de um Automato Celular com uma celula
configurada em seu estado inicial e a ”‘Similaridade a si Proprio ou auto-similaridade”’do ingles (Self-Similarity) onde.
25
Figura 2.18: Classe 2 - Aplicacao da Regra 164 com 100 passos
Figura 2.19: Classe 3 - Aplicacao da Regra 146 com 100 passos
Como mostrado na figura 2.21, porcoes de padrao, quando aproximadas, saoindistinguıveis do todo. Este padrao auto-similar e frequentemente chamado de fractal epode ser caracterizado pela sua dimensao. Muitos sistemas naturais exibem padroes destetipo, e por isso, podem ser gerados atraves de automatos celulares ou processos analogos.
Em sistemas que seguem a termodinamica convencional, a segunda lei da termo-dinamica implica numa degradacao progressiva de uma estrutura inicial e uma tendenciauniversal de evoluir com o tempo a estados de maxima entropia a maxima desordem.
2.4.11 Self-OrganizationEnquanto muitos sistemas tendem a desordem, uma grande classe de sistemas
mostram uma tendencia inversa: eles espontaneamente geram unma estrutura com o pas-sar do tempo, mesmo iniciando a partir de estados desordenados ou desestruturados. Oautomato celular na figura 2.22 e um exemplo de sistema auto-organizado.
A figura 2.22 mostra a evolucao de acordo com a regra 2.12 a partir de um estadoinicial desordenado. Os valores das celulas e seu estado inicial e escolhido aleatoriamente,cada celula tem a mesma probabilidade de ter valor 0 ou 1, independentemente dos valores
26
Figura 2.20: Classe 4 - Aplicacao da Regra 18 com 100 passos
das outras celulas. Mesmo que o estado inicial nao tenha estrutura, a evolucao manifestaalguma estrutura que formam alguns claros triangulares. O aparecimento espontaneodestes claros e um exemplo de auto-organizacao (do ingles, self-organization).
UniversalidadeSegundo (AGUIAR; COSTA, 2000) uma aboragem quantitativa das classes de
comportamentos e considerar o grau de previsibilidade do resultado da evolucao doautomato celular, dado um conhecimento do estado inicial.
Os comportamentos sao levados em consideracao quando da utilizacao deautomatos celulares no desenvolvimento de ferramentas que utilizem algoritmos evolu-tivos e, o comportamento de uma dada classe pode ser crucial para resultados otimos.
Cada classe possui um comportamento, definido a seguir:
• Para Classe1 - a previsao e trivial, independente do estado inicial a evolucao enorteada sempre para um estado unico e homogeneo.
• Para Classe2 - a previsao e a de os efeitos de uma celula possuirem uma propagacaofinita, ou seja, afetando uma distancia finita de outras celulas vizinhas.
• Para Classe3 - a previsao constitui uma evolucao com velocidade finita, ou seja,afetam celulas cada vez mais distantes a medida que o tempo passa. O valor deuma celula em particular depende cada vez mais de um numero maior de celulasnas geracoes anteriores.
Em especial, para o foco do estudo pode-se destacar o comportamento referente aClasse de comportamento 2, onde segundo (AGUIAR; COSTA, 2000) podem ser consi-derados como filtros que selecionam caracterısticas particulares do estado inicial. Comoexemplo, um automato desta classe pode ser construıdo de modo que as sequencias ini-ciais 111 sobreviverao, mas celulas que nao formam esta sequencia podem tender seusvalores a 0. Tais automatos celulares sao de extrema importancia para o processamentode imagens digitais, podendo ser utilizados para selecionar e melhorar padroes particula-res de pixels.
27
Figura 2.21: Propriedade de Auto Similaridade
Figura 2.22: Propriedade de Auto Organizacao
28
3 ESTADO-DA-ARTE DA APLICACAO DEAUTOMATOS CELULARES PARA MODE-LAGEM DE FENOMENOS DINAMICOS
Nesta secao serao apresentados trabalhos que demonstram aplicacoes desenvol-vidas com Automatos Celulares implementadas na modelagem de fenomenos dinamicos.Este capıtulo ajudara a aprimorar o entendimento e a aplicabilidade de regras de transicao,evolucao e tambem dara margem a novas possibilidades de aplicacoes em projetos futurospara a dissertacao de mestrado.
Para uma correta estruturacao dos conteudos os artigos mostrados foram divididose referenciados no final deste documento. Os artigos relacionados seguem abaixo:
• On Cellular Automaton Aproaches to Modeling Biological Cells (ALBER et al.,1999)
• Modelagem Dinamica de Plantas (BANDINI; PAVESI, 2004)
• Modeling Biology by Cellular Automata (BAGNOLI et al., 1999)
• A cellular Automata Model of Population Infected by Periodic Plague (DZWINEL,2004)
• Automata Network Simulator Applied to the Epidemiology of Urban Dengue Fever(GAGLIARDI; SILVA; ALVES, 2006)
3.1 Modelagem de Celulas BiologicasNo artigo (ALBER et al., 1999)sao apresentados modelos de automatos celula-
res do comportamento de gases (Lattice Gas based Cellular Automata) e dos grupos demodelos (Cellular Pots Model), e tambem suas aplicacoes no modelo biologico.
Os automatos celulares sao utilizados por compreenderem uma grande quantidadede fenomenos biologicos tıpicos, por serem estaveis e tambem faceis de serem modifi-cados. E possıvel descrever o comportamento de milhoes de celulas e simular compor-tamentos, ja que as celulas nao possuem senso de direcao ou de posicao. Os automatosconseguem aproximar-se muito, desde que obedecam certas regras, do comportamento devarias celulas ao mesmo tempo. Por isso, podem modelar a morfogenese, a modelagemda vida de tecidos durante o crescimento, regeneracao, o seu processo de cura e variasoutras patologias.
29
Observa-se que e possıvel de forma simples utilizar automatos celulares sobreparametros fısicos como a energia, temperatura e compressao combinados com processosde controle da evolucao de propriedades da vida e materiais nao-vivos para descreverorganismos de vida complexos.
Normalmente, os modelos de automatos celulares descrevem celula-a-celula asinteracoes no ambiente por regras logicas locais, permitindo a simulacao de um enormecampo de exemplos biologicos comecando da bacteria e o modelo de ameba, para tecidose tumores em embrioes.
Figura 3.1: Ciclo de Vida de um Dictyostelium
Figura 3.2: Grade Celular utilizada pela Modelagem de Celulas Biologicas
3.2 Modelagem Dinamica de PlantasO artigo (BANDINI; PAVESI, 2004) mostra um automato celular para a mode-
lagem de dinamica populacional de plantas. A evolucao de populacoes de plantas emuma dada area depende principalmente dos recursos disponıveis no territorio (em parteinfluenciados por outros fatores como luz do sol, chuva, temperatura etc)de modo comoas diferentes plantas competem entre si.
3.2.1 IntroducaoO modelo e aplicado com sucesso na simulacao de populacoes de robiniae (ga-
fanhotos pretos), carvalho, e arvores de pinho. Os problemas existentes que dificultama simulacao de dinamicas populacionais levam a fatores que podem ser culminantes emtodo o processo como:
30
• Grande dificuldade de adquirir dados para a definicao de modelos de plantas dife-rentes, pois a aquisicao destes leva um tempo exaustivo;
• Certas informacoes tambem deverao levar em consideracao os recursos de sobre-vivencia disponıveis no local como agua, sol, substancias presentes no solo, etc, naopossuindo exatidao nas informacoes devido as mudancas constantes de padroes.
• As informacoes discretas deverao ainda incluir dados necessarios a sobrevivenciados indivıduos como os processos de germinacao, sobrevivencia, crescimento ereproducao.
Acredita-se que atraves de um modelo basico de sobrevivencia tais fatores naoimpliquem tanto a ponto de causar grandes mudancas para uma correta simulacao.
3.2.2 FuncionamentoO modelo apresentado e aplicado em um automato de duas dimensoes contendo
dados sobre a populacao composta de diferentes indivıduos bem como a concorrenciade recursos disponıveis na area. Cada celula podera possuir dados de arvores, frutos, etambem podera ser candidata a receber arvores.
O tipo de vizinhanca utilizado para este artigo foram os de Neumann e Moore paraatualizar os estados das celulas, cada modelo de vizinhanca sera alternado dependendo domomento em que as arvores estiverem quando do seu crescimento, quando jovem e emfase de desenvolvimento a arvore estara competindo de forma mais intensa com as outraspor recursos.
Figura 3.3: Vizinhanca de Von Neumann Esq. e de Moore Dir.
Os recursos de vida que foram descritos no automato sao agua, luz, nitrogenioe potassio. Uma descricao mais formal do automato pode ser representada da seguinteforma:
CA =⟨R,N, Q,
∫, I
⟩onde:
• R = {(i, j)|1 ≤ i ≤ N, 1 ≤ j ≤ M} consiste na grade bidimensional N ×M ;
• N e considerada a vizinhanca que pode adotar o modelo de vizinhanca de VonNeumann ou de Moore;
• Q constitui o conjunto finito de valores das celulas;
•∫
: Q×QH −→ Q consiste na funcao de transicao de estados;
• I : R −→ Q consiste na funcao de inicializacao.
Cada celula do modelo reproduz uma porcao de terreno com um dos lados vari-ando de tres a cinco metros. Os possıveis estados que uma celula pode representar sao osseguintes:
31
• O tipo de terreno de reproducao da celula;
• Os recursos presentes na celula.
• O montante de recursos necessarios para uma celula se reproduzir em cada passo detempo e a quantidade maxima de recursos que uma celula pode possuir de acordocom o tipo: se a arvore esta presente nas celulas, ou nao; caso ela esteja presente, otamanho da arvore e o montante de recursos que ela necessita para crescer e viver;
• O montante utilizado por cada arvore em passsos anteriores;
• As sementes dispersas por outras arvores que vivem na area.
Assumindo que inicialmente k tipos de recursos e que pelo menos 1 especie dife-rente de arvore esta presente na regiao, o conjunto finito de estados Q pode ser definidocomo segue:
Q ={R,M,P, T, ZT , NT , UG
T , UST , RT , MT , GT , S
}Onde:
• R ={r1, ..., rk
}constitui um vetor definindo a quantidade de cada recurso presente
na celula;
• M = {m1, ...,mk} constitui a quantidade maxima de cada recurso que uma celulapode conter;
• P = {p1, ..., pk} constitui a quantidade de recursos produzidos para uma dada celulaem cada passo de atualizacao;
• T e uma flag indicando se uma arvore estara presente em uma celula ou nao;
• ZT ={
zrT , zt
T , zlT , zf
T
}, constitui um vetor definindo o tamanho das diferentes par-
tes de uma arvore no modelo descrito (raızes, folhas, troncos e frutos).
• NT = nT [1], ..., nT [k] constitui a quantidade de recursos que as arvores consomemda celula para cada etapa da atualizacao (por sua vez dependendo do tamanho atualda arvore ZT );
• UGT =
{uG
T [1], ..., uGT [k]
}constitui o vetor definindo a quantidade individual de
recursos que a arvore necessita para crescer em cada atualizacao;
• RT = {rT [1], ..., rT [k]} e o valor de cada recurso armazenado pela arvore no passoanterior;
• MT e um vetor descrevendo todos os parametros globais da arvore em si, comoo tamanho maximo a ser atingido, idade maxima de vida, idade mınima parareproducao, numero maximo de sementes produzidas pelas unidades de massa defrutos, assim por diante. Essas limiares podem ser fixas ou determinadas ao acasoem um intervalo determinado sempre que for criada uma nova arvore;
32
• GT ={
grT , gt
T , glT , gf
T
}e um vetor definindo a taxa de crescimento de cada uma
das partes da arvore, ou seja, como sera o crescimento de partes distintas da arvorequando existirem recursos suficientes para utilizar;
• S = {s1, ..., sl} e um vetor definindo o numero de sementes presentes em cadacelula de cada uma das especies que deverao crescer no territorio.
Os passos de funcionamento do automato podem ser descritos como segue:
1. Em cada etapa de atualizacao, a arvore presente na celula (se existir) toma recur-sos para suprir suas necessidades e as utiliza para sobreviver, crescer e produzirsementes;
2. Se os recursos disponıveis na celula excederem suas necessidades, a arvore arma-zenara recursos para passos posteriores;
3. Caso os recursos disponıveis nao sejam suficientes, serao utilizados recursos arma-zenados em passos anteriores;
4. Se nao existirem recursos em passos anteriores para serem utilizados a arvoremorre, deixando um novo espaco para sementes germinarem;
5. Fatores como a existencia de muitas arvores proximas a alguma regiao e tambem aexistencia de rios proximos influenciam na capacidade de arvores sobreviverem porexistirem recursos abundantes na regiao.
6. Para todas as arvores existentes na grade tambem existem limites de tempo de vida,quando elas atingem a idade adulta e sobrevivem uma quantidade x de anos, mor-rerao por velhice.
Cada etapa da atualizacao do automato abrange um determinado perıodo detempo. As regras sao adequadas para o tempo de um ano de atualizacoes (isto e, cadaatualizacao de celula reproduz a evolucao da populacao em um ano).
3.2.3 Regras de TransicaoSeja C(i, j) uma celula localizada na posicao (i, j) dentro da grade. Com R(i, j)
denotando o vetor de celulas com recursos C(i, j), com M(i, j) contendo os valoresmaximos de recursos existentes e assim por diante, a funcao de transicao pode ser de-finida com uma divisao em 4 sub-passos:
1. Sustentacao da Arvore - Se uma arvore estiver presente em uma celula C(i, j)ela consome uma quantidade determinada de recursos (definidos por NT (i, j)) dosr(i, j) que estiverem disponıveis. Se, por algum recurso i, o montante disponıvelri(i, j) for inferior ao valor correspondente em NT (i, j), a arvore pode utilizar todaa quantidade de recursos ri(i, j) que necessitar utilizar. A quantidade de recursos aserem utilizados dependem do tamanho da arvore ZT (i, j). Caso os recursos exis-tentes sejam suficientes para a etapa atual e para etapas anteriores, definidos pelovetor UG
T (i, j), a arvore esta apta a crescer de acordo com o vetor GT (i, j) associado
33
juntamente com a arvore. Caso contrario, os recursos podem ser apenas suficien-tes para a arvore sobreviver (controlados pelo vetor US
T (i, j)) permanecendo, nestecaso, os parametros da arvore inalterados.
Tanto no primeiro quanto no segundo caso, a arvore utilizara recursos, sendo defini-dos pelo vetor UG
T (i, j) ou UST . Todos os recursos que forem recolhidos porem nao
forem utilizados nesta etapa serao armazenados e adicionados ao vetor RT (i, j).Caso contario, se o montante global(armazenados mais todos os coletados) de pelomenos um recurso estiver sob o “limiar de sobrevivencia”da arvore, esta ultimamorre. Outro fator de morte para uma arvore e o fato de alcancar a idade maximadefinida no vetor MT (i, j). Os recursos que nao forem utilizados pela arvore podempermanecer em uma celula ou desaparecer.
2. Reproducao de Arvores - Para a reproducao foram considerados dois casos: apresenca de uma arvore em uma celula ou, a celula estar vazia. Caso exista umaarvore, ela pode produzir algumas sementes (caso ela seja velha o suficiente e,levando em consideracao o tamanho de seus frutos Zf
T (i, j)), que serao utilizadospara atualizar as variaveis correspondentes no vetor de sementes S(i, j). Novasarvores nao poderem nascer em celulas onde existem arvores porem, celulas vagaspodem conter varias sementes.
3. Producao de Recursos disponıveis - Cada celula produz uma determinada quan-tidade de recursos, definidos pelo vetor de producao P (i, j). Entretanto, o motantetotal de recursos contidos em uma celula nao pode exceder o valor correspondentedefinido no vetor M(i, j).
4. Fluxo de Recursos - Os recursos sao equilibrados entre as suas celulas vizinhas,com a finalidade de manter um fluxo de recursos ricos em celulas onde existemrecursos mais pobres. Atraves do vetor rh(i, j) e definida a quantidade de recursosh contidos por uma celula C(i, j) e assume que estara utilizando a vizinhaca de VonNeumann r
′
h(i, j). O montante de recursos apos esta atualizacao e definido como:
r′
h(i, j) =rh(i, j)
2+
rh(i + 1, j) + rh(i− 1, j)
8+
rh(i, j + 1) + rh(i, j − 1)
8
Em outras palavras, a celula e dividida em quatro partes, uma contendo o montanterh(i,j)
4de recursos h, e corresponde a um dos vizinhos. A quantidade de recursos h
contida em cada parte e equilibrada com a parte correspondente nos dos vizinhos.Neste caso foi adotada a vizinhanca de Moore imagindo que as celulas sejam parti-das em oito partes de forma a significar que uma celula C(i, j) rica em recursos hem relacao aos seus vizinhos, tera o seu conteudo derramado nos vizinhos. Obede-cendo a regra comentada anteriormente de que r
′
h(i, j) = mh(i, j). A mesma regrae aplicada para cada um dos componentes do vetor de sementes S(i, j).
Na implementacao, o estado inicial do automato celular pode ser definido pelousuario, atraves da configuracao de parametros adequando recursos para cada celula. Omodelo utilizado para implementacao foi a linguagem C++ rodando em uma plataformaWindows NT. Atraves da interface mostrada na figura (?) pode-se efetuar uma serie deconfiguracoes quanto ao comportamento dos elementos para a simulacao como:
34
• Diferentes tipos de celulas com a quantidade maxima de recursos que pode conterou produzir, reproduzir rios, tipos de terreno e estradas;
• Diferentes tipos de arvores, de acordo com os montantes dos recursos necessariospara cada etapa de atualizacao, com a taxa de crescimento das partes e quantidadede sementes produzidas.
• Recursos adicionais e tambem a configuracao inicial do automato.
Figura 3.4: Configuracao de Populacao Inicial
Figura 3.5: Visualizacao de Funcionamento da Dinamica Populacional
Alem das caracterısticas citadas a interface demonstra passo-a-passo a evolucaodo sistema, dando uma imagem clara do crescimento dar arvores, distribuicao dos re-cursos no territorio, resultados globais (como numero total de arvores, arvores para cadaespecie,etc)
Conclui-se que o experimento simula os fatores de dinamica populacional envol-vendo populacoes de arvores levando em consideracao os fatores externos como a quan-tidade de recursos disponıveis, tempo de vida, nascimento e crescimento de novos in-divıduos, etc tornando a simulacao muito proxima da realidade. A ferramenta serve paraefetuar a simulacao de casos reais e tambem entender os principais fatores que influen-ciam a dinamica as populacoes.
3.3 Modelagem de Epidemias: Simulacao de Dengue Ur-bana
O artigo (PASCOAL, 2005) demonstra um software para simulacao dePropagacoes de Epidemias de Dengue baseado na Automatos Celulares propabilısticos.
35
Visa reproduzir uma situacao onde existe a interacao de populacoes de humanos e mos-quitos, considerando a mobilidade populacional e geografica tanto de humanos quanto demosquitos.
A Modelagem matematica e estatıstica, em especial, sao valiosas no design einterpretacao dos estudos epidemiologicos, mas nao sao adequados para simulacao deintervencoes e resultantes de mudancas de comportamento. O aumento de velocidadedo computador transformadores e disponibilidade de memoria barata agora proporcio-nam uma melhores estrategias para prevenir a propagacao de epidemias dando origem aodesenvolvimento da novas metodologias.
O modelo basico de transmissao contagiosa e a simulacao entre interacoes depopulacoes (Humanos e mosquitos), incluindo o perıodo de infeccoes individuais quesao descritos diretamente em termos de locais(contactos fısicos) e de os modos de trans-missao de forma global (mobilidade populacional).
3.3.1 FuncionamentoComo o modelo utilizado no artigo considera interacoes entre humanos e mosqui-
tos, foi utilizado um vetor de humanos onde a populacao de N indivıduos foi distribuıdasobre os locais na malha M = m(ij) podendo variar de 1 a L (N = L× L). Cada celulafoi condicionada a receber tres atributos especıficos:
• Um endereco espacial ou posicao na malha (i, j);
• Um conjunto de possıveis estados clınicos especificando a situacao de doenca indi-vidualmente para cada elemento da populacao, por exemplo, alguem propıcio a sercontaminado, um transmissor de doencas ou recem recuperados ;
• Um perıodo t, especificando quantas unidades de tempo serao necessarias para umindivıduo conseguir recuperar-se de um estado clınico de infectado para recuperado.
A evolucao da populacao e descrita passo a passo por um conjunto de regras par-tindo do princıpio que cada nova configuracao de estado do sistema (descrita pela posicaodo indivıduo na grade (i,j) instantaneamente pelo numero de indivıduos de um determi-nado estado) depende apenas de seu estado anterior.
A parte principal do artigo se refere quanto as definicoes das regras de transicaopara a dengue, que sao definidas por dois tipos de estados, cada um para representaro comportamento populacoes distintas. Em uma linguagem de modelagem de estadosvariaveis, os humanos sao definidos pela sigla SEIR(Suscetıvel, Exposto, Infeccioso eRecuperado), onde o indivıduo quando exposto esta infectado mas nao infeccioso.
A populacao de mosquitos e representada por uma diferente sigla SEI(Suscetıvel,Exposto e Infeccioso), conforme mostrado na figura (?).
A figura (?) demonstra o Modelo esquematico da Dengue representando as fasesda doenca para ambas as populacoes, onde as setas azuis representam as interacoes entreas populacoes (mosquitos “mordendo” humanos) e as setas pretas as transicoes de estadointernas de cada uma.
O modelo de automato apresentado em (GAGLIARDI; SILVA; ALVES, 2006)utiliza duas grades para representar o vetor de humanos e mosquitos, onde interacoessao calculadas pela equivalencia entre as posicoes das malhas, ou seja, onde existir umasobreposicao de elementos humanos e mosquitos dever-se-a verificar um caso de infeccao.
36
Figura 3.6: Modelo Esquematico da Dengue
As interacoes entre celulas nao sao feitas entre vizinhos da mesma populacao, cada vizi-nho de uma celula humana e definida pelo vetor de mosquitos e os vizinhos da populacaode mosquitos sao definidos pelo vetor de humanos, esta caracterıstica possibilita que umhospedeiro humano seja picado por um mosquito saudavel e contamine outros mosquitosque ainda nao carregam a dengue.
A interacao (mordida) nunca ocorre diretamente, pelo fato de humanos nao pode-rem transmitir o Aedes Aegypti entre si e os mosquitos serem infectados apenas quandomorderem humanos infectados. No modelo apresentado existe um quadro novo propostopara a disseminacao do surto de dengue, tambem sao definidas as regras internas paracomandar a interacao entre as populacoes (humanos e mosquitos) conforme mostrado nafigura 3.7.
Figura 3.7: Demonstracao das interacoes Globais e Locais para a simulacao.
37
Na figura 3.7 as setas nos quadros representam os mosquitos afetados por in-fluencia local e global infecciosa por parte de humanos. Ao mesmo tempo as influenciasinfecciosas ocorrem de cima para baixo utilizando o mesmo modelo, embora agora sejamos humanos sendo infectados por mosquitos de forma local e global para cada passo dasimulacao. A figura demonstra tambem a influencia de um unico elemento em relacao avizinhanca do outro vetor.
Para o funcionamento, algumas regras sao adotadas:
1. Qualquer humano tem a possibilidade de tornar-se infectado com probabilidade Ps.
2. Um indivıduo contaminado torna-se infeccioso apos um curto perıodo de tempo tE(assumido como uma constante, sem perda de generalizacao).
3. Indivıduos infectados sao removidos deterministicamente do sistema, tornando-seimunes, apos um perıodo de infeccao t1 maior que 0, considerado uma constantepara todos os indivıduos humanos infectados e infinito para a populacao de mos-quitos.
4. Sempre que houver uma remocao de classe, o indivıduo participara somente deforma passiva na propagacao de infeccoes (eventualmente podendo interromper apropagacao) por um perıodo maior de imunidade do que o processo epidemico com-pleto.
A probabilidade de qualquer Ps indivıduo suscetıvel (humanos ou mosquitos) dese tornar infeccioso e uma sobreposicao de: o modo local de transmissao que incor-pora os indivıduos baseados em componentes de indivıduos suscetıveis, os atuais con-tatos fısicos de cada indivıduo suscetıvel com experiencias individuais e a influencia glo-bal feita intrinsicamente pela mobilidade da populacao, que pode ser visto como umaaproximacao resultante de um campo medio discreto. Neste sentido, a transmmissao dedoencas para cada indivıduo suscetıvel tambem depende instantaneamente do numero to-tal de indivıduos infecciosos na populacao. Portanto, pode-se presumir que a transmissaoda doenca ocorre com uma probabilidade total Ps descrita como:
PS = Γ P G + Λ P L,
onde os fatores precedentes Γ e Λ sao parametros de peso que regulam interacoesa curto e longo prazo, e e tambem requerido que Γ + Λ = 1 em ordem para satisfa-zer os requerimentos probabilısticos 0 ≤ PS ≤ 1. A influencia global PG representa aprobabilidade de um indivıduo suscetıvel de uma populacao (humano ou mosquito) detornar-se infeccioso devido a presenca de I (t) indivıduos infectados na outra populacao(meio campo) relacionados com movimentacao dos elementos internos sobre o espaco, ouseja, a capacidade de um elemento estabelecer contato com qualquer elemento da outrapopulacao e infecta-lo. Por outro lado, os termos locais PL = P
(i,j)L constituem a proba-
bilidade de um indivıduo suscetıvel (localizado na grade (i,j)) estarem infectados devidoaos n infectivos na primeira e segunda vizinhancas (mais vizinhancas).
As probabilidades resultantes para cada populacao seguem abaixo:Humanos:
PL = 1− (1− λm)nImePG =phNmi(t)
Nm
38
Mosquitos:
PL = 1− (1− λm)nIhePG =PmNih(t)
Nh
Entretanto, o sistema e regido pelo Ps e t e a evolucao temporal e determinadapela atualizacao da grade sincronizadamente em cada passo de tempo com a aplicacaodas regras apresentadas anteriormente.
Para a implementacao da ferramenta de simulacao da propagacao de epidemias foiutilizada a linguagem C++ utilizando a biblioteca OpenGL para a criacao de animacoesna grade. Conforme descrito anteiormente o sistema e composto dos quatro modulos,especificacao, simulacao, visualizacao e analise.
O sistema foi desenvolvido para permitir ao maximo o usuario configurarparametros como perıodo de dias que indivıduos podem ficar infectados, duracao detempo em que o vırus ficara incubado, probabilidades locais e globais, interacao entreas duas grades (humanos e mosquitos) bem como o tipo de visualizacao da animacao.
O modulo de simulacao e o responsavel pela execucao da simulacao obedecendoos parametros indicados, o estado inicial dos elementos na grade e definidos pelo propriosistema possuindo valores inteiros como (0 (zero) para suscetıvel, 1 com tE para a expos-tos (infectados), tE + 1 to tE + tI para infectivos e tE + t1 + 1 para recuperados). Dessaforma, para cada atualizacao e feito um aumento do tempo atual do sistema e sao lidosos dados das duas grades (vetor de humanos, vetor de mosquitos) para tambem atualizaros seus dados. Se um indivıduo no estado atual constituir um estado suscetıvel, existiraa probabilidade Ps de vir a ser infectado (Equacao 1), o qual e calculado pela soma dasprobabilidades globais e locais descritas nas equacoes 2 e 3, respectivamente. Caso naoseja suscetıvel no estado atual, o valor inteiro e aumentado.
Figura 3.8: Interacao entre as grades de mosquitos e humanos vista de cima
Nas figuras 3.8 e 3.9 mostradas, as duas possuem os mesmos parametros e va-lores γ porem com Γ = 0 para ambas as grades (sem um sistema de interacoes globais)para a 3.8 e Γ = 0,2 para a populacao humana (em um sistema humano com interacoesglobais com mosquitos). Fazendo uma comparacao entre as duas simulacoes pode-se verque que a primeira requer uma grande quantidade de tempo para percorrer toda a grade.Neste caso a propagacao e geograficamente dependente. No entanto, com apenas um pe-queno aumento no valor Γ pode-se observar que a propagacao e mais rapida pois se tornaconcorrente devido a movimentos globais entre as grandes redes de elementos.
39
Figura 3.9: Interacao entre as grades de humanos e mosquitos vista em perspectiva
Uma caracterıstica muito interessante da analise modulo e a capacidade de obser-var a progressao da epidemia entre a serie de realizacoes de medias que sao calculadaspelos dados gerados no processo simulado de epidemia. Em seguida, e possıvel visualizara media de comportamento do sistema para um conjunto de variaveis configuraveis comintervalos de parametros.
O artigo comenta ainda que as simulacoes utilizadas para testes do modelo pro-posto foram feitas em uma cidade criada virtualmente com ruas e construındo o modelode populacao de acordo com a situacao inicial da cidade. Na figura 3.10 e demonstrada acidade simulada e serve tambem de tema para futuros trabalhos como foco em simulacoesem mapas de cidades contendo dados populacionais reais para uma correta simulacao eobtencao de resultados.
Figura 3.10: Simulacao do Modelo de Dengue sobre a cidade de Santos reproduzidadigitalmente
40
4 CONSIDERACOES FINAIS
4.1 IntroducaoCom respeito a aplicacoes de automatos celulares, a utilizacao do sensoriamento
remoto e dos sistemas de informacao geograficos (SIGs) tem permitido que a integracaodos dados esteja em contexto espaco-temporal. Os SIGs tem sido empregados, entreoutras atividades, em zoneamento e gestao de unidades de conservacao e a sua insercaona paisagem de entorno.
Entretanto, os SIGs nao sao suficientemente expressivos para analises dos as-pectos que devem ser levados em consideracao na realizacao das analises que visam adeterminacao de areas para conservacao ambiental, principalmente quando se quer levarem conta aspectos dinamicos.
Estes aspectos inseridos na proposta do ambiente IPE servirao ao estabelecimento,por exemplo, de estrategias de conservacao e os resultados das simulacoes tambem po-derao ser aplicados ao gerenciamento ambiental. Em andamento, sob orientacao do co-ordenador deste Projeto e orientador na producao deste trabalho, tem-se um estudo demodelos dinamicos baseados em automatos celulares para as mais diversas aplicacoes ci-tadas anteriormente ( (ALBER et al., 1999), (BAGNOLI et al., 1999), (GAGLIARDI;SILVA; ALVES, 2006))entre outras.
A origem do projeto IPE se deu em uma aplicacao da pratica de segmentacaoe categorizacao (classificacao) de informacoes geograficas e a extracao de informacoescombinadas a partir das diversas propriedades geofısicas gerando material para o desen-volvimento de uma tese de Doutorado ( (AGUIAR; ROCHA COSTA, 2001) que posteri-ormente, no Projeto “Informatica Aplicada ao Meio Ambiente”, utilizaram-se os modelosdesenvolvidos na tese para a determinacao de areas prioritarias a conservacao ambiental apartir de informacoes obtidas em cooperacao com a Escola de Ciencias Ambientais destaUniversidade, mais especificamente, com o Prof. Alex Bager.
Neste contexto, foram utilizados Automatos Celulares como modelo teorico paraa fundamentacao dos algoritmos de segmentacao e categorizacao de regioes geograficas.Como estes modelos sao inerentemente paralelos, coube perfeitamente a utilizacao dacomputacao de alto desempenho no auxılio ao processamento da grande quantidade deinformacoes disponıveis. Alem disso, estes modelos utilizaram a Matematica Intervalarpara tratamento dos erros de discretizacao e computacao numerica.
O Projeto tem como objetivo geral o desenvolvimento de um ambiente computa-cional para o processamento de informacoes e simulacao de aspectos dinamicos baseadoem algoritmos evolutivos com alto desempenho de carater generico. Pretende-se, assim,
41
fornecer uma arquitetura computacional para o desenvolvimento de aplicacoes dinamicasdemandadas por diversas areas do conhecimento. Mais detalhadamente, pretende-sealcancar objetivos em tres ambitos de pesquisa:
1. ambito de arquitetura: um ambiente integrador dos modelos de segmentacao esimulacao baseados em algoritmos evolutivos de alto desempenho, do sistema ge-renciador de bancos de dados apropriado e da interface deste ambiente acessıvelpela internet ou por dispositivo movel;
2. ambito de pesquisa basica: aperfeicoamento dos modelos propostos na tese e nostrabalhos posteriores e criacao de novos modelos de segmentacao de imagens coma incorporacao de estruturas de dados mais eficientes; extensao destes modelos paracomputacao em agregados de computadores e computacao em grade; construcao dainterface entre as informacoes geradas pelos modelos, seu repositorio e visualizacaoremota;
3. ambito de pesquisa aplicada: desenvolvimento de aplicacoes baseadas nestes tiposde algoritmos em agregados de computadores ou computacao em grade.
Dada a interdisciplinaridade desta proposta, este Projeto oportunizara benefıciosrelacionados tanto no ambito computacional (de modelos e ferramentas) quanto no ambitode aplicacoes. Considerando a Informatica como atividade-meio, os benefıcios espera-dos estao concentrados nas seguintes questoes:
1. Meio-ambiente - Com vital importancia do desenvolvimento de ferramentas com-putacionais para auxılio a analise combinada de todos os aspectos que devem ser le-vados em consideracao quando da realizacao dos estudos que visam a determinacaode areas prioritarias para conservacao ambiental. Os sistemas de informacoes ge-ograficas nao sao suficientemente expressivos para analises desse tipo, principal-mente quando se desejam levar em conta aspectos dinamicos. O seu uso tem sidoempregado em avaliacoes do potencial turıstico de unidades de conservacao, zo-neamento de unidades de conservacao e a sua insercao na paisagem de entorno,elaboracao de planos de manejo e elaboracao de planos de gestao de sistemas deunidades de conservacao.
2. Medicina - Com a utilizacao de imagens digitais em ciencias biologicas, mais pre-cisamente na medicina, tem propiciado grandes avancos tanto na precisao de di-agnosticos como na documentacao de experimentos medicos. O avanco da medi-cina aponta para diagnosticos cada vez mais precisos e mais precoces utilizando-sede tecnicas de segmentacao de imagens digitais. Sobre o ambiente IPE poderiaser desenvolvido um aplicativo para confirmar as diferencas intra e entre grupos deareas de necrose entre cobaias submetidas a terapeuticas diferentes. Pretende-sea criacao de um modelo que consiga atraves da segmentacao das imagens obtidasnos experimentos estabelecer estas diferencas e propor alguma classificacao a par-tir da analise da evolucao dos padroes de necroses. A relevancia do projeto estana interpretacao dos efeitos mais precoces possıveis de uma droga antioxidante eoxigenacao hiperbarica sobre a cicatrizacao e na possibilidade de fazer predicoesde comportamento conforme o padrao apresentado pela necrose verificada.
42
5 CONCLUSAO
O presente trabalho apresenta um estudo sobre Automatos Celulares (AC) des-crevendo detalhadamente seus componentes, possıveis variaveis de comportamentos eregras atualmente aplicadas. Para a elaboracao deste buscou-se uma fundamentacaoteorica envolvendo artigos da area de modelagem de Automatos Celulares, algumasimplementacoes, bem como teses de doutorado, dissertacoes contendo pesquisas novasou em fase desenvolvimento.
O uso de automatos celulares compreende uma gama muito grande de aplicacoesque foram detalhadas ao longo deste trabalho e, uma quantidade exponencial de variantesque podem gerar temas de estudo para trabalhos futuros. Estes trabalhos e outros que naoforam abordados neste Trabalho Individual serao objetos de estudo e aprofundamentodurante o proximo perıodo de desenvolvimento da dissertacao de mestrado.
43
REFERENCIAS
AGUIAR, M. S.; COSTA, A. c. d. R. Maquinas Construtoras: Alternativa para o Estudoda Complexidade da Estrutura de Algoritmos. 2000. Exame de Qualificacao — Universi-dade Federal do Rio Grande do Sul, UFRGS, Porto AlegreRS.
AGUIAR, M. S. d.; COSTA, F. A. d.; DIMURO, G. P.; COSTA, A. C. d. R. ModelosMatematicos baseados em Automatos Celulares para Geoprocessamento. [S.l.]: SB-MAC - Sociedade Brasileira de Matematica Aplicada e Computacional, Sao Carlos - SP,Brasil, 2004.
AGUIAR, M. S. de; ROCHA COSTA, A. C. da. Automatos celulares para analise damonotonicidade da declividade de areas geologicas. , [S.l.], 2001.
ALBER, M. S.; KISKOWSKI, M. A.; GLAZIER, J. A.; JIANG. Automatos Celulares.[S.l.: s.n.], 1999.
BAGNOLI, F.; RUFFO, S.; PH, C.; COORDINATOR, D.; POZZI, G.; BEZZI, M. Mo-deling Biology By Cellular Automata.
BANDINI, S.; PAVESI, G. A Model Based on Cellular Automata for the Simulationof the Dynamics of Plant Populations.
DZWINEL. A Cellular Automata Model of Population Infected by Periodic Plague. In:INTERNATIONAL CONFERENCE ON CELLULAR AUTOMATA FOR RESEARCHAND INDUSTRY, ACRI, LNCS, 2004. Anais. . . [S.l.: s.n.], 2004. v.6.
FU, S. C.; MILNE, G. A Flexible Automata Model for Disease Simulation. In: INTER-NATIONAL CONFERENCE ON CELLULAR AUTOMATA FOR RESEARCH ANDINDUSTRY, ACRI, LNCS, 2004. Anais. . . [S.l.: s.n.], 2004. v.6.
GAGLIARDI, H. F.; SILVA, F. A. B. da; ALVES, D. Automata Network Simulator Ap-plied to the Epidemiology of Urban Dengue Fever. , [S.l.], v.3993, p.297–304, 2006.
PASCOAL, F. S. Sociedade Artificial FIGHT4LIFE: Automato Celular Mode-lando a Vida Artificial. 2005. Relatorio Final de Projeto de Iniciacao Cienti-fica(PIBIC,CNPq,INPE) — Instituto Nacional de Pesquisas Espaciais.
REY, A. M. del; WHITE, S. H.; SANCHEZ, G. R. A Model Based on Cellular Au-tomata to Simulate Epidemic Diseases. 2006. 304–310p. Dissertacao (Mestrado emCiencia da Computacao) — .
