SER 301 – Análise Espacial de Dados Geográficos
Introdução à Modelagem
e Simulação Computacional
Flávia F. Feitosa
[email protected]
Altamira
Vila Canopus
Altamira
Uruará
Vila Caboclo
Pontalina
Vila dos Crentes
Vila Central
Primavera
Rede
Rede
Hidrográfica
Porto Estrela
São Félix
Taboca
Estradas
Pistas
de
pouso
Tancredo Neves
Belém
Araguaína
Nereu
Sudoeste
Carapanã
Canopus
Sudoeste
Redenção
Taboca
Minerasul
Tucumã
Vila
Central
Ladeira Vermelha
São
Félix do
Xingu
Tucumã
e
Ourilândia
Metrópole
Cidades
>50.000 hab
Cidades
<50.000 hab
Setores
Urbanos
Localidades
Modelos
Yi = 0 + Xi 1
Representações simplificadas de um objeto, estrutura, ideia ou
sistema. Estas representações atendem a algum propósito!!!
São menores, menos detalhados, menos complexos, ou tudo isso junto…
Podem ser estáticos ou dinâmicos…
Um mapa é um modelo?
Representação simplificada de um estado do sistema
de interesse.
Mas é estático! E os processos?
Em busca de uma “Cartografia de Processos”…
Modelos de Simulação
(Computacional)
Inclui a representação de determinados
processos/comportamentos do sistema de interesse
Propósito de compreender melhor o comportamento
do sistema ao longo do tempo, explicar padrões que
observamos na realidade, dinâmicas não-lineares,
retroalimentação do sistema…
Como comportamentos individuais geram
padrões “macro” no nosso mundo...
Um exemplo simples de simulação…
Bird Flocking
o Modelo baseado em
interações “bottom-up”
o Nenhuma autoridade
central
o Cada pássaro reage ao
seu vizinho
Bird Flocking
Reynolds Model (1987) – Três regras
Coesão: movimento em direção à
posição média dos
vizinhos/colegas.
Separação: movimento buscando
evitar aglomeração com outros
colegas
Alinhamento: manutenção da
direção média dos vizinhos.
www.red3d.com/cwr/boids/
Bird Flocking
Reynolds Model (1987)
http://ccl.northwestern.edu/netlogo/models/Flocking
Complex Systems
Systems composed of interconnected parts that as a
whole exhibit one or more properties not obvious from
the properties of the individual parts.
“A Complex System is an entity, coherent in
some recognizabe way but whose elements,
interactions and dynamics generate
structures and admit surprise and novelty
that cannot be defined a priori”
(Batty and Torrens, 2005: 745)
Complex Systems
Complicated vs. Complex
Emergence
Small number of rules applied locally among many
individuals can generate complex global patterns
Self-organization
No centralized authority
Complex Systems
Non-linearity
Generate unexpected and counter-intuitive global
patterns that cannot be understood as a simple sum
of the parts. Invalidates simple extrapolation.
Path-dependence
Highly affected by past states
Adaptation
Adapt to unexpected changes in its environment (e.g.
avoiding obstacles)
What are complex adaptive systems?
Traditional Modelling Approaches
Statistical modeling, Classical optimization,
System dynamics modeling…
o Top-down view
o Linear
o Correlation
o Cause and effect reasoning
o Often assume homogeneity
o Some are static
o Seeks to find some equilibrium representing the
“solution” to the problem
Simulation models  Are “run” rather than “solved”
Autômatos Celulares
o Objetos Computacionais, geralmente chamados de
“células”
o Situados no tempo e espaço
o Caracterizados por “estados”
o Os processos para a mudança de estado de cada célula são
geralmente articulados como regras simples, chamadas de
“regras de transição”.
Nos modelos mais clássicos,
como no “Jogo da Vida” de
Conway, o estado de cada
célula muda em função do
estado das células vizinhas
Autômatos Celulares
Objetos “fixos” no espaço!
Mudanças de Estado não envolvem movimentos.
Já a noção de AGENTES introduz a ideia
de objetos móveis, e um pouco mais…
Agent-Based Modelling
Another Alternative to traditional modeling paradigms
What is an Agent?
o
o
o
o
Independent component (e.g. software object)
Do not have fixed location
Have a state and behavioral rules
Behavioral rules determine movements, interactions and
changes in the agent’s state
o The behavior can range from primitive reactive decision
rules to complex adaptive intelligence.
o They may represent a real world actor (family,
government, …)
Agent-Based Modelling
AGENTS
o Capability to make independent decisions
o They are usually unique, i.e., different from each other in
such characteristics as size, location, resource reserves,
and history
o Act and interact with one another as well as the
environment in which they exist according to some
purpose.
A
L
The simplest agent-based model structure
Agent-Based Modelling
Representations
Goal
Communication
Communication
Action
Perception
Environment
Gilbert, 2003
Agent-Based Modelling
Isento da limitação da tratabilidade matemática.
Ao invés de descrever um sistema apenas com
variáveis que representam o estado do sistema
como um todo, modelamos seus componentes
individualmente
Agent-Based Modelling
Útil para a representação de sistemas compostos
por agentes autônomos, que interagem entre
si e com o ambiente, diferem um do outro no
espaço e tempo e apresentam
comportamentos que são importantes para
como o sistema funciona.
Trata múltiplos níveis de um problema: do local
ao global, do individual ao coletivo
EXEMPLOS???
Agents are…
Identifiable and self-contained
Autonomous
– Exercises control over its own actions
Reactive
– Responds to changes in its environment
Goal-oriented
– Does not simply act in response to the environment
Mobile
– Able to transport themselves
Agents are…
Situated
– Living in an environment with which interacts with other
agents
Communicative/Socially aware
– Communicates with other agents
Adaptive / Learning /Flexible
– Changes its behavior based on its previous experience
– Actions are not scripted
Temporally continuous
– Continuously running process
Types of ABM
Minimalist Models
o
o
o
o
Based on a set of idealized assumptions
Abstract and artificial
Exploratory laboratories in which assumptions can be tested
Ex: Schelling, Sugarscape Model
Decision Support Models
o
o
o
o
Descriptive and realistic
Usually large-scale applications
Designed to answer policy questions
Include real data to calibrate and to compare simulation
outputs
o Ex: MASUS (Multi-Agent Simulator for Urban Segregation)
(Macal e North, 2005)
A Minimalist Model
Schelling’s Model of Segregation
Segregation is an outcome of individual choices
But high levels of segregation mean that people are prejudiced?
Schelling’s Model of Segregation
Schelling (1971) demonstrates a theory to explain
the persistence of racial segregation in an
environment of growing tolerance
If individuals will tolerate racial diversity, but will
not tolerate being in a minority in their locality,
segregation will still be the equilibrium
situation
Schelling’s Model of Segregation
Micro-level rules of the game
Stay if at least a
third of neighbors
are “kin”
< 1/3
Move to random
location otherwise
Schelling’s Model of Segregation
Tolerance values above 30%: formation of ghettos
http://ccl.northwestern.edu/netlogo/models/Segregation
O Ciclo da Modelagem
O Ciclo da Modelagem
Definir o propósito do modelo, as
questões que buscamos
responder
O Ciclo da Modelagem
Segregação é um resultado da
intolerância das famílias em
relação à presença de outros
grupos sociais?
O Ciclo da Modelagem
Segregação é um resultado da intolerância das famílias em
relação à presença de outros grupos sociais?
Todo modelo é uma representação simplificada
que serve a um propósito.
A simplificação é importante para que se construa
uma compreensão gradual do problema.
O propósito, que pode ser traduzido através de
uma pergunta, serve como um filtro para que
se decida o que incluir/ignorar em um modelo.
O Ciclo da Modelagem
Formular
hipóteses/premissas a
partir de nosso
conhecimento
preliminar sobre como
o sistema funciona
(Teorias)
O Ciclo da Modelagem
Se as famílias toleram a diversidade
racial, mas não toleram ser a
minoria em sua vizinhança, a
situação de equilíbrio ainda
apresentará altos níveis de
segregação.
O Ciclo da Modelagem
Quais fatores tem forte influência sobre o
fenômeno de interesse?
Estes fatores são independentes ou interagem
entre si?
São afetados por outros fatores importantes?
Momento de combinar conhecimentos, uma fase de
“brainstorming”
Gráficos, Diagramas, etc. são bem vindos!!!
Formulação do Modelo
Comunicar o modelo nas suas diversas fases é
importante!
Leva a novas discussões e reformulação do modelo
MODELO COMO UM
OBJETO MEDIADOR
Supressão do modelo como ‘produto’
Foco no PROCESSO DE CONSTRUÇÃO do modelo
Modelo de Simulação Computacional = Laboratório
1.Processo de construção deste laboratório (contínuo)
2.Design, uso e interpretação dos experimentos
O Ciclo da Modelagem
Quais elementos/interações a
serem considerados? Como
serão representados?
Autômatos? Agentes?
Escolher escalas, entidades,
variáveis, processos e
parâmetros do modelo
Formulação do Modelo
É hora de pensar nos detalhes do modelo
o Ideias representadas em palavras,
diagramas deverão ser traduzidas em
algoritmos, equações, etc.
o A formulação serve, inicialmente, para que
possamos pensar explicitamente sobre
todas as partes do modelo, identificar todas
as decisões que precisamos tomar.
O Ciclo da Modelagem
O Ciclo da Modelagem
A implementação permite-nos explorar, de maneira
lógica e rigorosa, as consequências de nossas
premissas.
Implementar um modelo não é difícil,
mas fazer ciência com ele sim!!!
Plataformas
TerraME (INPE/UFOP)
http://www.terrame.org
NetLogo
Northwestern's Center for Connected Learning and Computer-Based Modeling
http://ccl.northwestern.edu/netlogo/
Repast (University of Chicago)
http://repast.sourceforge.net/
Elementos do NetLogo
Turtles: Agentes. Podem ser diferenciados em diferentes
tipos (breeds)
Patches: Células regulares que representam o espaço
Links: Conectam agentes (turtles) e permitem representar
relações em rede.
Observer: Pode ser entendido como um controlador do
modelo e suas visualizações. Por exemplo, é o
observador que “cria” agentes e gerencia variáveis
globais.
O Ciclo da Modelagem
Verificação, Comparação com
Dados Reais, Simulação de
Cenários, Análises de
Sensibilidade
Lembrete Importante!
MODELOS NÃO SÃO BOLAS DE CRISTAL !!!!
“We may need to consider abandoning the
dream of long-term prediction”
Helen Couclelis, CAMUSS 2012
Modelos capturam apenas o que é
PADRÃO, ou seja, o que é típico, estável,
regular, recorrente, repetitivo,
PREVISÍVEL.
Futuro é uma mistura entre “padrão” e “ruído”
Duas sugestões de leitura sobre o assunto:
oBatty, M; Torrens, P (2005) Modelling and Prediction in a Complex World.
Futures, v.37, n.7, p.745-766.
oCouclelis, H. (2005) "Where has the future gone?" Rethinking the role of
integrated land-use models in spatial planning. Environment and Planning A,
v. 37, p. 1353-1371.
O Ciclo da Modelagem
O Ciclo da Modelagem
É um processo iterativo!!!
Nossos modelos podem ser sempre melhorados de
alguma forma:
-São muito simples ou muito complexos
-Podemos nos dar conta de que estamos fazendo as
perguntas erradas…
-O ciclo não precisa ser seguido inteiramente de
maneira contínua, “loops” menores são desejáveis
Protocolo ODD
(Overview, Design, Details)
Estrutura útil na formulação, descrição e comunicação dos modelos
Elements of the ODD Protocol
Grimm, V., Berger, U.,
Bastiansen, F., Eliassen, S.,
Ginot, V., Giske, J., John,
G.-C., Grand, T., Heinz, S.
K., Huse, G., Huth, A.,
Jepsen, J. U. & al., E. (2006)
A standard protocol for
describing individual-based
and agent-based models.
Ecological Modelling 198:
115-126.
Grimm, V., Berger, U.,
DeAngelis, D. L., Polhill, J.
G., Giske, J. & Railsback, S.
F. (2010) The ODD
protocol: a review and first
update. Ecological
Modelling 221: 2760-2768.
1. Overview
Propósito
o Que sistema estamos modelando?
o O que estamos querendo aprender com isso?
Entidades, Variáveis e Escalas
o Tipos de entidades: um ou mais tipos de agentes,
o ambiente onde agentes vivem e interagem
(geralmente composto por unidades locais –
células), ambiente “global”.
o Variáveis que caracterizam cada uma dessas
entidades (estáticas ou dinâmicas)
1. Overview
Entidades, Variáveis e Escalas
o Escala temporal: resolução e extensão temporal
o Escala espacial: resolução espacial
Process Overview and Schedule
o Estrutura dinâmica do modelo
o Quais os processos que modificam as variáveis
que caracterizam as entidades do modelo?
o Em que ordem estes processos ocorrem?
2. Design Concepts
Princípios Básicos
o Conceitos, teorias, hipóteses, etc…
o Como estes princípios estão incorporados no modelo?
Emergência
o Quais são as saídas e resultados importantes do modelo?
Quais deles emergem do mecanismo de representação do
comportamento dos agentes?
Adaptação
o Quais comportamentos adaptativos possuem os agentes?
Como eles respondem a mudanças?
2. Design Concepts
Objetivos
o Quais são os objetivos a serem alcançados pelos agentes?
Como o alcance destes objetivos pode ser mensurado
(exemplo: “fitness” em ecologia, “utilidade” em economia)?
Quais elementos de sucesso futuro estão presentes nesta
medida (ex. sobrevivência durante o próximo ciclo, lucros, etc. )
Aprendizagem/Predição
o Os agentes mudam seu comportamento em consequência de
sua experiência?
o Os agentes são capazes de prever condições futuras no seu
processo de adaptação? Como?
o Como essa predição simulada utiliza mecanismos como
memória e aprendizagem?
2. Design Concepts
Sensibilidade/Apreensão
o Quais variáveis ambientais e dos agentes são apreendidas
pelos agentes e consideradas em seu comportamento.
o Quais os mecanismos de apreensão são modeladas
explicitamente, existem incertezas neste processo?
Interação
o Como os agentes interagem? Eles interagem diretamente
uns com os outros ou esta interação é mediada?
Estocasticidade
o Como são os processos estocásticos (baseados em números
pseudo-aleatórios) utilizados no modelo e por quê?
2. Design Concepts
Coletivos
o Agregação de agentes que afetam o estado ou
comportamento dos indivíduos.
o Coletivos são representados no modelo? Como?
Observação
o Quais saídas do modelo são utilizadas para observar as
dinâmicas simuladas?
o Que tipo de saída/medida é necessária para testar o modelo
e resolver o problema para o qual o modelo foi
desenvolvido?
3. Details
Inicialização
o Condições iniciais da simulação
o Quantos agentes? Quais os valores iniciais das
variáveis?
Dados de Entrada
o Arquivos de dados importados ao longo das
simulações
Sub-Modelos
Outros Exemplos de Modelos
Minimalistas
oWealth distribution
oVirus Transmission
oClimate Change
o…
Wealth Distribution

Brazil ranks among the world's highest nations in the Gini
coefficient index of inequality (G = 0.55)
Source: Wikipedia
Wealth Distribution: Gini Ratio
G = 0: Perfect equality (everybody has same wealth)
G = 1: Perfect inequality (all is owned by one individual)
Wealth Distribution – Sugarscape Model
“The rich get richer and the poor get poorer”
Sugarscape Model – Epstein & Axtell (1996)
Illustrates Pareto’s Law
Most of the people are poor, fewer are middle
class, and very few are rich: 80/20 rule
Wealth Distribution – Sugarscape Model
Agents
o
Collect grain and eat grain to survive
o
Grain accumulation = WEALTH
o
Vision: high is good
o
Metabolism: low is good
Movement: move to cell within vision with more grains
Replacement: Replace dead agent with random new agent
Grain grows back with rate R
Wealth Distribution – Sugarscape Model
Initial conditions: randomly distributed
Wealth Distribution – Sugarscape Model
Uniform random
assignments of vision and
metabolism still result in
unequal distribution of
wealth
HOW????
Wealth Distribution
PROBABILITY DENSITY FUNCTION
Pareto Distribution
Non-linear distribution of wealth  Resembles a power law
The "probability" or fraction of the population f(x) that owns a small
amount of wealth per person (x) is rather high, and then decreases
steadily as wealth increases
Virus Transmission
Virus Transmission
http://ccl.northwestern.edu/netlogo/models/Virus
Virus Transmission
Baseline
Recover >
Recover <
Greenhouse Effect
Greenhouse Effect
http://ccl.northwestern.edu/netlogo/models/ClimateChange
Greenhouse Effect
Baseline
Albedo
CO2
EXERCÍCIO PARA PRÓXIMA AULA
(29/11)
Selecionar um modelo minimalista e descrevê-lo
de acordo com os princípios do protocolo ODD
Decision Support Models
MASUS: Multi-Agent Simulator for
Urban Segregation
Impacts of Segregation
Obstacles that
contribute to
perpetuate poverty
Policies to minimize segregation demand:
A better understanding of the dynamics of
segregation and its causal mechanisms
The Complex Nature of Segregation
The Process Matters!
MASUS
Multi-Agent Simulator for Urban Segregation
Scientific tool to explore alternative scenarios of segregation
Purpose
Improve the understanding about segregation and
its relation with different contextual mechanisms
Support planning actions by offering insights about
the impact of policy strategies
1. Problem analysis and
objective formulation
2. Conceptual model framework
MASUS
Methodological
Steps
4. Data collection
3. Theoretical specification
5. Empirical parameterization
N
Are the empirical results consistent
with the theoretical specification ?
Y
6. Programming in NetLogo
Next version of
MASUS
7. Verification
Is the program executing what is
stated in the theoretical specification ?
N
Y
8. Simulation
experiments
N
9. Validation
Are the simulation outputs appropriate
to represent the real target-system?
Y
10. Analyses of simulated results
N
MASUS Conceptual Model
1. Problem analysis and
objective formulation
2. Conceptual model framework
MASUS
Methodological
Steps
4. Data collection
3. Theoretical specification
5. Empirical parameterization
N
Are the empirical results consistent
with the theoretical specification ?
Y
6. Programming in NetLogo
Next version of
MASUS
7. Verification
Is the program executing what is
stated in the theoretical specification ?
N
Y
8. Simulation
experiments
N
9. Validation
Are the simulation outputs appropriate
to represent the real target-system?
Y
10. Analyses of simulated results
N
São José dos Campos, Brazil
City of São José dos
Campos
São Paulo State
Study
Area
MASUS: Process Schedule
Decision-making sub-model
ALTERNATIVES
• Not Move
• Move within the same neighborhood
• Move to the same type of neighborhood (n alternatives)
• Move to a different type of neighborhood (m alternatives)
Higher probability to choose alternative with higher
utility
Decision-making sub-model
Nesting Structure of the Model
NMNL: Affluent Households
Level
1st
Choice
Variable
Coef.
Std. err.
Age of the household head
-0.040***
0.011
Renter
2.542***
0.425
Renter * household income
-9.4(10-5)
-7.5(10-5)
Constant
-2.532 ***
0.693
Constant
-2.464 ***
0.855
Move to the same type
Type A neighborhood
0.477
0.661
of neighborhood
Type B neighborhood
0.062
0.495
Kids * Type A
-0.368
0.636
Move to another
Constant
-3.457 ***
1.053
type of neighborhood
Type A neighborhood
-0.256
0.732
Type B neighborhood
1.760 ***
0.709
Kids * Type A
1.49 **
0.784
Land price/ income
-0.084
0.053
Generic
Real estate offers
1.4(10-3) ***
5.1(10-4)
variables
Distance from orig. neighborhood
-4.9(10-5) **
2.5(10-5)
Distance to CBD
2.3(10-5)
2.9(10-5)
Prop. of high-income families
0.960 **
0.503
Move
Move within the same neigh.
2nd
3rd
MASUS: Process Schedule
1. Problem analysis and
objective formulation
2. Conceptual model framework
MASUS
Methodological
Steps
4. Data collection
3. Theoretical specification
5. Empirical parameterization
N
Are the empirical results consistent
with the theoretical specification ?
Y
6. Programming in NetLogo
Next version of
MASUS
7. Verification
Is the program executing what is
stated in the theoretical specification ?
N
Y
8. Simulation
experiments
N
9. Validation
Are the simulation outputs appropriate
to represent the real target-system?
Y
10. Analyses of simulated results
N
Operational Model
1. Problem analysis and
objective formulation
2. Conceptual model framework
MASUS
Methodological
Steps
4. Data collection
3. Theoretical specification
5. Empirical parameterization
N
Are the empirical results consistent
with the theoretical specification ?
Y
6. Programming in NetLogo
Next version of
MASUS
7. Verification
Is the program executing what is
stated in the theoretical specification ?
N
Y
8. Simulation
experiments
N
9. Validation
Are the simulation outputs appropriate
to represent the real target-system?
Y
10. Analyses of simulated results
N
Simulation Experiments
Comparing simulation outputs with
empirical data
Testing theoretical issues
Testing anti-segregation policy strategies
Comparison with Empirical Data
Initial condition: São José dos Campos in
1991
•
Import GIS layers (households, environment)
•
Set parameters
Run 9 annual cycles
Compare simulated results with real data
(year 2000)
Comparison with Empirical Data
Dissimilarity Index (local scale)
Initial State
(1991)
0.54
Simulated Data
(1991-2000)
0.51
0.51
0.31
0.30
0.30
0.15
Real Data
(2000)
0.19
0.19
Comparison with Empirical Data
Isolation Poor Households (local scale)
Initial State
(1991)
0.54
Simulated Data
(1991-2000)
0.51
Real Data
(2000)
0.51
Comparison with Empirical Data
Isolation Affluent Households (local scale)
Initial State
(1991)
0.15
Simulated Data
(1991-2000)
0.19
Real Data
(2000)
0.19
Testing a theory
How does inequality affect segregation?
Relation between both phenomena has caused controversy
in scientific debates
Experiment
Compare 3 scenarios 1991-2000
Scenario 1: Previous run (baseline)
Scenario 2: Decreasing inequality
Scenario 3: Increasing inequality
Testing a theory
Inequality (Gini)
Proportion Poor HH
Proportion Affluent HH
Dissimilarity
Isolation Poor HH
Isolation Affluent HH
Scenario 1 (Original)
Scenario 2 (Low-Ineq.)
Scenario 3 (High-Ineq.)
Testing policy strategies
Poverty Dispersion vs. Wealth Dispersion
Poverty Dispersion: housing vouchers to poor families
Experiment
Compare 3 scenarios
Scenario 1
no voucher (baseline)
Scenario 2
200 – 1700 vouchers
Scenario 3
400 – 4200 vouchers
Testing policy strategies
Dissimilarity
2.3 - 3.5 %
5.8 - 10.7%
Isolation Affluent HH
2.3 - 5.7 %
5.8 - 8.3 %
Isolation Poor HH
2.3 - 1.7 %
5.8 - 3.4%
Scenario 1
No voucher (baseline)
Scenario 2
200 - 1700 vouchers (2.3%)
Scenario 3
400 - 4200 vouchers (5.8%)
Testing policy strategies
Poverty Dispersion vs. Wealth Dispersion
Poverty Dispersion
Demands high and continous investment to decrease
poverty isolation
Slows down the increase in segregation, but does not
change the trends
Testing policy strategies
Poverty Dispersion vs. Wealth Dispersion
Wealth Dispersion: Incentives for constructing residential
developments for upper classes in poor regions of the city
Experiment
Compare 2 scenarios
Scenario 1
(baseline)
Scenario 2
new areas for upper classes
Urban areas in 1991
Undeveloped areas for upper classes
Testing policy strategies
Dissimilarity
Isolation Poor HH
Isolation Affluent HH
Scenario 1
baseline
Scenario 2
new areas for upper
classes
Testing policy strategies
Poverty Dispersion vs. Wealth Dispersion
Wealth Dispersion
Produces long-term outcomes
More effective at decreasing large-scale segregation
E.g.
Dissimilarity 2010
local scale (700m):
- 19%
large scale (2000m): - 36%
Testing policy strategies
Poverty Dispersion vs. Wealth Dispersion
Wealth Dispersion
Positive changes in the spatial patterns of segregation
Baseline
2010
Wealth Dispersion
2010
MASUS
Multi-Agent Simulator for Urban Segregation
Laboratory for testing theories and policy approaches
on segregation
Does not focus on making predictions
Exploratory tool, framework for assembling relevant
information
Um contador de histórias
Modelos de simulação contam uma história
Pode ser sobre o presente, passado ou futuro…
A história pode ser boa ou não…
Mas oferece uma outra maneira de examinar a situação!
FERRAMENTA PARA
COMPARTILHAR VISÕES,
LEVANTAR DÚVIDAS,
ESTRUTURAR DISCUSSÕES
E DEBATES