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 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 даёт не "оптимум", а карту компромиссов . Ценятся не проценты заполнения, а покрытие достижимых ниш и разнообразие поведений . Итог: простой, линейный по числу оценок, даёт инженеру не одну точку, а весь фронт возможностей.
https://habr.com/ru/articles/1061588/
#genetic_algorithms #искусственный_интеллект #разработка_игр #машинное+обучение
