Incorporating domain knowledge into Memetic Algorithms for solving Spatial Optimization problems

Subhodip Biswas, Fanglan Chen, Zhiqian Chen, Naren Ramakrishnan

Abstract

Spatial optimization problems (SOPs) are characterized by spatial relationships governing the decision variables, objectives and/or constraint functions. These are mostly combinatorial problems (NP-hard) due to the presence of discrete spatial units. Hence, exact optimization methods cannot solve them optimally under practical time constraints, especially for large-sized instances. Motivated by this challenge, we explore the use of population-based metaheuristics for solving SOPs. To this end, we observe that the search moves employed by these methods are suited to real-parameter continuous search space rather. To adapt them to the SOPs, we explore the role of domain knowledge in designing spatially-aware search operators that can efficiently search for an optimal solution in discrete search space while respecting the spatial constraints. These modifications result in a simple yet highly effective spatial hybrid metaheuristic called SPATIAL, which is applied to the problem of school boundary formation (also called school redistricting). Experimental findings on real-world datasets reveal the efficacy of our algorithm in obtaining superior quality solutions in comparison to traditional baseline methods. Additionally, we perform an in-depth study of the individual components of our framework and highlight the flexibility of our method in assimilating other search operators as well as in adapting it to related SOPs.

Subhodip Biswas, Fanglan Chen, Zhiqian Chen, Chang-Tien Lu, Naren Ramakrishnan: Incorporating domain knowledge into Memetic Algorithms for solving Spatial Optimization problems. SIGSPATIAL/GIS 2020: 25-35