CONHECENDO O ALGORITMO GARP
Adair Santa CatarinaCurso de Informática
Unioeste – Campus de Cascavel – PR
INPE – Set/2006
2
Roteiro
n Introdução
n Algoritmos Genéticos (AG)
n GMS e DesktopGARP
n Avaliação dos Modelos Ajustados
n Problemas e Soluções no GMS
n Spatial Aware Genetic Algorithm (SAGA)
3
Introdução
n GARP é parte de um sistema utilizado na modelagem da distribuição potencial de espécies biológicas a partir de dados rasterambientais e biológicos (Stockwell, 1993).
4
Objetivos da Apresentação
n Exibir um exemplo de Algoritmo Genético para facilitar a compreensão do GARP;
n Apresentar uma visão geral do GMS (GARP Modelling System);
n Mostrar um AG com representação explícita de relacionamentos espaciais para modelagem sócio-ambiental.
5
Roteiro
n Introdução
n Algoritmos Genéticos (AG)
n GMS e DesktopGARP
n Avaliação dos Modelos Ajustados
n Problemas e Soluções no GMS
n Spatial Aware Genetic Algorithm (SAGA)
6
Algoritmos Genéticos (AG)
n Algoritmos de busca que se utilizam do paradigma genético/evolucionário (Holland, 1975);
n Em 1983 o primeiro problema de otimização resolvido com aplicação de AG (Goldberg, 1989);
n Imitam processos observados na evolução natural das espécies; bons indivíduos sobrevivem e se reproduzem;
n A evolução ocorre sobre indivíduos codificados em cromossomos sob a forma de cadeias de bits – 0 e 1 – ou números reais;
n Operadores: seleção, recombinação e mutação;n Avaliação da qualidade da solução: Fitness.
7
Algoritmos Genéticos (AG)
Gerar uma população
Estimar a população
Parar
Seleção
Cruzamento
Mutação
Estimação da nova população
Não
Sim
Fim da busca?
8
Algoritmos Genéticos (AG) – Exemplo
n Encontrar a cadeia de 20 bits com o maior número de bits 1.
n População inicial: 8 indivíduos aleatórios.
3
11
10
13
4
10
6
7
Fitness
11000000000000000001
10111010111000100101
10101000101001110110
11001110101011101101
00001000101000000100
11001010101010100101
00011000101010000010
11001000101000100100
População inicial
8
7
6
5
4
3
2
1
Ind.10,9%
9,4%
15,6%
6,3%
20,3%
15,6%
17,2%
4,7%
Ind 1 Ind 2 Ind 3 Ind 4
Ind 5 Ind 6 Ind 7 Ind 8
9
Algoritmos Genéticos (AG) – Exemplo
n Seleção: método da roleta;¨ Sorteiam-se tantos números entre 0 e 100% quantos
forem os indivíduos na população;¨ Através da distribuição de freqüência acumulada
localizam-se os indivíduos selecionados.
62,55
1008
95,37
78,16
42,24
35,93
20,32
10,91
d.f.a.Indivíduo
3
5
6
5
1
7
6
3
Indivíduo
11001010101010100101
11001110101011101101
10101000101001110110
11001110101011101101
11001000101000100100
10111010111000100101
10101000101001110110
11001010101010100101
Cromossomo
55
30
53
71
4
92
66
31
Sorteio
10
Algoritmos Genéticos (AG) – Exemplo
n Cruzamento:¨ Diversos tipos de cruzamento à Um ponto aleatório.¨ Taxa de cruzamento varia de 60 a 80%;¨ Adotada = 80%.
11001010101010100101
11001110101011101101
10101000101001110110
11001110101011101101
11001000101000100100
10111010111000100101
10101000101001110110
11001010101010100101
Cromossomos pais
3
5
6
5
1
7
6
3
Indivíduo
11001010101010100101
11001110101011101101
10101000101011101101
11001110101001110110
11001010111000100101
10111000101000100100
10101000101001100101
11001010101010110110
Cromossomos filhos
27
81
37
50
Sorteio
11
Algoritmos Genéticos (AG) – Exemplo
n Mutação:¨ Taxa de mutação varia de 0,5% a 5%;¨ Adotada = 2%.
11001010101010100101
11001110101011101101
10101000101011101101
11001110101001110110
11001010111000100101
10111000101000100100
10101000101001100101
11001010101010110110
Cromossomos filhos
11001110101010100101
11001110101011101101
10101000101011101111
11001110101001110110
11001100101000100100
11111010111000100101
10101000101001110110
11101010101010000101
Cromossomos (mutação)
8
7
6
5
4
3
2
1
Indivíduo
12
Algoritmos Genéticos (AG) – Exemplo
n Após a 1a geração:
3
11
10
13
4
10
6
7
Fitness
11000000000000000001
10111010111000100101
10101000101001110110
11001110101011101101
00001000101000000100
11001010101010100101
00011000101010000010
11001000101000100100
População inicial
11001110101010100101
11001110101011101101
10101000101011101111
11001110101001110110
11001100101000100100
11111010111000100101
10101000101001110110
11101010101010000101
População 1a geração
8
7
6
5
4
3
2
1
Ind.
11
13
12
12
8
12
10
10
Fitness
13
Roteiro
n Introdução
n Algoritmos Genéticos (AG)
n GMS e DesktopGARP
n Avaliação dos Modelos Ajustados
n Problemas e Soluções no GMS
n Spatial Aware Genetic Algorithm (SAGA)
14
GMS
n GARP Modelling System (Stockwell, 1993):
¨ Um AG para predição da distribuição potencial de espécies biológicas a partir de dados raster ambientais e biológicos;
¨ Trabalha de forma automática e não-supervisionada;¨ Robusto: testa diversas soluções e diversos modelos (regras);¨ Maximiza a significância e a precisão de predição das regras.
15
GMS
n Estrutura modular: 8 módulos (Batch) ¨ Rasteriz, presampl, initial, explain, verify, predict,
image, translat
n Regras:¨ Se A é verdade então B (inferência lógica)¨ 4 tipos de regras:
n Atômicas, BIOCLIM, Faixas e Logísticas;n Exemplos:
¨ Se TANN = 23 e GEO = 4 então PRESENT¨ Se TANN = (23, 29] e TNCM = (10, 16) e ... e TCLQ = (21, 23] e TWM
= (23, 30] então PRESENT¨ Se GEO=(6, 244] e TMNE=(228, 1480] então ABSENT¨ Se 0,1 – GEO * 0,1 + TMNE * 0,3 então ABSENT
16
GARP
n Codificação das regras:
r1: Se TMIN = (5, 10] e TMED = (10, 22] e ELEV = (1, 2] então PRESENT
r2: Se TMIN = (0, 15] e TMED = (0, 50] e ELEV = (0, 20] então ABSENT
r3: Se TMIN * 0,80 + TMED * -0,2 + ELEV * 0,45 então ABSENT
17
GARP
n Mecanismo evolutivo:¨ Recombinação:
n cruzamento e junção.
¨ Mutação:n aleatória e incremental.
¨ Seleção:n um número de melhores regras definido a priori
¨ Função de avaliação:
nn
pYspYsno
npYs
nopXYsSig
−⋅⋅
⋅−=
1
• Sig: valor de aptidão da regra (significância);
• pXYs: número de pontos amostrados que a regra prevê corretamente;
• no: número de pontos amostrados avaliados pela regra;
• pYs: número de pontos amostrados com a mesma conclusão que a regra;
• n: número total de pontos amostrados.
18
DesktopGARP
n Re-engenharia do GARP - interface “amigável”
19
Roteiro
n Introdução
n Algoritmos Genéticos (AG)
n GMS e DesktopGARP
n Avaliação dos Modelos Ajustados
n Problemas e Soluções no GMS
n Spatial Aware Genetic Algorithm (SAGA)
20
Avaliação dos Modelos Ajustados
n Dados de treinamento e dados de teste;n Matriz de confusão:
Presente Ausente Predição – Presente A B Predição – Ausente C D
¨ B = erros por comissão
n Desconhecimento, fatores topológicos/biológicos, área inadequada.
¨ C = erros por omissão D
21
Seleção do Melhor Subconjunto Solução
n GARP = algoritmo estocástico à gera diversos modelos com os mesmos dados.
Índice de Comissão (% da área predita como presente)
Err
opo
rOm
issã
o(%
de
pont
osam
ostr
ais
fora
da
área
pred
ita)
0 100
100
Índice de Comissão (% da área predita como presente)
Err
opo
rOm
issã
o(%
de
pont
osam
ostr
ais
fora
da
área
pred
ita)
0 100
100
Índice de Comissão (% da áreapredita como presente)
Err
o po
r O
mis
são
(% d
epo
ntos
am
ostr
ais
fora
da
área
pre
dita
)0 100
100
↑ Omissão↓ Comissão
Omissão nula↑ Comissão
Omissão nulaSem Comissão
Superajuste
Distribuição da espécie na área
Índice de Comissão (% da áreapredita como presente)
Err
o po
r O
mis
são
(% d
epo
ntos
am
ostr
ais
fora
da
área
pre
dita
)0 100
100
↑ Omissão↓ Comissão↑ Omissão↓ Comissão
Omissão nula↑ Comissão
Omissão nula↑ Comissão
Omissão nulaSem Comissão
Superajuste
Omissão nulaSem Comissão
Superajuste
Distribuição da espécie na áreaDistribuição da espécie na área
22
Seleção do Melhor Subconjunto Solução
n Avaliação da qualidade do modelo ajustado (cont.)
Índice de Comissão (% da área predita como presente)
Err
o po
r Om
issã
o(%
de
pont
os
amos
trai
s fo
ra d
a ár
ea p
redi
ta)
0 100
100
Índice de Comissão (% da área predita como presente)
Err
o po
r Om
issã
o(%
de
pont
os
amos
trai
s fo
ra d
a ár
ea p
redi
ta)
0 100
100
Índice de Comissão (% da área predita como presente)
Err
o po
r Om
issã
o(%
de
pont
os
amos
trai
s fo
ra d
a ár
ea p
redi
ta)
0 100
100
Índice de Comissão (% da área predita como presente)
Err
o po
r Om
issã
o(%
de
pont
os
amos
trai
s fo
ra d
a ár
ea p
redi
ta)
0 100
100
Superpredição
Melhores modelos
Superajuste Mediana
Índice de Comissão (% da área predita como presente)
Err
o po
r Om
issã
o(%
de
pont
os
amos
trai
s fo
ra d
a ár
ea p
redi
ta)
0 100
100
Índice de Comissão (% da área predita como presente)
Err
o po
r Om
issã
o(%
de
pont
os
amos
trai
s fo
ra d
a ár
ea p
redi
ta)
0 100
100
Superpredição
Melhores modelos
Superajuste Mediana
23
Roteiro
n Introdução
n Algoritmos Genéticos (AG)
n GMS e DesktopGARP
n Avaliação dos Modelos Ajustados
n Problemas e Soluções no GMS
n Spatial Aware Genetic Algorithm (SAGA)
24
Problemas e Soluções no GMS
n 4 classes lógicas de problemas:¨ Preparação dos dados;¨ Desenvolvimento do modelo;¨ Aplicação do modelo;¨ Comunicação.
25
Preparação dos Dados – Rasteriz
n Utilizar todas as informações disponíveis: dados categóricos e contínuos.
n Não uniformidade da população:¨ Deve-se à variação na escala dos dados: 100 km a
poucos metros;¨ Um outlyer é mais importante que a amostragem em
duplicidade; dados próximos são absorvidos numa única célula;
¨ Rasteriz mapeia os dados para uma matriz, colocando os dados numa mesma escala.
26
Preparação dos Dados – Rasteriz
n Diferentes tipos de dados:¨ Rasteriz reconhece 3 tipos de dados diferentes:
presença/ausência, categóricos, contínuos.n Presença/ausência: Mais de um à Valor presença;n Categórico: Moda;n Contínuo: Média.
¨ Valores interpolados linearmente: [Min, Max] à Byte.
27
Produzindo o Conjunto de Dados
n Dados podem estar numa mesma escala, mas não estão livres de padrões indesejados oriundos do processo de amostragem.
n Presampl gera dois conjunto de dados (train e test) a partir dos dados produzidos por rasteriz.
n Apenas dados de presença:¨ Em herbários a maioria dos dados referem-se apenas
à presença da espécie;¨ GARP cria o conceito de background (pseudo-
ausência) selecionando pontos aleatórios no espaço geográfico.
28
Produzindo o Conjunto de Dados
n Proporções variáveis:¨ A proporção de amostras de presença e ausência
refletem a escassez ou abundância da espécie;¨ As métricas de avaliação da qualidade dos modelos
são afetadas quando as proporções de amostras estão próximas de 0 ou 1;
¨ Recomendação: manter o equilíbrio na amostragem de dados de presença/ausência (50% a 50%);
¨ O desequilíbrio prejudica a comparação dos modelos para diferentes espécies.
29
Produzindo o Conjunto de Dados
n Poucos ou muitos dados:¨ Muitos dados à aumento no tempo de computação
com poucos ganhos da precisão do modelo;¨ Poucos dados à amostragem com reposição pode
comprometer pressupostos estatísticos como a independência.
30
Desenvolvimento do Modelo
n Dois objetivos da modelagem: repetição e precisão nos resultados.
n Repetição:¨ GARP é um algoritmo estocástico à difícil obter
repetição de resultados;¨ Consumo de tempo para obter o resultados à Initialà gera um modelo inicial usando estatísticas e heurísticas que acelera o processo.
n Precisão nos resultados:¨ Não há consenso entre autores sobre a resposta das
espécies ao ambiente;¨ GARP usa diferentes modelos de regras que podem
ser vistas como diferentes tipos de modelos.
31
Aplicação do Modelo
n Superajuste (Overfitting): o modelo ajusta-se perfeitamente aos dados mas é muito pobre em predição;
n Um modelo com diversas regras pode apresentar conflitos entre regras.
n Overfitting:¨ Repetidos testes de significância estatística num
subconjunto amostrado a partir de train (Explain) elimina overfittingà Conclusão empírica (Stockwell, 1992);
¨ Uso do conjunto testà Verify à Matriz de confusão.
32
Aplicação do Modelo
n Conflito entre regras:¨ Aplica-se a regra que apresenta maior precisão de
previsão à predict;n Presente à P = probabilidade a posteriori;n Ausente à P = 1 – probabilidade a posteriori;n Gera transições abruptas nos mapas de saída;
¨ Suavização das transições:n média entre probabilidade a posteriori da melhor regra
(presença) e o inverso da probabilidade a posteriori da melhor regra (ausência).;
¨ Quando nenhuma regra se aplica a área é dita não-predita.
33
Avaliação do GMS
n Duas formas de avaliar sistemas de modelagem:¨ Demonstrar a validade do sistema em bases teóricas
usando a matemática e dados simulados;¨ Através de experimentação empírica e comparação
dos resultados com sistemas alternativos.
n A segunda opção foi escolhida: em uso desde 1995 por especialistas de todo o mundo, com as mais diferentes espécies.
34
Avaliação do GMS
n Sistema inovador:¨ O sistema foi testado com uma gama variada de
espécies com dados fornecidos por especialistas que depois analisaram os resultados.
¨ Conclusão: erros devem-se mais ao problema da falta de dados do que às limitações intrínsecas da tecnologia.
35
Roteiro
n Introdução
n Algoritmos Genéticos (AG)
n GMS e DesktopGARP
n Avaliação dos Modelos Ajustados
n Problemas e Soluções no GMS
n Spatial Aware Genetic Algorithm (SAGA)
36
Spatial Aware Genetic Algorithm (SAGA)
n AG são utilizados em diversas aplicações:¨ GARP (Stockwell, 1993);¨ Model Breeders (Openshaw, 1997).
n Limitação destes AG:
DependênciaEspacial
(Lei de Tobler)
Não incorporamrelacionamentos
espaciais
37
Questões
n É possível incorporar os relacionamentos espaciais em AG utilizados na análise de dados geográficos?
n Os AG são capazes de operar sobre um modelo generalizado de relacionamentos espaciais?
n Os AG permitem quantificar o efeito dos relacionamentos sobre as variáveis envolvidas num fenômeno espacial?
n Pode-se representar o conhecimento sobre as influências, favoráveis ou não, oriundas de formações naturais ou artificiais presentes na região em estudo?
38
Objetivo
n Incorporar aos AG, utilizados na modelagem de fenômenos sócio-ambientais, uma estrutura de representação explícita de relacionamentos espaciais, através da qual pode-se inserir o conhecimento sobre os elementos naturais e artificiais presentes na região em estudo, resultando em modelos mais confiáveis.
39
Estrutura do SAGA
40
Dados de Entrada
41
Estrutura do Cromossomo
∑ ∑= =
⋅⋅=
r
ji
n
kkijkiji XWeightsWX
1, 10
ˆ
( )∑=
−=n
iii XXFitness
1
2
00ˆ
Função de Avaliação
42
Considerações
n Estrutura proposta é flexível:¨ Layersà Polígonos ou matrizes;¨ Modelos de regressão linear à Elemento é vizinho
de si mesmo e Wij = 1;¨ Elemento de relevo divide o espaço em sub-regiões à Wij = 0;
¨ Modelos quadráticos: ∑ ∑= =
⋅⋅=
r
ji
n
kkijkiji XWeightsWX
1, 1
20
ˆ
n Layers de pesos:n Padrões podem indicar como as variáveis
independentes afetam a dependente considerando a componente espacial.
43
Fim
44
Referências Bibliográficas
n GOLDBERG, D. E. Genetic algorithms in search, optimization &machine learning. Reading : Addison-Wesley, 1989.
n HOLLAND, J. H. Adaptation in natural and artificial systems. Ann Arbor: University of Michigan Press, 1975.
n OPENSHAW, S.; OPENSHAW, C. Artificial intelligence ingeography. West Sussex : John Wiley & Sons, 1997.
n STOCKWELL, D. Machine learning and the problem ofprediction and explanation in ecological modelling. 1992. Tese de Doutorado – Australian National University, Austrália.
n STOCKWELL, D.; PETERS, D. Spatial predictions using Genetic Algorithm for Rule-set Production. 1993. Disponível em: <biodi.sdsc.edu/Symbiotik/ Model/GARP/Doc/tutorial.html>. Acesso em: 01/05/2006.