#genetic_algorithms — Public Fediverse posts

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 #искусственный_интеллект #разработка_игр #машинное+обучение

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

Проблема, которую не решает обычная оптимизация Классические методы оптимизации — градиентный спуск, генетические алгоритмы с элитизмом, CMA‑ES — заточены под одну вещь: найти один глобальный максимум функции приспособленности. Всё остальное население на пути к этому максимуму считается расходным материалом и отбрасывается. Но во многих задачах нас интересует не единственное решение, а набор разнообразных хороших решений: Эволюционная робототехника. Нужно не одно «оптимальное» положение ног шагающего робота, а целая библиотека походок под разные повреждения — если у робота откажет один сустав, он должен уметь быстро подобрать альтернативную походку вместо повторной оптимизации с нуля. Процедурная генерация контента в играх. Нужны не «лучшие» уровни, а уровни, покрывающие весь спектр: лёгкие/сложные, линейные/разветвлённые. Дизайн и инженерия. Инженеру интересно увидеть весь фронт компромиссов (вес vs прочность vs стоимость), а не одну точку. Открытые (так называемый open‑ended) эволюционные системы, где само понятие «лучшего» плохо определено, а интересна широта поведенческого репертуара. Это направление получило название Quality‑Diversity (QD) оптимизации: цель — не максимизировать один скаляр, а заполнить пространство возможных поведений решениями, каждое из которых максимально хорошо в своей поведенческой нише. MAP‑Elites — один из первых и самый концептуально простой алгоритм этого семейства. Идея алгоритма MAP‑Elites (Multi‑dimensional Archive of Phenotypic Elites) был предложен в 2015 году.

https://habr.com/ru/articles/1061584/

#genetic_algorithms #optimization #python

Я хотел повторить Growing Neural CA за вечер. Ушёл месяц

Месяц назад я прочитал на Хабре статью про нейронные клеточные автоматы. Маленькие нейросети управляют клетками на сетке, клетки сами собираются в букву T или крест, и всё это обучается без учителя через что‑то вроде эволюции. Я подумал: круто, повторю за пару вечеров, посмотрю, как себя ведёт. Эта статья — о том, что было дальше. Спойлер: пара вечеров превратилась в месяц, я провёл 22 эксперимента, упёрся в потолок IoU 0.44 на простой букве T, и главное, чему научился — вообще не о нейросетях.

https://habr.com/ru/articles/1039694/

#neural_cellular_automata #neuroevolution #genetic_algorithms #neural_networks #claude_code #ml_engineering #research #pytorch #optuna #reproducibility

[Перевод] Учимся летать: симуляция эволюции на Rust. 5/5

Это заключительная часть серии статей по разработке симуляции эволюции с помощью нейронной сети и генетического алгоритма . Первая часть Вторая часть Третья часть Четвертая часть

https://habr.com/ru/companies/timeweb/articles/825262/

#timeweb_статьи_перевод #rust #neural_networks #algorithms #genetic_algorithms #evolution #эволюция #генетические_алгоритмы #нейронные_сети

[Перевод] Учимся летать: симуляция эволюции на Rust. 4/5

Это предпоследняя часть серии статей по разработке симуляции эволюции с помощью нейронной сети и генетического алгоритма .

https://habr.com/ru/companies/timeweb/articles/823676/

#timeweb_статьи_перевод #rust #neural_networks #algorithms #genetic_algorithms #evolution #эволюция #генетические_алгоритмы #нейронные_сети

[Перевод] Учимся летать: симуляция эволюции на Rust. 3/5

Это третья часть серии статей по разработке симуляции эволюции с помощью нейронной сети и генетического алгоритма . Первая часть Вторая часть В предыдущей статье мы реализовали простую FFNN (feedforward neural network — нейронная сеть прямого распространения), которая может передавать числа через рандомизированные слои — это первый шаг на пути создания мозга. Однако рандомизация — это далеко не все. По большей части эволюция заключается во внесении небольших, постепенных изменений, чтобы система со временем становилась лучше, чтобы наш мозг начал накапливать знания и функционировать так, как ожидается. Но как мы можем обучить группу чисел с плавающей точкой (запятой, если угодно)?

https://habr.com/ru/companies/timeweb/articles/820699/

#timeweb_статьи_перевод #rust #neural_networks #algorithms #genetic_algorithms #evolution #эволюция #генетические_алгоритмы #нейронные_сети

[Перевод] Учимся летать: симуляция эволюции на Rust. 2/5

Это вторая часть серии статей по разработке симуляции эволюции с помощью нейронной сети и генетического алгоритма . Первая часть В этой статье мы заложим основы нашего проекта и реализуем простую FFNN (feedforward neural network — нейронная сеть прямого распространения), которая впоследствии станет мозгом. Мы также рассмотрим множество тонкостей и идиом, которые встречаются в коде Rust, включая тесты. Готовы? Тогда поехали.

https://habr.com/ru/companies/timeweb/articles/818985/

#timeweb_статьи_перевод #rust #neural_networks #algorithms #genetic_algorithms #evolution #эволюция #генетические_алгоритмы #нейронные_сети

[Перевод] Учимся летать: симуляция эволюции на Rust. 1/5

В этой серии статей мы создадим симуляцию эволюции с помощью нейронной сети и генетического алгоритма. Я расскажу вам, как работает простая нейронная сеть и генетический алгоритм, затем мы реализуем их на Rust и скомпилируем приложение в WebAssembly, чтобы получить следующее: Предполагается, что вы немного знакомы с Rust, остальное я постараюсь вам объяснить. Эта серия состоит из нескольких статей: Введение (что мы будем симулировать, как работает нейронная сеть и генетический алгоритм). Реализация нейронной сети. Реализация генетического алгоритма. Реализация глаз, мозга и самой симуляции (в двух частях). Интересно? Тогда поехали.

https://habr.com/ru/companies/timeweb/articles/817585/

#timeweb_статьи_перевод #rust #neural_networks #algorithms #genetic_algorithms #evolution #эволюция #генетические_алгоритмы #нейронные_сети

Создание простого и работоспособного генетического алгоритма с Python и NumPy

Генетический алгоритм нужен, когда ты знаешь параметры своей нейросети, но не знаешь, что должно получиться на выходе, например, этот алгоритм можно использовать для игры в Google динозаврика или Flappy Bird, потому что там ты не знаешь, что должно быть на выходе, но у тебя есть возможность сортировать наиболее жизнеспособные варианты, например по времени, это называется фитнес функций. Моя цель не растянуть написания этой статьи, и замучить читателей её длинной, поэтому сразу приступим к коду. Также код простой, поэтому большую часть не нужно описывать целыми сочинениями. Вначале нам потребуется импортировать модули.

https://habr.com/ru/articles/784192/

#genetic_algorithms #генетический_алгоритм #нейросети #python #numpy #обучение #python3 #genetic_algorythm #NEAT