Как работают генетические алгоритмы

Как работают генетические алгоритмы

Математический естественный отбор.

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

Математическая эволюция

Алгоритм начинается с создания популяции — списка моделей. Задачу для ГА важно построить так, чтобы каждую модель можно было представить списком чисел — набором характеристик (генов). Изначально их задают случайным образом. Список решений называют популяцией. Лучшие модели отбираются для создания следующей популяции. Это повторяется, пока не будет найден удовлетворительный результат. 

Чтобы установить, насколько качественное решение предоставляет модель, используют функцию приспособленности. Ее самые простые примеры — точность предсказания и F-score. Чем лучше решение, тем выше вероятность выбора особи для создания следующей популяции.

Основные этапы

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

#1. Отбор

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

Ключевые методы отбора — турнирный и ранговый.

  • Ранговый

Популяцию разбивают на несколько групп (рангов). Ранги присваивают в зависимости от функции приспособленности и пропорционально отбирают некоторую часть особей из каждого ранга.

  • Турнирный

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

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

#2. Скрещивание

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

#3. Мутация

Она возникает редко и случайным образом меняет значения отдельных генов. Например, меняет 1 на 0. 

Мутации помогают расширить область поиска и сохранить разнообразие в популяции. Они могут и улучшить, и ухудшить приспособленность особи. 

#4. Завершение алгоритма

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

Генетические алгоритмы vs нейросети

ГА хорошо работает с задачами, где есть большой набор ограниченных, дискретных данных, и находит решения быстрее, чем полный перебор. Data scientist Мишель Берк задал ГА определить содержание зашифрованного предложения Genetic Algorithms are wild. Алгоритму нужно было выбирать из всех возможных комбинаций — 2753. Он имел 30 особей в популяции и отгадал на 51-м поколении. То есть проверил 1530 комбинаций. 

Генетический алгоритм может найти короткий путь между точками. Поэтому он подходит для поиска решений NP-полных проблем (как проблема коммивояжера). Например, ГА применяют для расчета траектории движения или создания маршрутов для GPS-систем. 

Ученые также использовали клеточные автоматы на основе ГА для анализа распространения COVID-19 в 40 странах мира в течение разного времени. 

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

Симбиоз ГА и нейросети

Есть примеры объединения ГА с нейросетью. С помощью генетических алгоритмов можно оптимизировать работу модели. Например, подобрать гиперпараметры (веса или функцию активации).  

Но применение генетических алгоритмов для подбора требует много времени и вычислительной мощности. Например, чтобы обучить нейросети побеждать реальных игроков в видеоиграх. В 2017 году команда OpenAI использовала генетический алгоритм, чтобы отобрать игры ботов в Dota 2, которые проводили успешные матчи. Потом эти данные использовали для обучения нейросети. 

Подробнее о машинном обучении в геймдеве — тут

Ещё статьи
Как системы работают с высокими нагрузками.
Зачем нужны библиотеки для векторизации.