Novelty search

Novelty search is a method in evolutionary computation that guides a search by rewarding individuals for being behaviorally different from those previously encountered, rather than for making measurable progress toward a fixed goal. Introduced by Joel Lehman and Kenneth O. Stanley, it deliberately abandons the objective function that ordinarily drives optimization and instead maintains open-ended pressure to discover new behaviors. The central and counterintuitive claim of the approach is that, in problems where the objective is deceptive—where following the gradient of apparent progress leads away from the true goal—ignoring the objective entirely can, on some benchmark tasks, reach it more reliably than searching for it directly. Novelty search is a direct precursor of quality-diversity optimization and is closely tied to the study of open-endedness in artificial life.

Deception in objective-based search

Conventional evolutionary and stochastic optimization methods reward candidate solutions in proportion to a fitness or objective function, on the assumption that increasing fitness moves the search toward a solution. Lehman and Stanley argued that this assumption breaks down whenever the fitness landscape is deceptive: the sequence of intermediate steppingstones needed to reach the global optimum may require passing through regions of low apparent fitness, so a search that always climbs the fitness gradient becomes trapped in local optima that superficially resemble the goal. On such problems, adding more selection pressure toward the objective can make performance worse rather than better, because it prunes exactly the low-fitness intermediate behaviors that are prerequisites for eventual success. This "myth of the objective" was later developed for a general audience by Stanley and Lehman, who argued that ambitious goals are frequently reached through a chain of serendipitous, non-goal-directed steppingstones rather than through direct pursuit.

The algorithm

Novelty search replaces the objective with a measure of behavioral novelty. Each individual is characterized not by its genotype but by a behavior characterization—a domain-specific descriptor of what the individual actually did, such as the final position of a robot in a maze. The novelty of an individual is computed as the average distance, in behavior space, to its k nearest neighbors, drawn both from the current population and from an archive of previously encountered novel behaviors. Individuals in sparse regions of behavior space—those whose behavior is unlike anything seen before—receive high novelty scores and are preferentially selected, while individuals that repeat common behaviors are selected against. Because the archive accumulates over time, regions of behavior space that have already been explored become progressively less rewarding, producing a continual drift toward the unexplored frontier without any reference to a goal. The archive and the nearest-neighbor computation are the only additions relative to a standard evolutionary algorithm, so novelty search can be dropped into existing frameworks by substituting the novelty metric for the fitness function.

Novelty search with local competition

Pure novelty search rewards difference but is indifferent to quality: a behavior is favored simply for being new, even if it performs the task poorly. To combine exploration with a notion of performance, Lehman and Stanley proposed novelty search with local competition (NSLC), in which each individual is evaluated on two objectives simultaneously—its novelty, and its quality relative only to the behaviorally nearest individuals rather than to the whole population. Local competition means that a niche of unusual behaviors can be maintained even when its absolute performance is lower than that of a dominant niche, because each solution need only outperform its behavioral neighbors. Applied to the evolution of simulated virtual creatures, NSLC produced a wide range of morphologically and functionally distinct creatures in a single run, illustrating how the method illuminates many niches at once rather than converging on a single design.

Relationship to quality-diversity and open-endedness

Novelty search is generally regarded as the conceptual origin of the quality-diversity (QD) family of algorithms, which seek not a single best solution but a large collection of solutions that are both high-performing and behaviorally diverse. NSLC and the later MAP-Elites algorithm are the two canonical QD methods; MAP-Elites replaces the unstructured novelty archive with an explicit discretization of behavior space into a grid of niches, retaining the best individual found in each niche. Both descend from the observation, central to novelty search, that maintaining behavioral diversity is a productive engine of discovery. The approach also connects to research on open-ended evolution, since its removal of a terminal objective allows a search process to keep generating novel behaviors indefinitely rather than halting once a target is met.

Empirical findings and limitations

On deceptive navigation benchmarks such as maze-solving, novelty search has been reported to find goal-reaching behaviors more consistently than objective-based search, because the objective in these mazes rewards proximity to the goal in a way that traps fitness-driven search behind walls. Independent empirical work in evolutionary robotics compared behavioral-diversity methods, including novelty search, against classic objective-based neuroevolution on deceptive maze, light-seeking, and ball-collecting tasks, and found that explicitly encouraging diversity of behaviors substantially improved outcomes over rewarding the objective alone. These results are, however, task-dependent rather than universal. The effectiveness of novelty search hinges on the choice of behavior characterization: if the descriptor is misaligned with the structure of the problem, novelty pressure explores dimensions that are irrelevant to any useful outcome, and the method can waste effort in a large but unproductive behavior space. Analysts of the QD literature note that pure novelty search provides no guarantee of solution quality and that hybrids such as NSLC, or combinations of novelty with a weak objective, are typically needed when both exploration and performance matter.

Relevance to workforce management

The reasoning behind novelty search generalizes to planning problems in workforce management and contact-center operations, where a single scalar objective—such as minimizing forecast error or headcount cost—can be deceptive with respect to broader operational goals. A schedule or staffing plan that scores well on one narrow metric may leave an operation brittle under irregular operations or demand shocks, so that a collection of behaviorally diverse plans is more valuable than one nominal optimum. This motivation parallels the use of QD methods to generate a repertoire of distinct high-performing solutions rather than a single point estimate, and it complements risk-aware formulations that optimize tail outcomes, such as conditional value at risk, instead of an average-case objective. Applications of this kind in operational planning remain illustrative rather than established practice, and any such use would combine novelty-driven exploration with domain-specific quality criteria in the spirit of local competition.

See also

• MAP-Elites
• Quality-diversity optimization
• Evolutionary computation
• Stochastic optimization
• Pareto efficiency
• Mathematical optimization