---
kind: concept
slug: quality-diversity
title: Quality-diversity search
summary: >-
  Searching for a whole collection of good solutions that differ in behaviour, instead of one optimum. One card so far: a single loop with a swappable container (grid or epsilon-dominance archive) and selection operator, unifying MAP-Elites and NSLC. Results are simulation-only and author-reported.
tags: [evolutionary-computation, behaviour-descriptor, map-elites, novelty-search, robotics]
papers: ["1708.09251"]
related: [neuroevolution, nearest-neighbor-search, metaheuristic-optimization]
status: draft
updated_at: 2026-11-01
---

## Overview

A quality-diversity search keeps a collection of solutions rather than one
best answer. Each evaluated solution gets two values: a performance (quality)
and a behaviour descriptor that says what it does [arxiv:1708.09251 §1]
[arxiv:1708.09251 tab. 2]. The search tries to fill the collection with
high-quality solutions whose descriptors are spread out.

All variants share one loop: a container holds the collection, a selection
operator picks parents from it, offspring are made by mutation (and
optionally crossover), each offspring is evaluated and offered to the
container, and the scores are updated [arxiv:1708.09251 §3] [arxiv:1708.09251
alg. 1]. The variants differ in two parts: how the container is organised and
how parents are chosen. The paper's framing is that the two best-known
methods are the same loop with different parts plugged in [arxiv:1708.09251
§3] [arxiv:1708.09251 tab. 1].

## Variants

### Grid container

The behaviour space is cut into cells and each cell keeps one solution. A
candidate replaces the occupant only when its performance is higher
[arxiv:1708.09251 §3.1.1]. The grid needs its size fixed in advance: 100 by 100
cells for the two-dimensional tasks, and 5 cells per dimension for the
six-dimensional gait task, which is 5^6 = 15,625 cells [arxiv:1708.09251
tab. 2]. Card: [Quality and Diversity Optimization: A Unifying Modular
Framework](/papers/1708.09251).

### Unstructured archive container

No grid. Members are kept by Euclidean distance over their descriptors, and the
structure comes from the solutions that were found [arxiv:1708.09251 §3.1.2].
The paper's insertion rule has three parts. A candidate far from every member
is added. A candidate that is close to two members is rejected. A candidate
close to exactly one member replaces it only if it exclusively
epsilon-dominates that member on novelty and quality [arxiv:1708.09251
§3.1.2]. The author-reported arm collection reached about 6,000 solutions
[arxiv:1708.09251 §4.2.2]. Card: [Quality and Diversity Optimization: A
Unifying Modular Framework](/papers/1708.09251).

### Selection operators

The paper tests five ways to pick parents. All can be combined with either
container [arxiv:1708.09251 §3.2].

- **No selection**: random new solutions each batch. A baseline with no
  parents [arxiv:1708.09251 §3.2.1].
- **Uniform random from the container**: equal chance for each member. This is
  the MAP-Elites choice [arxiv:1708.09251 §3.2.2] [arxiv:1708.09251 tab. 1].
- **Score-proportionate**: chance proportional to a score. The score can be
  quality, novelty, or the paper's curiosity score [arxiv:1708.09251 §3.2.3].
- **Population-based**: a separate population of parents and offspring, with
  score-proportionate choice on it [arxiv:1708.09251 §3.2.4].
- **Pareto-based**: rank by novelty and local quality, NSGA-II style. This is
  the NSLC choice [arxiv:1708.09251 §3.2.5] [arxiv:1708.09251 tab. 1].

The curiosity score is the paper's new selection signal. A parent gains 1 when
its offspring enters the collection and loses 0.5 when it does not. Scores
start at 0 [arxiv:1708.09251 §3.2.3] [arxiv:1708.09251 alg. 1]. Card: [Quality
and Diversity Optimization: A Unifying Modular
Framework](/papers/1708.09251).

Two methods are named as baselines but have no card here, so nothing from them
is used on this page: MAP-Elites and Novelty Search with Local Competition
(NSLC) [arxiv:1708.09251 §1] [arxiv:1708.09251 tab. 1].

## When to use which

The paper's experiments are simulation only, with 10 to 20 replications per
variant [arxiv:1708.09251 §4]. The choice below follows what those runs show;
it is not a general ranking.

| Situation | Use | Why |
|---|---|---|
| You want many distinct good solutions over a low-dimensional descriptor (2-D here) | Grid or archive, with curiosity or whole-collection selection | On the arm task, curiosity over the whole collection beat population-based selection on all four collection metrics [arxiv:1708.09251 §4.2.2] [arxiv:1708.09251 fig. 4] |
| Descriptor has many dimensions and a fixed grid would explode | Archive container | A grid of 5 cells per dimension over 6 dimensions has 15,625 cells [arxiv:1708.09251 tab. 2]. On the six-dimensional gait task, curiosity with an archive reached the random-selection baseline's total quality at 11,000 batches, against 13,500 with a grid [arxiv:1708.09251 §4.4.2] [arxiv:1708.09251 fig. 7] |
| You need the single highest score | Not quality-diversity; keep population-based fitness selection | On the gait task, population-based fitness selection gave the best maximal quality (p < 0.0017) [arxiv:1708.09251 §4.4.2] |
| Collection is large and update cost matters | Plan for cost that grows with the collection | The archive recomputes novelty and local quality for all members after each batch [arxiv:1708.09251 alg. 1] [arxiv:1708.09251 §4.2.2] |
| Hardware time is tight | Budget for long runs | One hexapod variant took 4 to 5 hours on the physical simulator for 10,000 batches [arxiv:1708.09251 §4.3.1] |

Card for every row: [Quality and Diversity Optimization: A Unifying Modular
Framework](/papers/1708.09251).

## Implementation sketch

Language-agnostic pseudocode of the common loop. Variants differ in
`container` (grid or archive) and in `select`.

```pseudocode
# Quality-diversity loop  [arxiv:1708.09251 alg. 1]
# Input:  iterations, batch size B (200 in all three experiments [tab. 2])
# Output: container holding the collection

def quality_diversity(iterations, B):
    # Empty container: grid or archive  [§3.1]
    container = new_container()
    # Two random batches start the search  [alg. 1]
    parents = random_batch(B)
    offspring = random_batch(B)
    for iteration in range(1, iterations + 1):
        if iteration > 1:
            # Parent choice: uniform, score-based, population or Pareto  [§3.2]
            parents = select(container, offspring, B)
            # Mutate, optionally cross over (off in all three tasks)  [tab. 2]
            offspring = vary(parents)
        for individual in offspring:
            # Evaluate: quality and behaviour descriptor  [alg. 1]
            evaluate(individual)
            # Container decides whether it is kept  [§3.1]
            added = container.add(individual)
            # Curiosity update: +1 if kept, -0.5 if not  [§3.2.3]
            if added:
                curiosity[parent_of(individual)] += 1.0
            else:
                curiosity[parent_of(individual)] -= 0.5
        # Refresh novelty and local quality of all members  [alg. 1]
        container.update_scores()
    return container
```

Grid `add` keeps the higher performer per cell [§3.1.1]. Archive `add` uses
the nearest-neighbour test and epsilon-dominance described in [§3.1.2].

## Contradictions

Only one card lists this concept, so no two papers disagree here. Within the
card, the paper's stated rules and the released code differ in several places.
Read the card's Paper vs code section before reimplementing the archive or the
curiosity credit [arxiv:1708.09251 §3.1.2] [arxiv:1708.09251 alg. 1]. In
particular:

- The paper's second-neighbour test uses the distance l, while the code uses
  (1 − ε)·l [arxiv:1708.09251 §3.1.2].
- The paper's tolerance is (1 − ε) for both objectives, while the code's
  tolerance changes sign with the value [arxiv:1708.09251 §3.1.2].
- Algorithm 1 credits the actual parent of each offspring. The code appears to
  pair offspring with parents by index, with parents drawn through a random index list, which would
  credit a different individual. This is an inference from the code, not a run
  [arxiv:1708.09251 alg. 1].

The authors' conclusion that curiosity selection beats all other tested methods
across all experiments [arxiv:1708.09251 §5] is not borne out by every metric.
Population-based selection wins on maximal quality in the gait task, and
Pareto-based selection is weak there [arxiv:1708.09251 §4.4.2].

## Papers

- [Quality and Diversity Optimization: A Unifying Modular Framework](/papers/1708.09251): one loop with a swappable container and selection operator, unifies MAP-Elites and NSLC, and adds an epsilon-dominance archive rule and a curiosity selection score.