MAP-Elites: алгоритм, который ищет не одно лучшее решение, а лучшее в каждой нише

Обычные оптимизаторы — градиентный спуск, генетические алгоритмы с элитизмом, CMA-ES — ищут один глобальный максимум, отбрасывая всё остальное. Но во многих прикладных задачах нужно не одно «лучшее», а целый набор хороших решений: библиотека походок для робота на случай отказа сустава, уровни игры разной сложности, инженерные компромиссы между весом, прочностью и стоимостью. Это направление называют Quality-Diversity (QD) оптимизацией.

MAP-Elites (Multi-dimensional Archive of Phenotypic Elites), предложенный в 2015 году, — один из первых и концептуально самых простых алгоритмов QD. Его идея: разбить пространство возможных поведений на ячейки (ниши) и в каждой хранить лучшее из найденных решений. Так вместо одной точки получается карта элит, покрывающая весь спектр вариантов. Алгоритм нашёл применение в эволюционной робототехнике, процедурной генерации контента и открытых эволюционных системах.