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

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

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

11.04.2016 09:48

brainhack 14 5500 Источник

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

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

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

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

$\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.

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

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

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

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

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

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

Комментарии (14)

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

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

В любом случае, круто, что такие алгоритмы существуют. Наверное, можно даже перевести систему из начального состояния в конечное, пройдя сквозь множество промежуточных состояний. О, да это ж почти задача коммивояжёра! :)
1. brainhack
  11.04.2016 15:24
  #8848594
  Имеется ввиду время перерегулирования:)
  А для задачи коммивояжера больше подходит генетический алгоритм. Все-таки грамматическая эволюция направлена на решении задачи символьной регрессии. да вообще хорошо, когда есть интересные алгоритмы, решающие сложные проблемы:)
  1. Arastas
    11.04.2016 15:39
    #8848662
    Простите, что такое время перерегулирования? Может, время переходного процесса?
    
    brainhack
    11.04.2016 15:40
    #8848666
    Именно! Спасибо за замечание!

Secessus
11.04.2016 16:08
#8848716
Рассказывать о нем долго не буду.
Подход интересный и почему не хотите о нем подробно рассказывать — не понятно.

Параметры запуска, грамматика, система уравнений, — в статье указаны. А вот кода очень не хватает. Можно ссылку?
И вопрос: почему bigConst — не (1,200]?
1. brainhack
  11.04.2016 16:30
  #8848752
  1) изначально хотел обратить внимание на такой метод. что есть умельцы, которые крутят-вертят алгоритмами, и что из этого получается. В планах дальше перевести первоисточник. Тогда все сразу станет понятно, и код будет не нужен. Все концепции в голове сами будут рисовать картинку реализации:) Код пока на машине. Вскоре выложу на гитхаб, чтоб не потерять.
  2) интервал может быть любым. Дело вкуса и поставленной задачи. Данных констант может и не быть в реализации грамматики. Я для примера взял такой.
  1. Arastas
    11.04.2016 17:36
    #8848910
    Если будете дальше писать, то есть такой вопрос. Мне кажется, что время стабилизации не должно иметь локального минимума, т.е. его можно делать сколь угодно малым за счёт повышения амплитуды управляющего сигнала. Я давно не смотрел анализ осциллятора Дуффинга, но вроде так. У Вас же получается, что время сходится к значению 2.5 секунды, правильно я понял из статьи? Видимо, это из-за ограниченности выбранной грамматики и диапазонов для констант. Вопрос — можно ли Вашу грамматику переформулировать так, чтобы учитывать ограничение на амплитуду управляющего сигнала, а не на значения параметров? Это было бы более практично.
    
    brainhack
    11.04.2016 17:44
    #8848922
    Вы правы. В мире мы не можем постоянно крутить амплитуду, поэтому на самом деле амплитуда входного сигнала ограничена: u в рамках [-1,1]. 2.5 сек — частный случай(поэтому и нужно брать среднее значение по нескольким запускам), так как мутация и кроссовер вносят неплохую долю вероятности(да и само образование генотипа для индивидуума). Статья получилась безумно короткой и непонятной. Я понимаю. Постараюсь дальше рассмотреть данный подход под микроскопом, чтобы люди взглянули на этот метод со словами «хм! а надо попробовать!»
    
    Arastas
    11.04.2016 17:57
    #8848946
    Не понял. Если Вам надо минимизировать время стабилизации, то почему из серии запусков Вы берёте среднее, а не наилучшее значение?
    
    brainhack
    11.04.2016 18:04
    #8848960
    Для того, чтобы узнать какой результат в среднем выдает написанная мной грамматика. Ведь не всегда результат будет 2.6. Она может давать в 7 случаях из 10 результат равный 3.5. Да, это лучшее решение, но как характеризовать грамматику? это может быть и случайный выброс(отличный выброс, но всего лишь один), он мог и не выпасть. Исследователи рассматривают различные структуры грамматик, запускают некоторое число раз, а потом делают выводы. Одна и та же система (диффуры) может иметь разные параметры. Нужно рассматривать многие варианты, а не зацикливаться на одном. Быть может моя грамматика показала бы результат лучше чем 2.6(но я такого не наблюдал).
    Надеюсь, что ответил на вопрос:)

Dum_spiro_spero
11.04.2016 17:07
#8848832
+1
Могла бы быть интересная статья, но…
Мне было понятно многое, до фразы:
"… Осталось рассмотреть грамматику, которую я выбрал для метода:..."
Всё же Хабр это научно-популярный ресурс, а даже в чисто научных журналах сильно не одобряют статьи вида: «Постановка задачи рассмотрен в в работе 1, мы используем метод описанный в работе 2, но с такой-то модификацией значения крокозяблы, вот графики результатов, вывод статьи — так можно делать».
Хотелось бы расширить для чайников в генетических алгоритмах, с объяснением элементарных понятий типа «грамматика».
1. brainhack
  11.04.2016 17:10
  #8848840
  Полностью согласен. Поспешил. Просто был удивлен, что на Хабре не рассматривался такой метод. Хотел сразу показать результаты, опираясь на свой бэкграунд по этой теме. Постараюсь на этой недели написать статью, которая покажет, что творится за кулисами у данного метода. Это действительно интересно:)
  1. Dum_spiro_spero
    14.04.2016 02:02
    #8852657
    Жду с радостью и нетерпением!
    
    brainhack
    14.04.2016 11:22
    #8852907
    https://habrahabr.ru/post/281404/
    Надеюсь, что ответил хоть как-то на интересующие вопросы:)