MAP-Elites: как искать не «лучшее», а «лучшее в каждой нише»
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 spaceN_ITERATIONS = 5000MUTATION_SIGMA = 0.2def 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 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.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 даёт не «оптимум», а карту компромиссов. Ценятся не проценты заполнения, а покрытие достижимых ниш и разнообразие поведений.Итог: простой, линейный по числу оценок, даёт инженеру не одну точку, а весь фронт возможностей. Читать далее
03:45
03:24
15:50
