Эволюционные алгоритмы: как компьютеры учатся у природы

🎯 Зачем это нужно?

Представь, что тебе нужно найти лучшую стратегию в игре, но у неё миллиарды возможных комбинаций ходов 🎮. Или создать нейросеть для распознавания мемов, но не знаешь, какие именно параметры настроить из тысяч доступных. Градиентный спуск не поможет - слишком много локальных минимумов!

💼 Tesla использует эволюционные алгоритмы для обучения автопилота 📱 Spotify оптимизирует рекомендации музыки эволюционными методами
🤖 DeepMind создал AlphaStar для StarCraft II с помощью популяционных алгоритмов

📚 История вопроса

В 1960-х Джон Холланд смотрел на природу и думал: “А что если компьютеры будут решать задачи как живые организмы - через эволюцию?” 🧬

Природа за миллионы лет создала невероятно сложные системы:

• Глаз человека = 100 мегапикселей с автофокусом 👁️
• Мозг = 100 миллиардов нейронов, работает на 20 ваттах 🧠
• ДНК = сжатие информации лучше любого архиватора

Холланд подумал: “Если природа может оптимизировать ТАК эффективно, почему бы не скопировать её методы?”

💡 Интуиция

Эволюционный алгоритм = симулятор дарвиновской эволюции в компьютере! 🔄

Представь популяцию из 100 ботов в игре. Каждый бот - это набор параметров (генов):

• Агрессивность: 0.7
• Скорость: 0.3
• Точность: 0.9

Шаг 1: Тестирование 🏆 Запускаем всех ботов играть. Считаем очки (фитнес).

Шаг 2: Селекция ⭐ Лучшие боты “размножаются”, худшие “умирают”.

Шаг 3: Скрещивание 👥 Берем двух хороших ботов, смешиваем их параметры:

• Родитель А: [0.7, 0.3, 0.9]
• Родитель Б: [0.5, 0.8, 0.6]
• Потомок: [0.7, 0.8, 0.6] (взяли лучшее от каждого!)

Шаг 4: Мутация ⚡ Иногда случайно меняем параметры: 0.7 → 0.72 Это помогает найти неожиданно хорошие решения!

[МЕДИА: image_01] Описание: Диаграмма показывающая цикл эволюционного алгоритма с популяцией, селекцией, скрещиванием и мутацией Промпт: “evolutionary algorithm cycle diagram, population of candidate solutions represented as colorful organisms, selection arrows pointing to best performers, crossover between parents creating offspring, mutation sparks, modern infographic style, vibrant colors”

📐 Формальное определение

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

Основные компоненты:

🧬 Индивид = кандидат решения, представленный как вектор параметров x = [x₁, x₂, …, xₙ]

👥 Популяция P(t) = {x₁⁽ᵗ⁾, x₂⁽ᵗ⁾, …, xₘ⁽ᵗ⁾} в поколении t

🎯 Фитнес-функция f(x) → ℝ (чем больше, тем лучше)

Операторы эволюции:

• Селекция: P(t) → Pₘₐₜᵢₙ𝓰
• Кроссинговер: (x, y) → (x’, y')
• Мутация: x → x + δ, где δ ∼ N(0,σ²)

Алгоритм:

1. Инициализировать P(0) случайно
2. Для t = 0, 1, 2, ... пока не сойдется:
   a. Оценить f(xᵢ) для всех xᵢ ∈ P(t)
   b. Выбрать родителей селекцией
   c. Создать потомков кроссинговером  
   d. Применить мутацию
   e. P(t+1) = новая популяция
3. Вернуть лучший найденный x*

🔍 Примеры с разбором

Пример 1: Оптимизация гиперпараметров нейросети

Задача: Найти лучшие параметры для классификатора изображений собак vs котов 🐕🐱

Индивид: [learning_rate, batch_size, dropout, layers]

• learning_rate ∈ [0.001, 0.1]
• batch_size ∈ {16, 32, 64, 128}
• dropout ∈ [0, 0.5]
• layers ∈ {2, 3, 4, 5}

Фитнес: Точность на валидационной выборке

Популяция: 50 конфигураций нейросети

[МЕДИА: image_02] Описание: Визуализация эволюции гиперпараметров нейросети через поколения Промпт: “neural network hyperparameter evolution visualization, multiple generations showing improvement of accuracy scores, colorful parameter combinations represented as DNA-like structures, performance graphs, scientific illustration style”

Селекция: Турнирная (берем случайные 5, выбираем лучшего)

Кроссинговер: Одноточечный

parent1 = [0.01, 64, 0.2, 3]  # accuracy = 0.85
parent2 = [0.05, 32, 0.3, 4]  # accuracy = 0.83

# Точка разреза = 2
child1 = [0.01, 64, 0.3, 4]   # взяли первые 2 от parent1
child2 = [0.05, 32, 0.2, 3]   # взяли первые 2 от parent2

Мутация: С вероятностью 5% изменяем каждый параметр:

if random() < 0.05:
    learning_rate *= random_uniform(0.8, 1.2)

Результат: Через 20 поколений нашли конфигурацию с точностью 94%!

Пример 2: Создание игрового ИИ для шахмат

Задача: Настроить веса оценочной функции шахматной позиции

Индивид: [pawn_value, knight_value, bishop_value, …, king_safety, center_control]

Начальная популяция: 100 разных наборов весов

Фитнес: Количество побед против базового движка за 10 партий

Селекция: Элитарная - сохраняем топ-20, остальные 80 создаем от них

Специальная мутация: Адаптивная

• Если популяция не улучшается 5 поколений → увеличиваем мутацию
• Если быстро улучшается → уменьшаем мутацию

🎮 Практика

Базовый уровень 🟢

Задание 1: Представь популяцию из 4 ботов с параметром “агрессивность”: [0.2, 0.8, 0.5, 0.9]. Фитнес (очки в игре): [10, 80, 40, 70]. Какие 2 бота выберет элитарная селекция?

Задание 2: Проведи одноточечный кроссинговер родителей [1, 2, 3, 4] и [5, 6, 7, 8] с точкой разреза после 2-го гена.

Задание 3: Почему в эволюционных алгоритмах нужна мутация? Что будет без неё?

Продвинутый уровень 🟡

Задание 4: Реализуй турнирную селекцию: есть популяция [A:90, B:60, C:85, D:75, E:95] (буква:фитнес). Турнир из 3 случайных индивидов: {B, D, E}. Кто победит?

Задание 5: Популяция сошлась к одному решению [0.5, 0.5, 0.5] через 50 поколений. Какие параметры алгоритма стоит изменить, чтобы избежать преждевременной сходимости?

Задание 6: Для задачи поиска минимума функции f(x) = x², как модифицировать фитнес, если эволюционный алгоритм максимизирует?

Челлендж 🔴

Задание 7: Спроектируй эволюционный алгоритм для оптимизации маршрута доставки пиццы по 10 адресам. Как представить индивида? Какой кроссинговер использовать?

Задание 8: Почему для обучения нейросетей чаще используют Adam optimizer, а не эволюционные алгоритмы, хотя EA более универсальны?

⚠️ Частые ошибки

❌ Ошибка: Слишком маленькая популяция (10-20 индивидов) ✅ Правильно: Минимум 30-50 для простых задач, 100+ для сложных 💡 Почему: Маленькая популяция быстро теряет генетическое разнообразие

❌ Ошибка: Мутация только случайными числами ✅ Правильно: Адаптивная мутация в зависимости от progress 💡 Почему: В начале нужна сильная мутация (исследование), потом слабая (уточнение)

❌ Ошибка: Останавливать алгоритм при первом улучшении ✅ Правильно: Критерий остановки - отсутствие улучшения N поколений 💡 Почему: Эволюция может “застрять” на плато, а потом резко улучшиться

❌ Ошибка: Использовать только элитарную селекцию ✅ Правильно: Комбинировать элитизм с вероятностными методами 💡 Почему: Элитизм быстро убивает разнообразие, нужен баланс

🎓 Главное запомнить

✅ Суть: Эволюционные алгоритмы = имитация природной эволюции для оптимизации ✅ Ключевая формула: P(t+1) = Mutate(Crossover(Select(P(t)))) ✅ Применение: Гиперпараметры ML, игровой ИИ, оптимизация архитектур

🔗 Связь с другими темами

Назад: Урок 294 дал понимание метаэвристик - EA их яркий представитель Вперед: Генетическое программирование (эволюция программ, а не параметров) Связь с ML: Neuroevolution - эволюция архитектур нейросетей (NAS) Связь с оптимизацией: Когда градиенты недоступны или функция дискретная