Autômato celular e modelo baseado em indivíduos

De Física Computacional
Revisão de 17h14min de 1 de julho de 2021 por Jhordan (discussão | contribs)
Ir para navegação Ir para pesquisar

Anterior: Simulação e modelo de campo médio | Índice: Ecologia | Próximo: Contexto ecológico


Sociedades artificiais são modelos da sociologia computacional que são utilizados em análises sociais utilizando simulações computacionais, é um tema bastante conectado à sistemas complexos, desta forma se aproxima dos nossos modelos ecológicos.

Dentre as simulações computacionais utilizadas temos: algoritmos evolucionários (evolutionary algorithms - EA), algoritmos genéticos (genetic algorithms - GA), programação genética (genetic programming - GP), programação memetica (memetic programming - MP), modelos baseados em agentes (agent based model - ABMs) e autômatos celulares (cellular automata - CA). Estes dois últimos são de especial interesse para nós.

Autômatos celulares

Autômatos celulares consistem em uma grade de células, onde cada uma está em um estado possível dentro de um conjunto finito de estados. Utilizando como exemplo para discussões posteriores o modelo de 2 herbívoros com dinâmica de destruição do sistema, os possíveis estados de cada célula são:

  1. D - Destruído
  2. L - Livre
  3. O - Ocupado por ovelha
  4. G - Ocupado por guanaco
  5. OG - Ocupado por ovelhas e guanacos

Associado a cada célula temos um conjunto de células que são definidas em relação à esta célula específica, este conjunto recebe o nome de vizinhança. No nosso exemplo definimos como os 4 primeiros vizinhos da célula. Definimos um estado inicial para todas as células e temos uma nova geração em onde aplicamos uma regra de transição que determina o novo estado de um célula baseada em seu próprio estado atual e no estado das células vizinhas. Em geral as regras para atualização são as mesmas para cada células durante toda a simulação e é aplicado em toda a grade simultaneamente (síncrono). Algumas coisas que podem ser interessantes é mencionar que para o autômato celular, o espaço, o tempo e os estados são todos discretizados. Podemos comparar com outros sistemas dinâmicos espacialmente estendidos em termos da discretização destes três elementos[1]:


Modelo Espaço Tempo Estado
Autômato celular D D D
Rede de mapas acoplados (CML) D D C
Equação diferenciais ordinárias acopladas D C C
Equação diferencial parcial C C C

Onde D significa que é discreto e C que é contínuo, CML significa coupled map lattices.Também é interessante de se destacar aqui, é que matemática e ciência computacional são disciplinas básicas para o autômato celular, então estamos efetivamente utilizando estes conjuntos de conhecimentos como ferramentas e expandindo um pouco nossos recursos disponíveis. Utilizando não mais apenas a matemática tradicional, mas também a ciência da computação. O que explica um pouco alguns problemas de nomenclatura e definições de termos que podem ser encontrados ao longo dos textos, aos poucos estes devem ser corrigidos conforme o próprio conhecimento vai sendo amadurecido.

Investigações teóricas de CA geralmente consistem em pegar uma dada regra e descobrir propriedades matemáticas relacionadas. Mas a maior parte das aplicações em ciências naturais seguem uma aproximação inversa, ou seja, busca-se descobrir a regra que reproduz as propriedades conhecidas que governam o fenômeno estudado.

Além disto, as regras de transições podem ser determinísticas ou estocásticas. Como os termos sugerem, no caso determinístico o novo estado de cada célula é determinado rigidamente baseado no estado presente da própria célula e no estado das células vizinhas. No caso estocástico (também chamado de autômato celular probabilístico) a seleção do estado da célula em cada tempo é sujeita a uma função probabilística, esta regra de transição oferece uma melhor analogia a sistemas naturais e também é o caso do nosso exemplo.

Além disso classicamente se discute quatro classes de comportamentos que podem ser reproduzidos por um autômato celular elementar, eles são qualitativamente caracterizados como:

  • Classe 1: a evolução leva a um estado homogêneo; depois de um certo tempo, todas as células possuem um estado similar, independente do estado inicial.
  • Classe 2: a evolução leva a um conjunto de estruturas separadas simples ou periódicas; uma organização espacial surge com distintos domínios espaciais que podem ser homogêneos e estáveis ou periódico com alteração dos estados.
  • Classe 3: evolução leva a um padrão caótico; independente das condições iniciais o autômato celular leva a padrões aperiódicos em que não podem ser identificados qual foi o padrão inicial
  • Classe 4: evolução leva a estruturas complexas, algumas vezes com tempo de vida; nessa classe surge alguns padrões espaciais complexos que podem durar por um tempo específico, esses padrões possuem propagação espacial enquanto mantém uma conservação do seu formato.

Sem realizar análises detalhadas, aparentemente o exemplo que escolhemos pertence à classe 2. Claro que esta classificação é que com os parâmetros utilizados no artigo que levam o sistema à um regime oscilatório. Com outros parâmetros que levaria o sistema à uma extinção total por exemplo, teríamos uma classe 1.

A literatura ecológica que lida com autômatos celulares em sua maioria está de alguma forma relacionado à questão da heterogeneidade espacial. Alguns trabalhos buscam responder como os processos biológicos respondem a uma heterogeneidade preexistente. Pensando no outro modelo com a destruição fixa, este tinha como objetivo estudar como o sistema evolui a partir de uma distribuição fixa das células destruídas no início. Outra classe de trabalhos busca a resposta inversa: como os processos biológicos podem criar heterogeneidade. Neste caso, podemos lembrar do próprio exemplo, onde estuda-se como a dinâmica produz as ondas de desertificação.

Além disso vale destacar que as interações em um CA são de curto alcance, o que é negligenciado em modelos de campo médio por exemplo. Outras características importantes e interessantes de um modelo de autômato celular são as capacidades de auto-manutenção e auto-organização.

Em todas aplicação de CA na ecologia, cada célula é considerado um espaço para um indivíduo biológico. No nosso exemplo cada ’indivíduo biológico’ ganha a interpretação de uma metapopulação de cada espécie, isto pode representar um indivíduo ou uma manada, não há distinções do tamanho desta metapopulação. Desta forma cada célula tem nos seus estados a informação, como comentamos anteriormente, apenas se ela está ocupada ou não por aquela espécie, mas não admite uma variação de indivíduos dentro da mesma célula, isto é, não admite variar o tamanho da metapopulação que ocupa cada célula. Não é claro como o CA determinístico poderia incorporar esta variação individual, mas é perfeitamente concebível utilizando uma regra de transição estocástica. Isto poderia ser feito por exemplo, variando a probabilidade de adotar determinado estado, desta forma um modelo de CA pode ser utilizado com o objetivo de construir um modelo baseado em indivíduos. Esta é uma alternativa.

Modelos baseados em agentes

Modelos baseados em agentes são modelos computacionais para simular ações e interações entre agentes autônomos, estes modelos são mais intuitivos que modelos matemáticos ou estatísticos, uma vez que representam objetos como nós vemos: coisas individuais no mundo. Os exemplos mais familiares para muitas pessoas são os jogos The SIMS ou SIMCity.

Na ecologia estes modelos também são chamados de modelos baseados em indivíduos (individual-based models - IBMs), modelo baseado em entidades ou simulações baseadas em indivíduos/entidades/agentes. Além disso há uma discussão sem nenhuma resposta conclusiva na literatura e entre profissionais envolvidos se modelos baseados em agentes são a mesma coisa que sistemas multi-agentes (multi-agent system - MAS), ou se não são, então onde começaria um e terminaria outro, algumas autores ainda consideram IBMs como modelos pertencente à classe de modelos MAS. Para o resto do texto, se necessário vou considerar sistema de multi-agentes apenas como outro nome para modelo baseado em indivíduo[2]. Porém parece que MAS é um termo predominantemente das áreas baseadas em ciência computacionais e normalmente possui o propósito de resolver um problema real ou completar uma tarefa, um exemplo são redes de telecomunicação. Enquanto IBMs normalmente estão relacionados a ciências naturais como ecologia e ciência sociais, sendo predominantemente pesquisas sobre sistemas naturais em que a simulação tem por objetivo observar o comportamento coletivo dos agentes, mais que resolver um problema em específico[3][4].

Os modelos baseados em indivíduos historicamente evoluíram a partir dos autômatos celulares. Ainda explorando um pouco sua história nos anos 1990 houve uma grande expansão nas ciências sociais, e um os primeiros modelos úteis de autômatos celulares foi proposto por um cientista social e reimplementado muitas vezes em modelos IBM. Há três ideias centrais nos IBMs: agentes, emergencia e complexidade.

  • Agentes são os objetos que interagem seguindo algumas regras, tipicamente estão situados no espaço e residem em uma rede ou uma vizinhança tipo grade. Em alguns casos, como na ecologia, os agentes podem ser considerados como inteligentes e/ou com propósitos.
  • Emergencia ocorre quando uma entidade observada possui propriedades que suas partes não possuem. Então esta propriedade emerge somente quando as partes que constituem esta entidade interagem entre si, de forma simples, é algo que não pode ser obtido apenas como uma soma de suas partes.
  • A complexidade caracteriza o comportamento de um modelo em que seus componentes interagem de múltiplas formas e seguem regras locais.

Modelos baseados em agente são então simulações baseadas em consequências globais de interações locais dos membros de uma população. Neste tipo de modelo as características de cada indivíduo é rastreada através do tempo, em contraste com técnicas que caracterizam a população baseado em uma média, como os modelos de campo médio.

Alguns modelos baseados em indivíduos podem ser especialmente explícitos, isto é, os indivíduos estão associados a uma localização em um espaço geométrico, neste caso também podem (mas não necessariamente) exibir mobilidade através do ambiente.

Lembrando do exemplo que escolhemos para exemplificar características dos autômatos celulares, pensando na questão da mobilidade, se lembrarmos dos conceitos de meta-população originalmente proposto no modelo de Levins, não há mobilidade. Cada meta-população vive em determinado fragmento, o que ocorre na colonização é que uma nova geração coloniza um nova célula, mas não se desloca para ela. Na proposta original, a meta-população não possui mobilidade, ainda que o fenômeno de colonização de uma nova célula e extinção local produza um efeito análogo. Os modelos espacialmente explícitos ainda podem ser contínuos (valores reais) ou discreto (valores inteiros, tipo grade). Este último é o que se aproxima do nosso exemplo. Além disso os modelos também não precisam ser espacialmente explícitos, como uma rede de computadores por exemplo, onde as conexões entre os agentes não precisam estar relacionados a nenhuma localização espacial.

Conforme pode-se perceber, há uma relação entre modelos baseados em indivíduos e autômatos celulares. Conforme discutido enquanto uma célula de um autômato celular assume um estado que basicamente informa se a célula está ocupado ou não por uma espécie, em um modelo baseado em indivíduos podemos ter mais indivíduos ocupando o mesmo fragmento do ambiente e variando a população local de uma mesma espécie em um mesmo fragmento. É claro que podemos adicionar mais estados finitos no autômato celular, ou ainda conforme discutido adaptar as regras estocásticas de transição, mas talvez a diferença mais significativa seja se o loop da simulação procede célula por célula, ou indivíduo por indivíduo.

Mas a verdade é que muitos modelos estão entre CAs e IBMs, em geral uma das principais distinções dos modelos é exatamente se os agentes se movem ou simplesmente parecem se mover porque série de células mudam de estado, a exemplo da discussão que realizamos sobre nosso modelo baseado em autômatos, onde há apenas este movimento aparente. Já em IBMs os agentes que são os objetos no mundo tem posição conhecida e podem efetivamente se mover carregando propriedades auxiliares com eles. Dessa forma uma das vantagens chaves dos IBMs é que o conhecimento interno do agente é mantido com a entidade quando ela se move, enquanto no CA o conhecimento associado não se move. Como os agentes carregam conhecimento consigo, ele pode utilizar o conhecimento e a história para explorar novas áreas e conhecer outros agentes.

Com o desenvolvimento da programação orientada a objetos (Object Orientated Programming - OOP) que de certa forma lembra os conceitos dos IBMs, se tornou razoavelmente mais simples de implementar este tipo de modelo.

Referências utilizadas
  1. Coupled maps (Kunihiko Kaneko e Tatsuo Yanagita, Scholarpedia)
  2. Encyclopedia of Complexity and Systems Science (Editor: Robert A. Meyers). Artigo: Agent Based Modeling andSimulation, Introduction to (Cilipo Castiglione, Conselho Nacional de Pesquisa da Itália)
  3. Discussão aberta no Research Gate
  4. Agent-based computing from multi-agent systems to agent-based models: a visual survey (Niazi Muaz e Amir Hussain, Scientometrics)

Principal material utilizado

  1. Agent Based Modelling: Introduction (Nick Malleson e Andy Evans ,Universidade de Leeds)
  2. Individual-Based Models (Craig Reynolds, Instituto Indiano de Ciências)
  3. Individual-Basd Models and Approaches on Ecology ( Editores: DonaldL. DeAngelis e Louis J. Gross). Artigo: From Local to Global: The Lesson of Cellular Automata (M.J.Phipps , Universidade de Ottawa)


Anterior: Simulação e modelo de campo médio | Índice: Ecologia | Próximo: Contexto ecológico