Download Talk - DDDAS.org

Applying a Dynamic Data Driven
Genetic Algorithm to Improve
Forest Fire Spread Prediction
Mónica Denham, Ana Cortés, Tomàs Margalef and Emilio Luque
[email protected], {ana.cortes,tomas.margalef,emilio.luque}@uab.es
Computer Architecture &
Operating Systems Department
Content

Problem.

Method description.

Dynamic Data Driven Genetic Algorithm:
 Analytical Method.

Experiments and Results.

Conclusions.
Problem
Initial fire
Terrain slope
Terrain vegetation
Wind direction
Wind velocity
Live fuel moisture
Dead fuel moisture
Uncertainty source
Fire behavior
Simulator
Content

Problem.

Method description.

Dynamic Data Driven Genetic Algorithm.
 Analytical Method.

Experiments and Results.

Conclusions.
Method Description (I)
Prediction (ti+1)
Init (ti)
Fire
Simulator
real
spread
input parameters
Calibration (ti+1)
Init (ti)
Fire
Simulator
Fire
Best set of Simulator
parameters
¿
input parameters
Prediction (ti+2)
real
spread
*
Method Description (II)
Calibration (ti+1)
Init (ti)
Best set of
parameters
Fire
Simulator
multiple scenarios
huge search space
Genetic Algorithm
Fire
Simulator
¿
inputslope
parameters
Terrain
(static)
Terrain vegetation (static)
Wind direction (dynamic)
Wind velocity (dynamic)
Live fuel humidity (dynamic)
Dead fuel humidity (dynamics)
(1h, 10hs, 100hs)
Prediction (ti+2)
real
spread
master
Population dealing
worker0
simulation
comparison
Population gathering
Genetic Operators
workern
simulation
comparison
*
Content

Problem.

Method description.

Dynamic Data Driven Genetic Algorithm:
 Analytical Method.

Experiments and Results.

Conclusions.
Dynamic Data Driven Genetic
Algorithm (I)
DDDAS: ability to dynamically incorporate additional
data into an execution application, and in reverse,
ability of an application to dynamically steer
the measurement process (F. Darema).
Improving simulations
at Calibration stage
and improving
overall Prediction
process results
Analyzing real
fire spread
(Real fire spread at ti+1)
We can
Inject better
parameter values
Dynamic Data Driven Genetic
Algorithm (II)

Due to main fire physics
aspects, wind and slope
determine fire spread main
conditions:
Using fire and slope
characteristics we
can estimate wind
values to imitate
real fire spread
wind
fire
fire
wind
slope


slope
We know slope main
characteristics.
Due to Calibration stage
requirements we dispose fire
spread information from
instant ti to ti+1.
We had proposed a method that calculates ideal wind characteristics,
with which, in combination with slope aspects, achieves fire propagation
like fire spread observed at instant ti+1.
Dynamic Data Driven Genetic
Algorithm: Analytical Method (III)
Analytical Method:

Simulator uses slope and wind characteristics to calculate fire spread
characteristics. Simulator treats slope and wind as vectors.

We use simulator idea to calculate wind characteristics from slope and spread
characteristics.
X = Rs cos(β) + Rw cos(α)
Real map:
Simulator:
x, y Y = Rs sin(β) + Rw sin(α)
Rw
α
Rs
β
Where:
Rs : slope factor
we know X, Y,
β: slope direction
we have (Rs y β)
Rw: wind factor
α: wind direction
We can calculate wind
direction and speed
(Rw y α )
Isolating from the equations:
α = arctan ( y - Rs sin(β) )
( x - Rs cos(β) )
Rw =
( x - Rs cos(β) )
cos(α)
Dynamic Data Driven Genetic
Algorithm (IV)
Calibration (ti+1)
Init (ti)
Fire
Simulator
input slope
parameters
Terrain
Terrain vegetation
Wind direction
Wind velocity
Live fuel moisture
Dead fuel moisture
(1h, 10hs, 100hs)
wind
max
slope
real
spread
Genetic Algorithm
Selection - Elitism
Crossover
Mutation
*
Content

Problem.

Method description.

Dynamic Data Driven Genetic Algorithm.

Analytical Method.

Experiments and Results.

Conclusions.
Experiments & Results (I)
•
DDD Genetic Algorithm reduces
error for both Calibration and
Prediction stages.
•
Prediction stage shows bigger errors
(this stage works with calibration best
individual for previous time step).
Experiments & Results (II)
•
DDD Genetic Algorithm reduces
error for both Calibration and
Prediction stages.
Experiments & Results (III)
•
•
•
Real map: fire behavior is different
through time steps.
Errors are bigger than previous maps
(synthetic maps).
Errors are similar for different
configurations of our method.
Content

Problem.

Method description.

Dynamic Data Driven Genetic Algorithm.

Analytical Method.

Experimentation and Results.

Conclusions.
Conclusions

Calibration and Prediction stages have shown expected behavior.

We have used these techniques for real and synthetic burnings.
Proposed methods shown good performance.

Using DDD Genetic Algorithm we could improve whole prediction
process quality for synthetic cases.

Although real fires are our main objective, synthetic cases are the
first step for understanding and improving steering methods.

Real fires characteristics are more difficult to simulate. Simulators
implement abstractions of reality. We are working in this topic now.
Applying a Dynamic Data Driven
Genetic Algorithm to Improve
Forest Fire Spread Prediction
Thanks
[email protected], {ana.cortes,tomas.margalef,emilio.luque}@uab.es
Computer Architecture &
Operating Systems Department

Pseudocódigos.

Fórmulas



Fitness - Error / Volver.
Viento / Volver.
Pendiente / Volver.
Pseudocódigo:
Algoritmo Genético
void evolute(gentype * gen) {
double totfitc;
gen->num++;
newgen.num = gen->num;
cal_fit( gen ,&totfitc);
nsort(gen);
//keep_best(gen);
indcpy(&newgen.gen[0],*get_best());
indcpy(&newgen.gen[1],gen->gen[1]);
Volver
while (i<=(gen->size -2)) {
int p1 =select(totfitc, gen);
int p2 =select(totfitc, gen);
crossover(gen->gen[p1],gen->gen[p2],
&newgen.gen[i], &newgen.gen[i+1]);
/*mutation */
mutate(&newgen.gen[i], lmin,lmax);
mutate(&newgen.gen[i+1],lmin,lmax);
/ /* stay in the limites */
clip(&newgen.gen[i]);
clip(&newgen.gen[i+1]);
// next
i = i+2;
}
Pseudocódigo:
Algoritmo Genético (cont.)
int select( double totfitc,gentype * gen)
{
void crossover(indvtype og1, indvtype og2,indvtype *
ng1,indvtype * ng2) {
double cros =rand() % 1000;
if (cros <= crosp) //si se supera la probabilidad se cruzan
{
crospoint = (int) rand()% og1.n;
for(int i=0;i<crospoint;i++)
{
ng1->p[i] = og1.p[i];
ng2->p[i] =(og2.p[i]+og1.p[i])/2;
}
for(int i=crospoint;i<og1.n;i++)
{
ng1->p[i] =(og2.p[i]+og1.p[i])/2;
ng2->p[i] =og2.p[i];
}
}
else // se copian directamente los padres a los hijos
{
indcpy(ng1,og1);
indcpy(ng2,og2);
}
double r = random * totfitc;
p=0;
sumfit=0;
while((sumfit <= r)&&(p<gen->size))
sumfit += gen->gen[p++].fitc;
p--;
return p;
}
Volver
}
Viento








Sigma = acumulación de la contribución a la intensidad de reacción (modelo
comb.)
Beta = acumulación carga/densidad de todas las partículas del modelo.
betaOpt = 3.348 / sigma0.8189
Ratio = beta/betaOpt
c = 7.47 * exp(-0.133 * sigma0.55))
e = 0.715 * exp(-0.000359 * sigma)
WindK = c * ratio-e
WindB = 0.02526 * sigma0.54

Fuel_PhiWind = WindK * windSpeedWindB

Rw = Fuel_Spread0() * Fuel_PhiWind
Volver
Depende del individuo
Depende del modelo
de combustible
Pendiente
Beta = acumulación carga/densidad de todas las partículas del modelo.


SlopeK = 5.275 * beta-0.3

Fuel_PhiSlope = SlopeK * Slope2

Rs = Fuel_Spread0() * Fuel_PhiSlope
Depende del individuo
Volver
Depende del modelo
de combustible
Algoritmo Genético
Algoritmo inspirado en la selección natural y en la genética.
- Trabaja sobre una población de individuos.
- De forma iterativa, se evoluciona la población mediante las operaciones de:
- Selección: competición de los individuos candidatos: los mejores individuos tienen
mayor probabilidad de generar nuevos individuos. Función de evaluación. Elitismo.
- Crossover: bajo una probabilidad se elije un crosspoint y los hijos reciben una parte
de cada padre.
- Mutación: bajo una probabilidad se muta el valor de un “cromosoma”.
Población
Nueva Población
Elitismo = 2
Crossover:
CrossPoint
Padre 1
hijo1
Padre 2
hijo2
mutación
Volver
Fitness - Error
∩)
Error =
∩ - Init
∩
Fitness =
- Init
- Init) - (∩ - Init)
Real –Init
Volver