Transcript Document

GARP
Genetic Algorithm
for Rule-set Production
Computational
Point of View
Presentation Outline



Overview of Predictive Modeling (Arthur)
GARP and DesktopGARP (Ricardo)
Applications
–
–
–
–
Climate Changes (Marinez)
Risk Assessment (Raul)
Agriculture (Victor)
Disease Systems (Town)
Predictive Modeling Methodology
Slilde by Town Peterson
Temperature
Ecology
Ecological Niche Model
Projection Onto
Projection
Another Region
Over Changed
Climate
Precipitation
Geography
Algorithm
Occurrence Points
Native
Predicted
Range
Predicted Distribution
After Climate Changes
Invasive
Potential
GARP - General Approach

Divide data in training data set (used to build
models) and test data set (to validate the model)

Applies an algorithm to the training data set
– BIOCLIM
– Logistic Regression
– etc.

Evaluates model quality, by asking how errors
are different from random
GARP - Data and Results
Point occurrence data
vegetação
temperatura
precipitação
relevo
Environmental
Dimensions
(Environmental
Layers)
Predicted
Distribution
One Step at a Time
GARP = GA + RP
GA: Brief Introduction to Genetic Algorithms
RP: Rule-set Production
GA: Genetic Algorithms

Application from Artificial Intelligence

Concept taken from genetics and evolutions of species
applied as a generic problem solving technique in
Computer Science:
- Genes, chromossomes, mutations, insertions, deletions,
crossing over, genotype, individuals, population, survival of the
fittest.

For more info on GA,
–
–
visit: Marek Obitko's website at http://cs.felk.cvut.cz/~xobitko/ga/
Or ask me during the demo sessions (during lunch time)
RP: Rule-set Production


Rule: Logical Proposition
Format:
If A is true then B
A: precondition
B: result or prediction

Example:
If Tmin_winter in [5,10] & Tavg_winter in [10,22] & Elev in [1k,2k]
then taxon is present

R: Rule-set in GARP
Training Data-set

P: Set of training data point (spp)
Elements in P: pi = (a, b)
a: environmental variables at that point
b: observed presence or absence

Example: p1 = (10, 12, 2k, Present)



Rule-set Evaluation

P is used to test the rules in R:
If a in A:
If b=B then the rule predicts correctly
If b≠B then the rule DOES NOT predicts correctly
If a not in A:
Rule does not apply to the point: test next rule

f(ri): fitness function
–
Percentage of points that are predicted correctly by the
rule (can be something else)
Take a Look Inside GARP

Rule Coding:
r1: If Tmin_winter in [5,10] & Tavg_winter in [10,22] e Elev in [1k,2k] then present
r2: If Tmin_winter in [0,15] & Tavg_winter in [0,50] & Elev in [0,20k] then absent
r3: If [Tmin_winter x 0.80 + Tavg_winter x (-0.2) + Elev x 0.45] then absent
Rule
Tmin_win
Tmin_win
Tavg_win
Tavg_win
Elev
Elev
P/A
f(r)
r1
5
10
10
22
1k
2k
P
50%
r2
0
15
0
50
0k
20k
A
12%
r3
0.8
---
-0.2
---
0.45 ---
A
95%
Heuristic Operators

Mutation: random modification of a gene
Before:
r2
0
15
0
50
0k
20k
A
12%
0
15
0
28
0k
20k
A
15%
After:
r4
Heuristic Operators

Crossing over: Exchange of segments between two
chromossomes:
Before:
r1
5
10
10
22
1k
2k
P
50%
r2
0
15
0
50
0k
20k
A
12%
5
0
10
15
10
0
50
22
0k
1k
20k
2k
P
A
87%
9%
After:
r5
r6
Survival of The Fittest
Rule f(r)
r3
95%
r5
87%
r1
50%
r4
15%
r2
12%
r6
9%
Rules
Sorted
by f(r)
Survival of The Fittest
Rule f(r)
r3
95%
r5
87%
r1
50%
r4
15%
r2
12%
r6
9%
Survice and
have offspring
Threshold
Die
Results

After <n> iterations:
Rule f(r)
r3
95%
r5
87%
r1
50%
Survivors form a rule set
that represents the
ecological niche of that
species
Results

Ecological Niche Model of the Species:
r3: If [Tmin_winter x 0.80 + Tavg_winter x (-0.2) + Elev x 0.45] then absent
r5: If Tmin_winter in [5,10] & Tavg_winter in [10,50] & Elev in [0,20k] then present
r1: If Tmin_winter in [5,10] & Tavg_winter in [10,22] & Elev in [1k,2k] then present


Rule-set projection back onto the geography space
Model test, overlaying test points evaluating how
those points are predicted
Species Modeling: DesktopGARP
Acknowledgements




FAPESP and NSF
BRC & NHM - The University of Kansas
DesktopGARP Testers & Users
Other Collaborators
DesktopGARP information on-line

Website at:
www.lifemapper.org/desktopgarp

Or Email:
[email protected]
Stay With Us For More GARPing


Next: Lifemapper Project
Demo Session during Lunch Time:
–
–
–

Genetic Algorithms in General
GARP Algorithm
DesktopGARP live demo
In the Afternoon: Many Neat Applications
DesktopGARP
Thank you so much!!
Any questions?