Incorporating domain knowledge into Memetic Algorithms for solving Spatial Optimization problems
Incorporating domain knowledge into Memetic Algorithms for solving Spatial Optimization problems
复制标题
将领域知识融入模因算法中以解决空间优化问题
DOI：
10.1145/3397536.3422265
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Naren Ramakrishnan
中科院分区：
文献类型：
--
作者：
Subhodip Biswas;Fanglan Chen;Zhiqian Chen;Chang;Naren Ramakrishnan
空间优化问题（SOP）的特征在于控制决策变量、目标和/或约束函数的空间关系。由于离散空间单元的存在，这些主要是组合问题（NP难）。因此，精确的优化方法不能在实际的时间约束下最优地解决它们，特别是对于大规模的实例。出于这一挑战，我们探索使用基于人口的元算法来解决SOP。为此，我们观察到，这些方法所采用的搜索移动是适合于实参数连续搜索空间，而不是。为了使它们适应SOP，我们探索了领域知识在设计空间感知搜索算子中的作用，这些算子可以有效地在离散搜索空间中搜索最优解，同时尊重空间约束。这些修改导致一个简单而高效的空间混合元启发式称为空间，这是适用于学校边界形成（也称为学校重划）的问题。真实世界的数据集上的实验结果表明，我们的算法在获得上级质量的解决方案相比，传统的基线方法的功效。此外，我们进行了深入的研究，我们的框架的各个组成部分，并强调我们的方法在吸收其他搜索运营商，以及在适应相关的SOP的灵活性。
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.