Memetic Algorithms for Spatial Partitioning Problems
Memetic Algorithms for Spatial Partitioning Problems
复制标题
空间分区问题的模因算法
DOI：
10.1145/3544779
复制
发表时间：
2023
影响因子：
1.9
通讯作者：
Ramakrishnan, Naren
中科院分区：
文献类型：
--
作者：
Biswas, Subhodip;Chen, Fanglan;Chen, Zhiqian;Lu, Chang-Tien;Ramakrishnan, Naren
空间优化问题（SOP）的特点是空间关系的决策变量，目标，和/或约束函数。在这篇文章中，我们专注于一个特定类型的SOP称为空间分区，这是一个组合问题，由于离散空间单元的存在。精确的优化方法不随问题的大小而变化，特别是在可行的时间限制内。这促使我们开发基于人群的元分析来解决此类SOP。然而，这些基于种群的方法所采用的搜索算子大多是针对实参数连续优化问题而设计的。为了使这些方法适应SOP，我们应用领域知识设计空间感知搜索算子，在保持空间约束的同时有效地搜索离散搜索空间。为此，我们提出了一个简单而有效的算法称为swarm为基础的空间模因算法（SPATIAL），并测试它的学校（重）分区问题。详细的实验研究在真实世界的数据集上进行评估的性能SPATIAL。此外，还进行了消融研究，以了解SPATIAL各个组件的作用。此外，我们还讨论了空间是如何帮助在现实生活中的规划过程中，其适用于不同的场景和激励未来的研究方向。
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 calledswarm-based spatial memeticalgorithm (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.
登录
查看更多内容
研究动态
影响因子：
--
作者：
Blenerhassitt E. Buitendach;Elizabeth Erasmus;J. Conradie;J. W. Niemantsverdriet;Heinrich Lang;J. Swarts
通讯作者：
J. Swarts
托布勒定律和空间优化
DOI：
--
发表时间：
2018
期刊：
影响因子：
--
作者：
R. Church
通讯作者：
R. Church
将领域知识融入模因算法中以解决空间优化问题
DOI：
10.1145/3397536.3422265
发表时间：
2020
期刊：
Proceedings of the 28th International Conference on Advances in Geographic Information Systems
影响因子：
--
作者：
Subhodip Biswas;Fanglan Chen;Zhiqian Chen;Chang;Naren Ramakrishnan
通讯作者：
Naren Ramakrishnan
影响因子：
4.8
作者：
F. Glover;Jin-Kao Hao
通讯作者：
F. Glover;Jin-Kao Hao
简化的两党计算机重新划分
DOI：
--
发表时间：
1965
期刊：
影响因子：
--
作者：
S. Nagel
通讯作者：
S. Nagel