PaperlayerView exact revision on arXiv

Source-linked AI summary

Quality-Diversity Optimization: a novel branch of stochastic optimization

Konstantinos Chatzilygeroudis, Antoine Cully, Vassilis Vassiliades, Jean-Baptiste Mouret

arXiv:2012.04322v2cs.NEcs.LGmath.OCstat.ML

TL;DR

Real-world optimization often entails iterative cost-function tuning and exploration of design trade-offs. This chapter reviews Quality-Diversity algorithms, which collect high-performing solutions across behavioral features, and discusses their applications and current research topics. It concludes that QD collections cover behavioral space with locally optimized solutions, while noting challenges in discretizing features and tuning containers.

  • Problem

    Real-world optimization problems may not be captured by simple cost functions, and optimization is often used to explore options and trade-offs rather than identify a final solution.

    Source: §1 · p. 1

  • Method

    The chapter reviews QD algorithms, which collect locally optimized solutions across behavioral descriptors, as well as current research topics and applications.

    Source: §1 · p. 1, §6 · p. 10

  • Results

    The chapter concludes that QD archives aim to cover behavioral space with locally optimized solutions and surveys successful applications across fields.

    Source: §6 · p. 10

  • Takeaways & Limitations

    QD collections provide a set of high-performing solutions across user-defined features for users to select from or study.

    Source: §1 · p. 1

    MAP-Elites can be difficult to apply when behavioral spaces are high-dimensional or have highly irregular bounds because discretizing them is challenging.

    Source: §3.1 · p. 3

Abstract

from arXiv · show

Traditional optimization algorithms search for a single global optimum that maximizes (or minimizes) the objective function. Multimodal optimization algorithms search for the highest peaks in the search space that can be more than one. Quality-Diversity algorithms are a recent addition to the evolutionary computation toolbox that do not only search for a single set of local optima, but instead try to illuminate the search space. In effect, they provide a holistic view of how high-performing solutions are distributed throughout a search space. The main differences with multimodal optimization algorithms are that (1) Quality-Diversity typically works in the behavioral space (or feature space), and not in the genotypic (or parameter) space, and (2) Quality-Diversity attempts to fill the whole behavior space, even if the niche is not a peak in the fitness landscape. In this chapter, we provide a gentle introduction to Quality-Diversity optimization, discuss the main representative algorithms, and the main current topics under consideration in the community. Throughout the chapter, we also discuss several successful applications of Quality-Diversity algorithms, including deep learning, robotics, and reinforcement learning.

1 Introduction

Real-world optimization often requires repeated cost-function changes and is used to explore design options and trade-offs rather than deliver a final optimum. Quality-Diversity algorithms address this by collecting high-performing solutions across user-defined features, and the chapter surveys their algorithms, recent ideas, and applications.

1 Introduction

  • Engineering optimization often requires repeated optimizer runs and cost-function changes because real-world problems are not easily captured by a simple cost function.Even after fine-tuning, the solution is rarely used as final; optimization is often used early to explore options and trade-offs.Source: §1 · p. 1
  • QD algorithms return large sets of high-performing solutions that vary across user-defined features, letting users choose solutions or study how features relate to performance.Some features need not affect the cost function, while others may need to satisfy a threshold for acceptable performance.Source: §1 · p. 1
  • For six-legged-robot gait design, QD can find high-performing parameters for many directions in one run, and a solution for one direction can serve as a stepping stone toward another.Nearby directions may have similar solutions, making simultaneous optimization potentially more efficient.Source: §1 · p. 1
  • The chapter reviews evolutionary-algorithm-based QD methods, ideas for improving data efficiency and scaling to high-dimensional spaces, and applications.Source: §1 · p. 1

2 Problem Formulation

QD optimization seeks the highest-fitness solution for each behavioral descriptor, using a collection to represent diverse solution types. Its performance reflects both solution quality and behavior-space coverage, with alternative ways to organize and assess that collection.

2 Problem Formulation

  • The objective function is assumed to return both a fitness value and a behavioral descriptor for each parameterized solution.Source: §2 · p. 1
  • The behavioral descriptor describes how a solution solves the problem, while fitness quantifies how well it solves it.Examples of descriptors include design curvature, volume, or robot trajectory; corresponding fitness measures can include drag, energy use, or distance to a target.Source: §2 · p. 1
  • QD aims to find the maximum-fitness parameters for each point in the behavioral feature space.Source: §2 · p. 1
  • When descriptors are discretized, a QD result can be represented as a table of descriptor locations.A two-dimensional behavioral descriptor is usually displayed as a colored image or heatmap.Source: §2 · pp. 1–2, Table 1 · p. 2
  • Although QD resembles optimizing separately for each feature combination, the feature space may be continuous and descriptors are only known after evaluating a candidate.Thus, QD can be viewed as a set of optimizations constrained by behavioral descriptors.Source: §2 · p. 2
  • QD's central hypothesis is that solving descriptor-constrained problems together can be faster than solving them independently, because nearby descriptors may have similar high-performing solutions and evaluated candidates can be useful for other feature combinations.Source: §2 · p. 2

2.1 Collections of Solutions

  • A collection groups similar descriptors into solution types, with a hyperparameter setting the behavioral-space resolution and allowing one solution to occupy each region.Source: §2.1 · p. 2
  • MAP-Elites discretizes the behavioral space into a grid whose cells represent solution types; other containers can use distance thresholds or local-density estimates instead.Source: §2.1 · p. 2

3 Optimizing a collection of solutions

QD algorithms build collections that are both diverse and locally optimized, using different containers, selection operators, and scores to guide search. The chapter describes MAP-Elites and a unified framework, then reviews findings on selection strategies and the limitations of distance-based containers.

3.1 MAP-Elites

  • MAP-Elites alters copies of archived solutions through mutation or crossover, evaluates them, and keeps the best solution in each descriptor cell.If a cell is empty, the candidate is added; otherwise it replaces the incumbent only when better.Source: §3.1 · p. 2

3.2 A Unified Framework

  • A unified QD framework describes algorithms through three choices: container type, selection operator, and scores used by the container and selection process.Its repeated cycle selects and varies individuals, evaluates performance and descriptors, potentially adds them to the container, and updates scores until stopping.Source: §3.2 · p. 3

3.2.1 Containers

  • Containers keep the best and most diverse solutions; grids assign descriptor regions to cells, while distance-based archives admit behaviorally distant or improved neighbors without discretizing the space.Distance-based archives can require maintenance to limit erosion, in which better but closer solutions may displace distant ones and slow optimization.Source: §3.2.1 · p. 3

3.2.2 Selection Operators

  • MAP-Elites randomly samples parents from its archive, while score-weighted sampling can bias selection toward desired behaviors or individuals likely to improve the collection.In the original strategy, each solution's selection chance is inversely proportional to archive size, weakening selection pressure as the collection grows; NSLC instead uses separate novelty and performance populations.Source: §3.2.2 · p. 3

3.3 Considerations of Quality-Diversity Optimization

  • Curiosity-based QD was consistently better than many variants in distance- and grid-based containers, and learned six-legged-robot repertoires for walking in any direction or in many straight-line ways.The reported results suggest curiosity can support continued exploration while locally optimizing solutions.Source: §3.3 · p. 4
  • Uniform random selection over the MAP-Elites container performed effectively with both distance- and grid-based containers [54].This supports selecting reproduction candidates from the archive rather than generating them randomly.Source: §3.3 · p. 4
  • Novelty-Search with Local Competition was less effective than curiosity-based QD and QD using MAP-Elites selection.The comparison favors evolving one collection over splitting solutions into populations with different characteristics and functions.Source: §3.3 · p. 4
  • Distance-based containers produce fewer individuals, with the count depending on a threshold that can be difficult to tune.The chapter identifies better container structure as a need for addressing this limitation.Source: §3.3 · p. 4

4 Origins and Related Work

The section traces QD’s emergence from novelty-driven behavior search and distinguishes its behavior-space objective from multimodal and multitask optimization. It also reviews where these methods overlap and where specialized QD approaches remain necessary.

4.1 Searching for Diverse Behaviors

  • Novelty Search and Novelty Search with Local Competition reward solutions for differing from previously encountered ones, using an archive to compute novelty rather than to collect high-performing diverse solutions.Source: §4.1 · pp. 4–5
  • BR-Evolution made the novelty archive the outcome by replacing solutions with better-performing ones; MAP-Elites also produced effective behavioral repertoires, and the approach was later formalized as Quality-Diversity, [17], [54],.Source: §4.1 · p. 5

4.2 Connections to Multimodal Optimization

  • Niching methods maintain diversity through mechanisms including fitness sharing, which reduces fitness in dense regions, and clearing, which removes less-fit neighbors,.Source: §4.2 · p. 5
  • QD seeks the highest-fitness parameters for each behavior-space point and typically returns more solutions than underlying optima, unlike MMO’s search for locally optimal solutions in parameter space.Source: §4.2 · p. 5
  • Some multimodal methods perform as well as QD when comparing behavior-space distances, while others fail; QD also works in high-dimensional parameter spaces and can address multimodal optimization,.Source: §4.2 · p. 5

4.3 Connections to Multi-task Optimization

  • Multitask optimization seeks a maximum-fitness solution for each task, and Multitask-MAP-Elites outperformed independent CMA-ES optimization, especially on hard problems [34],.Source: §4.3 · p. 6

5 Current Topics

The chapter surveys current QD approaches to expensive objectives, high-dimensional behavior spaces, learned descriptors, variation operators, and noisy evaluations. Across these topics, it describes methods for preserving diverse high-performing collections under differing computational and representation constraints.

5.1 Expensive Objective Functions

  • At CMA-ES’s evaluation budget for a near-optimal single bin, SAIL found similar-quality airfoils in all 625 bins; per-bin CMA-ES required an order of magnitude more evaluations.The authors also report promising results on a more complex 3-dimensional aerodynamic optimization.Source: §5.1 · p. 7
  • For objectives too costly for millions of evaluations, EJIE weights each niche’s expected improvement by the predicted probability of a candidate belonging to that bin.It showed promising results on a 1-dimensional benchmark, while comparison with SAIL remains necessary; surrogate models can also raise map resolution in minutes.Source: §5.1 · pp. 6–7

5.2 High-Dimensional Feature Space

  • For 10,000 effective gaits, CVT-MAP-Elites performed similarly across 12-, 24-, and 36-dimensional feature spaces, unlike MAP-Elites.CVT controls the number of regions independently of feature dimensionality, avoiding the exponential bin growth of a grid; sequence features require representative sampling informed by physical constraints.Source: §5.2 · pp. 7–8

5.3 Learning the Behavior Descriptor

  • Learned latent spaces can organize QD collections by example similarity, enabling a robot arm to draw digits without manually defined features; alternatively, descriptors can be iteratively updated from generated solutions.AURORA uses this iterative approach to discover diverse robot skills without prior knowledge of robot capabilities; TAXONS uses camera images for behavioral descriptors.Source: §5.3 · p. 8

5.4 Improving Variation Operators

  • Because elites occupy a specific genotype-space hypervolume, crossover can produce high-performing solutions, with blending guaranteed to remain elite when that volume is convex.When the hypervolume is non-convex, blending is not guaranteed to succeed, though it may still do so.Source: §5.4 · pp. 8–9, Figure 4 · p. 9
  • Data-Driven Encoding uses a VAE trained on archive genotypes, enabling MAP-Elites on tasks up to 1000 dimensions and a reusable latent representation of elite solutions.A multi-armed bandit balances VAE variation against other operators because the VAE cannot generate candidates outside its current hypervolume approximation; more tasks remain to be investigated.Source: §5.4 · pp. 9–10
  • CMA-ME uses optimizing, random-direction, and improvement emitters to specialize search toward higher performance, behavioral-space coverage, or adding solutions to the collection.The emitters are independent processes based on CMA-ES.Source: §5.4 · p. 10

5.5 Noisy Functions

  • Noisy fitness can preserve undeserving elites and noisy descriptors can place solutions in wrong cells; adaptive sampling helps especially when only fitness is noisy, while Deep-Grid MAP-Elites stores multiple solutions per cell to improve descriptor robustness.Repeated evaluations can gather robust statistics but severely reduce data efficiency; noise in behavioral descriptors can cause drifting elites and empty cells.Source: §5.5 · p. 10

6 Conclusion

Quality-Diversity optimization collects locally optimized solutions across behavioral space, using objectives that return both fitness and a behavior descriptor. The chapter concludes that QD can illuminate sparse or non-convex search spaces and produce repertoires of behaviors, while reviewing applications and current limitations.

6 Conclusion

  • QD objectives return both fitness and a behavior descriptor, and the archive aims to cover behavioral space with locally optimized solutions.The chapter characterizes QD as a branch of stochastic optimization and reviews its history, current topics, applications, and limitations.Source: §6 · p. 10
  • QD algorithms are described as effective for sparse or non-convex functions, illuminating search spaces by user-defined or learned features, and producing locally optimized behavior repertoires.One example is robots walking in every direction.Source: §6 · p. 10
Loading 2012.04322v2…