Cascading CMA-ES Instances for Generating Input-diverse Solution Batches

• URL: http://arxiv.org/abs/2502.13730v1
• Date: Wed, 19 Feb 2025 13:55:51 GMT
• Title: Cascading CMA-ES Instances for Generating Input-diverse Solution Batches
• Authors: Maria Laura Santoni, Christoph Dürr, Carola Doerr, Mike Preuss, Elena Raponi,
• Abstract summary: Aiming for batches of diverse solutions of high quality is often desirable, as it provides flexibility to accommodate post-hoc user preferences. We propose a new approach, where parallel runs of the covariance matrix adaptation evolution strategy (CMA-ES) inherit tabu regions in a cascading fashion. We empirically demonstrate that our CMA-ES-Diversity Search (CMA-ES-DS) algorithm generates trajectories that allow to extract high-quality solution batches that respect a given minimum distance requirement.
• Score: 1.932871350415445
• License:
• Abstract: Rather than obtaining a single good solution for a given optimization problem, users often seek alternative design choices, because the best-found solution may perform poorly with respect to additional objectives or constraints that are difficult to capture into the modeling process. Aiming for batches of diverse solutions of high quality is often desirable, as it provides flexibility to accommodate post-hoc user preferences. At the same time, it is crucial that the quality of the best solution found is not compromised. One particular problem setting balancing high quality and diversity is fixing the required minimum distance between solutions while simultaneously obtaining the best possible fitness. Recent work by Santoni et al. [arXiv 2024] revealed that this setting is not well addressed by state-of-the-art algorithms, performing in par or worse than pure random sampling. Driven by this important limitation, we propose a new approach, where parallel runs of the covariance matrix adaptation evolution strategy (CMA-ES) inherit tabu regions in a cascading fashion. We empirically demonstrate that our CMA-ES-Diversity Search (CMA-ES-DS) algorithm generates trajectories that allow to extract high-quality solution batches that respect a given minimum distance requirement, clearly outperforming those obtained from off-the-shelf random sampling, multi-modal optimization algorithms, and standard CMA-ES.

Related papers

• Learning Multiple Initial Solutions to Optimization Problems [52.9380464408756]
  Sequentially solving similar optimization problems under strict runtime constraints is essential for many applications. We propose learning to predict emphmultiple diverse initial solutions given parameters that define the problem instance. We find significant and consistent improvement with our method across all evaluation settings and demonstrate that it efficiently scales with the number of initial solutions required.
  arXiv  Detail & Related papers  (2024-11-04T15:17:19Z)
• An Efficient Approach for Solving Expensive Constrained Multiobjective Optimization Problems [0.0]
  An efficient probabilistic selection based constrained multi-objective EA is proposed, referred to as PSCMOEA. It comprises novel elements such as (a) an adaptive search bound identification scheme based on the feasibility and convergence status of evaluated solutions. Numerical experiments are conducted on an extensive range of challenging constrained problems using low evaluation budgets to simulate ECMOPs.
  arXiv  Detail & Related papers  (2024-05-22T02:32:58Z)
• Multiobjective variational quantum optimization for constrained problems: an application to Cash Management [45.82374977939355]
  We introduce a new method for solving optimization problems with challenging constraints using variational quantum algorithms. We test our proposal on a real-world problem with great relevance in finance: the Cash Management problem. Our empirical results show a significant improvement in terms of the cost of the achieved solutions, but especially in the avoidance of local minima.
  arXiv  Detail & Related papers  (2023-02-08T17:09:20Z)
• On the Global Solution of Soft k-Means [159.23423824953412]
  This paper presents an algorithm to solve the Soft k-Means problem globally. A new model, named Minimal Volume Soft kMeans (MVSkM), is proposed to address solutions non-uniqueness issue.
  arXiv  Detail & Related papers  (2022-12-07T12:06:55Z)
• Ensemble Feature Extraction for Multi-Container Quality-Diversity Algorithms [0.2741266294612775]
  Quality-Diversity algorithms search for large collections of diverse and high-performing solutions. We describe MC-AURORA, a Quality-Diversity approach that optimises simultaneously several collections of solutions. We show that this approach produces solutions that are more diverse than those produced by single-representation approaches.
  arXiv  Detail & Related papers  (2021-05-03T08:35:00Z)
• Modeling the Second Player in Distributionally Robust Optimization [90.25995710696425]
  We argue for the use of neural generative models to characterize the worst-case distribution. This approach poses a number of implementation and optimization challenges. We find that the proposed approach yields models that are more robust than comparable baselines.
  arXiv  Detail & Related papers  (2021-03-18T14:26:26Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)
• Uncertainty aware Search Framework for Multi-Objective Bayesian Optimization with Constraints [44.25245545568633]
  We consider the problem of constrained multi-objective (MO) blackbox optimization using expensive function evaluations. We propose a novel framework named Uncertainty-aware Search framework for Multi-Objective Optimization with Constraints. We show that USeMOC is able to achieve more than 90 % reduction in the number of simulations needed to uncover optimized circuits.
  arXiv  Detail & Related papers  (2020-08-16T23:34:09Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  Security-constrained optimal power flow (SCOPF) is fundamental in power systems. Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs. This paper proposes a novel approach that combines deep learning and robust optimization techniques.
  arXiv  Detail & Related papers  (2020-07-14T12:38:21Z)
• sKPNSGA-II: Knee point based MOEA with self-adaptive angle for Mission Planning Problems [2.191505742658975]
  Some problems have many objectives which lead to a large number of non-dominated solutions. This paper presents a new algorithm that has been designed to obtain the most significant solutions. This new algorithm has been applied to the real world application in Unmanned Air Vehicle (UAV) Mission Planning Problem.
  arXiv  Detail & Related papers  (2020-02-20T17:07:08Z)
• GACEM: Generalized Autoregressive Cross Entropy Method for Multi-Modal Black Box Constraint Satisfaction [69.94831587339539]
  We present a modified Cross-Entropy Method (CEM) that uses a masked auto-regressive neural network for modeling uniform distributions over the solution space. Our algorithm is able to express complicated solution spaces, thus allowing it to track a variety of different solution regions.
  arXiv  Detail & Related papers  (2020-02-17T20:21:20Z)

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.