Генетические алгоритмы: как это работает

Генетические алгоритмы прекрасно применимы для автоматического подбора архитектуры нейронных сетей (AutoML). Их мало кто использует, мы же в работе часто применяем генетические алгоритмы и получаем превосходные автоматизированные результаты. Дмитрий Романов, основатель Университета искусственного интеллекта, рассказывает, как это работает.

Что такое генетические алгоритмы

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

С помощью генетических алгоритмов можно автоматически подбирать архитектуру нейронной сети. Во многих задачах, особенно простых, у разработчика много времени уходит на эксперименты с архитектурой нейронной сети: классификация изображений и текстов, табличные данные, прогнозирование временных рядов и так далее. Нужно сидеть и проводить сотни экспериментов по подбору архитектуры нейронной сети, чтобы вытянуть точность, например, со стартовых 90% до 98%, которые необходимы заказчику. В сложных задачах это может занимать до 1-3 месяцев. Генетика позволяет это ускорить и подобрать нужную архитектуру автоматически.

Плюсы генетики:

• подберет автоматически;
• в 95% случаев решит задачу быстрее, чем человек;
• в 50% случаев выдает точность лучше, чем человек, а в оставшихся случаях — не хуже, чем человек.

Пример: мы использовали генетические алгоритмы для определения эффективности рекламы в Telegram. Когда мы покупаем рекламный пост в Telegram, сложно заранее оценить, будет ли данный Tg-канал эффективным. Мы решили применить нейронные сети, чтобы по тексту последних 10 постов в канале определить, стоит ли покупать в нём рекламу. Задача довольно сложная, особенно если учитывать сильно ограниченный обучающий датасет - всего 1800 записей.

Senior AI-разработчик за 1 день экспериментов достиг точности 81%, а генетический алгоритм всего за 6 часов достиг точности 90%.

Альтернативы генетических алгоритмов

Искать и экспериментировать с архитектурой самому

Это занимает от 1 недели до 2-3 месяцев, а генетика решает задачу всего за несколько часов. Запускаем ее на Google Colab на ночь и утром получаем крутую архитектуру.

Использовать Grid search

Это тоже значительно дольше, потому что Grid search — это не подбор интеллектуальным образом, а шаблонный перебор параметров нейронной сети.

Результаты работы с генетическими алгоритмами

Мы для себя разработали эту технологию еще в 2007-м, когда ещё не было Tensorflow, Pytorch, Keras. Нейронки писали вручную и подбирали алгоритмы для оптимизации архитектур. Сейчас мы используем это на практике в проектах, в том числе для крупных компаний, а также в нейросетевых реалити-проектах, которые проводим для широкой аудитории и демонстрируем, как люди с нуля пишут нейронные сети за 10 дней.

Пример: на последнем реалити мы решали задачу с цифрового прорыва — классификация текста на 17 классов, датасет около 2000 записей. Люди добились максимальной точности 98,7% на проверочной выборке, причем это была команда из 4-х человек, которые занимались этим неделю по вечерам. Генетический алгоритм за 4 часа собрал сетку на 99% точности, то есть +0,3%.

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

Создаем ботов генетического алгоритма с нужной структурой

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

То есть один бот – это архитектура нейронки. Допустим, решаем классификацию изображений, и бот говорит: "У вас будет два сверточных слоя по 32 нейрона, потом maxpooling слой, потом batch-нормализация, один dense слой и финальный dense слой". Это структура бота.

Оцениваем эффективность бота

Бота необходимо оценивать по качеству и эффективности.

Если мы расставляем светильники – это равномерность освещения и минимальное количество израсходованных светильников. Если говорим о самолетах — оптимальность маршрутов, чтобы был максимальный пассажиропоток, чтобы не летели вместе конфликтующие друг с другом пилоты, и чтобы пилоты, которые не любят заходить на посадку с моря, не заходили с моря и так далее. За оптимальность маршрута боту начисляются баллы, поставил посадку с моря пилоту, который не любит заходить на посадку с моря — получает штрафные баллы. Это реальный кейс, который мы обсуждали с очень крупной российской авиакомпанией.

Как мы оцениваем бота в случае нейронной сети? Оцениваем точность на проверочной выборке. Мы запустим эту нейронку обучаться 10 раз подряд, потому что нейронка стартует с разных рандомных стартовых весов и нельзя судить о ней по одному запуску обучения. Мы запустим нейронку 10 раз подряд и возьмем лучшую точность. В итоге критерий оценки таков: бот собрал нейронку, мы ее запускаем 10 раз и получаем 89% точности.

Сортируем ботов генетического алгоритма

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

Генерируем новых ботов генетического алгоритма, скрещивая выживших

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

Например, у одного первым слоем стояло в сверточном слое 32 нейрона, а у другого 64. Рандомно выбираем одного из ботов-"родителей" с 50% вероятности и берём его параметр - получаем 64 нейрона у потомка. У первого было ядро свертки 3/3, а у второго 5/5 — например, выпадает 3/3 от первого бота. И так далее проходим по всем слоям и параметрам ботов-"родителей". Можно применять разные хитрые механизмы, но суть такая: из этих двух архитектур собираем новую архитектуру, которая наследует их признаки. Если ни один из них не использовал maxpooling или dropout слои, то и у потомка этих слоев не будет. Если у обоих было много сверточных слоев, то и у потомка будет много сверточных слоев. Потомок в целом наследует признаки двух родителей, и, так как это были лучшие боты в популяции, с некоторой вероятностью он унаследует лучшие признаки и от того, и от другого. Хотя может унаследовать все худшее от обоих, это непредсказуемо.

Делаем мутацию ботов генетического алгоритма

После скрещивания мы делаем мутацию — вносим небольшие изменения. Если в первой популяции ни у кого из ботов не было определенного слоя (например, maxpooling), то ни у кого из потомков его не будет, если не сделать мутацию.

Мутации обычно делаются небольшие, порядка 0,5-1% вероятности. Например, с вероятностью 1% у полученного потомка убираем или добавляем конкретный слой, или меняем количество нейронов, или меняем ядро свертки. В среднем у бота 200-300 управляемых параметров, поэтому по статистике 2-3 параметра у него смутируют.

Запускаем и проверяем новую популяцию ботов генетического алгоритма

Новую популяцию ботов снова запускаем и проверяем их качество. К примеру, окажется, что из 70-ти ботов-потомков 10 войдут в число лучших 30 и вытеснят кого-то из предков. С большой вероятностью потомки войдут в первую тройку, потому что кто-то из них унаследует лучшие признаки от своих родителей и окажется еще более эффективным.

Таким образом, генетические алгоритмы – это метод интеллектуального перебора. В целом это похоже на то, как AI-разработчик ищет архитектуры. Мы запускаем новую архитектуру, смотрим, что срабатывает, что не срабатывает, из сработавшего собираем что-то новое.

Повышаем качество генетики

Генетический алгоритм идет эпохами. Один запуск, отсев, скрещивание и мутация – это одна эпоха генетики, обычно их проходит 10-30 штук. Есть много продвинутых техник, которые позволяют повысить качество генетики, ее сходимости и так далее. Например:

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

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

Как строится нейронная сеть в боте генетического алгоритма

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

Классификация изображений - это двумерные сверточные сетки с типовой структурой. Бот сначала выбирает, какую сетку собрать — маленькую, среднюю или большую (S, M, L). Есть типовые сверточные блоки — свертка-свертка, maxpooling, batchnorm, dropout и так далее. Бот выбирает, сколько блоков сделать и какое выбрать наполнение, и рандомно генерирует архитектуру сетки.

Для классификации текстов с помощью генетического алгоритма мы выбираем, по какому принципу действуем – bag of words или embedding. Bag of words – это полносвязные сетки, embedding – одномерные свертки, LSTM и полносвязные сетки.

Если это табличные данные, то выбираем просто генерить полносвязные сетки.

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

Эта идея очень простая, при этом крайне эффективная. Генетический алгоритм действительно может, будучи написанным всего за ночь, собрать архитектуру сетки, которую человек бы подбирал неделю. Полная автоматизация процесса, причем точность в 50% случаев оказывается заметно лучше, чем у человека, а в 50% случаев такая же. Я не встречал случаев, когда генетический алгоритм собрал бы архитектуру сети хуже, чем человек, а у нас были десятки баттлов "человек против генетики" в реальных проектах для крупных компаний.

Ограничения генетических алгоритмов

Генетический алгоритм не подходит для сложных нейронных сетей

С помощью генетического алгоритма можно запускать только простые быстрые сетки. Если сетка учится 5 часов, нельзя запустить генетику, потому что генетический алгоритм в среднем делает в 5-10 раз больше запусков сетки, чем человек. Все-таки человек обладает интеллектом и подбирает более точные решения, чем генетика. Если человек решит задачу за 20 запусков, а генетический алгоритм за 100 запусков — при 5-часовом обучении сетки это будет 100 часов времени машинного обученияу AI-разработчика против 500-1000 часов у генетики.

Генетические алгоритмы применимы там, где сетка обучается до 10-20 минут. К счастью, это большинство простых типовых задач. Не подходят для генетики сложные задачи типа object detection на YOLOv5, большие датасеты и так далее. Но мы делаем десятки реальных проектов и видим, что в половине случаев генетика прекрасно применима и творит просто чудеса.

Генетический алгоритм не подходит там, где не нужны эксперименты

В генетике нет особого смысла там, где не нужны эксперименты. Например, speech recognition— там мы берем Tinkoff VoiceKit, Яндекс, Сбер voicekit-ы либо типовую библиотеку Google, и готово. В задачах object detection – берем предобученную YOLOv5 и готово. Для чат-ботов мы тоже смотрим в сторону GPT-3. В задачах, где нет процесса экспериментов, мы берем предобученную готовую сетку, и она гарантированно даст лучший результат.

Генетический алгоритм надо кодить

Необходимо разобраться в генетическом алгоритме, кодить автоматический сбор нейронки и так далее. Даже на примитивном уровне это занимает несколько дней, а то и неделю.

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

Подведем итог

У генетических алгоритмов есть ограничения, но выгоды их использования очевидны. Если перед вами стоит задача классификации изображений, текстов, табличных данных или предсказания временных рядов — вы либо неделю-две экспериментируете сами, либо запускаете генетику, и она за ночь собирает архитектуру, причем такую комбинацию, которую вы себе и представить не можете. Я 20 лет занимаюсь нейронными сетями, и все равно генетика постоянно находит что-то такое, что мне бы в голову не пришло, и точность у нее лучше, чем у меня.

Генетика — мощный инструмент, рекомендую к применению в типовых задачах.