An Extended Study of Quality Diversity Algorithms

ABSTRACT

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.

References

1. J. Lehman and K. O. Stanley. Evolving a diversity of virtual creatures through novelty search and local competition. In phProceedings of the 13th Annual Conference on Genetic and Evolutionary Computation, pages 211--218. ACM, 2011.
2. J.-B. Mouret and J. Clune. Illuminating search spaces by mapping elites. pharXiv preprint arXiv:1504.04909, 2015.
3. J. K. Pugh, L. B. Soros, P. A. Szerlip, and K. O. Stanley. Confronting the challenge of quality diversity. In phProceedings of the 17th Annual Conference on Genetic and Evolutionary Computation, ACM, 2015.

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Planning and scheduling

      • Robotic planning

        • Evolutionary robotics

  • Machine learning

    • Machine learning approaches

      • Bio-inspired approaches

      • Neural networks

• Mathematics of computing

  • Mathematical analysis

    • Mathematical optimization

      • Discrete optimization

        • Optimization with randomized search heuristics

          • Evolutionary algorithms