Символьная регрессия считается очень интересной. «Найди мне функцию, которая будет лучше всего подходить для решения поставленной задачи». И на Хабре я уже встречал пост, в котором автор рассматривал один из эволюционных алгоритмов в применении к этой проблеме (вот он).
Генетическое программирование действительно является мощным методом. Но в этой статье я хочу рассмотреть другой (не менее интересный) метод — грамматическая эволюция. Рассказывать о нем долго не буду. Скажу лишь то, что метод использует свободную грамматику в форме Бакуса-Наура, а также любой эволюционный алгоритм в качестве «движка» (я выбрал генетическое программирование). И метод очень крутой!
Перейду сразу к примеру. В качестве рабочей лошадки я выбрал Осциллятор Дуффинга.
Опишу задачу. Есть неоднородное дифференциальное уравнение второго порядка:
Делаем из него однородное (нефорсированный ОД):
После приведения уравнения к нормальной форме Коши получим следующую систему:
Вектор начальных условий будет равен [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)) (довольно понятный вид, хотя много скобок)
Вывод: Грамматическая эволюция — молодой, но мощный инструмент в решении задач символьной регрессии. Да, не существует математически точного метода выбора той или иной грамматики для решаемой задачи. Нужно опираться на опыт и пробы с ошибками. Но метод работает и зачастую выдает приемлемый результат без оптимизированной грамматики.
Если кого-то заинтересовал ГЭ, то вот статья авторов этого метода (может быть, вскоре переведу).
Автор: brainhack