SAHGA – Um algoritmo genético
híbrido com representação
explícita de relacionamentos
espaciais para análise de dados
geoespaciais
Tese de doutorado em Computação Aplicada
Adair Santa Catarina
Orientadores: Dr. Antônio Miguel Vieira Monteiro
Dr. João Ricardo de Freitas Oliveira
INPE – Abr/2009
Roteiro

Introdução

Referencial Teórico:

Representação do espaço bi-dimensional e vizinhança espacial;

Algoritmos Genéticos;

Model Breeders;

Species Distribution Models.

SAHGA Model Breeder

SAHGA SDM

Conclusões

Referências Bibliográficas
2
Introdução
Informações
GIS
Dados
Dados
Organizados
3
Introdução
Informações
• Model Breeders (Openshaw, 1997);
• GARP (Stockwell e Peters, 1999).
Dados
Organizados
D
Negligenciam os
relacionamentos
espaciais
X
Dependência
Espacial
(Lei de Tobler)
4
Questões




É possível incorporar os relacionamentos
espaciais em sistemas semi-automáticos de
análise de dados geoespaciais baseados em
AG?
Estes sistemas são capazes de operar sobre um
modelo generalizado de relacionamentos
espaciais?
Os relacionamentos espaciais afetam os
resultados fornecidos por tais sistemas?
O conhecimento pré-existente, acerca dos
fatores ambientais que afetam o problema em
estudo, pode ser representado nestes
sistemas?
5
Hipótese Central

É possível incorporar aos AG, utilizados em
sistemas de análise de dados geoespaciais, uma
estrutura para representação explícita de
relacionamentos espaciais, a GPM – Generalized
Proximity Matrix, possibilitando-os considerar os
efeitos da dependência espacial nos fenômenos
estudados.

Verificação da hipótese  prova de conceito

SAHGA – Spatially Aware Hybrid Genetic Algorithm


SAHGA MB  dados sócio-econômicos
SAHGA SDM  duas espécies de aves
6
Roteiro

Introdução

Referencial Teórico:

Representação do espaço bi-dimensional e vizinhança espacial;

Algoritmos Genéticos;

Model Breeders;

Species Distribution Models.

SAHGA Model Breeder

SAHGA SDM

Conclusões

Referências Bibliográficas
7
Representação do Espaço 2D

Polígonos ou grades regulares:
8
Generalized Proximity Matrix (GPM)


Aguiar et al., 2003.
Estrutura da GPM:

Conjunto de objetos O:



Grafo (G):



Células regulares;
Polígonos.
Nós = objetos;
Arcos = relacionamentos.
Matriz de proximidade (V):


Conjunto de valores Wij que indicam o quanto dois objetos Oi
e Oj estão relacionados;
Wij  relacionamentos no espaço absoluto ou relativo.
9
Algoritmos Genéticos (AG)
10
Simulated Annealing

Metropolis (1953); Kirkpatrick et al. (1983):
1

Pck (aceitar j )     g j  g i  


exp 
ck

 
se g j  g i 

se g j  g i 

gi e gj = níveis energéticos;
ck = temperatura.


Extensão do método de busca local;
Habilidade para fugir da armadilha do ótimo local.
11
Model Breeders

Openshaw & Openshaw (1997), Santa Catarina
et al. (2005):
y = f(x1, x2, ..., xn);



Núcleo de otimização utilizam AG;
Vantagens: modelos simples de compreender e
eficiência computacional;
Desvantagem: simplificação do fenômeno
observado e grande consumo de tempo para
resposta ótima.
12
Species Distribution Models (SDM)
Fonte: Adaptado de Siqueira (2005)
13
Tipos de Modelos usados em Ecologia



Analíticos;
Mecanicistas;
Empíricos 
SDM.
Fonte: Adaptado de Guisan e Zimmerman (2000)
14
Avaliação dos SDM
Matriz de Confusão
Fonte: Adaptado de Siqueira (2005)
Fonte: Braga (2000)
Fonte: Adaptado de Meyer (2005)
15
Roteiro

Introdução

Referencial Teórico:

Representação do espaço bi-dimensional e vizinhança espacial;

Algoritmos Genéticos;

Model Breeders;

Species Distribution Models.

SAHGA Model Breeder

SAHGA SDM

Conclusões

Referências Bibliográficas
16
SAHGA Model Breeder

Dados de entrada:

Codificação:

Função de aptidão:
NREi


Xˆ 0i    CX k    Wij  X kj 

k 1 
 j 1
n
m
Aptidão  
i 1


Wij    Constante


j 1

NREi
X 0i  Xˆ 0i

2
17
Núcleo de Otimização – SAHGA
18
Operadores Genéticos – SAHGA






Seleção pelo método da roleta;
Cruzamento aritmético de Michalewicz (1996):
c1  p1  1    p2
c2  1    p1  p2
Mutação uniforme [-4; 4];
Busca local (SA)  mutação uniforme [-0,5; 0,5];
Elitismo.
Padronização das variáveis de entrada:
X x
Xp 
s
19
Parâmetros do SAHGA

Grefenstette (1986), De Jong e Spears (1991) e
Santa Catarina e Bach (2003).
20
Estudo de Caso – SAHGA MB
 X0
Fonte: IBGE (2007)
= Número de
filhos nascidos
vivos;
 X1 = Número de
domicílios com
banheiro;
 X2 = Número de
domicílios cujo
responsável tem 8
ou mais anos de
estudo;
 X3 = Número de
domicílios onde a
renda é maior que
3 salários
mínimos.
21
Modelos Ajustados – SAHGA MB

Configuração dos parâmetros = Default

Desconsiderando a GPM:
Cada estado está relacionado apenas consigo
mesmo  Wii = 1
Xˆ 0 p  1,5605 X 1 p  2,7114  X 2 p  3,3185 X 3 p  0,0025
Aptidão mínima = 0,9298.

Considerando a GPM:
Xˆ 0 p  1,5397  X 1 p  3,3491 X 2 p  4,0  X 3 p  0,011
Aptidão mínima = 1,0737.
22
Conclusões – SAHGA MB


Modelos ajustados estimam adequadamente X0
em função das variáveis independentes;
Trabalha com diferentes tipos de modelos,
utilizando a mesma estrutura de codificação:

Adaptação para modelos quadráticos

 NREi

  Wij  X kj2
n

 j 1
Xˆ 0i    CX k2   NREi
k 1


Wij



j 1







  CX k



 NREi

  Wij  X kj   
 j 1

  NREi
   Constante


W

ij


j 1


23
Roteiro

Introdução

Referencial Teórico:

Representação do espaço bi-dimensional e vizinhança espacial;

Algoritmos Genéticos;

Model Breeders;

Species Distribution Models.

SAHGA Model Breeder

SAHGA SDM

Conclusões

Referências Bibliográficas
24
SAHGA SDM

Dados de entrada:

Codificação (=):

Função de aptidão:



Xˆ    CX    W  X  W    Constante


NREi
n
0i
k 1


Aptidão    X 0i  Xˆ 0i

i 1

m

k

2

j 1
NREi
ij
kj


j 1
ij

 
 

 

0, se X 0i  0 e Xˆ 0i  0,5 ou X 0i  1e Xˆ 0i  0,5
 0,1  
ˆ
ˆ

1, se X 0i  0 e X 0i  0,5 ou X 0i  1e X 0i  0,5
25
Estudos de Caso – SAHGA SDM

Distribuição potencial de duas espécies de
aves:
Strix varia
Thalurania furcata boliviana
26
Estudos de Caso – SAHGA SDM

Comparação  SAHGA SDM x GARP (SR e
BS)


openModeller Desktop v1.0.6 (CRIA et al., 2008);
SAHGA SDM:
Modelos com e sem relacionamentos espaciais;
 Construção da GPM:


Parâmetros: Hard.
27
Espécie Strix varia

Dados:
Base exemplo do DesktopGarp (Kansas University,
2007);
 1218 pontos de presença  100 selecionados;
 7 layers geográficos: temperatura, precipitação e
relevo;
 100 pontos de pseudo-ausência  modelo BioClim
(Nix, 1986)  openModeller Desktop;
 Treino (50%) e teste (50%);
 GPM  raio de 100 km.

28
Modelo BioClim – Strix varia
29
Modelos S1 e S2 – Strix varia
Modelo S1
Modelo S2
30
Distribuição Potencial – Modelos S1 e S2
31
Modelos SGSR e SGBS – Strix varia
Modelo SGSR
Modelo SGBS
32
Distribuição Potencial – Modelos SGSR e SGBS
33
Espécie Thalurania furcata boliviana

Dados:
Base exemplo do openModeller Desktop;
 65 pontos de presença;
 8 layers geográficos: precipitação e temperatura;
 50 pontos de pseudo-ausência  modelo BioClim 
openModeller Desktop;
 Treino (40P/30A) e teste (25P/20A);
 GPM  raio de 100 km.

34
Modelo BioClim – Thalurania furcata boliviana
35
Modelos T1 e T2 – Thalurania furcata boliviana
Modelo T1
Modelo T2
36
Distribuição Potencial – Modelos T1 e T2
37
Modelos TGSR e TGBS – Thalurania furcata boliviana
Modelo TGSR
Modelo TGBS
38
Distribuição Potencial – Modelos TGSR e TGBS
39
Roteiro

Introdução

Referencial Teórico:

Representação do espaço bi-dimensional e vizinhança espacial;

Algoritmos Genéticos;

Model Breeders;

Species Distribution Models.

SAHGA Model Breeder

SAHGA SDM

Conclusões

Referências Bibliográficas
40
Conclusões

Sistemas de análise de dados geoespaciais que
utilizam AG negligenciam os efeitos da
dependência espacial;

Prova de conceito  SAHGA – Spatially Aware
Hybrid Genetic Algorithm  relacionamentos
espaciais  GPM;

Algoritmo de uso múltiplo:
SAHGA MB  Dados sócio-econômicos;
 SAHGA SDM  Strix varia e Thalurania furcata
boliviana.

41
Conclusões

SAHGA MB:

Ajuste de modelos sem e com relacionamentos
espaciais (GPM);

Modelos ajustados são distintos  influência dos
relacionamentos espaciais.

Ambos estimam adequadamente o valor padronizado
da variável dependente.
42
Conclusões

SAHGA SDM:
43
Conclusões

C Representação de conhecimento do
especialista:

No espaço relativo  SAHGA MB:



No espaço absoluto  SAHGA SDM:



Associações entre estados independem da distância;
Válida para alguns estados.
Pesos Wij variam em função da distância;
0 – 50 km = 1,0; 50 – 100 km = 0,5.
C Adaptabilidade do algoritmo  modelos mais
complexos:
Adaptação da estrutura cromossômica;
 Reescrita da função de aptidão.

44
Trabalhos Futuros

Geração automática da GPM:


Outros tipos de modelos:




Relacionamentos pré-definidos: toca, intercepta,
perto de, etc.
Estruturas cromossômicas e funções de aptidão prédefinidas;
Rotinas de pré-análise de dados;
Geração automática de pontos de pseudoausência;
GPM dinâmicas:

Análise de dados espaço-temporais.
45
Roteiro

Introdução

Referencial Teórico:

Representação do espaço bi-dimensional e vizinhança espacial;

Algoritmos Genéticos;

Model Breeders;

Species Distribution Models.

SAHGA Model Breeder

SAHGA SDM

Conclusões

Referências Bibliográficas
46
Referências Bibliográficas
AGUIAR, A. P. D. et al. Modeling spatial relations by generalized proximity matrices. In: Brazilian
Symposium on Geoinformatics, 5, 2003. Campos do Jordão - SP. Anais eletrônicos... São José dos
Campos: INPE, Nov. 2003. Disponível em: <http://www.geoinfo.info/geoinfo2003/papers/geoinfo200311.pdf>. Acesso em: 04/07/2006.
BRAGA, A. C. S. Curvas ROC: aspectos funcionais e aplicações. 2000. 243 p. Tese (Doutorado
em Engenharia de Produção e Sistemas) - Universidade do Minho, Braga.
CENTRO DE REFERÊNCIA EM INFORMAÇÃO AMBIENTAL; ESCOLA POLITÉCNICA DA USP;
INSTITUTO NACIONAL DE PESQUISAS ESPACIAIS. openModeller. 2008. Disponível em:
<http://openmodeller.sourceforge.net/>. Acesso em: 12/07/2008.
DE JONG, K. A. An analysis of the behavior of a class of genetic adaptive systems. 1975. 256 p.
Tese (Ph. D. in Computer and Communication Sciences) - University of Michigan, Ann Arbor.
GREFENSTETTE, J. J. Optimization of control parameters for genetic algorithms. IEEE transactions
on systems, man and cybernetics, v. 16, n. 1, p. 122-128, Jan./Fev. 1986.
GUISAN, A.; ZIMMERMANN, N. E. Predictive habitat distribution models in ecology. Ecological
Modelling, v. 135, n. 2-3, p. 147-186, Dez. 2000.
HOLLAND, J. H. Adaptation in natural and artificial systems. Cambridge: MIT Press, 1992. 228 p.
47
Referências Bibliográficas
KANSAS UNIVERSITY. DesktopGarp. 2007. Disponível em: <http://www.nhm.ku.edu/desktopgarp/>.
Acesso em: 03/05/2008.
KIRKPATRICK, S.; GELATT, C. D.; VECCHI, M. P. Optimization by simulated annealing. Science, v.
220, n. 4598, p. 671-680, Maio 1983.
METROPOLIS, N. et al. Equation of state calculations by fast computing machines. The Journal of
Chemical Physics, v. 21, n. 6, p. 1087, Jun. 1953.
MEYER, E. M. Ecological niche modelling: inter-model variation, best-subset models selection. In:
Workshop on Biodiversity Data Modelling, 2005. Cidade do México. Anais eletrônicos...
Copenhague: GBIF, Abr. 2005. Disponível em:
<http://www.gbif.org/prog/ocb/modeling_workshop/bangalore/presentations/ENMIV>. Acesso em:
21/10/2007.
MICHALEWICZ, Z. Genetic algorithms + data structures = evolution programs. 3. ed. Berlin:
Springer-Verlag, 1996. 387 p.
NIX, H. A. A biogeographic analysis of Australian elapid snakes. In: LONGMORE, R. (Ed.) Atlas of
elapid snakes of Australia. Canberra: Australian government publishing service, v.7, 1986. p. 4–15.
(Australian flora and fauna series).
OPENSHAW, S.; OPENSHAW, C. Artificial intelligence in geography. West Sussex: John Wiley &
Sons, 1997. 348 p.
48
Referências Bibliográficas
PEDROSA, B. M. Ambiente computacional para modelagem dinâmica. 2003. 71 p. Tese
(Doutorado em Computação Aplicada) - Instituto Nacional de Pesquisas Espaciais, São José dos
Campos.
SANTA CATARINA, A.; BACH, S. L. Estudo do efeito dos parâmetros genéticos sobre a solução
otimizada e sobre o tempo de convergência em algoritmos genéticos com codificações binária e real.
Acta Scientiarum. Technology, v. 25, n. 2, p. 147-152, Jul./Dez. 2003.
SIQUEIRA, M. F. Uso de modelagem de nicho fundamental na avaliação do padrão de
distribuição geográfica de espécies vegetais. 2005. 107 p. Tese (Doutorado em Ciências de
Engenharia Ambiental) - Universidade de São Paulo, São Carlos.
STOCKWELL, D. R. B.; PETERS, D. The GARP modeling system: problems and solutions to
automated spatial prediction. International Journal of Geographical Information Science, v. 13, n. 2, p.
143-158, Mar. 1999.
49