MBA: Caminhante aleatório

De Física Computacional
Revisão de 17h18min de 20 de julho de 2022 por Jhordan (discussão | contribs) (Criou página com '{{Ecologia| Por que usar e o que são modelos baseados em indivíduos |Contexto}} = Caminhante aleatório = O problema do caminhante aleatório pode ser definido da se...')
(dif) ← Edição anterior | Revisão atual (dif) | Versão posterior → (dif)
Ir para navegação Ir para pesquisar

Anterior: Por que usar e o que são modelos baseados em indivíduos | Índice: Ecologia | Próximo: Contexto

Caminhante aleatório

O problema do caminhante aleatório pode ser definido da seguinte forma: Um homem começa de um ponto Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\textstyle 0} e caminha 1 metro em uma linha reta, então ele vira um ângulo qualquer e anda outro Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\textstyle 1} metro em uma linha reta. Ele repete esse processo Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\textstyle n} vezes, qual é a probabilidade de após estes Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\textstyle N} passos que o homem esteja a uma distância entre Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\textstyle r} e Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\textstyle r+\delta r} da origem.

Inspirado por este problema, propõe-se uma situação bidimensional similar. A principal diferença constitui-se no fato de que o ângulo não é mais aleatório. Reescrevendo o problema, agora em cada um dos eixos, nos quais o homem se move de maneira independe, há uma probabilidade Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\textstyle p} de se mover Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\textstyle 1} metro em um sentido e uma probabilidade Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\textstyle q=1-p} de se mover no sentido contrário.

Trabalhando inicialmente apenas com uma dimensão, executando Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\textstyle N} passos, um caminho possível para o homem terminar a simulação em uma posição Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\textstyle m=n_1-n_2} tendo dado Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\textstyle n_1} passos à direita e Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\textstyle n_2} passos à esquerda, é dado por:

Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle p^{n_{1}}q^{n_{2}}=p^{\frac{N+m}{2}}q^{\frac{N-m}{2}}} Pois sendo Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\textstyle N=n_1+n_2} podemo escrever: Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle n_{1}=\frac{N+m}{2},\qquad n_{2}=\frac{N-m}{2}} Porém, está é a probabilidade de obtermos apenas um dos caminhos que leva o homem a Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\textstyle m} . O número total de caminhos indistinguíveis com Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\textstyle n_1} passos à direita e Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\textstyle n_2} passos a esquerda é dado por: Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{N!}{n_{1}!n_{2}!}=\frac{N!}{n_{1}!\left(N-n_{1}\right)!}=\frac{N!}{\left(\frac{N+m}{2}\right)!\left(\frac{N-m}{2}\right)!}} Temos então que a probabilidade estar na posição Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\textstyle m} após Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\textstyle N} passos é dado por: Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle p\left(m,N\right)=\frac{N!}{\left(\frac{N+m}{2}\right)!\left(\frac{N-m}{2}\right)!}p^{\frac{N+m}{2}}q^{\frac{N-m}{2}}} Ou reescrevendo Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\textstyle n_{1}=n} para facilitar, e lembrando que Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\textstyle n_{1}=\frac{N+m}{2}} e Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\textstyle N=n_{1}+n_{2}} : Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle p\left(n\right)=\frac{N!}{n!\left(N-n\right)!}p^{n}q^{N-n}=\left(\begin{array}{c} N\\ n \end{array}\right)p^{n}q^{N-n}} Onde Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\textstyle \left(\begin{array}{c}N\\n \end{array}\right)=C_{n}^{N}} também é chamado de combinatória. Utilizando o binômio de Newton: Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left(x+y\right)^{n}=\sum_{k=0}^{n}\left(\begin{array}{c} n\\ k \end{array}\right)x^{n-k}y^{k}} Temos a normalização: Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{n=0}^{n}p\left(n\right)=\sum_{n=0}^{n}\left(\begin{array}{c} N\\ n \end{array}\right)q^{N-n}p^{n}=\left(p+q\right)^{N}=1} Uma vez que Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\textstyle p+q=1} . E lembrando que Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\textstyle p\left(n\right)} é a probabilidade de estar em Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\textstyle m=2n-N} , ou seja de obtermos Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\textstyle n} vezes passo a direita em Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\textstyle N} passos no total, então o valor médio de Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\textstyle n} pode ser dado por: Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left\langle n\right\rangle =\sum_{n=0}^{N}np\left(n\right)} Derivando o binômio de Newton: Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{array}{c} p\frac{d}{dp}\left(p+q\right)^{N}=pN\left(p+q\right)^{N-1}=pN\end{array}} E também: Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} p\frac{d}{dp}\left(p+q\right)^{N} & =p\frac{d}{dp}\left[\sum_{n=0}^{n}\left(\begin{array}{c} N\\ n \end{array}\right)q^{N-n}p^{n}\right]\\ & =p\sum_{n=0}^{n}n\left(\begin{array}{c} N\\ n \end{array}\right)q^{N-n}p^{n-1}\\ & =\sum_{n=0}^{n}n\left(\begin{array}{c} N\\ n \end{array}\right)q^{N-n}p^{n}\\ & =\sum_{n=0}^{n}np\left(n\right)\end{align}} Então: Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle pN=\sum_{n=0}^{n}np\left(n\right)=\left\langle n\right\rangle} E com isso podemos obter a posição final média Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\textstyle \left\langle m\right\rangle} . Utilizando a notação anterior posição final exata é Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\textstyle m=n_1-n_2} , ou ainda podemos rescrever como Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\textstyle m=2n-N} , pois: Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle n_{1}-n_{2}=n_{1}-\left(N-n_{1}\right)=2n_{1}-N} A partir destes resultados podemos obter: Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} \left\langle m\right\rangle & =\sum_{n=0}^{N}mp\left(n\right)\\ & =\sum_{n=0}^{N}\left(2n-N\right)p\left(n\right)\\ & =2\sum_{n=0}^{N}np\left(n\right)-\sum_{n=0}^{N}Np\left(n\right)\\ & =2\left\langle n\right\rangle -N\sum_{n=0}^{N}p\left(n\right)\\ & =2\left\langle n\right\rangle -N\end{align}} A princípio, não temos motivos para dar preferência para o movimento em nenhuma direção, logo é razoável utilizar Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\textstyle p=q=1/2} , o que resulta em Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\textstyle \left\langle n\right\rangle=N/2} consequentemente Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\textstyle \left\langle m\right\rangle=0} . O que pode parecer contra-intuitivo para nosso modelo, mas além de distribuirmos animais por todo o espaço, o que resultado implica é a posição final média, mas é preciso entender que não impede que ao longo da simulação cada indivíduo percorra diferentes áreas do espaço.


Distribuição Gaussiana

Quando Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\textstyle N\rightarrow\infty} tendo Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\textstyle p \not\approx 1} temos a distribuição Gaussiana:


Foi realizada uma simulação utilizando Python e o módulo Mesa, grande parte do código segue a mesma discussão feita anteriormente no Jogo da Vida. A figura ilustra uma simulação com 10.000 caminhantes aleatórios em uma grade 100 X 100, iniciando na posição P=(50,50).

Resultado da simulação com a distribuição gaussiana sobreposta para N=100 para ambas as coordenadas.


Código

#Bibliotecas necessárias
from mesa import Agent, Model                                      #Classes Agente e Modelo
from mesa.time import SimultaneousActivation                       #Agendador simultâneo
from mesa.space import MultiGrid                                   #Malha multigrid
import random                                                      #Número aleatórios

#AGENTE---------------------------------------------------------------------------------
class Agente(Agent):
    """Classe do agente"""
    def __init__(self,modelo):
      """Bibliotecas necessárias"""
      #modelo     - Modelo que ao qual o agente pertence
      super().__init__(self,modelo)             #Necessário para funcionar o modelo
      self.ppos=(0,0)
      
    def step(self):
      """Método obrigatório que prepara as mudanças"""
      dx = (+1) if (random.random()<0.5) else(-1)
      dy = (+1) if (random.random()<0.5) else (-1)
      self.ppos = (self.pos[0]+dx,self.pos[1]+dy)                                 #Próxima posição
          
    def advance(self):
        """Método obrigatório que aplica as mudanças"""
        self.model.grid.move_agent(self, self.ppos)

#MODELO
class Modelo(Model):
    """Modelo geral"""

    def __init__(self, modelo,N,seed=None):
        """Função chamada quando o modelo é inicializazdo"""
        # Modelo   - Dicionário com especificações do modelo
        # N        - Quantiade de caminhantes
        # seed     - Seed dos números aleatórios do modelo do mesa
        
        largura = modelo["Largura"];altura=modelo["Altura"];seed_random=modelo["Seed"]
        random.seed(seed_random)                                 #Seed dos números aleatórios
        self.grid     = MultiGrid(largura, altura, True)         #Configura a grade
        self.schedule = SimultaneousActivation(self)             #Configura o agendador
        self.running  = True                                     #Condiçao para seguir executando o modelo
        for n in range(N):
          a = Agente(self)
          self.schedule.add(a)
          X= 50
          Y= 50
          self.grid.place_agent(a, (X, Y))
            
    def step(self):
        """Avançar um passo do modelo"""
        self.schedule.step()                              #Avançamos os agentes


MAX =100
N=10000
modelo  = {"Largura":100   ,"Altura":100       ,"Seed":0} 
M = Modelo(modelo,N)
for i in range(MAX):
    M.step()
    if ((i+1)%(MAX/100)==0):
      print(str(100*(1+i)/MAX)+"%")

E o gráfico foi gerado utilizando: 

import numpy as np
import matplotlib.pyplot as plt


x=[];y=[]
for a in M.schedule.agents:
  x.append(a.pos[0])
  y.append(a.pos[1])

a,b,c=plt.hist(x, 70, density=True, facecolor='g', alpha=0.75)
m=1
K=100
X=np.arange(0,100, 0.1)
sigma = 2*np.pi*K*0.5*0.5
plt.plot(X,np.exp(-((X-K*0.5)**2)/sigma)/(np.sqrt(sigma)))

Acima fazendos um histograma das posições em x, uma alteração simples permite visualizarmos o equivalente em y.

Principais materiais utilizados:


Anterior: Por que usar e o que são modelos baseados em indivíduos | Índice: Ecologia | Próximo: Contexto

Disponível em “http://fiscomp.if.ufrgs.br/index.php?title=MBA:_Caminhante_aleatório&oldid=7850”