JuliaCon 2023

Evolving Robust Facility Placements
2023-07-26 , Online talks and posters

Climate change is leading to an increase in natural disasters, such as floods and earthquakes, which can damage critical infrastructure like hospitals and schools. To address this problem, we propose a project that uses evolutionary algorithms to design facility placements that are robust to disaster. By using evolutioanary algorthims as a metaheursitc solution to the p-median problem, we are show that our approach leads to facility layouts that are more robust to natural disasters.


As climate change continues to worsen, natural disasters such as floods, storms, and earthquakes are becoming more frequent and destructive. These disasters often destroy or damage critical infrastructure such as hospitals, schools, and shelters, reducing access to essential services for affected populations. To address this problem, our project focuses on evolving facility placements that are robust to disasters, using evolutionary algorithms and highly optimized tolerance (HOT) as a mechanism for design. We show that our evolved facility layouts are more robust to natural disasters than empirical layouts, providing a potential solution to the challenges posed by climate change and other disasters. Our work also highlights the utility of the Julia programming language in scientific computing and specifically in evolutionary computation.

Our work draws on two bodies of literature, the p-median problem and highly optimized tolerance (HOT). We formulate the p-median problem as follows: given N facilities and a heterogeneous population distribution across an area, find the optimal placement of facilities that minimizes the average distance to the nearest facility. No exact analytical solution exists, but approximate solutions show that the optimal facility density should scale as the population density to the 2/3rds power.
We implement an evolutionary algorithm as a metaheuristic solution to the p-median problem. We compare its performance to other metaheuristics found in the literature such as simulated annealing, and show that evolutionary algorithms converge to near-optimal facility locations and follow the analytically predicted 2/3 scaling relationship.
The second body of literature revolves around HOT, a mechanism through which engineered systems become robust to a pattern of perturbations through design. Previous work by Carlson, Doyle, and Zhou applied evolutionary algorithms to a percolation lattice model to demonstrate how complexity and robustness can arise in biological contexts.
We extend this work by applying evolutionary algorithms to evolve robust facility locations. We introduce perturbations in the form of catastrophes with locations drawn from a distribution over event locations. All facilities within a specified radius of the catastrophe are eliminated. These catastrophes mimic natural disasters, targeted attacks, or random failures. A robust facility layout minimizes the drop in fitness due to catastrophes. We evolve our facility layout with perturbations. Every generation we apply a set amount of catastrophes to each individual within our population before we evaluate the fitness. We show that the facility layouts evolved with perturbations are more robust than layouts evolved without perturbations. The average decrease in fitness due to a catastrophe is lower in facility layouts evolved with perturbations. We also show that evolutionary algorithms are a viable alternative to simulated annealing in the rugged landscape induced by the stochastic nature of the perturbations. We compare evolution to empirical data and show that our evolved facility layouts are more robust to natural disasters than empirical layouts. This work has the potential to improve the resilience of critical infrastructure to climate change.
We wrote our own evolutionary framework for this project that allows for the introduction of perturbations to the genome during evolution. While evolutionary computation packages exist in Julia, to our knowledge none allow for perturbation during the evolutionary process. This is a contribution to the community because the framework is general and extensible and could be applied to a diverse array of other problems.
Our project makes novel use of Julia's ecosystem of geospatial packages in its application to evolutionary algorithms. The speed of the Julia language is essential. Our algorithm involves tens of thousands of nearest-neighbor assessments for each individual every generation. This computation is prohibitively slow in Python. By leveraging static arrays and Julia's ample multiprocessing capabilities, we were able to make our code several orders of magnitude faster than its Python equivalent. Julia allowed us to implement a full-scale version of our evolutionary algorithm even though relatively little computational power was available to us. As such, our project is a demonstration of the incredible utility of the Julia programming language in scientific computing and specifically in evolutionary computation.

We are graduate students in complex systems science at the University of Vermont. Our interests include cool data science projects and having fun with epistemology.

Alex Friedrichsen is a Master's student in the Complex Systems Center of the University of Vermont studying Data Science and Complex Systems. I graduated with my bachelor's degree in Data Science in the spring of 2022 through the Honors College at UVM while taking accelerated master's classes. I am currently doing research in multiple labs here at UVM including most recently the Social-Ecological Gaming and Simulation (SEGS) lab.

Some of my interests include game theory, music, agent-based models, evolutionary computation, philosophy of mind and chaos theory! I enjoy both technical and holistic learning experiences. I am a huge proponent of habits and routine to promote daily flexiblity through self-automation. I love to read about self-improvement, behavioral economics, theory versus action, and fantasy! I try to optimize and strategize everything.

Currently open to work.