Minimalist Genetic Programming: новый алгоритм вдохновлён лингвистикой и превосходит классический GP
Генетическое программирование (GP) десятилетиями решает задачи машинного обучения через эволюционный поиск синтаксических деревьев. Однако новый подход Minimalist Genetic Programming (MGP) кардинально меняет эту концепцию: вместо биологической эволюции алгоритм опирается на теорию синтаксиса человеческого языка — Минималистскую программу.
В основе MGP лежит оператор MERGE — бинарная операция формирования множеств, которая постепенно строит сложные символьные выражения. Этот процесс напоминает марковскую цепь: каждый шаг зависит только от предыдущего состояния. Такой подход позволяет алгоритму не просто перебирать случайные варианты, а целенаправленно конструировать выражение из атомарных синтаксических объектов.
Авторы протестировали MGP на нескольких задачах символьной регрессии, которые считаются сложными для классического GP из-за склонности к раздуванию (bloat) — неконтролируемому росту размера программ. Результаты показали, что при правильном выборе лексикона атомарных объектов MGP стабильно восстанавливает точную целевую модель, в то время как стандартный GP часто терпит неудачу.
«Инсайты, полученные из лингвистики, оказались релевантны для задачи индукции программ, — отмечают исследователи. — MGP демонстрирует потенциал, который стоит изучить дальше». Это может означать новый поворот в области автоматического синтеза программ и символьного регрессионного моделирования.
Работа опубликована на arXiv и доступна для рецензирования. Пока MGP проверен только на небольших задачах, но авторы планируют расширить тестирование на более сложные области, включая обработку естественного языка и автоматическое программирование.
