Evolutionary Algorithms

Эволюционные алгоритмы развивают популяцию возможных решений посредством отбора, скрещивания и мутаций. Рассматриваются основные типы, код и практическое применение.

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

Как работают эволюционные алгоритмы#

Все EA состоят из одних и тех же элементов:

Представление: каждый кандидат кодируется геномом, например строкой битов, вектором вещественных чисел или деревом программы.
Инициализация: первое поколение обычно создается случайным образом, иногда с добавлением известных удачных решений.
Оценка приспособленности: функция приспособленности оценивает каждого кандидата по целевой задаче.
Отбор: у более приспособленных кандидатов больше шансов стать родителями. Например, при турнирном отборе выбирают лучшего из нескольких случайных кандидатов, а элитизм переносит лучших без изменений в следующее поколение.
Вариация: скрещивание объединяет части двух родителей, а мутация вносит небольшие случайные изменения, чтобы популяция продолжала исследовать пространство решений.

В машинном обучении (ML) функцией приспособленности часто служит метрика валидации, например точность или средняя точность (mAP). Поэтому оценка кандидата включает обучение и тестирование модели — это, безусловно, самый затратный этап. Цикл повторяется, пока не закончится бюджет или не прекратится улучшение функции приспособленности:

Сила отбора и интенсивность мутаций определяют баланс между использованием найденных решений и исследованием новых. Сильный отбор с небольшими мутациями ускоряет сходимость, но может привести к локальному оптимуму. Слабый отбор с крупными мутациями позволяет широко исследовать пространство, но приводит к лишним оценкам.

Основные типы эволюционных алгоритмов#

Генетические алгоритмы (GA): кандидаты кодируются строками, часто битовыми, а основную роль играет скрещивание. Джон Холланд изложил их основы в своей книге Adaptation in Natural and Artificial Systems, опубликованной в 1975 году.
Эволюционные стратегии (ES): оптимизируют векторы вещественных чисел с помощью гауссовых мутаций, шаг которых адаптируется в ходе выполнения. CMA-ES, который обучается полной ковариации распределения мутаций, — один из лучших универсальных методов для непрерывных задач с черным ящиком.
Генетическое программирование: эволюционным путем создает программы или математические выражения, представленные в виде деревьев. Применяется для символьной регрессии и автоматического проектирования программ.
Нейроэволюция: эволюционным путем оптимизирует веса, а иногда и структуру нейронных сетей. В 2017 году OpenAI показала, что стратегии эволюции, выполняемые более чем на тысяче параллельных рабочих процессов, могут за 10 минут обучить трехмерного человекоподобного робота ходить. Это масштабируемая альтернатива обучению с подкреплением.

Генетический алгоритм в коде#

Задача о рюкзаке состоит в том, чтобы выбрать предметы с максимальной суммарной ценностью, не превышая ограничения по весу. Это дискретная задача без градиента. Этот генетический алгоритм на NumPy эволюционирует 50 геномов в виде битовых строк — по одному биту на предмет — с помощью турнирного отбора, равномерного скрещивания, побитовой мутации и элитизма, а затем сверяет ответ со всеми 1,048,576 возможными наборами предметов:

import itertools

import numpy as np

rng = np.random.default_rng(0)
# Knapsack problem: pick from 20 items to maximize total value within a weight limit of 200
values, weights, limit = rng.integers(10, 100, 20), rng.integers(5, 50, 20), 200


def fitness(pop):
    """Return each selection's total value, or 0 if it exceeds the weight limit."""
    return np.where(pop @ weights <= limit, pop @ values, 0)


population = rng.random((50, 20)) < 0.2  # 50 random genomes, one bit per item
for generation in range(100):
    scores = fitness(population)
    # Tournament selection: each parent is the better of two random genomes
    pairs = rng.integers(50, size=(50, 2))
    parents = population[np.where(scores[pairs[:, 0]] > scores[pairs[:, 1]], pairs[:, 0], pairs[:, 1])]
    # Uniform crossover with the next parent, then flip each bit with probability 0.05
    children = np.where(rng.random((50, 20)) < 0.5, parents, np.roll(parents, 1, axis=0))
    children ^= rng.random((50, 20)) < 0.05
    children[0] = population[scores.argmax()]  # elitism: keep the best genome
    population = children

all_selections = np.array(list(itertools.product([0, 1], repeat=20)))
print(f"GA best: {fitness(population).max()}, true optimum: {fitness(all_selections).max()}")

Он выводит GA best: 811, true optimum: 811. Алгоритм нашел оптимальный набор после 5,000 оценок приспособленности — это около 0.5% от миллиона вариантов, которые пришлось бы проверить полным перебором.

Эволюционная настройка гиперпараметров#

Параметры обучения, такие как скорость обучения, веса функции потерь и интенсивность аугментации, взаимодействуют непредсказуемым образом, а оценка каждого кандидата требует полного цикла обучения. Поэтому для этой задачи хорошо подходит эволюционный поиск. Метод tune() в Ultralytics YOLO использует такой подход для моделей YOLO26: на каждой итерации выбирается родитель из девяти лучших конфигураций на данный момент с вероятностью, пропорциональной функции приспособленности, затем примерно половина из 26 гиперпараметров пространства поиска по умолчанию мутирует с помощью гауссовых шагов, масштабированных по диапазонам поиска. После этого обучается модель и записывается ее показатель приспособленности — mAP_50-95 для обнаружения объектов. После 30 результатов часть мутаций также начинает учитывать ковариацию 20% лучших конфигураций. Этот прием заимствован из CMA-ES. В руководстве по настройке гиперпараметров указано полное пространство поиска:

from ultralytics import YOLO

# Загрузи предварительно обученную nano-модель YOLO26
model = YOLO("yolo26n.pt")

# Эволюционная настройка гиперпараметров: 30 итераций, на каждой обучается одна мутировавшая конфигурация в течение 10 эпох
model.tune(data="coco8.yaml", epochs=10, iterations=30, plots=False)

Настройщик записывает каждую конфигурацию и ее показатель приспособленности в tune_results.ndjson, а лучшую конфигурацию сохраняет в best_hyperparameters.yaml. Ее можно передать в полноценный цикл обучения.

Другие области применения#

Поиск архитектур нейронных сетей: AmoebaNet от Google была получена с помощью регуляризованной эволюции — EA с турнирным отбором, который исключает самые старые модели, а не худшие. В 2018 году AmoebaNet достигла точности top-1 83.9% на ImageNet.
Инженерное проектирование: в 2006 году в рамках миссии NASA Space Technology 5 использовали антенну X-диапазона, спроектированную компьютером эволюционным методом. Ее причудливая форма изогнутой проволоки обеспечивала характеристики, сопоставимые с антенной, спроектированной традиционным способом.
Открытие алгоритмов: AlphaEvolve, о котором Google DeepMind объявила в мае 2025 года, объединяет модели Gemini, предлагающие изменения кода, автоматические средства оценки и эволюционную базу программ. Одна из эвристик планирования, разработанных этим методом для центров обработки данных Google, позволяет в среднем высвобождать 0.7% мировых вычислительных ресурсов компании.

Градиентный спуск: использует градиент дифференцируемой функции потерь и гораздо эффективнее при обучении весов сети с миллионами параметров. EA подходят для задач с небольшим числом параметров, дорогостоящими оценками или отсутствием градиента.
Роевой интеллект: методы, такие как оптимизация роя частиц, перемещают по пространству поиска набор взаимодействующих агентов. Каждый агент корректирует свое положение на основе собственных лучших результатов и результатов соседей; при этом нет смены поколений, скрещивания или мутации.
Байесовская оптимизация: строит вероятностную модель целевой функции и выбирает следующий эксперимент в точке, где модель ожидает наибольшее улучшение. На небольших гладких пространствах поиска этот метод требует меньше оценок, чем EA, но хуже масштабируется на большое число параметров и параллельных рабочих процессов.