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

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

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

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

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

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

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

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

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

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

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

Оригинальный препринт:  — «Illuminating search spaces by mapping elites: a new algorithm for pursuing quality diversity» — https://arxiv.org/abs/1504.04909

Ключевая идея разделяет пространство решений на два независимых измерения:

Генотип — параметры решения, которые мы мутируем/скрещиваем.

Поведенческий дескриптор — низкоразмерный вектор признаков, описывающий как решение себя проявляет (не насколько оно хорошо, а какое оно). Например, для походки робота это может быть «средняя высота подъёма ноги» и «энергопотребление».

Пространство поведенческих дескрипторов заранее дискретизируется в регулярную сетку ячеек (их еще называют ниши). Алгоритм поддерживает архив, где в каждой ячейке хранится максимум одно решение — то, что оказалось лучшим (по приспособленности) среди всех когда‑либо попавших в эту ячейку.

Как это работает пошагово:

1) Инициализировать пустой архив‑сетку N‑мерных ячеек.

2) Сгенерировать случайную начальную популяцию решений, оценить их приспособленности и поведенческому дескриптору, поместить каждое в соответствующую ячейку (если ячейка пуста или новый кандидат лучше текущего жителя - записать его в архив).

3) Цикл до исчерпания бюджета оценок:

3.1) Выбрать случайное существующее решение из архива (уже заполненную ячейку).

3.2) Мутировать его (иногда — скрестить с другим случайным жителем архива).

3.3) Оценить потомка: посчитать приспособленность и поведенческий дескриптор.

3.4) Определить, в какую ячейку сетки попадает потомок.

3.5) Если ячейка пуста ИЛИ потомок лучше текущего обитателя этой ячейки — заменить.

По завершении архив представляет собой карту (map) «elite»‑решений — по одному лучшему решению на нишу.

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

В классическом MAP‑Elites родитель выбирается равновероятно среди всех заполненных ниш архива. Такая стратегия максимально проста и не создаёт смещения поиска, однако значительная часть вычислений со временем начинает тратиться на области, которые уже практически перестали улучшаться. Поэтому в последующих работах были предложены различные стратегии выбора родителей: отдавать предпочтение недавно открытым нишам, областям с низкой плотностью решений (границам архива), элитам, чьи потомки чаще создают новые или улучшают существующие ниши, а также использовать механизмы curiosity, увеличивающие вероятность выбора наиболее «продуктивных» решений.

Современные реализации MAP‑Elites (например, CMA‑ME и библиотеки pyribs или QDax) обычно идут ещё дальше и отделяют архив от механизма генерации новых решений. Вместо простой случайной мутации используются специализированные эмиттеры (emitters), которые самостоятельно выбирают родителей и применяют различные стратегии поиска (генетические операторы, CMA‑ES, суррогатные модели, градиентные методы и др.). При этом сам принцип MAP‑Elites остаётся неизменным: архив по‑прежнему хранит лучшее решение в каждой нише,

а различаются лишь способы поиска новых кандидатов.

Сложность

Пусть:

M — число ячеек в архиве (произведение числа делений по каждому измерению множества поведений),

T — число итераций (эволюционных поколений/оценок),

D — размерность генотипа,

E — стоимость одной оценки решения (симуляция/вычисление приспособленности).

По времени: каждая итерация — это выбор случайного родителя за O(1) (при хранении в виде массива/словаря), мутация за O(D),

вычисление дескриптора и приспособленности — доминирующая часть, O(E), и вставка/сравнение в ячейке за O(1).

Итого на одну итерацию — O(D + E), а весь алгоритм — O(T·(D + E)).

На практике E почти всегда доминирует (типичные оценки включают симуляцию физики, клеточных автоматов, инференс LLM и тому подобное), так что сложность алгоритма как такового — линейная по числу оценок,

это его отличие от многих QD‑методов (например, есть такой алгоритм, Novelty Search с k‑NN по архиву — там поиск соседей стоит O(log|archive|) или O(|archive|) на добавление).

Базовая имплементация

```python

import numpy as np

# Задача: найти x, y в [-5, 5], максимизируя fitness,

# ниши определяются по (x, y) с сеткой 20x20

BOUNDS = (-5.0, 5.0)

GRID_SIZE = 20 # число ячеек по каждой оси behavior space

N_ITERATIONS = 5000

MUTATION_SIGMA = 0.2

def fitness(genome):

x, y = genome

# произвольная многомодальная функция для иллюстрации

return -(x**2 + y**2) + 5 np.sin(3 * x) * np.cos(3 * y)

def behavior_descriptor(genome):

# в этой игрушечной задаче поведенческий дескриптор совпадает с генотипом,

# в реальных задачах это обычно совсем другое пространство признаков

return genome

def to_cell(bd):

lo, hi = BOUNDS

idx = ((bd - lo) / (hi - lo) * GRID_SIZE).astype(int)

return tuple(np.clip(idx, 0, GRID_SIZE - 1))

def random_genome():

return np.random.uniform(*BOUNDS, size=2)

def mutate(genome):

child = genome + np.random.normal(0, MUTATION_SIGMA, size=genome.shape)

return np.clip(child, *BOUNDS)

# архив: ключ - индекс ячейки, значение - (genome, fitness)

archive = {}

# 1) инициализация случайными решениями

for _ in range(200):

g = random_genome()

f = fitness(g)

cell = to_cell(behavior_descriptor(g))

if cell not in archive or f > archive[cell][1]:

archive[cell] = (g, f)

# 2) основной цикл MAP-Elites

for it in range(N_ITERATIONS):

parent_cell = list(archive.keys())[np.random.randint(len(archive))]

parent_genome, = archive[parent_cell]

child = mutate(parent_genome)

f_child = fitness(child)

cell = to_cell(behavior_descriptor(child))

if cell not in archive or f_child > archive[cell][1]:

archive[cell] = (child, f_child)

print(f"Заполнено ниш: {len(archive)} / {GRID_SIZE**2}")

best_cell = max(archive, key=lambda c: archive[c][1])

print("Лучшее решение:", archive[best_cell])

```

Вывод результатов:

Заполнено ниш: 379 / 400 # финальная заполненность не детерминированная, зависит от случайной инициализации и мутаций

Лучшее решение: (array([0.52733742, 0.00456922]), np.float64(4.721110167064826))

Как это интерпретировать?

1) Изначальные 200 случайных геномов при равномерном разбросе по сетке 20×20=400 ячеек попадают в ячейки далеко не равномерно — часть клеток просто не выпадает по закону больших чисел

(как при бросании 200 шаров в 400 корзин, часть корзин гарантированно останется пустой).

2) После 5000 итераций алгоритм успел заполнить почти все ячейки, но не все — некоторые ячейки так и не были достигнуты за выделенный бюджет оценок из-за локального характера мутации и случайной инициализации.

3) Мутация — локальный оператор, а не глобальный поиск. На каждой итерации ребёнок получается из родителя гауссовским шумом с σ=0.2.

Это значит, что новый кандидат почти всегда падает рядом со своим родителем во множестве поведений. Если какая‑то ячейка сетки не была занята на старте, и вокруг неё тоже нет занятых соседей (то есть до неё нет «моста» из заполненных ниш), у алгоритма практически нет шанса туда допрыгнуть за разумное число итераций — это классический эффект изоляции ниш при чисто локальной мутации.

4) В реальных задачах поведенческий дескриптор может быть совсем не совпадать с генотипом, и тогда «мосты» между нишами могут быть ещё более редкими.

5) Сама fitness‑функция. Многие комбинации (x, y) физически не бывают «лучшими ни в чём» — если приспособленность в каком‑то регионе всегда хуже, чем в соседних, то решения там просто быстро «проигрывают» и вымирают, но сама ячейка при этом всё равно может быть достигнута случайным блужданием — так что это не главная причина пустот, а скорее (3) и (1).

6) Из‑за (5) почти никогда не берут простую гауссовскую мутацию — используют направленный шаг вдоль линии между двумя случайными жителями архива, что резко улучшает связность архива и покрытие

Что значит «Лучшее решение»:

(array([0.52733742, 0.00456922]), np.float64(4.721110167064826))

Это геном (x, y) ≈ (0.527, 0.005) и его fitness ≈ 4.721 — генотип из той ниши архива, у которой fitness оказался максимальным среди всех 379 заполненных ячеек. Поскольку в этой игрушечной задаче behavior_descriptor = генотип, «лучшая ниша» здесь просто совпадает с глобальным (или локальным) максимумом функции ‑(x²+y²) + 5·sin(3x)·cos(3y) вблизи начала координат — то есть в этом вырожденном случае MAP‑Elites фактически выродился в обычный поиск максимума плюс попутное картирование окрестности, что и ожидаемо, раз здесь пространство ниш не несёт отдельной поведенческой информации, а дублирует генотип.

Важно понимать: 379 из 400 в этом примере — не «недолёт» алгоритма, а скорее иллюстрация того, что даже на простейшей функции с локальной гауссовской мутацией мы не получаем 100% покрытия. В реальных же задачах цель MAP‑Elites практически никогда не состоит в том, чтобы заполнить вообще все мыслимые ниши подряд. Чаще всего часть поведенческого пространства физически нереализуема (для шагающего робота, например, не существует походки, которая одновременно тратит ноль энергии и высоко поднимает ногу — на эту комбинацию придётся пустая ячейка, и это нормально).

Поэтому в QD‑оптимизации ценятся не столько проценты заполнения, сколько покрытие достижимых ниш и разнообразие поведений внутри них.

Итого:

В этой статье мы рассмотрели классический MAP-Elites. В современных реализациях чаще используются более сложные стратегии генерации кандидатов — CMA-ME, GeneticEmitter, Surrogate-assisted MAP-Elites и другие. Именно эти методы сегодня составляют основу большинства исследований в области Quality-Diversity.