генетические алгоритмы в машинном обучении
r_d media
Как работают генетические алгоритмы
Математический естественный отбор.
Генетический алгоритм — способ решения задач, который использует методы, похожие на механизмы эволюции. Такой алгоритм применяют, если количество возможных решений слишком велико, чтобы их протестировать. Рассказываем, как устроены генетические алгоритмы и как они улучшают работу нейросетей.
Математическая эволюция
Алгоритм начинается с создания популяции — списка моделей. Задачу для ГА важно построить так, чтобы каждую модель можно было представить списком чисел — набором характеристик (генов). Изначально их задают случайным образом. Список решений называют популяцией. Лучшие модели отбираются для создания следующей популяции. Это повторяется, пока не будет найден удовлетворительный результат.
Чтобы установить, насколько качественное решение предоставляет модель, используют функцию приспособленности. Ее самые простые примеры — точность предсказания и F-score. Чем лучше решение, тем выше вероятность выбора особи для создания следующей популяции.
Основные этапы
После создания начальной популяции генетические алгоритмы проходят четыре стадии:
#1. Отбор
Суть отбора в том, чтобы выбрать самые эффективные модели и передать их гены другому поколению. Пары особей (родителей) отбирают в зависимости от приспособленности. Количество родителей может быть произвольным, но одинаковым для каждого следующего цикла.
Ключевые методы отбора — турнирный и ранговый.
Популяцию разбивают на несколько групп (рангов). Ранги присваивают в зависимости от функции приспособленности и пропорционально отбирают некоторую часть особей из каждого ранга.
Случайным образом отбирают несколько особей. Среди них определяют лучшую. Процесс повторяется, пока промежуточная популяция не будет заполнена.
Универсального метода отбора не существует. У каждого — свои преимущества. Ранговый отбор позволяет сохранить большее разнообразие моделей. Турнирный метод удобен, если мы можем только сравнивать модели попарно, а не выражать функцию приспособленности числом. Он подходит, например, для игровых стратегий.
#2. Скрещивание
На этапе скрещивания происходит обмен данными между родительскими парами. В популяции выбирают пары родителей и перемешивают фрагменты их хромосом, получая новый набор генов. Часто используют одноточечное скрещивание: определяют точку разреза хромосом у родителей, а затем меняют их части. После обмена новые данные добавляют в популяцию.
#3. Мутация
Она возникает редко и случайным образом меняет значения отдельных генов. Например, меняет 1 на 0.
Мутации помогают расширить область поиска и сохранить разнообразие в популяции. Они могут и улучшить, и ухудшить приспособленность особи.
#4. Завершение алгоритма
Алгоритм заканчивает процесс, если создана популяция, которая почти не отличается от прошлой. Это не значит, что найденное решение идеально, но улучшаться оно не будет.
Генетические алгоритмы vs нейросети
Генетический алгоритм может найти короткий путь между точками. Поэтому он подходит для поиска решений NP-полных проблем (как проблема коммивояжера). Например, ГА применяют для расчета траектории движения или создания маршрутов для GPS-систем.
Ученые также использовали клеточные автоматы на основе ГА для анализа распространения COVID-19 в 40 странах мира в течение разного времени.
Нейросети же лучше справляются с непрерывными данными. Они подходят для задач классификации (распознавания изображений, понимания языка). Также нейросети применяют для задач линейной регрессии — поиска зависимости между переменными.
Симбиоз ГА и нейросети
Есть примеры объединения ГА с нейросетью. С помощью генетических алгоритмов можно оптимизировать работу модели. Например, подобрать гиперпараметры (веса или функцию активации).
Но применение генетических алгоритмов для подбора требует много времени и вычислительной мощности. Например, чтобы обучить нейросети побеждать реальных игроков в видеоиграх. В 2017 году команда OpenAI использовала генетический алгоритм, чтобы отобрать игры ботов в Dota 2, которые проводили успешные матчи. Потом эти данные использовали для обучения нейросети.
Подробнее о машинном обучении в геймдеве — тут.
Как еще генетические алгоритмы могут помочь глубокому обучению?
Разбираемся, зачем генетические и подобные им алгоритмы используют в машинном, а в частности — в глубоком обучении. Пытаемся найти альтернативу градиентному спуску при обучении нейронных сетей и смотрим, что из этого получается.
С тех пор, как человечество начало переходить в информационную эру, данные стали одним из главнейших ресурсов, а извлечение необходимой информации — жизненно необходимым навыком для науки и бизнеса в XXI веке. И вполне закономерно, что машинное обучение стало такой популярной и активно развивающейся наукой. Один раздел машинного обучения получил особенно бурное развитие в последние несколько лет. Мы говорим о глубоком обучении, которое основано на использовании многослойных нейронных сетей в качестве базового инструмента.
Каждый день появляются новые примеры практического применения глубокого обучения, способы обучения нейронных сетей, новые архитектуры. Количество данных все увеличивается, сети становятся глубже, архитектуры изощренней, а видеокарты — более производительными и приспособленными под нужды машинного обучения.
Но нерешённых проблем в глубоком обучении остается достаточно, как в теории, так и на практике. Есть замечательная поговорка:
”Чем глубже в лес — тем злее партизаны”. (с) народ
С нейронными сетями так же:
“Чем глубже становится архитектура, тем сложнее её обучать”. (с) народ, который занимается глубоким обучением
Мы, команда Phygitalism, стараемся найти новые варианты применения глубокого обучения и новые подходы, в частности в области 3D machine learning (раздел машинного обучения, имеющий дело с 3-х мерными данными: 3D модели, сцены, облака точек и пр.). Но так же нам нравится “копаться под капотом” — разбираться в математике, скрывающейся за алгоритмами, и пытаться улучшить алгоритмы на уровне теории.
Если мы говорим про математику, стоящую за обучением нейронных сетей, то конечномерная оптимизация здесь будет на первом плане. Для фиксированной архитектуры сети мы пытаемся найти такой набор весов, который обеспечит минимум некоторому функционалу качества. Обычно поиск такого набора весов осуществляется с помощью процедуры градиентного спуска.
Публикация, разъясняющая данный подход:
Types of Optimization Algorithms used in Neural Networks and Ways to Optimize Gradient Descent
Have you ever wondered which optimization algorithm to use for your Neural network Model to produce slightly better and…
Градиентный подход — парадигма, проверенная временем, постоянно совершенствующаяся, но не лишённая недостатков и не единственно существующая. Основное ограничение, накладываемое на градиентные методы — это требование дифференцируемости оптимизируемой функции. Основной недостаток — локальность найденного оптимума.
Одними из самых известных представителей данного класса алгоритмов являются генетические алгоритмы. На Medium уже есть ряд интересных статей с разбором как самих алгоритмов, так и их возможных применений для машинного обучения:
Evolution of a salesman: A complete genetic algorithm tutorial for Python
Drawing inspiration from natural selection, genetic algorithms (GA) are a fascinating approach to solving search and…
Introduction to Genetic Algorithms — Including Example Code
A genetic algorithm is a search heuristic that is inspired by Charles Darwin’s theory of natural evolution. This…
Genetic Algorithms + Neural Networks = Best of Both Worlds
Learn how Neural Network training can be accelerated using Genetic Algorithms!
Let’s evolve a neural network with a genetic algorithm—code included
Building the perfect deep learning network involves a hefty amount of art to accompany sound science. One way to go…
Но мы бы хотели рассмотреть подзадачу глубокого обучения, к которой генетические и подобные им алгоритмы сегодня не принято применять, а именно — непосредственный поиск наилучших весов для фиксированной архитектуры сети. Мы хотим понять, насколько успешно можно обучать нейронные сети с помощью алгоритмов, подобных генетическим.
Область искусственного интеллекта, которая пытается ответить на подобные вопросы, называется нейроэволюция [1]. Несмотря на первоначальный позитивный настрой учёных и исследователей, которые в конце XX века получили некоторые обнадёживающие результаты [2], сегодня методы нейроэволюции применяются в основном для вспомогательных задач глубокого обучения, например для настройки гиперпараметров алгоритмов (кстати, с этого года этот подход входит в стандарт TensorFlow). Также методы нейроэволюции успешно применяются в области обучения с подкреплением [3], но для решения основных оптимизационных задач все же принято использовать именно градиентный подход. Почему же так вышло и может ли данный подход снова стать популярным в будущем? Давайте попробуем разобраться.
В качестве экспериментальной задачи рассмотрим классификацию рукописных цифр (датасет MNIST) с помощью полносвязной нейронной сети. Архитектура рассматриваемой сети представлена на рисунке 1.
Теперь нужно определиться с критерием качества (objective/fitness function), который мы будем оптимизировать. Обычно для обучения нейронной сети используют две функции: функцию потерь на обучающей выборке (loss function) и функцию-метрику качества на тестовой выборке (validation metric). Первая функция выбирается гладкой и на ней происходит оптимизация градиентным спуском. Вторая же функция обычно не является гладкой и используется для определения обобщающей способности сети.
Поскольку для работы метаэвристических алгоритмов гладкость оптимизируемого функционала не требуется, мы будем оптимизировать непосредственно долю правильных ответов (accuracy) на обучающей выборке и использовать её же для валидации обобщающей способности на тестовой выборке.
После написания несложного кода можно провести несколько численных экспериментов. На графике ниже видно, что градиентный метод смог добиться почти 100% значения accuracy почти в 8 раз быстрее, чем PSO, который не достиг и 80%.
Мы привели здесь всего 3 запуска PSO алгоритма, который имеет множество гиперпараметров и зависит от начального случайного распределения особей в пространстве оптимизируемых весов. Давайте посмотрим, как ведёт себя этот алгоритм в нашей задаче, если выбирать разные параметры и делать большее число запусков.
На рисунке 4а) можно увидеть, как растет точность от увеличения числа поколений для разных запусков (с различными random seed и лучшими из найденных параметрами алгоритма). Из усреднения 4б) видно, что алгоритм с течением времени перестает наращивать точность — для дальнейшего улучшения результата работы необходимо менять шаг/разбиение сетки.
Что же здесь получилось: градиентный метод, направленный на локальный поиск, справился с задачей быстрее и лучше, чем метод, направленный на поиск наилучшего из наилучших решений. Почему же так вышло?
Дело в том, что нейронная сеть в компьютере представляется в виде вычислительного графа, который мы умеем аналитически дифференцировать, например TensorFlow делает это автоматически после задания архитектуры. Функция потерь (Loss function, objective) алгоритма, рассчитываемая на тренировочной выборке, в отличие от доли правильных ответов ( accuracy), рассчитываемой на тестовой выборке, выбирается непрерывной. А это значит, что для неё можно достаточно быстро и точно определить градиент. Поэтому градиентный метод получает своё первое преимущество — дополнительная информация о ландшафте функции потерь. Вторым преимуществом градиентного метода является возможность подстраивать скорость обучения (learning rate), что позволяет на более поздних этапах обучения лучше исследовать оптимизируемые параметры на более мелких масштабах.
Некоторые метаэвристические методы так же способны изменять скорость обучения и величину шага. Например, метод эволюции ковариационной матрицы (CMA-ES) с течением времени уменьшает область поиска. Но, к сожалению, для нашего примера этот метод неприменим, поскольку для его работы потребовалось бы 5 Тбайт в оперативной памяти для хранения ковариационных матриц. Подробное сравнение метаэвристических алгоритмов оставим на следующую публикацию.
Значит ли всё вышесказанное, что ̶п̶л̶а̶с̶т̶м̶а̶с̶с̶о̶в̶ы̶й̶ градиентный мир победил? Благодаря теореме о бесплатных завтраках [4] мы знаем, что это не так. Для каждой задачи найдётся алгоритм, который её решает лучше, чем другие, и для каждого алгоритма найдутся плохие задачи.
Мы рассмотрели всего лишь одну задачу. Возможно, что для другой архитектуры или для других типов данных, подобный метаэвристический подход покажет себя лучше градиентного. Но в случае каких именно задач это может произойти? На сегодняшний день этот вопрос остается открытым, и возможно именно вам повезёт узнать на него ответ!
Спасибо за внимание и удачных экспериментов!
[1] Stanley, Kenneth O. (2017–07–13). “Neuroevolution: A different kind of deep learning”. O’Reilly Media. Retrieved 2017–09–04
Генетический алгоритм
Материал из MachineLearning.
Генетический алгоритм (англ. genetic algorithm) — это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём последовательного подбора, комбинирования и вариации искомых параметров с использованием механизмов, напоминающих биологическую эволюцию. Является разновидностью эволюционных вычислений (англ. evolutionary computation). Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивания», который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе.
Содержание
Постановка задачи
Для функции приспособленности в пространстве поиска требуется найти (или ).
Описание алгоритма
В процессе селекции выживают отбирают только несколько лучших пробных решений, остальные далее не используются. Скрещивание за место пары решений создаёт другую, элементы которой перемешаны каким-то особым образом. Мутация случайным образом меняет какую-нибудь компоненту пробного решения на иную.
Иные обозначения
Несмотря на внушительный возраст, в генетических алгоритма до сих пор используют различную терминологию, проистекающей как из генетики, так и из кибернетики.
Встречаются такие обозначения:
Применение генетических алгоритмов
Генетические алгоритмы применяются для решения следующих задач:
Подробное описание алгоритма
Кодирование пространства поиска
В ГА часто используют следующие типы кодирования компонент пространства поиска:
Начальная популяция
Оценка приспособленности
Оператор отбора (селекции)
На этом этапе отбирается оптимальная популяция для дальнейшего размножения. Обычно берут определённое число лучших по приспособленности. Имеет смысл также отбрасывать «клонов», т.е. особей с одинаковым набором генов.
Оператор скрещивания
Оператор мутаций
Критерии останова
Эвристики
Генетические алгоритмы богаты возможностями встраивания различных эвристик. До сих пор не существует (и не будет!) точных критериев оптимального размера популяции, способов мутаций и скрещивания, выбора начальной популяции и т.п.
Плоидность
Мета ГА
Простейший пример ГА
Подбор ключа 2048 бит
Эффективность генетических алгоритмов
Холланд недвусмысленно пишет[1], что при прочих равных условиях ГА будет работать хуже, чем специальный алгоритм, рассчитанный на конкретную задачу (тип признаков, целевую функцию). Например, полный перебор конечного небольшого пространства или любой эффективных алгоритм спуска будет всегда эффективнее чем ГА. Тем не менее, в ситуации, когда о задаче ничего a priori не известно, можно полагаться на результат работы простейшего генетического алгоритма как некого приближения.
Существуют некоторый класс функций (Hyperplane-defined functions, Holland), с которым за приемлемое время[2] справляются только генетические алгоритмы.
Тестовые функции
В процессе разработки эффективной реализации генетического алгоритма появляется необходимость простой тестовой функции, которая
Мнения
Конвергенция с генетикой и синтетической теории эволюции
Прообраз генетического алгоритма пришёл из биологии и, несомненно, продолжает «подсматривать» оттуда ответы на многие вопросы, возникающие при проектированию эффективных реализаций генетических алгоритмов. Более того, идеи по оптимизации ГА находят подтверждение и у биологов. Например, такие явления как га- ди- и квадру- плоидные наборы хромосом, инцест, удвоение гена, управление скоростью мутаций, триггеры и т.п. Тем не менее, математика и кибернетика позволяет выйти за пределы химической реальности клетки и представить n-плоидный набор хромосом, объектные сущности вместо генов и т.п.
Нейронные сети и эволюционное моделирование
ИНС и ГА часто пытаются применять в тандеме, т.к. и те и другие имеют корни из биологии. Тем не менее (см. выше об эффективности ), во-первых алгоритм обратного распространения ошибки настройки ИНС работает значительно (на порядок) быстрее в простых случаях. А во-вторых, настройка нейронной сети в биологии происходит методом, который, скорее всего, значительно разнится с генетическим подходом.
Аналогия с другими алгоритмами
В случае отключённого кроссинговера ГА начинает вести себя по образу случайного поиска. Также у ГА есть аналогия со случайным поиском с адаптацией. Во многих стохастических алгоритмах можно найти аналогию с ГА.
Алгоритм машинного обучения Flappy Bird
Я познакомлю вас с полным туториалом на HTML5 с демо по алгоритму машинного обучения видеоигре Flappy Bird. Цель этого эксперимента — написать игровой контроллер искусственного интеллекта на основе нейросетей и генетического алгоритма.
То есть мы хотим создать ИИ-робота, который сможет учиться оптимальной игре во Flappy Bird. В результате наша маленькая птица сможет спокойно пролетать через препятствия. В наилучшем сценарии она не умрёт никогда.
Прочитав теорию, лежащую в основе этого проекта, можно скачать исходный код в конце этого туториала. Весь код написан на HTML5 с использованием фреймворка Phaser. Кроме того, мы использовали библиотеку Synaptic Neural Network для реализации нейросети, чтобы не создавать её с нуля.
Для начала посмотрите демо, чтобы оценить алгоритм в действии:
Видеопрезентация
В дополнение к демо вы можете посмотреть короткое видео с простым объяснением алгоритма. Понравится тем, кто любит получать информацию быстро!
Что такое «алгоритм машинного обучения»
По формулировке Артура Самуэля 1959 года, машинное обучение — это способ заставить компьютеры работать без программирования в явной форме. В общем случае, это процесс тонкой настройки обучения, постепенно улучшающий исходную случайную систему.
То есть целью здесь является создание искусственного интеллекта, который сможет найти правильное решение из плохой системы тонкой настройкой параметров модели. Для этого в алгоритме машинного обучения используется множество различных подходов.
Конкретно в этом проекте, основной подход к машинному обучению (machine learning algorithm, ML) основан на нейроэволюции. В этой форме машинного обучения используются эволюционные алгоритмы, такие как генетический алгоритм (genetic algorithm, GA), для обучения искусственных нейронных сетей (artificial neural networks, ANN).
То есть в нашем случае можно сказать, что ML = GA + ANN.
Искусственная нейронная сеть
Искусственная нейронная сеть — это подмножество алгоритма машинного обучения. За основу в ней взяты структура и функции биологических нейронных сетей. Эти сети созданы из множества нейронов, передающих сигналы друг другу.
То есть для создания искусственного мозга нам нужно симулировать нейроны и соединить их, чтобы они сформировали нейронную сеть.
Стандартная искусственная нейронная сеть состоит из слоя входных данных, одного или нескольких скрытых слоёв и слоя выходных данных. В каждом слое есть несколько нейронов. Нейроны входных и выходных данных присоединены непосредственно к внешней среде. Скрытые нейроны соединяются между ними.
В этом проекте каждый объект (птица) имеет собственную нейронную сеть, используемую в качестве ИИ-мозга для прохождения игры. Она состоит из следующих трёх слоёв:
Генетический алгоритм
Когда мы обсуждали алгоритм машинного обучения, то говорили, что для обучения и совершенствования нейронных сетей используется генетический алгоритм.
Генетический алгоритм — это техника оптимизации на основе поиска, копирующая естественный отбор и генетику. В ней используется такое же сочетание отбора, кроссинговера и мутаций для изменения исходной случайной популяции.
Вот основные этапы реализации нашего генетического алгоритма:
Функция приспособленности
В дополнение к генетическому алгоритму (этап 3), мы рассмотрим здесь подробнее функцию приспособленности — что это такое и как её определить.
Поскольку мы хотим, чтобы популяция эволюционировала из наилучших объектов, нам необходимо определить функцию приспособленности.
В общем случае, функция приспособленности — это метрика, измеряющая качество объекта. Если у нас будет метрика качества каждой птицы, мы сможем выбрать самые приспособленные объекты и использовать их для воссоздания следующего поколения.
В этом проекте мы вознаграждаем птицу в прямой зависимости от проделанного расстояния. Кроме того, мы наказываем её по текущему расстоянию до ближайшего промежутка. Таким образом мы сможем различать птиц, пролетевших одинаковое расстояние.
Подведём итог: наша функция приспособленности — это разность между общим расстоянием, проделанным птицей, и текущим расстоянием до ближайшего промежутка.
Стратегия замены
В дополнение к генетическому алгоритму (этап 4), вот этапы применения естественной эволюции к умирающему поколению. В сущности, выживают лучшие объекты, а их потомки заменяют наихудшие объекты следующим образом:
Исходный код
И вот, наконец, ссылка для скачивания исходного кода:
Алгоритм машинного обучения для Flappy Bird — заключение
В этом туториале мы успешно реализовали ИИ-робота для обучения игре во Flappy Bird. В результате нескольких итераций мы можем получить почти неуязвимого игрока. Для достижения этой цели мы использовали два подхода к алгоритмам машинного обучения: искусственные нейронные сети и генетический алгоритм.
Для эксперимента можете попробовать изменить некоторые из параметров в коде и посмотреть, что произойдёт. Например, вы можете изменить количество нейронов в скрытом слое или количество объектов в популяции. Кроме того, можете попробовать изменить функции приспособленности. Более того, попробуйте менять некоторые физические параметры — расстояния между препятствиями, гравитацию и так далее.
Попробуйте также применить тот же подход к эволюции в других играх.