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

    Одним субботним декабрьским вечером сидел я над книгой The Blind Watchmaker (Слепой Часовщик), как на глаза мне попался невероятно интересный эксперимент: возьмём любое предложение, например Шекспировскую строку: Methinks it is like a weasel и случайную строку такой же длины: wdltmnlt dtjbkwirzrezlmqco p и начнем вносить в неё случайные изменения. Через сколько поколений эта случайная строка превратится в Шекспировскую строку, если выживать будут лишь потомки более похожие на Шекспировскую?

    Сегодня мы повторим этот эксперимент, но в уже совершенно другом масштабе.



    Структура статьи:
    1. Что такое генетический алгоритм
    2. Почему это работает
    3. Формализуем задачу со случайной строкой
    4. Пример работы алгоритма
    5. Эксперименты с классикой
    6. Код и данные
    7. Выводы

    Осторожно трафик!

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


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

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



    Почему это работает


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

    Популяция всегда стремится к ближайшему максимуму, так как мы отбираем текущие точки поиска, как имеющие максимальное значение (все остальные точки «умрут», не выдержат конкуренции с ближайшим максимумом). Так как размер популяции значительный, а значит вероятность сделать хотя бы один шаг в направлении максимума не пренебрежимо мала, то через некоторое количество шагов популяция сместится в сторону локального максимума. А потомки точки, смещенной ближе к максимуму, имеют большую «выживаемость». Значит через достаточное количество шагов, потомки этой точки начнут доминировать в популяции и вся она сместится к максимуму.

    Визуализация популяции стремящейся к локальному максимуму:


    (due to Randy Olson)

    Формализуем задачу со случайной строкой


    Входные данные: строка S
    Выходные данные: натуральное число N, равное количеству поколений необходимых для преобразования случайной строки длины len(S) в строку S

    Что в нашем случае мутация? Под мутацией строки S мы понимаем замену одного случайно выбранного символа из строки S на другой произвольный символ алфавита. В данной задаче мы используем только символы нижнего регистра латиницы и пробел.

    Что такое изначальная популяция (initial population в схеме)? Это случайная строка равная по длине входной строке S.

    Что такое потомки (offsprings)? Пусть мы зафиксировали количество мутаций одной строки на константу k, тогда потомки — это k мутаций каждой строки текущего поколения.

    Что такое выжившие (survivors)? Пусть мы зафиксировали размер популяции на константу h, тогда выжившие — это h строк максимально похожих на входную строку S.

    В псевдокоде (подозрительно похожем на python) это выглядит следующим образом:


    Пример работы алгоритма


    Рассмотрим следующую строку: The quick brown fox jumps over the lazy dog и воспроизведём для неё вывод нашей программы:
    Рассмотрим цепочку изменений (слева номер поколения):
    1  rbbzmffwfhwtxnjjiozz ujhhlxeoyhezarquvmopyk
    2  rbbzmffwfhwtxnjjiozz ujhhlxeoyhezarquzmopyk
    3  rbb mffwfhwtxnjjiozz ujhhlxeoyhezarquzmopyk
    4  rbb mffwfhwtxnjjiozz ujhhlxeoyhezarquzmodyk
    5  rbb mffwfhbtxnjjiozz ujhhlxeoyhezarquzmodyk
    6  rbb mffcfhbtxnjjiozz ujhhlxeoyhezarquzmodyk
    7  rbb mffcf btxnjjiozz ujhhlxeoyhezarquzmodyk
    8  rbb mffcf btxnjjiozz ujhhlxeoyheza quzmodyk
    9  rbb mffcf brxnjjiozz ujhhlxeoyheza quzmodyk
    10 rbb mffcf brxnjjiozz ujphlxeoyheza quzmodyk
    20 rbb mffcf bronj fox jujpslxveyheza luzmodyk
    30 rbb mficf bronj fox jumps overhehe luzy dyg
    40  he m ick bronn fox jumps over the lazy dog
    41  he q ick bronn fox jumps over the lazy dog
    42  he q ick bronn fox jumps over the lazy dog
    43  he q ick brown fox jumps over the lazy dog
    44  he quick brown fox jumps over the lazy dog
    45 ahe quick brown fox jumps over the lazy dog
    46 the quick brown fox jumps over the lazy dog
    

    Полный вывод
    print_genes("The quick brown fox jumps over the lazy dog")
    1  rbbzmffwfhwtxnjjiozz ujhhlxeoyhezarquvmopyk
    2  rbbzmffwfhwtxnjjiozz ujhhlxeoyhezarquzmopyk
    3  rbb mffwfhwtxnjjiozz ujhhlxeoyhezarquzmopyk
    4  rbb mffwfhwtxnjjiozz ujhhlxeoyhezarquzmodyk
    5  rbb mffwfhbtxnjjiozz ujhhlxeoyhezarquzmodyk
    6  rbb mffcfhbtxnjjiozz ujhhlxeoyhezarquzmodyk
    7  rbb mffcf btxnjjiozz ujhhlxeoyhezarquzmodyk
    8  rbb mffcf btxnjjiozz ujhhlxeoyheza quzmodyk
    9  rbb mffcf brxnjjiozz ujhhlxeoyheza quzmodyk
    10 rbb mffcf brxnjjiozz ujphlxeoyheza quzmodyk
    11 rbb mffcf brxnj iozz ujphlxeoyheza quzmodyk
    12 rbb mffcf brxnj ioz  ujphlxeoyheza quzmodyk
    13 rbb mffcf bronj ioz  ujphlxeoyheza quzmodyk
    14 rbb mffcf bronj ioz  ujphlxeeyheza quzmodyk
    15 rbb mffcf bronj ioz  ujphlxeeyheza luzmodyk
    16 rbb mffcf bronj ioz  ujphlxveyheza luzmodyk
    17 rbb mffcf bronj foz  ujphlxveyheza luzmodyk
    18 rbb mffcf bronj foz jujphlxveyheza luzmodyk
    19 rbb mffcf bronj foz jujpslxveyheza luzmodyk
    20 rbb mffcf bronj fox jujpslxveyheza luzmodyk
    21 rbb mffcf bronj fox jujpslxveyheza luzm dyk
    22 rbb mffcf bronj fox jujpslxverheza luzm dyk
    23 rbb mffcf bronj fox jumpslxverheza luzm dyk
    24 rbb mffcf bronj fox jumpslxverheha luzm dyk
    25 rbb mffcf bronj fox jumpslxverhehe luzm dyk
    26 rbb mffcf bronj fox jumps xverhehe luzm dyk
    27 rbb mffcf bronj fox jumps xverhehe luzm dyg
    28 rbb mffcf bronj fox jumps xverhehe luzy dyg
    29 rbb mffcf bronj fox jumps overhehe luzy dyg
    30 rbb mficf bronj fox jumps overhehe luzy dyg
    31 rbb mficf bronj fox jumps overhehe lazy dyg
    32 rbb mficf bronn fox jumps overhehe lazy dyg
    33 rbb mficf bronn fox jumps over ehe lazy dyg
    34 rhb mficf bronn fox jumps over ehe lazy dyg
    35  hb mficf bronn fox jumps over ehe lazy dyg
    36  hb mfick bronn fox jumps over ehe lazy dyg
    37  hb m ick bronn fox jumps over ehe lazy dyg
    38  hb m ick bronn fox jumps over ehe lazy dog
    39  he m ick bronn fox jumps over ehe lazy dog
    40  he m ick bronn fox jumps over the lazy dog
    41  he q ick bronn fox jumps over the lazy dog
    42  he q ick bronn fox jumps over the lazy dog
    43  he q ick brown fox jumps over the lazy dog
    44  he quick brown fox jumps over the lazy dog
    45 ahe quick brown fox jumps over the lazy dog
    46 the quick brown fox jumps over the lazy dog
    


    Как мы видим каждое поколение отличается не более, чем на один символ друг от друга. Всего потребовалось 46 поколений, чтобы добраться от rbbzmffwfhwtxnjjiozz ujhhlxeoyhezarquvmopyk до the quick brown fox jumps over the lazy dog с помощью мутаций и отбора.

    Эксперименты с классикой


    Отдельные примеры, шекспировской строка или английская панграмма про лису, интересны, но не слишком убедительны. Поэтому и решил рассмотреть более интересный вопрос: что будет если взять пару классических произведений, разбить их на предложения и посчитать число поколений для каждого из них? Какой будет характер зависимости количества поколений от строки (например, от её длины)?

    В качестве классических произведений выбрал To Kill a Mocking Bird by Harper Lee (Убить Пересмешника, Харпер Ли) и Catcher in the Rye by J.D. Salinger (Над Пропастью во Ржи, Джей Ди Сэлинджер). Мы будем измерять два параметра — распределение количества поколений по предложениям и зависимость количества поколений от длины строки (есть ли корреляция?).

    Параметры были следующие: количество потомков у строки: 100; количество выживших в поколении: 10.

    Результаты

    Как мы видим, для большинства предложений получилось достичь строку достаточно быстро, требуются менее 100 итераций, практически для всех предложений достаточно 200 итераций (среди всех предложений было только одно, которому потребовалось 1135 итераций, судя по предложению алгоритм разбивки ошибся и склеил несколько предложений в одно):



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


    R^2 равен 0.996 и 0.997 соответственно.

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

    Код и данные


    Весь код, python — генетический алгоритм\обработка текста и R — визуализация, доступен в github:
    github.com/SergeyParamonov/genetics-experiments

    Выводы


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

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

    Ну. И что?
    Реклама
    Комментарии 22
    • +16
      Как по мне — самое сложное в реальных приложениях генетических алгоритмов — правильная фитнес-функция. В примере из топика все тривиально, однако на деле все не так просто. Если у вас есть достаточно линейная, гладкая и легко вычислимая фитнес-функция — вы решите задачу и генетикой, и градиентным спуском, и прочей нейронщиной, без проблем. А если фитнес-функция плоха, то ничего не поможет.

      Второе по сложности — генетический код. Нужно придумать хорошие признаки, которые опять-таки должны быть достаточно линейны относительно фитнес-функции.

      Подвох в том, что если у вас есть и первое, и второе, задача скорее всего и так уже имеет достаточно простое и очевидное аналитическое решение.
      • +1
        Не соглашусь. Чтобы написать правильную фитнес-функцию, нужно только лишь внимательно подумать и составить формализованный перечень требований к конечному решению задачи. Сверка решения с этими требованиями — задача, как правило, линейная и решаемая. Создание генома — в общем-то, тоже вопрос сформулированности ТЗ.

        Генетическое программирование призвано решать недетерминированные задачи, для которых невозможно линейным образом сгенерировать хоть какое-либо решение. IRL их всегда было и будет много. Один из классов таких задач — NP-полные задачи. Я сейчас как раз занимаюсь решением одной из них. Весьма, скажу, увлекательное занятие!

        Кстати, хозяйке на заметку, довольно неплохая библиотека для работы с сабжем (java):
        jgap.sourceforge.net/
        • +1
          Кстати говоря, сам занимаюсь NP задачами (и выше) и иногда вижу статьи, которые успешно применяют GA для решения задач с примерно такой формулировкой: «Сложность задачи слишком высока для поиска точного решения, поэтому мы предлагаем генетический алгоритм в качестве аппроксимации». Обычно на этом этапе формальная спецификация задачи уже присутствует и вопрос в том, как найти хоть какое-то разумное решение.
          • 0
            Можно спросить, как более сведущего человека? Я правильно понимаю, что задачи из пространства NP можно решить алгоритмически, а NP-сложные и, в частности, NP-полные задачи можно решить исключительно аппроксимацией (будь то ГП, graph rewriting или что-то еще)?
            • +1
              Не, можно и точно, весь вопрос в существовании эффективных солверов для класса сложности. Для NP есть куча эффективных SAT солверов, а для других классов их как правило мало и скорость поиска решений очень быстро падает с ростом сложности. Поэтому для конкретных задач часто используют эвристики и приближенные решения.

              Для примера, SMT — обобщение SAT для разных логик в духе функций или арифметики. Сложность выше, скорость существенно меньше, но можно решать задачи в духе найти f такую, что f(x) > 5 для всех x и f(x) > f(y) для x > y.

              Или answer set programming — решает задачи на второму уровне полиномиальной иерархии (т.е. один уровень выше, чем NP), используя некоторые логические правила вывода, из которых состоит программа.
        • +2
          Согласен про фитнес функцию. Хотя мне кажется, что генетические алгоритмы оптимизации рулят в многоанентских средах, где фитнес функция невычислима вообще, и результатом может быть только победа в поединке с другим агентом.
          • 0
            Не по теме: есть русский термин для фитнесс-функции — функционал невязки. Просто вспомнил)
            • 0
              В общем случае нет: функционал невязки — это скорее что-нибудь, использующее только лишь разницу между текущим значением функции и ожидаемым.

              Например, в задачах нелинейной символьной регрессии, которой я изредка пытаюсь заниматься, среднеквадратичное отклонение вполне себе можно назвать функционалом невязки, пожалуй. А вот если попытаться ввести в фитнесс-функцию что-либо, характеризующее решение с других точек зрения (сложность, например, и штрафовать за неё), то это едва ли уже будет синонимами.
              • 0
                Т.е. fitness в английском варианте содержит в себе понятие сложность? Не думаю, что термин зависит от задачи. Это всего лишь термин. Захотите, он будет значить всё, что душе угодно) Важно, чтобы термин устоялся и был принят сообществом. Тогда он будет понятен.
                • 0
                  В английском варианте это, в общем-то, любая функция, используемая для ранжирования особей. А включается ли там сложность (их, кстати, тоже несколько разных бывает) или ещё что — дело уж десятое. Чего, насколько я знаю отечественную терминологию, не скажешь о невязке.

                  Вот функционал качества — это уже другое дело, да.
          • +2
            В комменте выше речь о том, что «Если у вас есть достаточно линейная, гладкая и легко вычислимая фитнес-функция ...». А не любая фитнес-функция.

            Тоже много экспериментировал с ГА. От себя добавлю, что сложность ГА прежде всего в правильной реализации операторов (скрещивания и мутации, а также селекции и редукции), чтобы подальше отвести ГА от случайного поиска и поближе к направленному. Представление особи (хромосомы/решения) тоже нетривиальная задача. Давно уже никто битовой строкой не представляет. Можно просто векторами. Можно списками, деревьями и графами. Но чем сложнее кодирование особи, тем еще более сложными будут скрещивание и мутация.

            Наверное, надо бы статью на хабр сделать со своим видением ГА. Плюсами и минусами.
            • 0
              Но, простите, это заложено в определении NP-задачи — решаемость за полиномиальное время. Предполагать решение NP-задачу сколько-нибудь «быстро» — это абсурд. Тем более, NP-полную задачу.

              Совершенно согласен про операторы. Причем важно не только их правильно реализовать, но и правильно применять в алгоритме эволюции. Про геном не соглашусь. Разумеется, битовая строка — это смешно в век ООП. Как и невозможность/нетривиальность представления какого-либо типа данных. Весь мир уже описан в XML так или иначе.

              Признаюсь, я новичок в этом деле, статью непосредственно про ГП я не осилю, но если у меня получится решить мою задачу — обязательно об этом напишу.
              • 0
                > Предполагать решение NP-задачу сколько-нибудь «быстро» — это абсурд.

                Если у вас есть доказательство, что ваша задача NP класса, согласен, абсурд. Доказательство есть? :)
                • 0
                  А вот это уже нетривиальный вопрос, но правильный :) Формулами не блесну, ибо я не математик (и, строго говоря, даже не программист по профессии), но скажу, что моя задача, в принципе, сводится к этой, с некоторыми дополнительными условиями.
                • +1
                  Битовая строка смешна скорее не потому, что ООП, а потому, что при скрещивании двух битовых строк могут вылезать всякие не очень корректные и не очень приятные особи.

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

                  Подробнее, например, тут.
                  • 0
                    Да, в случае с построением формулы в фитнес-функцию пришлось бы встраивать непростую проверку синтаксиса, а ООП избавляет от такой необходимости на корню.

                    Интересный документ. Технически — используется достаточно очевидная в наше время объектная модель с хэшмапами символов, однако в качестве хромосомы все равно выступает, по сути, битовая строка. Забавно читать: девять лет назад считалось космическими технологиями, а сегодня сделать по другому и в голову-то не приходит :)

                    Вот только с математической точки зрения мне трудно понять, как апроксимируются математические выражения. Ведь при изменении любого оператора или параметра результат выполнения функции будет меняться на всем пространстве аргументов, так? К примеру, если в популяции появится хромосома с абсолютно правильным набором операторов, но с неправильными параметрами, она с большой вероятностью будет отброшена, разве нет?
                • 0
                  Да, думаю много кому (включая меня) было бы интересно.
                • +9
                  Знал бы фитнес-функцию, жил бы в Сочи.
                  • 0
                    Ну, если бы еще мог клонироваться и мутировать… то да :)
                  • 0
                    Как по мне, так генетический алгоритм достаточно узок в применении и скорее позволяет красиво посмотреть как там ищется минимум в нашем многомерном пространстве. Как более практически применимый я бы порекомендовал Simmulated Annealing (Алгоритм имитации отжига) — он умеет выпрыгивать из маленьких ям, у меня с ним получалось решать оптимизационные задачи и он тоже достаточно прост по своей идее и хорош с точки зрения контроля за ним.
                    • +2
                      немного не в тему, но тоже любопытный пример применения генетического алгоритма

                    Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                    Самое читаемое