MAP-Elites: Отдельные максимумы вместо единого оптимума

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

Задачи, требующие разнообразия решений

  • Эволюционная робототехника: Вместо одной «идеальной» походки для шагающего робота необходима библиотека адаптивных движений, позволяющая роботу быстро переключаться на альтернативные стратегии при повреждении сустава без необходимости повторной оптимизации.
  • Процедурная генерация контента: В игровой индустрии важно создавать не просто «лучшие» уровни, а уровни, охватывающие весь спектр сложности и структуры — от простых и линейных до сложных и разветвленных.
  • Дизайн и инженерия: Инженеры заинтересованы в изучении всего фронта компромиссов, например, между весом, прочностью и стоимостью, а не только в одной точке оптимального решения.
  • Открытые эволюционные системы: В таких системах, где понятие «лучшего» часто размыто, важна широта поведенческого репертуара.

MAP-Elites (Multi-dimensional Archive of Phenotypic Elites), предложенный в 2015 году, является одним из первых и наиболее концептуально простых алгоритмов в семействе QD-оптимизации.

Принцип работы MAP-Elites

Основная идея MAP-Elites заключается в разделении пространства поведений на сетку дискретных ниш. В каждой нише алгоритм хранит лишь одно, наилучшее решение. Мутации применяются к генотипу, а поведенческий дескриптор (например, высота шага или энергетические затраты) используется для определения соответствующей ячейки в сетке.

Алгоритм функционирует следующим образом:

  1. Инициализация пустого архива.
  2. Генерация случайной популяции решений, оценка их приспособленности (fitness) и поведенческого дескриптора. Каждое решение помещается в соответствующую ячейку архива, если ячейка пуста или новое решение превосходит существующее.
  3. В цикле выбирается родительское решение из архива, мутируется, оценивается его приспособленность и поведенческий дескриптор. Если мутировавшее решение лучше существующего в своей нише или ниша пуста, оно добавляется в архив.

Важной особенностью является отсутствие отбора между нишами, что позволяет алгоритму формировать карту всего пространства компромиссов, а не фокусироваться на одной точке. Примеры реализации показывают, что алгоритм эффективно заполняет достижимые ниши, даже если не все ячейки могут быть заполнены из-за локальности мутаций или физической недостижимости некоторых поведенческих комбинаций.

Производительность и значимость

Сложность алгоритма MAP-Elites по времени оценивается как O(T·(D + E)), где T — число итераций, D — размерность генотипа, а E — стоимость одной оценки решения. Этот подход предоставляет инженерам не просто «оптимум», а всеобъемлющую карту компромиссов, подчеркивая ценность покрытия достижимых ниш и разнообразия поведений. MAP-Elites является простым, линейным по числу оценок и эффективным инструментом для исследования широкого спектра возможностей.