Эволюционные алгоритмы и генетическое программирование

Эволюционные алгоритмы и генетическое программирование

Эволюционные алгоритмы — методы оптимизации, вдохновлённые биологической эволюцией. Там, где классические методы оптимизации (градиентный спуск, LP) терпят неудачу — многовершинные ландшафты, комбинаторные пространства, недифференцируемые цели — эволюция находит хорошие решения.

Генетический алгоритм (GA)

Биологическая аналогия: особи в популяции = решения задачи. Хромосома = кодирование решения. Приспособленность = качество решения. Отбор, скрещивание, мутация = поиск в пространстве решений.

Структура GA:

1. Инициализация: случайная популяция из P хромосом (строк длины L)
2. Оценка: вычисляем fitness f(xᵢ) для каждой особи
3. Отбор: выбираем «родителей» с вероятностью ∝ f(xᵢ) (roulette wheel selection) или топ-k (tournament selection)
4. Скрещивание (crossover): берём два «родителя», с вероятностью p_c создаём «потомков» обменом фрагментов хромосом (одноточечный, двухточечный, uniform)
5. Мутация: с малой вероятностью p_m изменяем случайный бит хромосомы
6. Замена: потомки заменяют часть популяции (стратегия elitism: лучшая особь всегда сохраняется)

Схема-теорема Холланда: Схема = шаблон H (строка с символами {0,1,*}). Длина l(H) — позиция последнего специфического символа. Порядок o(H) — число специфических символов. Краткие (малый l), низкопорядковые, высокоприспособленные схемы экспоненциально увеличивают частоту в следующем поколении. «Строительные блоки» → оптимальное решение.

Генетическое программирование (GP)

Расширение GA: хромосомы — не строки, а синтаксические деревья (программы). Узлы = операции (+, -, sin, if). Листья = переменные и константы.

Операции GP: кроссовер деревьев = обмен случайными поддеревьями между родителями. Мутация = замена случайного поддерева случайно сгенерированным.

Символьная регрессия: GP находит формулу f(x) по данным. Feynman symbolic regression (Cranmer et al., 2019): из синтетических данных GP «открывает» физические законы (ньютоновская гравитация, закон Ома, уравнение Шрёдингера) — чистая машина в роли Ньютона.

Стратегии эволюции (ES) для непрерывной оптимизации

Для непрерывных пространств: хромосома = вещественный вектор x ∈ ℝⁿ. Мутация: x_new = x + ε, где ε ~ N(0, σ²I). σ — «размер шага», адаптируется.

Правило 1/5: если более 1/5 мутаций улучшают приспособленность → увеличиваем σ; меньше → уменьшаем. Поддерживает эффективный размер шага.

CMA-ES (Covariance Matrix Adaptation): адаптирует полную матрицу ковариаций C: mₜ₊₁ = mₜ + α/λ·Σᵢ wᵢ(xᵢ − mₜ) (новое среднее). Cₜ₊₁ = (1−c_C)Cₜ + c_C·pₓpₓᵀ + c_μ/λ·Σᵢ wᵢ(xᵢ−mₜ)(xᵢ−mₜ)ᵀ. Один из лучших безградиентных методов оптимизации. BBOB (Black-Box Optimization Benchmark): CMA-ES доминирует на многих типах задач.

Многокритериальная эволюция (MOEA)

Фронт Парето: x доминирует y (x≻y), если x не хуже y по всем критериям и лучше хотя бы по одному. Множество недоминируемых решений — фронт Парето.

NSGA-II (Deb, 2002): (1) Недоминируемая сортировка: разбиваем популяцию на фронты F₁, F₂,... (F₁ — Парето-фронт). (2) Дистанция в нагрузке (crowding distance): в пределах фронта поддерживаем разнообразие. (3) Выбор: предпочитаем более ранний фронт, при равном фронте — большую crowding distance.

Применения: оптимизация конструкций (масса vs прочность), торговые стратегии (доходность vs риск), настройка гиперпараметров ML (accuracy vs inference time).

OpenAI ES и нейроэволюция

OpenAI ES (Salimans et al., 2017): вместо backpropagation — эволюционная стратегия для обучения нейросетей. Возмущаем параметры θ → θ + σεᵢ, i=1,...,n. Оцениваем reward F(θ + σεᵢ). Обновление: θ' = θ + α/(nσ) Σᵢ F(θ+σεᵢ)εᵢ. Параллелизуется на тысячи CPU, устойчив к разреженным наградам.

NAS эволюцией (Google AutoML, 2017): контроллер эволюционирует архитектуры нейросетей через мутации (добавить/убрать слой, изменить операцию). После 450 GPU-дней: нашли EfficientNet-подобные архитектуры, превосходящие человеческие дизайны.

Численный пример: GA для задачи коммивояжёра

10 городов, TSP (найти кратчайший маршрут через все). Популяция P=50, p_c=0.85, p_m=0.02. Начало: случайные маршруты, средняя длина ≈ 450 (норм. единицы). После 200 поколений: лучший маршрут ≈ 310 (снижение на 31%). Оптимальный (brute force): 295. GA нашёл решение, близкое к оптимальному, за секунды.

Задание: Реализуйте GA для оптимизации: функция f(x,y) = sin(x)·cos(y) − 0.5·sin(x+y) на [-π,π]². Кодирование: 16-битная строка для x, 16-битная для y (Gray code). P=100, p_c=0.8, p_m=0.01, 500 поколений. Постройте: (1) кривую convergence (лучший и средний fitness vs поколение); (2) «тепловую карту» частоты посещений точек (x,y) в популяции. Сравните с CMA-ES на той же задаче — кто быстрее и точнее?