MAP-Elites: алгоритм поиска лучшего решения в каждой нише

MAP-Elites (Multi-dimensional Archive of Phenotypic Elites) — это алгоритм, предложенный в 2015 году, который решает задачу Quality-Diversity оптимизации: вместо поиска одного глобального максимума он стремится заполнить пространство поведенческих дескрипторов лучшими решениями в каждой нише. Алгоритм использует архив-сетку, где каждая ячейка соответствует определённому поведению (дескриптору), и хранит в ней наилучшее найденное решение. Работа начинается с инициализации случайными решениями, затем на каждой итерации из архива случайно выбирается родитель, мутируется, оценивается приспособленность и поведенческий дескриптор потомка, и если ячейка пуста или потомок лучше — решение заменяется. Современные версии (CMA-ME, pyribs, QDax) используют более сложные эмиттеры для генерации кандидатов. В статье приведён пример реализации на Python для игрушечной задачи с сеткой 20×20, где после 5000 итераций было заполнено 379 из 400 ячеек. Автор отмечает, что из-за локальной мутации некоторые ячейки могут остаться недостижимыми, а в реальных задачах часть поведенческого пространства физически нереализуема, поэтому цель — не 100% покрытие, а разнообразие в достижимых нишах.