Show code
knitr::opts_chunk$set(message = FALSE,
warning = FALSE
#cache = TRUE
)
source("functions.R")
# TODO change order
maps <- c('520','533','751','519','534')
maps <- c('533','519','751','534','520')ESS-NS Experimentation
Supplementary Material
Introduction
This notebook, source code and data are provided as additional material for the paper “Evolutionary Statistical System with Novelty Search: a Parallel Metaheuristic for Uncertainty Reduction Applied to Wildfire Spread Prediction”. This report contains the same results published in the paper, with slight modifications and additional tools that allow for better visualization and exploration of those results.
The first two sections have both a static and an interactive version of the code. The plots shown by default are from the interactive version, made using R with the plotly package.
The repository with the primary data and the source code is available at https://github.com/jstrappa/ess-ns-supplementary. The complete source code can be seen by opening the source for this notebook in an editor, together with the functions.R script, which contains most of the code for static plots.
License
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License.
Experimentation
Preliminary requirements
Results
Average Fitness: ESS-NS vs ESS, ESSIM-EA, and ESSIM-DE
All methods are compared over 5 cases of controlled fires, labeled by numbers (751, 520, 533, 519, 534). The x-axis corresponds to prediction steps, while the y-axis shows the average fitness for each step.
Show static version code
# Static version
for (mapn in maps){
csvname <- c("../data/all_fitness_",mapn,".csv")
fitness_filename <- paste(csvname, collapse="")
plot_fitness_averages(maps, fitness_filename, save = FALSE)
}Show interactive version code (plotly)
# Interactive version
plotlist = list()
i = 1
for (mapn in maps) {
csvname <- c("../data/all_fitness_", mapn, ".csv")
fitness_filename <- paste(csvname, collapse = "")
# 30 seeds + 2 columns for method and step number
limit = 32
# Read csv with fitness for every method, step and seed
fitness_all_seeds = read_delim(
fitness_filename,
col_names = TRUE,
show_col_types = FALSE,
skip = 1,
delim = ','
)
# There are some missing values in previous results. Replace zeros with NA
fitness_all_seeds <-
fitness_all_seeds %>% mutate(across(3:limit, ~ na_if(., 0)))
# Convert to factor and define order of levels
# Makes it easier to use the palette as intended for plotting
fitness_all_seeds$method <- factor(fitness_all_seeds$method,
levels = c("ESS-NS", "ESSIM-EA",
"ESSIM-DE", "ESS"))
# Compute mean and standard deviation. Omit NAs
fitness_all_seeds_mean <- fitness_all_seeds %>%
rowwise() %>%
mutate(m = mean(c_across(3:limit), na.rm = TRUE),
sd = sd(c_across(3:limit), na.rm = TRUE))
# Plot average fitness
p <-
ggplot(data = fitness_all_seeds_mean, aes(
group = method,
colour = method,
shape = method
)) +
geom_line(data = fitness_all_seeds_mean, aes(x = step, y = m),
size = 1.5) +
geom_point(data = fitness_all_seeds_mean, aes(x = step, y = m),
size = 4) + # size of points
scale_color_manual(values = cbp) +
ylab("average fitness\n") + # y axis label
scale_x_discrete(name = "prediction step",
limits = unique(as.vector(fitness_all_seeds_mean$step))) +
scale_y_continuous(limits = c(0.25, 1), breaks = seq(0, 1, 0.1)) +
theme(
text = element_text(size = 16),
panel.grid.minor = element_line(
colour = "lightgray",
linetype = "solid",
size = 0.3
),
panel.grid.major = element_line(
colour = "lightgray",
linetype = "solid",
size = 0.6
)
) +
theme(plot.margin = unit(c(1,1,2.5,1), "cm")) + # to have a little more space between plots
ggtitle(mapn) # for the main title
plotlist[[i]] = ggplotly(p, height = 600, tooltip = c("step","m"))
i = i + 1
}Fitness distribution
Fitness distribution for the 30 repetitions of each run. Each method is shown in a different color. Column number corresponds to prediction step. The y-axis corresponds to the fitness value.
Show static version code
# Static version
for (mapn in maps) {
csvname <- c("../data/all_fitness_", mapn, ".csv")
fitness_filename <- paste(csvname, collapse = "")
plot_fitness_distribution(maps,
fitness_filename,
save = FALSE,
jitter = TRUE)
}Show interactive version code (plotly)
# Interactive version
jitter = FALSE
plotlist_d = list()
i = 1
for (mapn in maps) {
csvname <- c("../data/all_fitness_", mapn, ".csv")
fitness_filename <- paste(csvname, collapse = "")
# 30 seeds + 2 columns for method and step number
limit = 32
# Read csv with fitness for every method, step and seed
fitness_all_seeds = read_delim(
fitness_filename,
col_names = TRUE,
show_col_types = FALSE,
skip = 1,
delim = ','
)
# Replace missing values (coded as 0 in the csv) by NAs
fitness_all_seeds <-
fitness_all_seeds %>% mutate(across(3:limit, ~ na_if(., 0)))
# Convert to factor and define order of levels
# Makes it easier to use the palette as intended for plotting
fitness_all_seeds$method <-
factor(fitness_all_seeds$method,
levels = c("ESS-NS", "ESSIM-EA", "ESSIM-DE", "ESS"))
df <- gather(fitness_all_seeds, "seed", "fitness", 3:limit) %>%
select(-seed)
# Plot, omit NAs.
p <- ggplot(df %>% filter(!is.na(method)),
aes(
x = method,
y = fitness,
color = method,
group = method
)) +
facet_wrap( ~ step, nrow = 1) + # one column per prediction step
scale_color_manual(values = cbp) +
theme(
text = element_text(size = 16),
axis.text.x = element_text(
angle = 45,
hjust = 1,
size = 10,
color = cbp
),
axis.title.x = element_text(
margin = margin(t = 18)
)
) +
theme(plot.margin = unit(c(0.5,0.5,2,0.5), "cm")) +
ggtitle(mapn) # for the main title
if (jitter) {
p <-
p + geom_boxplot(outlier.shape = NA) + # avoid duplicating outliers
geom_jitter()
} else {
p <- p + geom_boxplot()
}
p <- plotly_build(p)
plotlist_d[[i]] = p
i = i + 1
}Appendix: Calibration
Description of the experiment
Calibration was performed by varying two parameters: tournament probability and mutation probability.
The values vary among the following:
\(tour\_prob \in \{ 0.75, 0.8, 0.85, 0.9 \}\)
\(mut\_prob \in \{ 0.1, 0.2, 0.3, 0.4 \}\)
Results
Fitness averages over different combinations of parameters
There is one table for each controlled fire. In each table, the rows show the fitness values, averaged over 30 repetitions, for a particular configuration of the parameters. For columns labeled by numbers, the number indicates the prediction step. The \(m\) column is the average fitness over all steps, and the last column, \(t (s)\), shows total runtime values in seconds. The runtimes for each repetition correspond to the whole execution (including all steps); the runtimes shown are averaged over 30 repetitions. The darker the color, the better the results, both for quality (fitness) and runtimes.
| 1 | 2 | 3 | 4 | m | t (s) | |
|---|---|---|---|---|---|---|
| 0.75, 0.1 | 0.672 | 0.675 | 0.731 | 0.696 | 0.694 | 2122.970 |
| 1 | 2 | 3 | m | t (s) | |
|---|---|---|---|---|---|
| 0.75, 0.1 | 0.886 | 0.931 | 0.783 | 0.867 | 1738.670 |
| 1 | 2 | 3 | m | t (s) | |
|---|---|---|---|---|---|
| 0.75, 0.1 | 0.893 | 0.888 | 0.805 | 0.862 | 992.433 |
| 1 | 2 | 3 | 4 | 5 | m | t (s) | |
|---|---|---|---|---|---|---|---|
| 0.75, 0.1 | 0.738 | 0.573 | 0.588 | 0.804 | 0.768 | 0.694 | 1593.330 |
| 1 | 2 | 3 | 4 | 5 | m | t (s) | |
|---|---|---|---|---|---|---|---|
| 0.75, 0.1 | 0.879 | 0.720 | 0.864 | 0.817 | 0.883 | 0.833 | 2813.000 |
We computed the mean squared error (MSE) for each combination, using \(1-\bar{f}\) (where \(\bar{f}\) is the average fitness over all prediction steps, shown in column \(m\) in the tables above) as the error. Formally, for each combination of parameters \(\{tour\_prob,mut\_prob\}\), we computed:
\[\begin{equation}\label{eq:mse} MSE_{tour,mut} = \frac{1}{n}{\sum_{i=1}^n{(1 - \bar{f}_i)^2}} \end{equation}\]
where \(\bar{f}_i\) is the fitness average over all steps for each map, and \(n\) is the number of experiments, in this case, 5, corresponding to the 5 controlled fires.
The best combination by this criterion is:
Show code
means <- means_and_configs[[1]]
configurations <- means_and_configs[[2]]
errors <- (1 - means) ^ 2
mse_data <-
as.data.frame(errors) %>% rowwise %>% mutate(mse = mean(c_across(1:5)))
best <- which.min(mse_data$mse)
print(configurations[best])[1] "0.75, 0.4"Runtime analysis
The jitter (small black dots) shows the distribution of ESS-NS results for the 16 parameter combinations. The bigger black dots are the average runtime of ESS-NS over these combinations. The remaining points (in different shapes and colors) represent the average runtimes for ESS, ESSIM-EA and ESSIM-DE over 30 repetitions. Each label on the x-axis is a different controlled fire case. The y-axis is the runtime in human-readable format (hours, minutes, seconds).
Show code for interactive version
library(scales)
library(lubridate)
competitors <-
read_csv(
"../data/runtimes_competitors.csv",
col_names = TRUE,
col_types = list(col_character(), col_guess(), col_guess(), col_guess())
)
competitors <- competitors %>% mutate(map = factor(map, levels=maps)) #%>%
tournament_parameters = c("0.75", "0.8", "0.85", "0.9")
mutation_parameters = c("0.1", "0.2", "0.3", "0.4")
n_configurations = length(tournament_parameters) * length(mutation_parameters)
data <-
tibble(map = factor(),
t = numeric(),
h = vctrs::new_duration(1))
for (mapn in maps) {
for (tour in tournament_parameters) {
for (mut in mutation_parameters) {
timesname = c(
"../data/calibration_results/",
mapn,
"/avg_execution_time_",
tour,
"_MUT",
mut,
".csv"
)
runtime = read_csv(
paste(timesname, collapse = ""),
col_names = c("map", "t", "h"),
col_types = list(col_character(), col_double(), col_guess())
)
runtime <- runtime %>% mutate(map = factor(map))
data <- add_row(data, runtime)
}
}
}
data <- data %>% rename('time' = h)
data$time <- seconds_to_period(data$t)
ns_times <- data %>%
group_by(map) %>%
summarise(across(t, mean)) %>%
mutate(map = fct_reorder(map, maps))
all_times <- competitors %>% add_column("ESS-NS" = ns_times$t, .before = "ESSIM-EA")
# Convert to longer format for plotting
d <- melt(all_times, id.vars="map", value.name = "time") %>% rename(method = variable)
#Time conversions
d$time <- round(seconds_to_period(d$time))
data$time <- round(seconds_to_period(data$t))
# Plot runtime averages
p <-ggplot(d, aes(map, time, col=d$method), show.legend = FALSE) +
geom_point(size = 4, aes(shape = method)) +
scale_y_time(breaks = date_breaks('30 min'), labels = date_format('%H:%M')) +
theme(text = element_text(size = 16)) +
geom_jitter(data = data, aes(x=map,y=time), color = cbp[1], show.legend = FALSE) +
scale_color_manual(values = cbp) +
ylab("execution time\n\n\n\n\n\n") +
ggtitle("Runtime distribution for ESS-NS") +
guides(color = guide_legend(title = ""))
#ggplotly(p)
ggplotly(p, tooltip = c("method", "map", "time"))Funding and Acknowledgments
This supplementary material and the corresponding article have been supported by:
- Universidad Tecnológica Nacional under the project SIUTIME0007840TC,
- FONCyT (Fondo para la Investigación Científica y Tecnológica, Agencia Nacional de Promoción de la Investigación, el Desarrollo Tecnológico y la Innovación, Argentina) under the project UUMM-2019-00042,
- CONICET (Consejo Nacional de Investigaciones Científicas y Técnicas) through a postdoctoral scholarship for the first author.
We wish to thank María Laura Tardivo (ORCiD ID: 0000-0003-1268-7367, Universidad Nacional de Río Cuarto, Argentina) for providing primary results for the fitness and average runtimes of the methods ESS, ESSIM-EA and ESSIM-DE. These results were first published in summarized form in (Tardivo, Caymes Scutari, Bianchini, Méndez Garabetti, Cencerrado, et al. 2017) and (Tardivo, n.d., chap. 5), and are used here with her permission.
Thanks are also due to the LIDIC laboratory (Laboratorio de Investigación y Desarrollo en Inteligencia Computacional), Universidad Nacional de San Luis, Argentina, for providing the hardware equipment for the experimentation.
References
Bianchini, Germán, Paola Caymes-Scutari, and Miguel Méndez Garabetti. 2015. “Evolutionary-Statistical System: A Parallel Method for Improving Forest Fire Spread Prediction.” Journal of Computational Science 6 (January): 58–66. https://doi.org/10.1016/j.jocs.2014.12.001.
Caymes Scutari, Paola, María Laura Tardivo, Germán Bianchini, and Miguel Méndez Garabetti. 2020. “Dynamic Tuning of a Forest Fire Prediction Parallel Method.” In Computer Science CACIC 2019, edited by Patricia Pesado and Marcelo Arroyo, 1184:19–34. Cham: Springer International Publishing. https://doi.org/10.1007/978-3-030-48325-8_2.
Méndez Garabetti, Miguel, Germán Bianchini, Paola Caymes Scutari, María Laura Tardivo, and Verónica Gil Costa. 2017. “ESSIM-EA Applied to Wildfire Prediction Using Heterogeneous Configuration for Evolutionary Parameters.” XXIII Congreso Argentino de Ciencias de La Computación, 10.
Méndez Garabetti, Miguel, Germán Bianchini, María Laura Tardivo, and Paola Caymes Scutari. 2015. “Comparative Analysis of Performance and Quality of Prediction Between ESS and ESS-IM.” Electronic Notes in Theoretical Computer Science 314 (June): 45–60. https://doi.org/10.1016/j.entcs.2015.05.004.
Strappa, Jan, Paola Caymes-Scutari, and Germán Bianchini. 2022. “A Parallel Novelty Search Metaheuristic Applied to a Wildfire Prediction System.” In 2022 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), 798–806. Lyon, France: IEEE Computer Society. https://doi.org/10.1109/IPDPSW55747.2022.00134.
Tardivo, María Laura. n.d. “Paralelización Y Sintonización De Evolución Diferencial Aplicada a Un Método De Reducción De Incertidumbre Para La Predicción De Incendios Forestales.” PhD thesis.
Tardivo, María Laura, Paola Caymes Scutari, Germán Bianchini, and Miguel Méndez Garabetti. 2017. “Hierarchical Parallel Model for Improving Performance on Differential Evolution: Hierarchical Parallel Model for Improving Performance on Differential Evolution.” Concurrency and Computation: Practice and Experience 29 (10): e4087. https://doi.org/10.1002/cpe.4087.
Tardivo, María Laura, Paola Caymes Scutari, Germán Bianchini, Miguel Méndez Garabetti, Andrés Cencerrado, and Ana Cortés. 2017. “A Comparative Study of Evolutionary Statistical Methods for Uncertainty Reduction in Forest Fire Propagation Prediction.” Procedia Computer Science 108: 2018–27. https://doi.org/10.1016/j.procs.2017.05.252.
Tardivo, María Laura, Paola Caymes Scutari, Miguel Méndez Garabetti, and Germán Bianchini. 2018. “Optimization for an Uncertainty Reduction Method Applied to Forest Fires Spread Prediction.” In Computer Science CACIC 2017, edited by Armando Eduardo De Giusti, 790:13–23. Cham: Springer International Publishing. https://doi.org/10.1007/978-3-319-75214-3_2.