Gradient-Informed Quality Diversity for the Illumination of Discrete Spaces

• URL: http://arxiv.org/abs/2306.05138v2
• Date: Wed, 13 Sep 2023 08:28:46 GMT
• Title: Gradient-Informed Quality Diversity for the Illumination of Discrete Spaces
• Authors: Raphael Boige, Guillaume Richard, J\'er\'emie Dona, Thomas Pierrot, Antoine Cully
• Abstract summary: Quality Diversity (QD) algorithms have been proposed to search for a large collection of both diverse and high-performing solutions instead of a single set of local optima. We introduce a Gradient-Informed Discrete Emitter (ME-GIDE), which extends QD with differentiable functions over discrete search spaces. We evaluate our method on challenging benchmarks including protein design and discrete latent space illumination and find that our method outperforms state-of-the-art QD algorithms in all benchmarks.
• Score: 7.799824794686343
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quality Diversity (QD) algorithms have been proposed to search for a large collection of both diverse and high-performing solutions instead of a single set of local optima. While early QD algorithms view the objective and descriptor functions as black-box functions, novel tools have been introduced to use gradient information to accelerate the search and improve overall performance of those algorithms over continuous input spaces. However a broad range of applications involve discrete spaces, such as drug discovery or image generation. Exploring those spaces is challenging as they are combinatorially large and gradients cannot be used in the same manner as in continuous spaces. We introduce map-elites with a Gradient-Informed Discrete Emitter (ME-GIDE), which extends QD optimisation with differentiable functions over discrete search spaces. ME-GIDE leverages the gradient information of the objective and descriptor functions with respect to its discrete inputs to propose gradient-informed updates that guide the search towards a diverse set of high quality solutions. We evaluate our method on challenging benchmarks including protein design and discrete latent space illumination and find that our method outperforms state-of-the-art QD algorithms in all benchmarks.

Related papers

• Multiway Point Cloud Mosaicking with Diffusion and Global Optimization [74.3802812773891]
  We introduce a novel framework for multiway point cloud mosaicking (named Wednesday) At the core of our approach is ODIN, a learned pairwise registration algorithm that identifies overlaps and refines attention scores. Tested on four diverse, large-scale datasets, our method state-of-the-art pairwise and rotation registration results by a large margin on all benchmarks.
  arXiv  Detail & Related papers  (2024-03-30T17:29:13Z)
• Efficient Quality-Diversity Optimization through Diverse Quality Species [3.428706362109921]
  We show that a diverse population of solutions can be found without the limitation of needing an archive or defining the range of behaviors in advance. We propose Diverse Quality Species (DQS) as an alternative to archive-based Quality-Diversity (QD) algorithms.
  arXiv  Detail & Related papers  (2023-04-14T23:15:51Z)
• Don't Bet on Luck Alone: Enhancing Behavioral Reproducibility of Quality-Diversity Solutions in Uncertain Domains [2.639902239625779]
  We introduce Archive Reproducibility Improvement Algorithm (ARIA) ARIA is a plug-and-play approach that improves the quality of solutions present in an archive. We show that our algorithm enhances the quality and descriptor space coverage of any given archive by at least 50%.
  arXiv  Detail & Related papers  (2023-04-07T14:45:14Z)
• Score-based Diffusion Models in Function Space [140.792362459734]
  Diffusion models have recently emerged as a powerful framework for generative modeling. We introduce a mathematically rigorous framework called Denoising Diffusion Operators (DDOs) for training diffusion models in function space. We show that the corresponding discretized algorithm generates accurate samples at a fixed cost independent of the data resolution.
  arXiv  Detail & Related papers  (2023-02-14T23:50:53Z)
• Deep Diversity-Enhanced Feature Representation of Hyperspectral Images [87.47202258194719]
  We rectify 3D convolution by modifying its topology to enhance the rank upper-bound. We also propose a novel diversity-aware regularization (DA-Reg) term that acts on the feature maps to maximize independence among elements. To demonstrate the superiority of the proposed Re$3$-ConvSet and DA-Reg, we apply them to various HS image processing and analysis tasks.
  arXiv  Detail & Related papers  (2023-01-15T16:19:18Z)
• Accelerating Inverse Learning via Intelligent Localization with Exploratory Sampling [1.5976506570992293]
  solving inverse problems is a longstanding challenge in materials and drug discovery. Deep generative models are recently proposed to solve inverse problems. We propose a novel approach (called iPage) to accelerate the inverse learning process.
  arXiv  Detail & Related papers  (2022-12-02T08:00:04Z)
• Fighting the curse of dimensionality: A machine learning approach to finding global optima [77.34726150561087]
  This paper shows how to find global optima in structural optimization problems. By exploiting certain cost functions we either obtain the global at best or obtain superior results at worst when compared to established optimization procedures.
  arXiv  Detail & Related papers  (2021-10-28T09:50:29Z)
• Differentiable Quality Diversity [1.0965065178451106]
  We present the differentiable quality diversity (DQD) problem, where both the objective and measure functions are first order differentiable. We then present MAP-Elites via Gradient Arborescence (MEGA), a DQD algorithm that leverages gradient information to efficiently explore the joint range of the objective and measure functions. Results in two QD benchmark domains and in searching the latent space of a StyleGAN show that MEGA significantly outperforms state-of-the-art QD algorithms.
  arXiv  Detail & Related papers  (2021-06-07T18:11:53Z)
• Selection-Expansion: A Unifying Framework for Motion-Planning and Diversity Search Algorithms [69.87173070473717]
  We investigate the properties of two diversity search algorithms, the Novelty Search and the Goal Exploration Process algorithms. The relation to MP algorithms reveals that the smoothness, or lack of smoothness of the mapping between the policy parameter space and the outcome space plays a key role in the search efficiency.
  arXiv  Detail & Related papers  (2021-04-10T13:52:27Z)
• BOP-Elites, a Bayesian Optimisation algorithm for Quality-Diversity search [0.0]
  We propose the Bayesian optimisation of Elites (BOP-Elites) algorithm. By considering user defined regions of the feature space as 'niches' our task is to find the optimal solution in each niche. The resulting algorithm is very effective in identifying the parts of the search space that belong to a niche in feature space, and finding the optimal solution in each niche.
  arXiv  Detail & Related papers  (2020-05-08T23:49:13Z)
• Discovering Representations for Black-box Optimization [73.59962178534361]
  We show that black-box optimization encodings can be automatically learned, rather than hand designed. We show that learned representations make it possible to solve high-dimensional problems with orders of magnitude fewer evaluations than the standard MAP-Elites.
  arXiv  Detail & Related papers  (2020-03-09T20:06: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.