# Memetic algorithms for Spatial Partitioning problems

arXiv: https://arxiv.org/abs/2208.02867 · HTML: https://mlsanity.com/paper/2208.02867/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 104 references that are in the map.
- First posted on arXiv 4 Aug 2022.

## Builds on (most cited first, 4 of 4)

- [Recent Advances in Graph Partitioning](https://mlsanity.com/paper/1311.3144/) (2013)
- [Recombination: A family of Markov chains for redistricting](https://mlsanity.com/paper/1911.05725/) (2019)
- [Redistricting Algorithms](https://mlsanity.com/paper/2011.09504/) (2020)
- [Sampling-based techniques for designing school boundaries](https://mlsanity.com/paper/2206.03703/) (2022)

## Built on by (most cited first, 1 of 1)

- [ATM-R: An Adaptive Tradeoff Model with Reference Points for Constrained Multiobjective Evolutionary Optimization](https://mlsanity.com/paper/2301.03317/) (2023)

## Abstract (arXiv)

Spatial optimization problems (SOPs) are characterized by spatial relationships governing the decision variables, objectives, and/or constraint functions. In this article, we focus on a specific type of SOP called spatial partitioning, which is a combinatorial problem due to the presence of discrete spatial units. Exact optimization methods do not scale with the size of the problem, especially within practicable time limits. This motivated us to develop population-based metaheuristics for solving such SOPs. However, the search operators employed by these population-based methods are mostly designed for real-parameter continuous optimization problems. For adapting these methods to SOPs, we apply domain knowledge in designing spatially-aware search operators for efficiently searching through the discrete search space while preserving the spatial constraints. To this end, we put forward a simple yet effective algorithm called swarm-based spatial memetic algorithm (SPATIAL) and test it on the school (re)districting problem. Detailed experimental investigations are performed on real-world datasets to evaluate the performance of SPATIAL. Besides, ablation studies are performed to understand the role of the individual components of SPATIAL. Additionally, we discuss how SPATIAL~is helpful in the real-life planning process and its applicability to different scenarios and motivate future research directions.