MAP‑Elites: как искать не «лучшее», а «лучшее в каждой нише»

Проблема, которую не решает обычная оптимизация

Классические методы оптимизации — градиентный спуск, генетические алгоритмы с элитизмом, CMA‑ES — заточены под одну вещь: найти один глобальный максимум функции приспособленности. Всё остальное население на пути к этому максимуму считается расходным материалом и отбрасывается.

Но во многих задачах нас интересует не единственное решение, а набор разнообразных хороших решений:

Эволюционная робототехника. Нужно не одно «оптимальное» положение ног шагающего робота, а целая библиотека походок под разные повреждения — если у робота откажет один сустав, он должен уметь быстро подобрать альтернативную походку вместо повторной оптимизации с нуля.

Процедурная генерация контента в играх. Нужны не «лучшие» уровни, а уровни, покрывающие весь спектр: лёгкие/сложные, линейные/разветвлённые.

Дизайн и инженерия. Инженеру интересно увидеть весь фронт компромиссов (вес vs прочность vs стоимость), а не одну точку.

Открытые (так называемый open‑ended) эволюционные системы, где само понятие «лучшего» плохо определено, а интересна широта поведенческого репертуара.

Это направление получило название Quality‑Diversity (QD) оптимизации: цель — не максимизировать один скаляр, а заполнить пространство возможных поведений решениями, каждое из которых максимально хорошо в своей поведенческой нише.

MAP‑Elites — один из первых и самый концептуально простой алгоритм этого семейства.

Идея алгоритма

MAP‑Elites (Multi‑dimensional Archive of Phenotypic Elites) был предложен в 2015 году.