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

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

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

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

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

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

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

Вектор начальных условий будет равен [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',
  ]
}

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

За 2.5 секунды система вышла на заданное условие.

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

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

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

Автор: brainhack

Источник ^[4]