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

В сфере искусственного интеллекта произошло заметное событие. MAP-Elites: лучший в каждой нишеКлассическая оптимизация ищет один максимум. Но в робототехнике, генерации уровней и инженерии нужен набор разнообразных хороших решений — библиотека походок под разные поломки, уровни любой сложности, фронт компромиссов. Это Quality-Diversity.

MAP-Elites (2015, arXiv:1504. 04909) — простейший алгоритм. Идея: делим пространство поведений на сетку ниш.

Технические детали

В каждой нише храним одно лучшее решение. Генотип мутируем, поведенческий дескриптор (высота шага, энергия) — для адресации ячейки. Алгоритм:Пустой архив.

Случайная популяция → оценить fitness и дескриптор → в ячейку (если лучше). Цикл: выбрать родителя → мутировать → оценить → в ячейку, если пусто или лучше. Никакого отбора между нишами — только внутри.

Это даёт карту всего пространства, а не одну точку. Код:```import numpy as np# Задача: найти x, y в , максимизируя fitness, ниши определяются по (x, y)BOUNDS = (-5. 0)GRID_SIZE = 20 # число ячеек по каждой оси behavior spaceN_ITERATIONS = 5000MUTATION_SIGMA = 0.

Отраслевые последствия

2def fitness(genome):x, y = genome# произвольная многомодальная функция для иллюстрацииreturn -(x**2 + y**2) + 5 np. cos(3 * y)def behavior_descriptor(genome):# в этой игрушечной задаче поведенческий дескриптoр совпадает с генотипом,# в реальных задачах это обычно совсем другое пространство признаковreturn genomedef to_cell(bd):lo, hi = BOUNDSidx = ((bd - lo) / (hi - lo) * GRID_SIZE). astype(int)return tuple(np.

clip(idx, 0, GRID_SIZE - 1))def random_genome():return np. uniform(*BOUNDS, size=2)def mutate(genome):child = genome + np. normal(0, MUTATION_SIGMA, size=genome.

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:archive = (g, f)Вывод: 379 / 400, лучшее (0. Три причины:200 случайных точек не покрывают все ячейки (эффект корзин). Мутация локальна (σ=0.

Этот прогресс даёт важные сигналы о будущем отрасли, и технологический мир внимательно наблюдает.