MAP-Elites: лучший в каждой нише
Классическая оптимизация ищет один максимум. Но в робототехнике, генерации уровней и инженерии нужен набор разнообразных хороших решений — библиотека походок под разные поломки, уровни любой сложности, фронт компромиссов.
Это Quality-Diversity. MAP-Elites (2015, arXiv:1504.04909) — простейший алгоритм.
Идея: делим пространство поведений на сетку ниш. В каждой нише храним одно лучшее решение. Генотип мутируем, поведенческий дескриптор (высота шага, энергия) — для адресации ячейки.
Алгоритм:
Пустой архив.
Случайная популяция → оценить fitness и дескриптор → в ячейку (если лучше).
Цикл: выбрать родителя → мутировать → оценить → в ячейку, если пусто или лучше.
Никакого отбора между нишами — только внутри. Это даёт карту всего пространства, а не одну точку.
Код:
```
import numpy as np
# Задача: найти x, y в [-5, 5], максимизируя fitness, ниши определяются по (x, y)
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):
# в этой игрушечной задаче поведенческий дескриптoр совпадает с генотипом,
# в реальных задачах это обычно совсем другое пространство признаков
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)
# 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)
Вывод: 379 / 400, лучшее (0.527, 0.005), fitness 4.72.
Почему не 400? Три причины:
200 случайных точек не покрывают все ячейки (эффект корзин).
Мутация локальна (σ=0.2). До пустой ячейки без занятых соседей не допрыгнуть — изоляция ниш.
В реальности часть пространства физически недостижима (напр, походка с нулевой энергией и высоким шагом).
Сложность
M — число ячеек в архиве (произведение числа делений по каждому измерению множества поведений), T — число итераций (эволюционных поколений/оценок), D — размерность генотипа, E — стоимость одной оценки решения (симуляция/вычисление приспособленности).
По времени: каждая итерация - это выбор случайного родителя за O(1) (при хранении в виде массива/словаря), мутация за O(D), вычисление дексриптора и приспособленности — доминирующая часть, O(E), и вставка/сравнение в ячейке за O(1). Итого на все итерации - O(T·(D + E))
Вывод: MAP-Elites даёт не "оптимум", а карту компромиссов. Ценятся не проценты заполнения, а покрытие достижимых ниш и разнообразие поведений.
Итог: простой, линейный по числу оценок, даёт инженеру не одну точку, а весь фронт возможностей.
