[Из песочницы] Символьная регрессия и еще один подход Опции

[Decker]

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



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



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



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







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







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











Вектор начальных условий будет равен [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)) (довольно понятный вид, хотя много скобок)



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



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



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

Original source: habrahabr.ru (comments, light).

Читать дальше