Quality and Diversity Optimization: A Unifying Modular Framework

In plain words

Most optimisers look for one best answer. Quality-diversity methods try to fill a whole collection with good answers that behave differently from each other, so you end up with a catalogue of solutions rather than a single winner. Two popular methods do this in different ways: one splits the space of behaviours into a fixed grid of boxes, the other keeps an unstructured list of solutions that are spread out from each other.

This paper shows that both methods are the same loop with different parts plugged in: one part keeps the collection, the other chooses which members to build new candidates from. That view makes it possible to mix the parts. The paper proposes a new rule for keeping the unstructured list from losing its edges, and a new way of choosing parents that favours those which keep producing new entries. In three simulated robot tasks, the authors report that the new choice of parents produced the best collections.

TL;DR

• Unifies MAP-Elites and Novelty Search with Local Competition (NSLC) as one loop with a container and a selection operator §3 alg. 1.
• Container options: an N-dimensional grid §3.1.1 or an unstructured archive with a new insertion rule, the exclusive epsilon-dominance §3.1.2.
• New selection signal, the curiosity score: +1 when a parent's offspring enters the collection, −0.5 when it does not §3.2.3.
• Results are author-reported and come from simulation only. Three tasks, 10 to 20 replications each §4.
• The official code is public, carries no LICENSE file, and differs from the paper in several details listed under Paper vs code.

Problem

Searching for one optimum discards the diversity that a designer may need, and quality-diversity methods were introduced to return many different high-quality solutions §1. The two families that the paper compares, MAP-Elites (grid container, random selection from the collection) and NSLC (novelty archive plus a population, Pareto selection on novelty and local quality), are usually compared only as whole algorithms. That comparison does not show which parts cause the differences §3.

Known weaknesses that the paper addresses:

• An unstructured archive that admits a candidate when its novelty score is high can show uneven density. Replacing members by better ones can erode the border of the collection and lose coverage §3.1.2.
• Selection that uses only the current population converges to a few regions and is weaker than selection over the whole collection in the experiments §4.2.2 §4.4.2.
• Selection by random choice from the collection loses pressure as the collection grows §3.2.2.

The paper does not state a formal problem class beyond the setting: a fixed-length real or sampled genotype, a performance value, and a behaviour descriptor per evaluated solution §4 tab. 2.

Method

Loop. A search keeps a container of solutions and repeats four steps. A selection operator picks parents, using the container and possibly the last batch. Offspring are made by mutation and, optionally, crossover. Each offspring is evaluated for its performance and its descriptor, then offered to the container. Scores such as novelty, local quality and curiosity are then updated §3 alg. 1. The first two batches are random alg. 1. The code uses batches of 200 offspring tab. 2.

# Quality-diversity loop  [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: a grid or an unstructured 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:
            # Parents come from the container and the last batch  [§3.2]
            parents = select(container, offspring, B)
            # Mutate, and optionally cross over, copies of the parents  [alg. 1]
            offspring = vary(parents)
        for individual in offspring:
            # Evaluate: performance and behaviour descriptor  [alg. 1]
            evaluate(individual)
            # Offer it to the container (rule depends on it)  [§3.1]
            added = container.add(individual)
            # Reward the parent: +1 if added, otherwise -0.5  [§3.2.3] [alg. 1]
            parent = parent_of(individual)
            if added:
                curiosity[parent] += 1.0
            else:
                curiosity[parent] -= 0.5
        # Recompute novelty and local quality for all members  [alg. 1]
        container.update_scores()
    return container

Grid container §3.1.1. The descriptor space is cut into cells, one solution per cell. A candidate replaces the occupant only if its performance is higher. Novelty is the count of filled cells in a sub-grid of ±k cells around the individual, and a lower value is treated as more novel §3.1.1.

Archive container §3.1.2. The archive is unstructured: members are kept by Euclidean distance over descriptors, and the structure emerges from the solutions found. The paper's insertion rule is:

# Archive insertion, exclusive epsilon-dominance  [§3.1.2] [fig. 2]
# Input:  candidate, archive, l (max density), eps (tolerance)
# Output: True if the archive changed

def archive_add(candidate, archive, l, eps):
    # Find the nearest and second-nearest members  [§3.1.2]
    nearest, second = two_nearest(candidate, archive)
    # Far enough from every member: always added  [§3.1.2] [fig. 2 A]
    if distance(candidate, nearest) > l:
        archive.insert(candidate)
        return True
    # Must be farther than l from the second member, or reject  [§3.1.2]
    if distance(candidate, second) <= l:
        return False
    # Compete with the nearest member  [§3.1.2] [fig. 2 B]
    if exclusively_dominates(candidate, nearest, eps):
        archive.replace(nearest, candidate)
        return True
    return False

The competition uses novelty N (mean distance to the k nearest members) and quality Q, both maximised. Candidate x1 exclusively dominates x2 when the following hold §3.1.2:

# Exclusive epsilon-dominance of x1 over x2  [§3.1.2] [fig. 2 C]
# Each objective may drop by at most a fraction eps of the other value.

def exclusively_dominates(x1, x2, eps):
    # Condition 1: novelty within the tolerance  [§3.1.2]
    if novelty(x1) < (1 - eps) * novelty(x2):
        return False
    # Condition 2: quality within the tolerance  [§3.1.2]
    if quality(x1) < (1 - eps) * quality(x2):
        return False
    # Condition 3: the gain on one objective pays for the other  [§3.1.2]
    gain_nov = novelty(x1) - novelty(x2)
    gain_qual = quality(x1) - quality(x2)
    return gain_nov * quality(x2) > -gain_qual * novelty(x2)

The paper names the archive rule's novelty as the traditional mean distance to the k nearest neighbours §3.1.2 and uses the nearest-neighbour distance, not the mean over k, as the density test §3.1.2.

Selection operators §3.2. All operators can be used with either container.

• No selection draws random solutions each batch; it is a motor-babbling baseline §3.2.1.
• Uniform random picks from the container with equal probability; this is MAP-Elites §3.2.2.
• Score proportionate picks from the container with probability proportional to a score, where the score is quality (fitness), novelty or curiosity §3.2.3.
• Population-based keeps a separate population of parents and offspring and applies score-proportionate selection to it §3.2.4.
• Pareto-based ranks the population on novelty and local quality, the number of neighbours that do better, in the NSGA-II style. This is the selection used by NSLC §3.2.5 tab. 1.

Curiosity score §3.2.3 alg. 1. Each individual starts at 0. Each offspring that enters the collection adds 1 to its parent's score, and each offspring that does not enter subtracts 0.5. The score therefore rises while a region keeps producing new members and falls when it stops. The paper contrasts this with a related successful-offspring counter that starts at a fixed value and resets to it §3.2.3.

# Curiosity-proportionate parent selection  [§3.2.3]
# Input:  members of the container, batch size B
# Output: B parents, drawn with replacement

def select_by_curiosity(members, B):
    scores = [curiosity[m] for m in members]
    # Shift so the least curious member has weight 0  [§3.2.3]
    floor = min(scores)
    weights = [s - floor for s in scores]
    # Roulette-wheel draw in proportion to the weights  [§3.2.3]
    return random_choices(members, weights, k=B)

Relation to the named methods. Grid container with uniform random selection is MAP-Elites tab. 1. Pareto-based selection with a novelty and local-quality score, on a population and an archive, is NSLC tab. 1 §3.2.5.

Hyperparameters

Values from the paper's parameter table, with the code values where the code was read. Three columns are given for the three experiments: arm, hexapod turn and gait task, in that order tab. 2.

Results

Author-reported, simulation only. Hardware and wall-clock are not stated except for the hexapod run time. Baselines are the other variants in Table 1 and NSLC tab. 1 §4.

Experiments §4:

• Redundant planar arm, 8 joints, 2-D descriptor of the gripper position, quality is joint-angle uniformity, 50,000 batches, 20 replications §4.2.1 tab. 2.
• Six-legged robot turning in every direction, 36 parameters, 2-D descriptor of the final position, quality is the orientation error relative to a circular trajectory. 10,000 batches, 10 replications. One variant takes 4 to 5 hours on the physical simulator §4.3.1.
• Six-legged robot walking in straight lines, 6-D descriptor (fraction of time each leg touches the ground), quality is the distance walked in 3 s. 20,000 batches, 10 replications §4.4.1.

Other reported points: the arm collection has about 6,000 solutions §4.2.2; NSLC achieves good coverage in the gaits task but lower maximal quality §4.4.2; Pareto-based selection is weak in the gaits task and the authors suggest premature convergence to the collection border §4.4.2.

The figures are described in the text and not reproduced here fig. 3 fig. 5 fig. 6 fig. 7.

Paper vs code

Code: https://github.com/sferes2/modular_QD at 5d70c140a5775829bc7b688c93edae4c80b71696. The paper links it, and the README lists Antoine Cully as author. It is built on the sferes2 framework, which is not in this repository. There is no LICENSE file, and the source headers in quality_diversity.hpp and scenarii/scenario_arm.cpp name the CeCILL license. Code is cited by path and line, with no verbatim snippets.

Checked against the code, and matching the paper: batch size 200, k = 15, eps = 0.1, archive l, sub-grid depths, grid shapes, mutation rates, crossover off, genotype sizes, curiosity reward +1 and penalty −0.5, and curiosity starting at 0 tab. 2 scenario_arm.cpp quality_diversity.hpp quality_diversity.hpp fit_qd.hpp.

Differences:

1. Arm quality is a standard deviation, not a variance. The paper says the quality is the variance of joint angles §4.2.1. The code takes the square root of the mean squared deviation, i.e. the standard deviation, and negates it scenario_arm.cpp. Quality is therefore negative, as the figure caption also says fig. 4.
2. Second-neighbour test. The paper rejects a candidate when its distance to the second-nearest member does not exceed l §3.1.2. The code rejects only when the distance is below (1 − eps) × l archive.hpp. A candidate at a distance between 0.9 l and l is therefore accepted by the code and rejected by the paper. A commented-out line uses plain l, and the author's comment says the (1 − eps) form "works better" archive.hpp.
3. Sign-dependent tolerance. The paper multiplies by (1 − eps) for both objectives §3.1.2. The code uses (1 − sign(value) × eps) archive.hpp with sign(d) = −1 for d < 0 and +1 otherwise tool.hpp. For a negative value, such as the arm's quality, this becomes (1 + eps) × value, which loosens the test and lets through candidates the paper rejects.
4. Absolute values in condition 3. The code's third condition multiplies by absolute values of the nearest member's scores archive.hpp. The paper's inequality has no absolute values §3.1.2.
5. Novelty neighbours differ between candidate and member. The paper states the traditional mean over the k nearest neighbours §3.1.2. The code averages over k+1 neighbours for the candidate archive.hpp and over k neighbours with the member itself omitted for members archive.hpp archive.hpp.
6. Curiosity credited by index. Offspring are built from _parents[a[i]], where a is a list from misc::rand_ind quality_diversity.hpp. The insertion call pairs offspring i with _parents[i] quality_diversity.hpp quality_diversity.hpp. Algorithm 1 credits the actual parent alg. 1. Unless misc::rand_ind is the identity permutation (a sferes2 utility not in this repository), the code credits a different individual. This is an inference from the code, not a run.
7. Grid tie-break. Equal performance is broken by distance to the cell centre grid.hpp. The paper keeps only the higher performer §3.1.1.
8. NSLC and crowding. The code tags the Pareto selector as NSLC scenario_arm.cpp and sets a genotypic-diversity crowding flag scenario_arm.cpp which is passed to the crowding assignment paretoBased.hpp. The paper describes NSGA-II-style selection without this term §3.2.5. NSLC's rho_init from tab. 2 has no counterpart in the repository.
9. Hexapod turn descriptor and quality. The descriptor is the final position divided into a box of radius 1 m scenario_hexa_turn.cpp. The orientation error is rounded to 0.01 rad before conversion to degrees scenario_hexa_turn.cpp. Neither detail is stated in the paper §4.3.1.
10. Sanity checks. Gait individuals are marked dead when the distance is below −1000 or above 1.5 scenario_hexa_walk.cpp. Neither bound is mentioned in the paper.
11. Iteration counts. The code's counts are 50001, 10001 and 20001 scenario_arm.cpp scenario_hexa_turn.cpp scenario_hexa_walk.cpp, against 50,000, 10,000 and 20,000 in tab. 2. The difference is likely a counting convention, which is not stated.
12. Missing dependencies. The hexapod scenarios need external simulator and controller packages, and the build requires the robdyn option wscript. Those packages are not in this repository and were not checked.

Pitfalls

• Degenerate score-proportionate draw. When every member has the same score, the weights sum to zero and each draw returns the first member of the list scoreProportionate.hpp. After a few batches this is unlikely, but it can happen, for example when all curiosity values are equal.
• Dead individuals and novelty. Dead individuals get novelty and local quality of minus infinity archive.hpp. Population-based selectors read offspring directly, so a novelty-proportionate draw can receive a minus-infinity minimum, which makes the weights non-finite scoreProportionate.hpp. The repository's dead-individual rules are not described in the paper, and whether this occurs in practice was not tested.
• Density units. The archive threshold l is in normalised descriptor units. The paper uses 0.01 for the 2-D tasks and 0.25 for the 6-D gaits task tab. 2. The value is not transferable to other descriptor ranges without renormalising.
• Cost of the grid. The gait task grid has 5^6 = 15,625 cells scenario_hexa_walk.cpp. The archive recomputes novelty and local quality for every member after each batch archive.hpp, so update cost grows with the collection, which reached about 6,000 members in the arm task §4.2.2.
• Hexapod run time. One variant takes 4 to 5 hours per 10,000 batches on the physical simulator §4.3.1. Reproducing these runs also needs the external simulator packages (Paper vs code, item 12).
• Small samples. There are 10 to 20 replications per variant. The paper uses Wilcoxon rank-sum tests with Holm–Bonferroni correction §4.2.2 footnote. Some NSLC comparisons in the gaits task (p < 0.0374) do not pass the corrected threshold at α = 0.05 and pass only at α = 0.1 §4.4.2 footnote.
• Interpreting "best". The statement that curiosity outperforms all other tested algorithms on all experiments is the authors' conclusion §5. The arm experiment's Pareto result and the population-based gaits result show that the ranking depends on the metric.
• Curiosity dynamics. Curiosity can go negative, and the scores change during the run. The paper argues that a population of 200 cannot track the highest-curiosity individuals in an arm collection of about 6,000 §4.2.2.
• Selection pressure. The paper says uniform random selection loses pressure as the collection grows §3.2.2. The gait experiment shows random selection as second best at 20,000 batches §4.4.2.

Lineage

• Builds on: MAP-Elites and Novelty Search with Local Competition, the two methods the paper unifies §1 tab. 1. It also builds on the BR-Evolution archive, whose replacement rule the new archive rule changes §3.1.2.
• Compared against: MAP-Elites variants (grid, random selection), NSLC, population-based EA, no-selection motor babbling, novelty-based MAP-Elites variant tab. 1 §4.
• Superseded by: not stated.