🔴 Сложный ⏱️ 25 минут

Генетические алгоритмы: эволюция для решения задач

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

🎮 Game Development: Bethesda использует генетические алгоритмы для создания реалистичной анимации лиц в Skyrim 📱 Рекомендательные системы: Spotify оптимизирует плейлисты для миллионов пользователей одновременно 🚗 Автопилот: Tesla настраивает параметры автономного вождения через эволюционные подходы 🏭 Производство: Boeing оптимизирует маршруты резки деталей самолетов, экономя $50M в год

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

В 1975 году Джон Холланд смотрел на муравейник возле своего дома в Мичигане и подумал: “А что если заставить компьютерные программы эволюционировать так же, как живые существа?” 🐜

Через 50 лет его идея стала одним из самых мощных инструментов ИИ. Забавный факт: первая успешная эволюция нейросети в 1989 году создала “мозг”, который научился играть в нарды лучше человека за одну ночь!

💡 Интуиция

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

Генетический алгоритм делает то же, что природа:

🔄 Размножение лучших: “Скрещиваем” топ-решения
🎭 Мутации: Добавляем случайные изменения
🏆 Естественный отбор: Слабые решения исчезают
🔁 Повторяем: До тех пор, пока не найдем оптимум

[МЕДИА: image_01] Описание: Схема эволюционного процесса с поколениями решений, показывающая улучшение фитнеса Промпт: “evolutionary algorithm diagram showing population evolution over generations, fitness improvement curve, colorful chromosome representations, modern technical illustration, clean design”

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

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

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

🧬 Популяция P(t): Множество кандидатов-решений в поколении t 🎯 Фитнес-функция f(x): Оценка качества решения x
👥 Селекция: Выбор родителей для размножения 💕 Кроссовер: Создание потомков из родительских генов ⚡ Мутация: Случайные изменения с вероятностью p_m

Базовый алгоритм:

def genetic_algorithm(population_size, generations):
    population = initialize_random_population(population_size)
    
    for generation in range(generations):
        # Оценка приспособленности
        fitness = [evaluate_fitness(individual) for individual in population]
        
        # Селекция лучших
        parents = selection(population, fitness)
        
        # Создание потомков
        offspring = []
        for i in range(0, len(parents), 2):
            child1, child2 = crossover(parents[i], parents[i+1])
            offspring.extend([mutate(child1), mutate(child2)])
        
        # Обновление популяции
        population = survival_selection(population + offspring)
    
    return best_individual(population)

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

Пример 1: Задача коммивояжера

Нужно найти кратчайший маршрут через 10 городов.

🧬 Представление решения: Перестановка городов [3,1,7,2,5,8,4,6,9,0] 🎯 Фитнес: f(маршрут) = 1 / общая_длина_пути

Кроссовер (Order Crossover):

Родитель 1: [3,1,7,2,5,8,4,6,9,0]
Родитель 2: [5,8,4,6,1,3,9,7,2,0]
Потомок: [3,8,4,6,5,1,7,2,9,0]

Мутация (Swap): Случайно меняем местами два города

[МЕДИА: image_02] Описание: Визуализация кроссовера для задачи коммивояжера с городами и маршрутами Промпт: “traveling salesman problem visualization, cities connected by routes, genetic crossover operation illustrated, before and after states, educational diagram style”

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

Ищем оптимальную архитектуру CNN для классификации изображений.

🧬 Хромосома: [num_layers=5, filters=[32,64,128,64,32], dropout=0.3, lr=0.001] 🎯 Фитнес: Точность на валидации × (1 - complexity_penalty)

Кроссовер: Uniform crossover - каждый ген берется случайно от одного из родителей Мутация:

Гауссовский шум для вещественных параметров
±1 для целочисленных параметров

🎮 Практика

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

Задание 1: Для максимизации функции f(x) = x² на отрезке [0,31], какое двоичное представление имеет число 25?

💡 Подсказка

Переведи 25 в двоичную систему счисления

✅ Ответ

25 = 16 + 8 + 1 = 2⁴ + 2³ + 2⁰ → [1,1,0,0,1]

Задание 2: При одноточечном кроссовере родителей [1,0,1,1,0] и [0,1,0,0,1] с точкой разреза после 3-го гена, какие получатся потомки?

💡 Подсказка

Первые 3 гена от первого родителя, остальные от второго, и наоборот

✅ Ответ

Потомок 1: [1,0,1,0,1], Потомок 2: [0,1,0,1,0]

Задание 3: Если вероятность мутации 0.1, и у нас хромосома длины 10, сколько в среднем генов изменится?

💡 Подсказка

Математическое ожидание = длина × вероятность

✅ Ответ

E[мутаций] = 10 × 0.1 = 1 ген

Задание 4: Реализуй рулеточную селекцию для популяции с фитнесами [10, 20, 30, 40]:

💡 Подсказка

Вероятность выбора = фитнес_индивида / сумма_всех_фитнесов

✅ Ответ

Вероятности: [0.1, 0.2, 0.3, 0.4]. Суммарная приспособленность = 100

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

Задание 5: Сравни эффективность турнирной селекции с размером турнира 2 и 5 для популяции 100 особей. Какая создает большее селекционное давление?

💡 Подсказка

Большие турниры чаще выбирают лучших особей

✅ Ответ

Турнир размера 5 создает большее давление: P(выбор лучшего) = 0.5² = 0.25 vs 0.5⁵ = 0.03

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

💡 Подсказка

Используй штрафную функцию для нарушения ограничений

✅ Ответ

fitness(x,y) = -(x² + y²) - penalty × max(0, x² + y² - 25)²

Задание 7: Почему для вещественной оптимизации часто используют самоадаптивные мутации вместо фиксированных?

💡 Подсказка

Подумай о том, как должен изменяться размер шага по мере приближения к оптимуму

✅ Ответ

Адаптивная мутация уменьшает шаг около оптимума (точная настройка) и увеличивает в плоских областях (исследование)

Задание 8: Реализуй элитизм: если лучшие 10% родителей лучше всех потомков, как их сохранить?

💡 Подсказка

Замени худших потомков лучшими родителями

✅ Ответ

elite = top_10_percent(parents) offspring = replace_worst(offspring, elite)

Челлендж 🔴

Задание 9: Спроектируй гибридный алгоритм GA + локальный поиск для задачи размещения антенн сотовой связи. Какие компоненты использовать?

💡 Подсказка

GA для глобального поиска, локальный поиск для финальной настройки

✅ Ответ

GA находит перспективные области → Hill Climbing доводит до локального оптимума → Мемический алгоритм

Задание 10: Как решить проблему преждевременной сходимости в GA при оптимизации многомодальных функций?

💡 Подсказка

Нужно поддерживать разнообразие популяции

✅ Ответ

Niching (ниширование): расстояние между особями, sharing, crowding, или island model

Задание 11: Докажи, что Schema Theorem Холланда объясняет, почему GA эффективно исследует пространство поиска:

💡 Подсказка

Короткие схемы с высоким фитнесом экспоненциально размножаются

✅ Ответ

E[m(s,t+1)] ≥ m(s,t) × f(s)/f_avg × (1 - p_c×δ(s)/(l-1) - o(s)×p_m), где короткие низкодефинирующие схемы растут экспоненциально

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

❌ Ошибка: “GA всегда найдет глобальный оптимум” ✅ Правильно: GA - эвристический метод, гарантий нет 💡 Почему: Может застрять в локальных оптимумах, особенно при малой популяции

❌ Ошибка: Очень высокая вероятность мутации (>0.5) ✅ Правильно: Обычно 0.01-0.1 для битовых строк 💡 Почему: Высокая мутация разрушает хорошие решения быстрее, чем создает новые

❌ Ошибка: Игнорирование преждевременной сходимости ✅ Правильно: Мониторинг разнообразия популяции 💡 Почему: Потеря разнообразия = потеря способности к исследованию

❌ Ошибка: Неправильное масштабирование фитнеса ✅ Правильно: Нормализация или ранговая селекция 💡 Почему: Суперособи могут доминировать в ранних поколениях

❌ Ошибка: Неподходящее представление решения ✅ Правильно: Представление должно соответствовать структуре задачи 💡 Почему: Плохое представление = неэффективные генетические операторы

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

✅ Суть: GA имитирует эволюцию - селекция лучших + скрещивание + мутации + отбор ✅ Формула успеха: Правильные операторы + баланс исследование/использование
✅ Применение: Оптимизация в пространствах, где градиент неприменим

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

Назад: Метаэвристические алгоритмы (урок 295) заложили основы для понимания эволюционных подходов Вперед: Particle Swarm Optimization, дифференциальная эволюция, коэволюционные алгоритмы ML-связи: AutoML, нейроэволюция, оптимизация гиперпараметров, архитектурный поиск нейросетей

Понял тему? Закрепи в боте! 🚀

Попрактикуйся на задачах и получи персональные рекомендации от AI

💪 Начать тренировку