Memetic algorithms for Spatial Partitioning problems

• URL: http://arxiv.org/abs/2208.02867v1
• Date: Thu, 4 Aug 2022 20:05:46 GMT
• Title: Memetic algorithms for Spatial Partitioning problems
• Authors: Subhodip Biswas, Fanglan Chen, Zhiqian Chen, Chang-Tien Lu and Naren Ramakrishnan
• Abstract summary: In this article, we focus on a specific type of SOP called spatial partitioning on real-world datasets. We put forward a simple yet effective algorithm called swarm-based spatial memetic algorithm (SPATIAL) and test it on the school (re)districting problem.
• Score: 26.73720392872553
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Reclaiming the Source of Programmatic Policies: Programmatic versus Latent Spaces [10.654876600946865]
  We show that the programmatic space presents values for the behavior loss similar to those observed in latent spaces. Algorithms searching in the programmatic space significantly outperform those in LEAPS and HPRL.
  arXiv  Detail & Related papers  (2024-10-16T02:10:04Z)
• On Probabilistic Embeddings in Optimal Dimension Reduction [1.2085509610251701]
  Dimension reduction algorithms are a crucial part of many data science pipelines. Despite their wide utilization, many non-linear dimension reduction algorithms are poorly understood from a theoretical perspective.
  arXiv  Detail & Related papers  (2024-08-05T12:46:21Z)
• Combinatorial Optimization with Policy Adaptation using Latent Space Search [44.12073954093942]
  We present a novel approach for designing performant algorithms to solve complex, typically NP-hard, problems. We show that our search strategy outperforms state-of-the-art approaches on 11 standard benchmarking tasks.
  arXiv  Detail & Related papers  (2023-11-13T12:24:54Z)
• AI planning in the imagination: High-level planning on learned abstract search spaces [68.75684174531962]
  We propose a new method, called PiZero, that gives an agent the ability to plan in an abstract search space that the agent learns during training. We evaluate our method on multiple domains, including the traveling salesman problem, Sokoban, 2048, the facility location problem, and Pacman.
  arXiv  Detail & Related papers  (2023-08-16T22:47:16Z)
• Efficient Model-Free Exploration in Low-Rank MDPs [76.87340323826945]
  Low-Rank Markov Decision Processes offer a simple, yet expressive framework for RL with function approximation. Existing algorithms are either (1) computationally intractable, or (2) reliant upon restrictive statistical assumptions. We propose the first provably sample-efficient algorithm for exploration in Low-Rank MDPs.
  arXiv  Detail & Related papers  (2023-07-08T15:41:48Z)
• Efficient Sensor Placement from Regression with Sparse Gaussian Processes in Continuous and Discrete Spaces [3.729242965449096]
  The sensor placement problem is a common problem that arises when monitoring correlated phenomena. We present a novel formulation to the SP problem based on variational approximation that can be optimized using gradient descent.
  arXiv  Detail & Related papers  (2023-02-28T19:10:12Z)
• Region-Based Semantic Factorization in GANs [67.90498535507106]
  We present a highly efficient algorithm to factorize the latent semantics learned by Generative Adversarial Networks (GANs) concerning an arbitrary image region. Through an appropriately defined generalized Rayleigh quotient, we solve such a problem without any annotations or training. Experimental results on various state-of-the-art GAN models demonstrate the effectiveness of our approach.
  arXiv  Detail & Related papers  (2022-02-19T17:46:02Z)
• Learning Space Partitions for Path Planning [54.475949279050596]
  PlaLaM outperforms existing path planning methods in 2D navigation tasks, especially in the presence of difficult-to-escape local optima. These gains transfer to highly multimodal real-world tasks, where we outperform strong baselines in compiler phase ordering by up to 245% and in molecular design by up to 0.4 on properties on a 0-1 scale.
  arXiv  Detail & Related papers  (2021-06-19T18:06:11Z)
• Spatio-temporal Sequence Prediction with Point Processes and Self-organizing Decision Trees [0.0]
  We study the partitioning-temporal prediction problem introduce a point-process-based prediction algorithm. Our algorithm can jointly learn the spatial event and the interaction between these regions through a gradient-based optimization procedure. We compare our approach with state-of-the-art deep learning-based approaches, where we achieve significant performance improvements.
  arXiv  Detail & Related papers  (2020-06-25T14:04:55Z)
• Localized active learning of Gaussian process state space models [63.97366815968177]
  A globally accurate model is not required to achieve good performance in many common control applications. We propose an active learning strategy for Gaussian process state space models that aims to obtain an accurate model on a bounded subset of the state-action space. By employing model predictive control, the proposed technique integrates information collected during exploration and adaptively improves its exploration strategy.
  arXiv  Detail & Related papers  (2020-05-04T05:35:02Z)
• Discrete Action On-Policy Learning with Action-Value Critic [72.20609919995086]
  Reinforcement learning (RL) in discrete action space is ubiquitous in real-world applications, but its complexity grows exponentially with the action-space dimension. We construct a critic to estimate action-value functions, apply it on correlated actions, and combine these critic estimated action values to control the variance of gradient estimation. These efforts result in a new discrete action on-policy RL algorithm that empirically outperforms related on-policy algorithms relying on variance control techniques.
  arXiv  Detail & Related papers  (2020-02-10T04:23:09Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.