year: 2025
paper: https://wires.onlinelibrary.wiley.com/doi/epdf/10.1002/wics.70047?domain=author&token=MQ5TDUHQGG2WNBP2PHF3 | html version
website:
code:
connections: quality diversity, novelty search, minimal-criterion novelty search MAP-Elites, diffusion evolution
Background & Evolution of Novelty Search / Quality-Diversity Methods
Behavioral descriptors can be derived from the internal representation / structure of the solution (cf. genotype) or obtained upon applying the solution (cf. phenotype).Circular transclusion detected: general/Quality-Diversity-Methods-for-the-Modern-Data-Scientist
Circular transclusion detected: general/Quality-Diversity-Methods-for-the-Modern-Data-Scientist
Circular transclusion detected: general/Quality-Diversity-Methods-for-the-Modern-Data-Scientist
Circular transclusion detected: general/Quality-Diversity-Methods-for-the-Modern-Data-Scientist
Novelty search
Rather than pursuing the best-performing solution, NS rewards solutions that behave differently from those already discovered. It evaluates candidates solely based on behavioral novelty, quantified using a novelty score. This score is computed by maintaining an archive of previously encountered solutions and calculating the average distance between a candidate’s behavioral descriptor and those of its nearest neighbors in the archive. This mechanism encourages exploration of the behavior space without regard for objective performance. For example, when evolving robot locomotion strategies, NS would prefer a new gait pattern, regardless of its speed, if that gait differed sufficiently from previous ones. This behavioral prioritization allows NS to uncover stepping stones—intermediate solutions that may not be useful or optimal in themselves but can lead to qualitatively better outcomes in the future. For instance, a robot might first learn how to fall or roll in novel ways before eventually discovering how to walk. While falling is neither optimal nor desired behavior by objective standards, it opens up new behavioral trajectories that make walking discoverable later on. This principle demonstrated, for the first time, the effectiveness of conducting the search in the behavioral space rather than exclusively in the objective space.
Minimal Criteria Novelty Search
While novelty search enabled the discovery of diverse behaviors, it suffered from a lack of direction—often leading to aimless exploration and accumulation of novel but low-performing solutions. This limitation motivated the development of Minimal Criteria Novelty Search (MCNS), which introduced a simple yet effective mechanism: solutions had to meet a minimal performance threshold to be considered viable. Only those satisfying this threshold were eligible for selection based on their novelty. This approach ensured that exploration was constrained to regions of the behavioral space that were at least marginally useful, such as robots that moved forward by any means. Although MCNS brought the search closer to relevance, it still lacked strong selective pressure toward improvement beyond the minimal criteria.
Novelty Search with Local Competition
The next conceptual advance came with Novelty Search with Local Competition (NSLC), which combined the benefits of novelty-driven exploration with localized performance optimization. NSLC retained the novelty criterion but added a second selection pressure: solutions were compared only to their behavioral neighbors and rewarded if they outperformed them in quality. This dual pressure balanced exploration and exploitation, rewarding both novel behaviors and local excellence. NSLC can thus be seen as one of the first fully fledged QD algorithms, as it explicitly optimizes for both quality and diversity. However, it required the definition of behavior neighborhoods and distance metrics, which could be non-trivial to choose and tune, particularly in high-dimensional or irregular behavior spaces.
MAP-Elites
A major step forward was the introduction of MAP-Elites, which restructured the QD process through a conceptually simple yet powerful framework. MAP-Elites discretizes a user-defined behavioral space into a grid of niches and maintains, for each niche, the highest-performing solution found so far, that is, the elites. New solutions are generated by varying existing elites and are inserted into the archive if they outperform the current occupant of a cell. This setup enables the search to simultaneously explore and exploit, systematically illuminating the space of possible behaviors. MAP-Elites proved particularly successful in robotics, where it enabled damaged robots to adapt by drawing on a pre-computed archive of alternative gaits tailored to different behavior niches.
Despite its advantages, MAP-Elites faces scalability challenges. Due to the curse of dimensionality, the number of niches grows exponentially with the number of behavior descriptor dimensions, making it computationally expensive and memory-intensive in high-dimensional settings. Several extensions have been proposed to address these limitations. Centroidal Voronoi Tessellation (CVT)-MAP-Elites replaces the rigid grid with a Centroidal Voronoi Tessellation, which uses clustering to define a fixed number of behavioral niches, making it more suitable for high-dimensional behavior spaces. CMA-ME integrates cma-es within each niche, adapting the mutation distribution to local performance gradients and improving sample efficiency and behavior space coverage. In cases where both the quality and behavior functions are first-order differentiable, Differentiable Quality Diversity (DQD) algorithms leverage gradient information to guide the search process more effectively. For example, MAP-Elites via Gradient Arborescence (MEGA) uses gradients to branch out across the behavior space while ascending the quality landscape, significantly improving sample efficiency in continuous domains… and more.,