MAPElites

MAPElites is a family of quality diversity algorithms used in artificial intelligence and evolutionary computation. These algorithms aim to find a diverse set of high-performing solutions to optimization problems, rather than a single optimal solution. The core idea is to divide the search space into a grid of "niches" defined by user-specified behavioral descriptors. MAPElites then maintains a collection of the best solution found so far for each niche. When a new candidate solution is generated, it is evaluated based on its performance and its position in the behavioral space. If the candidate is better than the current best solution in its corresponding niche, or if the niche is empty, the candidate replaces the existing solution in that niche. This process encourages exploration across the behavioral dimensions, ensuring that a wide range of behaviors, each with good performance, is discovered. MAPElites has been applied to various domains including game AI, robotics, and creative content generation, demonstrating its utility in problems where exploring diverse strategies or designs is valuable.