Quality-diversity optimization
Quality-diversity optimization (QD) is a family of evolutionary algorithms whose goal is not to return a single best solution but to illuminate a search space by returning a large archive of solutions that are simultaneously high-performing and diverse.[1] Rather than treating diversity as a means of escaping local optima on the way to one global optimum, QD algorithms treat the collection of diverse, locally optimal solutions as the desired output in its own right. Each entry in the returned archive is the best solution found so far that exhibits a particular combination of user-defined behavioral or feature characteristics, so the archive maps how performance varies across the space of possible behaviors.[2]
The paradigm emerged from research on open-ended evolution and divergent search in evolutionary computation, and it unifies two earlier lines of work: Novelty search, which rewards solutions for being behaviorally different from those already found, and objective-based selection, which rewards quality.[1] QD algorithms combine both pressures so that the population diversifies across the behavior space while each niche is optimized for performance.[1] Because the output is an archive rather than a point, QD is sometimes described as an illumination algorithm, a term introduced to distinguish it from conventional optimization, which is characterized as returning only the highest point of a landscape.[2]
Motivation and definition
Conventional optimization seeks a single solution that maximizes (or minimizes) an objective function. In many deceptive or open-ended problems, however, a purely objective-driven search converges prematurely to a single region and discards the intermediate stepping stones that would have led to qualitatively different, and sometimes ultimately better, solutions.[3] The founding insight of divergent search is that in naturally evolving systems, pressure toward novelty can discover complex, functional structures even without an explicit objective, because rewarding behavioral difference forces the search to keep accumulating stepping stones.[3]
Quality-diversity optimization formalizes this idea. A QD problem is specified by three ingredients: a genotype or solution space to be searched, a scalar quality (fitness) function, and a behavior descriptor (also called a feature or behavior characterization) that maps each candidate solution to a low-dimensional vector describing how it behaves.[1] The task is to return, for every reachable region of the behavior space, the highest-quality solution that maps to that region.[2] The behavior descriptor is chosen by the practitioner and defines the axes along which diversity is measured — for example, in a locomotion task the descriptor might record which legs a robot uses, independent of how fast it moves.[4]
Canonical algorithms
Two algorithms are generally regarded as the canonical members of the QD family, and most later methods are variants or hybrids of them.[1]
MAP-Elites
The Multi-dimensional Archive of Phenotypic Elites (MAP-Elites) discretizes the behavior space into a grid of cells, each corresponding to a range of behavior-descriptor values.[2] The algorithm maintains at most one solution — the elite — per cell. New candidates are generated by varying existing elites; each candidate is evaluated, assigned to the cell matching its behavior descriptor, and kept only if its cell is empty or if it outperforms the current occupant.[2] Repeating this process gradually fills the grid with a diverse set of high-performing solutions, producing a map of how the best achievable quality varies across the behavior space.[2] MAP-Elites is valued for its conceptual simplicity and for exposing relationships between behavioral features and performance that a single-solution optimizer would hide.[2]
Novelty search with local competition
Novelty search with local competition (NSLC) predates the MAP-Elites formulation and combines two selection pressures within a population-based evolutionary algorithm.[1] A novelty pressure rewards each individual in proportion to how behaviorally different it is from the individuals nearest to it in behavior space, driving the population to spread out. Simultaneously, a local competition pressure rewards each individual for outperforming its behavioral neighbors rather than the population as a whole, so that quality is optimized separately within each behavioral niche.[1] By competing only locally, NSLC avoids the premature convergence that occurs when a globally superior morphology or strategy dominates selection, and it was originally shown to discover a wider range of functional forms in a single run of evolving virtual creatures.[5]
Relationship to other optimization paradigms
Quality-diversity optimization is distinct from both single-objective and multi-objective optimization.[1] Single-objective optimization returns one solution that maximizes a scalar objective, discarding all others. Multi-objective optimization returns a set of non-dominated trade-offs among several conflicting objectives, but that set is defined purely by the objectives; two solutions that achieve the same objective values but behave very differently are treated as interchangeable.[1] QD instead retains diversity along explicitly chosen behavioral dimensions that are not objectives to be optimized, and it seeks the best solution for every such behavior rather than only the non-dominated frontier.[1] In this sense QD generalizes divergent novelty search by adding a local quality pressure, and it can be viewed as running many co-located local optimizations, one per behavioral niche, within a single search.[1]
Because it accumulates and reuses intermediate stepping stones, QD is also related to work on avoiding deception and on open-ended search, where the value of a solution lies partly in the further solutions it enables rather than in its immediate fitness.[3] QD techniques have subsequently been used to pre-compute large repertoires of diverse controllers that downstream systems can select from at run time.[4]
Applications
A prominent demonstration of QD applied MAP-Elites offline to generate a large repertoire of thousands of diverse walking gaits for a legged robot; when the robot was later damaged, an adaptation procedure searched this behavior–performance map to quickly identify a compensating gait, allowing the robot to recover function within about two minutes without diagnosing the specific fault.[4] This behavioral repertoire use case — build a diverse archive of robust options offline, then choose among them online when conditions change — illustrates the general appeal of returning an archive rather than a single plan.[4] QD has since been applied across robotics, procedural content generation, and design exploration, wherever practitioners benefit from seeing a range of qualitatively different high-quality solutions.[1]
Application to workforce management
The QD framing is a natural fit for workforce management and contact-center planning problems, where a planner rarely wants only the single lowest-cost schedule. A staffing or scheduling problem can be posed as a QD problem in which quality is a cost or service-level objective and the behavior descriptor captures operationally meaningful features such as the amount of overtime used, the number of distinct shift patterns, or robustness to demand variability. Illustratively, a MAP-Elites-style search could then return an archive of schedules — one near-optimal plan for each combination of those features — so that a manager confronted with disruptions or a sudden forecast change could select an alternative plan with the desired operational profile rather than re-solving from scratch. This mirrors the robot-repertoire pattern of pre-computing a diverse set of robust options for use when conditions change.[4] Such applications extend the general QD methodology and are not specific published results.
See also
- MAP-Elites
- Novelty search
- Evolutionary computation
- Mathematical optimization
- Pareto efficiency
- Stochastic optimization
References
- ↑ 1.00 1.01 1.02 1.03 1.04 1.05 1.06 1.07 1.08 1.09 1.10 1.11 Pugh, J. K., Soros, L. B., Stanley, K. O. (2016). "Quality Diversity: A New Frontier for Evolutionary Computation". Frontiers in Robotics and AI 3, 40. doi:10.3389/frobt.2016.00040.
- ↑ 2.0 2.1 2.2 2.3 2.4 2.5 2.6 Mouret, J.-B., Clune, J. (2015). "Illuminating search spaces by mapping elites". arXiv:1504.04909 [cs.AI].
- ↑ 3.0 3.1 3.2 Lehman, J., Stanley, K. O. (2011). "Abandoning Objectives: Evolution Through the Search for Novelty Alone". Evolutionary Computation 19 (2), 189–223. doi:10.1162/EVCO_a_00025.
- ↑ 4.0 4.1 4.2 4.3 4.4 Cully, A., Clune, J., Tarapore, D., Mouret, J.-B. (2015). "Robots that can adapt like animals". Nature 521 (7553), 503–507. doi:10.1038/nature14422.
- ↑ Lehman, J., Stanley, K. O. (2011). "Evolving a diversity of virtual creatures through novelty search and local competition". In Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation (GECCO '11), 211–218. doi:10.1145/2001576.2001606.
