Символьная регрессия и еще один подход

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


Генетическое программирование действительно является мощным методом. Но в этой статье я хочу рассмотреть другой (не менее интересный) метод — грамматическая эволюция. Рассказывать о нем долго не буду. Скажу лишь то, что метод использует свободную грамматику в форме Бакуса-Наура, а также любой эволюционный алгоритм в качестве "движка" (я выбрал генетический алгоритм). И метод очень крутой!



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


Опишу задачу. Есть неоднородное дифференциальное уравнение второго порядка:


\dot{x}\dot{} + \delta \dot{x} - \beta x + \alpha x^3 = F \cos(\omega t)

Делаем из него однородное (нефорсированный ОД):


\dot{x}\dot{} + \delta \dot{x} - \beta x + \alpha x^3 = 0

После приведения уравнения к нормальной форме Коши получим следующую систему:


\dot{x} = y \\
\dot{y} = \beta x - \alpha x^3 - \delta y


Пусть \beta = 1, \alpha = 1, \delta = 0 и вектор начальных условий X_0 = [x_1,x_2]^T


Вектор начальных условий будет равен [1,1]. Цель: получить такую функцию u(t,x), которая за минимальное время переведет систему из состояния [1,1] в [0,0].


Код системы дифур:


Duffing = [
  lambda t,x: x[1],
  lambda t,x: -x[0] - x[0]**3 + u(t,x)
]

Осталось рассмотреть грамматику, которую я выбрал для метода:


grammar = {
  '<expr>' : [ 
    '(<expr>)<op>(<expr>)', '<val>', '<func1>(<expr>)'
  ],
  '<op>' : [ 
    '+', '-', '*', '/' 
  ],
  '<val>' : [
    'x2', 'x1', '(smallConst)', '(bigConst)' 
  ],
  "<func1>": [
    'minus','math.sin',
  ]
}

Она примитивна, но дает нужный результат. Замечу, что smallConst — константа в интервале [0,1], а bigConst — константа в интервале [0,200].


Запускаем генетический алгоритм с параметрами


Длина хромосомы(каждое число в хромосоме — целочисленное значение в интервале от 0 до 200) = 10
Длина популяции = 50.
Число итераций (продолжительность эволюции) = 200.


Получаем следующий результат:


image

2.5 секунды — время переходного процесса.


u(t,x) = ((minus(x2))-((x1)((0.69028))))((11)) (довольно понятный вид, хотя много скобок)


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


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


Если кого-то заинтересовал ГЭ, то вот статья авторов этого метода (может быть, вскоре переведу).

Share post

Comments 14

    0
    >> Цель: получить такую функцию u(t,x), которая за минимальное время переведет систему из состояния [1,1] в [0,0].

    Имеется в виду минимальное процессорное время (т.е. эти самые 2.5 секунды) или же минимальное время движения какой-то точки без инерции?

    В любом случае, круто, что такие алгоритмы существуют. Наверное, можно даже перевести систему из начального состояния в конечное, пройдя сквозь множество промежуточных состояний. О, да это ж почти задача коммивояжёра! :)
      0
      Имеется ввиду время перерегулирования:)
      А для задачи коммивояжера больше подходит генетический алгоритм. Все-таки грамматическая эволюция направлена на решении задачи символьной регрессии. да вообще хорошо, когда есть интересные алгоритмы, решающие сложные проблемы:)
        0
        Простите, что такое время перерегулирования? Может, время переходного процесса?
          0
          Именно! Спасибо за замечание!
      0
      Рассказывать о нем долго не буду.
      Подход интересный и почему не хотите о нем подробно рассказывать — не понятно.

      Параметры запуска, грамматика, система уравнений, — в статье указаны. А вот кода очень не хватает. Можно ссылку?
      И вопрос: почему bigConst — не (1,200]?
        0
        1) изначально хотел обратить внимание на такой метод. что есть умельцы, которые крутят-вертят алгоритмами, и что из этого получается. В планах дальше перевести первоисточник. Тогда все сразу станет понятно, и код будет не нужен. Все концепции в голове сами будут рисовать картинку реализации:) Код пока на машине. Вскоре выложу на гитхаб, чтоб не потерять.
        2) интервал может быть любым. Дело вкуса и поставленной задачи. Данных констант может и не быть в реализации грамматики. Я для примера взял такой.
          0
          Если будете дальше писать, то есть такой вопрос. Мне кажется, что время стабилизации не должно иметь локального минимума, т.е. его можно делать сколь угодно малым за счёт повышения амплитуды управляющего сигнала. Я давно не смотрел анализ осциллятора Дуффинга, но вроде так. У Вас же получается, что время сходится к значению 2.5 секунды, правильно я понял из статьи? Видимо, это из-за ограниченности выбранной грамматики и диапазонов для констант. Вопрос — можно ли Вашу грамматику переформулировать так, чтобы учитывать ограничение на амплитуду управляющего сигнала, а не на значения параметров? Это было бы более практично.
            0
            Вы правы. В мире мы не можем постоянно крутить амплитуду, поэтому на самом деле амплитуда входного сигнала ограничена: u в рамках [-1,1]. 2.5 сек — частный случай(поэтому и нужно брать среднее значение по нескольким запускам), так как мутация и кроссовер вносят неплохую долю вероятности(да и само образование генотипа для индивидуума). Статья получилась безумно короткой и непонятной. Я понимаю. Постараюсь дальше рассмотреть данный подход под микроскопом, чтобы люди взглянули на этот метод со словами «хм! а надо попробовать!»
              0
              Не понял. Если Вам надо минимизировать время стабилизации, то почему из серии запусков Вы берёте среднее, а не наилучшее значение?
                0
                Для того, чтобы узнать какой результат в среднем выдает написанная мной грамматика. Ведь не всегда результат будет 2.6. Она может давать в 7 случаях из 10 результат равный 3.5. Да, это лучшее решение, но как характеризовать грамматику? это может быть и случайный выброс(отличный выброс, но всего лишь один), он мог и не выпасть. Исследователи рассматривают различные структуры грамматик, запускают некоторое число раз, а потом делают выводы. Одна и та же система (диффуры) может иметь разные параметры. Нужно рассматривать многие варианты, а не зацикливаться на одном. Быть может моя грамматика показала бы результат лучше чем 2.6(но я такого не наблюдал).
                Надеюсь, что ответил на вопрос:)
        +1
        Могла бы быть интересная статья, но…
        Мне было понятно многое, до фразы:
        "… Осталось рассмотреть грамматику, которую я выбрал для метода:..."
        Всё же Хабр это научно-популярный ресурс, а даже в чисто научных журналах сильно не одобряют статьи вида: «Постановка задачи рассмотрен в в работе 1, мы используем метод описанный в работе 2, но с такой-то модификацией значения крокозяблы, вот графики результатов, вывод статьи — так можно делать».
        Хотелось бы расширить для чайников в генетических алгоритмах, с объяснением элементарных понятий типа «грамматика».

          0
          Полностью согласен. Поспешил. Просто был удивлен, что на Хабре не рассматривался такой метод. Хотел сразу показать результаты, опираясь на свой бэкграунд по этой теме. Постараюсь на этой недели написать статью, которая покажет, что творится за кулисами у данного метода. Это действительно интересно:)
            0
            Жду с радостью и нетерпением!
              0
              https://habrahabr.ru/post/281404/
              Надеюсь, что ответил хоть как-то на интересующие вопросы:)

        Only users with full accounts can post comments. Log in, please.