An Extended Study of Quality Diversity Algorithms
Justin K. Pugh, Lisa B. Soros, Kenneth Owen Stanley · 2016
In a departure from conventional optimization where the goal is to find the best possible solution, a new class of evolutionary algorithms instead search for quality diversity (QD) -- a maximally diverse collection of individuals in which each member is as high-performing as possible. In QD, diversity of behaviors or phenotypes is defined by a behavior characterization (BC) that is typically unaligned with (i.e. orthogonal to) the notion of quality. As experiments in a difficult maze task reinforce, QD algorithms driven by such an unaligned BC are unable to discover the best solutions on sufficiently deceptive problems. This study comprehensively surveys known QD algorithms and introduces several novel variants thereof, including a method for successfully confronting deceptive QD landscapes: driving search with multiple BCs simultaneously.