Quality-diversity search

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 1708.09251 §1 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 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] 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 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.

Unstructured archive container

No grid. Members are kept by Euclidean distance over their descriptors, and the structure comes from the solutions that were found 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 1708.09251 §4.2.2. Card: Quality and Diversity Optimization: A Unifying Modular Framework.

Selection operators

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

• No selection: random new solutions each batch. A baseline with no parents 1708.09251 §3.2.1.
• Uniform random from the container: equal chance for each member. This is the MAP-Elites choice 1708.09251 §3.2.2 1708.09251 tab. 1.
• Score-proportionate: chance proportional to a score. The score can be quality, novelty, or the paper's curiosity score 1708.09251 §3.2.3.
• Population-based: a separate population of parents and offspring, with score-proportionate choice on it 1708.09251 §3.2.4.
• Pareto-based: rank by novelty and local quality, NSGA-II style. This is the NSLC choice 1708.09251 §3.2.5 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 1708.09251 §3.2.3 1708.09251 alg. 1. Card: Quality and Diversity Optimization: A Unifying Modular Framework.

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) 1708.09251 §1 1708.09251 tab. 1.

When to use which

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

Card for every row: Quality and Diversity Optimization: A Unifying Modular Framework.

Implementation sketch

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

# 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 1708.09251 §3.1.2 1708.09251 alg. 1. In particular:

• The paper's second-neighbour test uses the distance l, while the code uses (1 − ε)·l 1708.09251 §3.1.2.
• The paper's tolerance is (1 − ε) for both objectives, while the code's tolerance changes sign with the value 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 1708.09251 alg. 1.

The authors' conclusion that curiosity selection beats all other tested methods across all experiments 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 1708.09251 §4.4.2.

Papers

• Quality and Diversity Optimization: A Unifying Modular Framework: 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.