A RankNet-Inspired Surrogate-Assisted Hybrid Metaheuristic for Expensive Coverage Optimization

• URL: http://arxiv.org/abs/2501.07375v1
• Date: Mon, 13 Jan 2025 14:49:05 GMT
• Title: A RankNet-Inspired Surrogate-Assisted Hybrid Metaheuristic for Expensive Coverage Optimization
• Authors: Tongyu Wu, Changhao Miao, Yuntian Zhang, Chen Chen,
• Abstract summary: We propose a RankNet-Inspired Surrogate-assisted Hybrid Metaheuristic (RI-SHM) Our algorithm can effectively handle large-scale coverage optimization tasks of up to 300 dimensions and more than 1,800 targets within desirable runtime. Compared to state-of-the-art algorithms for EMVOPs, RI-SHM consistently outperforms them by up to 56.5$%$ across all tested instances.
• Score: 3.470566170862975
• License:
• Abstract: Coverage optimization generally involves deploying a set of facilities (e.g., sensors) to best satisfy the demands of specified points, with wide applications in fields such as location science and sensor networks. In practical applications, coverage optimization focuses on target coverage, which is typically formulated as Mixed-Variable Optimization Problems (MVOPs) due to complex real-world constraints. Meanwhile, high-fidelity discretization and visibility analysis may bring additional calculations, which significantly increases the computational cost. These factors pose significant challenges for fitness evaluations (FEs) in canonical Evolutionary Algorithms (EAs), and evolve the coverage problem into an Expensive Mixed-Variable Optimization Problem (EMVOP). To address these issues, we propose the RankNet-Inspired Surrogate-assisted Hybrid Metaheuristic (RI-SHM), an extension of our previous work. RI-SHM integrates three key components: (1) a RankNet-based pairwise global surrogate that innovatively predicts rankings between pairs of individuals, bypassing the challenges of fitness estimation in discontinuous solution space; (2) a surrogate-assisted local Estimation of Distribution Algorithm (EDA) that enhances local exploitation and helps escape from local optima; and (3) a fitness diversity-driven switching strategy that dynamically balances exploration and exploitation. Experiments demonstrate that our algorithm can effectively handle large-scale coverage optimization tasks of up to 300 dimensions and more than 1,800 targets within desirable runtime. Compared to state-of-the-art algorithms for EMVOPs, RI-SHM consistently outperforms them by up to 56.5$\%$ across all tested instances.

Related papers

• Optimistic ε-Greedy Exploration for Cooperative Multi-Agent Reinforcement Learning [16.049852176246038]
  We propose Optimistic $epsilon$-Greedy Exploration, focusing on enhancing exploration to correct value estimations. We introduce an optimistic updating network to identify optimal actions and sample actions from its distribution with a probability of $epsilon$ during exploration. Experimental results in various environments reveal that the Optimistic $epsilon$-Greedy Exploration effectively prevents the algorithm from suboptimal solutions.
  arXiv  Detail & Related papers  (2025-02-05T12:06:54Z)
• CVaR-Based Variational Quantum Optimization for User Association in Handoff-Aware Vehicular Networks [23.140655547353994]
  We present a novel Conditional Value at Risk (CVaR)-based Variational Quantum Eigensolver (VQE) framework to address generalized assignment problems (GAP) in vehicular networks (VNets) Our approach leverages a hybrid quantum-classical structure, integrating a tailored cost function that balances both objective and constraint-specific penalties to improve solution quality and stability. We apply this framework to a user-association problem in VNets, where our method achieves 23.5% improvement compared to the deep neural network (DNN) approach.
  arXiv  Detail & Related papers  (2025-01-14T20:21:06Z)
• Distributed genetic algorithm for application placement in the compute continuum leveraging infrastructure nodes for optimization [1.3723120574076126]
  Three distributed designs of a genetic algorithm (GA) for resource optimization in fog computing are presented. Results show that the design with the lowest distribution degree achieves comparable solution quality to the traditional approach but incurs a higher network load.
  arXiv  Detail & Related papers  (2024-06-13T09:58:21Z)
• Federated Multi-Level Optimization over Decentralized Networks [55.776919718214224]
  We study the problem of distributed multi-level optimization over a network, where agents can only communicate with their immediate neighbors. We propose a novel gossip-based distributed multi-level optimization algorithm that enables networked agents to solve optimization problems at different levels in a single timescale. Our algorithm achieves optimal sample complexity, scaling linearly with the network size, and demonstrates state-of-the-art performance on various applications.
  arXiv  Detail & Related papers  (2023-10-10T00:21:10Z)
• Federated Conditional Stochastic Optimization [110.513884892319]
  Conditional optimization has found in a wide range of machine learning tasks, such as in-variant learning tasks, AUPRC, andAML. This paper proposes algorithms for distributed federated learning.
  arXiv  Detail & Related papers  (2023-10-04T01:47:37Z)
• A hybrid level-based learning swarm algorithm with mutation operator for solving large-scale cardinality-constrained portfolio optimization problems [0.0]
  We propose a hybrid variant of the level-based learning swarm (LLSO) for solving large-scale portfolio optimization problems. Our goal is to maximize a modified formulation of the Sharpe ratio subject to cardinality, box and budget constraints. The algorithm involves a projection operator to deal with these three constraints simultaneously and we implicitly control transaction costs thanks to a rebalancing constraint.
  arXiv  Detail & Related papers  (2022-06-29T16:45:37Z)
• Coverage and Capacity Optimization in STAR-RISs Assisted Networks: A Machine Learning Approach [102.00221938474344]
  A novel model is proposed for the coverage and capacity optimization of simultaneously transmitting and reflecting reconfigurable intelligent surfaces (STAR-RISs) assisted networks. A loss function-based update strategy is the core point, which is able to calculate weights for both loss functions of coverage and capacity by a min-norm solver at each update. The numerical results demonstrate that the investigated update strategy outperforms the fixed weight-based MO algorithms.
  arXiv  Detail & Related papers  (2022-04-13T13:52:22Z)
• Evolving Pareto-Optimal Actor-Critic Algorithms for Generalizability and Stability [67.8426046908398]
  Generalizability and stability are two key objectives for operating reinforcement learning (RL) agents in the real world. This paper presents MetaPG, an evolutionary method for automated design of actor-critic loss functions.
  arXiv  Detail & Related papers  (2022-04-08T20:46:16Z)
• GPSAF: A Generalized Probabilistic Surrogate-Assisted Framework for Constrained Single- and Multi-objective Optimization [7.8140593450932965]
  This paper proposes a generalized probabilistic surrogate-assisted framework (GPSAF) GPSAF is applicable to a broad category of unconstrained and constrained, single- and multi-objective optimization algorithms.
  arXiv  Detail & Related papers  (2022-04-06T13:22:30Z)
• Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
  We study optimization of areas under precision-recall curves (AUPRC), which is widely used for imbalanced tasks. We develop novel momentum methods with a better iteration of $O (1/epsilon4)$ for finding an $epsilon$stationary solution. We also design a novel family of adaptive methods with the same complexity of $O (1/epsilon4)$, which enjoy faster convergence in practice.
  arXiv  Detail & Related papers  (2021-07-02T16:21:52Z)
• Adaptive Stochastic ADMM for Decentralized Reinforcement Learning in Edge Industrial IoT [106.83952081124195]
  Reinforcement learning (RL) has been widely investigated and shown to be a promising solution for decision-making and optimal control processes. We propose an adaptive ADMM (asI-ADMM) algorithm and apply it to decentralized RL with edge-computing-empowered IIoT networks. Experiment results show that our proposed algorithms outperform the state of the art in terms of communication costs and scalability, and can well adapt to complex IoT environments.
  arXiv  Detail & Related papers  (2021-06-30T16:49:07Z)

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.