Стать автором

Вернуться

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

21.07.2026 18:28:57 | Хабр

Хабы: Python, Поисковая оптимизация

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 даёт не "оптимум", а карту компромиссов. Ценятся не проценты заполнения, а покрытие достижимых ниш и разнообразие поведений.

Итог: простой, линейный по числу оценок, даёт инженеру не одну точку, а весь фронт возможностей.

Подробнее

Читайте также