Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Como implementar o modelo baseado em agentes Diffusion-Limited Aggregation (DLA) em Python?

+1 voto
21 visitas
perguntada Jul 12 em Ciência da Computação por Daniel Castro (46 pontos)  

Aula 22, Exercício 1. Considere os modelos baseados em agentes apresentados no capítulo 3 do livro "An Introduction to Agent-Based Modeling: Modeling Natural, Social, and Engineered Complex Systems with NetLogo - Wilensky, Uri; Rand, William (2015)". Implemente em Python, possivelmente usando a biblioteca Mesa. Explique/Descreva o modelo, explique cuidadosamente o código que você desenvolveu em Python, replique todas as tabelas e figuras apresentadas para cada um dos modelos apresentados.
d) (*) DLA model

Compartilhe

1 Resposta

+1 voto
respondida Jul 12 por Daniel Castro (46 pontos)  
editado Jul 12 por Daniel Castro

Obs: O módulo Mesa do Python apresenta diversos exemplos de ABMs (Agent-based Models) implementados com ele, inclusive o Fire Model e o Segregation Model . O Fire Model, inclusive, é baseado em Wilensky e Rand (1997). Por isso, optei por implementar o El Farol e o DLA, que não são apresentados como exemplo do Mesa.

Código do NetLogo
Como o próprio livro menciona, o código do modelo está disponível no NetLogo (o software deve ser baixado a partir da Web e instalado localmente) Sample Models > IABM > Textbook > Chapter Three > DLA Extensions. A sintaxe do NetLogo é bem específica, mas, mesmo não sabendo programar na linguagem, é possível entender a lógica dos comandos. De maneira geral, o NetLogo é bastante simples, permitindo controlar diversos aspectos da simulação, dos agentes e da exibição de maneira relativamente simples. Entretanto, por ser uma linguagem específica, não permite utilizar recursos presentes em linguagens de uso mais geral, como os diversos módulos do Python.

O modelo implementado em NetLogo começa por criar as sementes verdes e as partículas vermelhas no método setup:

A imagem será apresentada aqui.

A função go executa as iterações ou passos do modelo. Cada partícula vermelha é girada aleatoriamente para a direita e depois para a esquerda por determinado ângulo e então anda uma célula. Se tocar uma partícula verde, a partícula se torna verde e gruda na agregação. O ângulo com que a partícula gira não parece influenciar o resultado da simulação.

A imagem será apresentada aqui.

O resultado da simulação é o seguinte:

A imagem será apresentada aqui.

Extensões

A primeira extensão modifica o modelo para que, se tocar uma partícula verde, a partícula vermelha grudar nela (e também se torna verde) com determinada probabilidade. Quanto maior a probabilidade, mais rápido a agregação cresce.

A imagem será apresentada aqui.

O resultado da simulação é o seguinte:

A imagem será apresentada aqui.

A segunda extensão permite que a probabilidade de grudar possa ser influenciada pelo número de vizinhos verdes da posição da partícula. Quanto maior o número de vizinhos verdes, maior a probabilidade de grudar.

A imagem será apresentada aqui.

O resultado da simulação é o seguinte:

A imagem será apresentada aqui.

Notem que, com a consideração do número de vizinhos verdes, a agregação torna-se mais densa.

Por fim, a terceira extensão permite que mais de uma semente sejam criadas:

A imagem será apresentada aqui.

Com 3 sementes, o resultado é apresentado abaixo:

A imagem será apresentada aqui.

Código Python com Mesa
O Mesa disponibiliza uma série de classes para implementação do modelo, dos agentes e da visualização. Orientada a objetos, a biblioteca permite uma implementação mais elegante e direta dos modelos orientados a objetos. A documentação da biblioteca é satisfatória, mas foi necessário consultar o código do módulo (disponível no GitHub) para verificar diversos aspectos de seu funcionamento.

A estrutura de arquivos não é rígida, mas a documentação e os exemplos sugerem um arquivo model.py em que está a classe que implementa o modelo propriamente dito, responsável pela criação e pelas definições das interações entre os agentes, e as classes que definem os próprios agentes (a definição dos agentes opcionalmente pode ser feita em um arquivo agents.py, mas optei por colocar essas definições no model.py mesmo, já que existe apenas um tipo de agente). O arquivo server.py contém as definições para visualização do modelo na Web. Ou seja, não há um aplicativo stand-alone como no NetLogo. Por fim, o arquivo run.py chama o servidor web ou, como optei por fazer, executa o modelo sem visualização gráfica, ou seja, permite apenas as inspeção das variáveis coletadas ao longo da simulação. Essa forma de execução foi útil para depuração do programa.

O código do arquivo model.py começa por definir a classe Particle, que herda da classe Agent do Mesa, com atributos cor, direção, posição e ângulo. Direção e ângulo são atributos necessários para movimentar as partículas de maneira similar ao modelo do NetLogo, que, nesse ponto, apresenta um código mais simples e direto para movimentar os agentes.


import math
import random
from mesa import Agent, Model
from mesa.time import BaseScheduler
from mesa.space import SingleGrid GREENCOLOR = 0 # agentes verdes são parados
RED
COLOR = 1 # agentes vermelhos se movem class Particle(Agent):
"""
Uma partícula que, se verde não se move e, se vermelha, se move
aleatoriamente até tocar uma partícula verde e parar de se mover.
Partículas vermelhas são exibidas como setas vermelhas no arquivo
server.py, direcionadas de acordo com o atributo heading. Uma possibilidade seria implementar duas classes de agentes, uma para os vermelhos e uma para os verdes, já que para os verdes importa apenas os atributos color e pos. """ def __init__(self, unique_id, model, color, heading, pos): super().__init__(unique_id, model) self.color = color # pode ser vermelho ou verde self.heading = heading # direção da seta self.pos = pos # posição do agente self.angle = 0 # ângulo para o qual a partícula vermelha está direcionada

Uma alternativa seria criar duas classes, uma para as sementes (partículas verdes que não se movem) e uma para as partículas vermelhas que se movem, já que os atributos relacionados à movimentação só são relevantes para as partículas vermelhas.

Os métodos setangle, setheading e determinenewposition são métodos necessários para implementar um comportamento similar ao do modelo do NetLogo com o Mesa. No NetLogo basta setar a direção e mover os agentes, mas no Mesa parece que os agentes só têm posição e, assim, para simular comportamento direcional, é necessário implementar código.


def set_angle(self):
"""
Determina o ângulo para o qual a partícula vermelha está direcionada,
com base no heading.
Os valores de heading poderiam ser constantes em uma evolução do código.
"""
if (self.heading == (1, 0)): # direita -> angulo 0
self.angle = 0
elif (self.heading == (0, 1)): # cima -> angulo 90
self.angle = 90
elif (self.heading == (-1, 0)): # esquerda -> angulo 180
self.angle = 180
elif (self.heading == (0, -1)): # baixo -> angulo 270
self.angle = 270 def set_heading(self): """ Determina o heading para o qual a partícula vermelha está direcionada, com base no ângulo. Os valores de heading poderiam ser constantes em próxima versão do código. """ if (self.angle >= 315 or self.angle < 45): self.heading = (1, 0) # direita elif (self.angle >= 45 and self.angle < 135): self.heading = (0, 1) # cima elif (self.angle >= 135 and self.angle < 225): self.heading = (-1, 0) # esquerda elif (self.angle >= 225 and self.angle < 315): self.heading = (0, -1) # baixo def determine_new_position(self): """ Determina para qual vizinho a partícula vermelha se moverá, com base no ângulo para o qual está direcionada. """ if (self.angle >= 338 or self.angle < 23): new_position = (self.pos[0] + 1, self.pos[1]) # leste elif (self.angle >= 23 and self.angle < 68): new_position = (self.pos[0] + 1, self.pos[1] + 1) # nordeste elif (self.angle >= 68 and self.angle < 113): new_position = (self.pos[0], self.pos[1] + 1) # norte elif (self.angle >= 113 and self.angle < 158): new_position = (self.pos[0] - 1, self.pos[1] + 1) # noroeste elif (self.angle >= 158 and self.angle < 203): new_position = (self.pos[0] - 1, self.pos[1]) # oeste elif (self.angle >= 203 and self.angle < 248): new_position = (self.pos[0] - 1, self.pos[1] - 1) # sudoeste elif (self.angle >= 248 and self.angle < 293): new_position = (self.pos[0], self.pos[1] - 1) # sul elif (self.angle >= 293 and self.angle < 338): new_position = (self.pos[0] + 1, self.pos[1] - 1) # sudeste " verifica se a posição é válida, já que as coordenadas podem ser " " passado do limite do grid para mais ou para menos" if (new_position[0] >= self.model.grid.width): new_position = (0, new_position[1]) if (new_position[0] < 0): new_position = (self.model.grid.width - 1, new_position[1]) if (new_position[1] >= self.model.grid.height): new_position = (new_position[0], 0) if (new_position[1] < 0): new_position = (new_position[0], self.model.grid.height - 1) return new_position

O método move determina uma direção aleatória para a partícula e, se o vizinho escolhido estiver vazio, move o agente para a posição determinada. Caso contrário, apenas muda a direção da partícula, sem movê-la.


def move(self):
"""
Desloca uma partícula vermelha aleatoriamente, primeiro direcionando-a
aleatoriamente para a direita e depois para a esqueda. Com base na
direção, vai a para o vizinho apropriado, se estiver vazio. Se o
vizinho estiver ocupado, não se move, mas muda a direção.
"""
right = random.randrange(0, self.model.wiggleangle)
left = random.randrange(0, self.model.wiggle
angle)
self.set_angle()
self.angle -= right
self.angle +- left
if self.angle < 0:
self.angle += 360 new_position = self.determine_new_position() " verifica se o vizinho apropriado está vazio antes de mover" " se o vizinho estiver ocupado, não se move" if (self.model.grid.is_cell_empty(new_position)): self.model.grid.move_agent(self, new_position) self.pos = new_position self.set_heading()

Uma alternativa seria escolher aleatoriamente, entre os oito vizinhos da partícula, uma que esteja vazia. O efeito é igual ao do modelo do NetLogo e bem mais simples que a opção implementada acima. Pode ser visto no repositório do GitHub, diretório aula22_1b.

O método step, após movimentar as partículas vermelhas, muda sua cor para verde se ela tocar em outra partícula verde, de acordo com a probabilidade de grudar, pré-definida ou influenciada pelo número de vizinhos verdes.


def step(self):
"""
Passo da extensão 2. Desloca as partículas apenas se forem vermelhas.
Dependendo da probabilidade de grudar, a partícula muda para o tipo
verde, se ela tiver tocado em outra partícula verde.
""" if self.color == RED_COLOR: self.move() "recupera a lista de vizinhos verdes da partícula, já na nova" "posição" green_neighbors = [neighbor for neighbor in self.model.grid.iter_neighbors(self.pos, moore = True) if neighbor.color == GREEN_COLOR] number_green_neighbors = len(green_neighbors) "oito vizinhos no total, contando com as diagonais" total_number_neighbors = 8 if self.model.neighbor_influence: "Comentário de Wilensky e Rand (2015):" "if neighbor-influence is TRUE then make the probability" "proportionate to the number of green neighbors, otherwise" "use the slider as before" "increase the probability of sticking the more green neighbors" "there are" local_prob = self.model.probability_of_sticking * \ number_green_neighbors/total_number_neighbors else: local_prob = self.model.probability_of_sticking if number_green_neighbors > 0: "se algum dos vizinhos da nova posição, muda de cor com a" "probabilidade calculada acima" random_number = random.uniform(0, 1) if (random_number < local_prob): self.color = GREEN_COLOR

O método steporiginalandextension1 implementa o passo dado pelo agente, sem levar em conta probabilidade local, ou seja, influencida pelo número de vizinhos verdes. Ou seja, corresponde ao modelo original e à extensão 1. Pode ser visto no repositório do GitHub, diretório aula221b.

A classe DLAModel herda da classe Model do Mesa, recebe uma série de parâmetros e define as variáveis do modelo, sendo o agendador e o grid as mais importantes. O agendador define como o modelo se comportará temporalmente e o grid define como o modelo se comportará espacialmente. No caso, optei pelo BaseScheduler, que simplesmente chama o método step dos agentes de forma sequencial. O grid é o SingleGrid, que só permite um agente por célula, mas requer tratamento para que não haja sobreposição.


class DLAModel(Model):
"""
Modelo DLA como implementado no NetLogo.
"""
def init(self, wiggleangle, numberparticles, probabilityofsticking,
neighborinfluence, numseeds):
self.running = True # necessário para que o modelo seja chamado pelo servidor web
self.wiggleangle = wiggleangle
self.numberparticles = numberparticles
" indica com que probabilidade uma partícula vermelha se torna verde "
" e pára ao tocar uma partícula verde"
self.probabilityofsticking = probabilityofsticking
"indica se o número de vizinhos verdes influencia a probabilidade de"
"grudar"
self.neighborinfluence = neighborinfluence
if numseeds <= 0: # número de sementes deve ser positivo
raise ValueError("Number of seeds should be greater than zero.")
self.num
seeds = num_seeds
"direções das particulas"
"(1,0) direita; (0, 1) cima; (-1, 0) esquerda (0, -1) baixo"
self.headings = ((1, 0), (0, 1), (-1, 0), (0, -1))
self.schedule = BaseScheduler(self) "tamanho do grid definido em função do número de partículas, como na" "visualização; pode ser um valor comum aos dois" width = height = round(2 * round(math.sqrt(number_particles))) "apenas um agente por célula" self.grid = SingleGrid(width, height, True)

Após as definições iniciais, são criadas as sementes. Se houver apenas uma, ela é posicionada no centro do grid (comportamento que não exite na terceira extensão do modelo do NetLogo, apenas no modelo original e nas duas primeiras extensões). Se houver mais de uma semente, elas são posicionadas de forma aleatória. Depois são criadas as partículas vermelhas, posicionadas também de forma aleatória. Por fim, o método step do modelo apenas chama os passos dos agentes (em imagem porque o limite dos 20k caracteres foi ultrapassado):

A imagem será apresentada aqui.

O arquivo server.py, por sua vez, define como exibir a simulação de forma dinâmica através de elementos gráficos em um arquivo HTML. A função agent_portrayal (notem que não é um método, já que não está associado a nenhuma classe) define como exibir os agentes. As partículas verdes são quadrados e as partículas vermelhas são setas, direcionadas de acordo com o que foi definido no modelo, de forma aleatória:

A imagem será apresentada aqui.

No corpo do arquivo, os objetos correspondentes aos diversos elementos a exibir são criados. No caso, apenas o grid. Há ainda a definição dos parâmetros que o usuário pode selecionar. Logo depois, o servidor que alimentará a página HTML no browser é criado com o modelo, os elementos a exibir, o nome a exibir e os parâmetros a passar para o modelo.

A imagem será apresentada aqui.

Por fim, o servidor é inicializados. Em alguns exemplos, essa linha de código está no arquivo run.py, mas optei por deixar aqui para que o arquivo run.py possa executar o modelo sem associação à exibição gráfica da simulação. Há também classes do Mesa que permitem que o modelo seja assim executado não apenas uma vez, mas várias vezes, variando os parâmetros do modelo e permitindo verificar o comportamento do modelo em função dos parâmetros. Entretanto, como o modelo do NetLogo é apenas visual, não implementei essas chamadas automáticas. Pode ser visto no repositório do GitHub, diretório aula22_1b.

A figura abaixo apresenta como o modelo é exibido no browser:

A imagem será apresentada aqui.

Os parâmetros à esquerda podem ser setados como desejado. O parâmetro superior é default do Mesa e define a velocidade com que a exibição do modelo é atualizada. Clicando no link Start, o modelo começa a ser executado. A figura abaixo apresenta o estado do modelo após diversos passos, com apenas uma semente e probabilidade de grudar igual a 1:

A imagem será apresentada aqui.

Clicando no link Stop, a simulação é interrompida. O link Step, por sua vez, executa uma iteração do modelo.

A figura abaixo apresenta o estado considerando a presença dos vizinhos verdes para determinar a probabilidade de grudar. Notem que a agregação fica mais densa de fato:

A imagem será apresentada aqui.

Sem considerar os vizinhos verdes, a agregação é mais dispersa:

A imagem será apresentada aqui.

Resultado com 4 sementes e probabilidade de grudar 0.5. Uma probabilidade de grudar menor apenas faz com que a agregação cresça mais devagar.

A imagem será apresentada aqui.

Resultado com 10 sementes, algumas já conurbadas:

A imagem será apresentada aqui.

O código do modelo está disponível nesse repositório do GitHub, no diretório aula22_1b.

comentou Jul 13 por Pedro Duque (51 pontos)  
editado Jul 13 por Pedro Duque
Ótimo, Daniel! Muito interessante esse modelo, consegui rodá-lo perfeitamente no Python! No início me confundi um pouco por não saber que o módulo Mesa deveria ser baixado externamente, mas depois consegui!!!

Seria bacana também tentar aplicar o DLA no Python sem o módulo Mesa, definindo uma matriz com números indicando partículas verdes e vermelhas geradas aleatoriamente para construir a imagem e regras de interação para definir o movimento das partículas vermelhas e a agregação delas nas verdes (semelhante a resposta do Fire Model desse semestre). Por mais trabalhoso que pareça, acredito que assim seja possível incluir mais facilmente extensões do modelo (como saltos ou viés no movimento, por exemplo) que provavelmente o módulo Mesa não permita com tanta facilidade!
...