Грамматическая эволюция (GE) - это эволюционное вычисление и, более конкретно, метод (или подход) генетического программирования (GP), впервые примененный Конором Райаном, Дж. Дж. Коллинзом и Майклом О'Нилом в 1998 г. [1] в группе BDS при Университете г. Лимерик , хотя есть и другие родственные работы, которые публиковались и раньше, например. [2]
Как и в любом другом подходе GP, цель состоит в том, чтобы найти исполняемую программу, фрагмент программы или функцию, которая достигнет хорошего значения пригодности для данной целевой функции . В большинстве опубликованных работ по GP, древовидным выражением в стиле LISP манипулируют напрямую, тогда как GE применяет генетические операторы к целочисленной строке, впоследствии отображаемой в программу (или подобную) с помощью грамматики, которая обычно выражается в Форма Бэкуса – Наура . Одним из преимуществ GE является то, что это отображение упрощает применение поиска для различных языков программирования и других структур.
Проблема решена
В обычном GP-стиле Коза без типов набор функций должен удовлетворять требованию замыкания: все функции должны иметь возможность принимать в качестве своих аргументов вывод всех других функций в наборе функций. Обычно это реализуется путем работы с одним типом данных, например с плавающей запятой двойной точности. Хотя современные фреймворки генетического программирования поддерживают типизацию, такие системы типов имеют ограничения, от которых не страдает Grammatical Evolution.
Решение GE
GE предлагает решение этой [ какой? ] проблема путем развития решений в соответствии с заданной пользователем грамматикой (обычно грамматика в форме Бэкуса-Наура ). Следовательно, пространство поиска может быть ограничено, а знания предметной области могут быть включены. Источником вдохновения для этого подхода является желание отделить «генотип» от «фенотипа»: в GP объекты, на которых оперирует алгоритм поиска, и то, что интерпретирует функция оценки пригодности, являются одними и теми же. Напротив, «генотипы» GE - это упорядоченные списки целых чисел, которые содержат код для выбора правил из предоставленной контекстно-свободной грамматики. Фенотип, однако, тот же, что и у GP в стиле Коза: древовидная структура, которая оценивается рекурсивно. Эта модель больше соответствует тому, как генетика работает в природе, где существует разделение между генотипом организма и конечным проявлением фенотипа в белках и т. Д.
Разделение генотипа и фенотипа позволяет использовать модульный подход. В частности, поисковая часть парадигмы GE не должна выполняться каким-либо одним конкретным алгоритмом или методом. Обратите внимание, что объекты, по которым GE выполняет поиск, такие же, как объекты, используемые в генетических алгоритмах . В принципе это означает, что любой существующий пакет генетических алгоритмов, такой как популярный GAlib , может использоваться для выполнения поиска, а разработчику, реализующему систему GE, нужно только беспокоиться о выполнении сопоставления из списка целых чисел в дерево программы. . В принципе также возможно выполнить поиск, используя какой-либо другой метод, например оптимизацию роя частиц (см. Примечание ниже); Модульная природа GE создает множество возможностей для гибридов, поскольку того требует решение интересующей проблемы.
Брабазон и О'Нил успешно применяли GE для прогнозирования корпоративного банкротства, прогнозирования фондовых индексов, кредитных рейтингов облигаций и других финансовых приложений. [ необходима цитата ] GE также использовалась с классической моделью хищник-жертва для изучения влияния таких параметров, как эффективность хищника, количество ниш и случайные мутации на экологическую стабильность . [3]
Можно структурировать грамматику GE, которая для данной функции / терминального набора эквивалентна генетическому программированию.
Критика
Несмотря на свои успехи, GE подвергалась некоторой критике. Одна из проблем заключается в том, что в результате операции отображения генетические операторы GE не достигают высокой локальности [4] [5], что является высоко оцененным свойством генетических операторов в эволюционных алгоритмах. [4]
Варианты
Несмотря на то, что GE является относительно новым, существуют уже усовершенствованные версии и варианты, которые были разработаны. Исследователи GE экспериментировали с использованием оптимизации роя частиц для выполнения поиска вместо генетических алгоритмов с результатами, сопоставимыми с результатами обычной GE; это упоминается как «грамматический рой»; Используя только базовую модель PSO, было обнаружено, что PSO, вероятно, в равной степени способна выполнять процесс поиска в GE, как и простые генетические алгоритмы. (Хотя PSO обычно представляет собой парадигму поиска с плавающей запятой, ее можно дискретизировать, например, простым округлением каждого вектора до ближайшего целого числа для использования с GE.)
Еще один возможный вариант, с которым экспериментировали в литературе, - это попытка закодировать семантическую информацию в грамматике, чтобы еще больше повлиять на процесс поиска.
Смотрите также
Заметки
- ^ http://www.cs.bham.ac.uk/~wbl/biblio/gp-html/ryan_1998_geepal.html
- ^ https://www.researchgate.net/profile/PA_Whigham/publication/2450222_Grammatic-based_Genetic_Programming/links/55c3c89908aebc967df1b765.pdf
- ^ Альфонсека, Мануэль; Солер Хиль, Франсиско Хосе (2 января 2015 г.). «Развитие экосистемы математических выражений хищник-жертва с грамматической эволюцией». Сложность . 20 (3): 66–83. DOI : 10.1002 / cplx.21507 . hdl : 10486/663611 .
- ^ a b DOI.org
- ^ http://www.cs.kent.ac.uk/pubs/2010/3004/index.html
Ресурсы
- Учебник по грамматической эволюции .
- Грамматическая эволюция в Java .
- jGE - Грамматическая эволюция Java .
- Biocomputing и Развивающее Systems (BDS) Группа в Университете Лимерик .
- Страница Грамматической эволюции Майкла О'Нила , включая библиографию.
- DRP , направленное программирование на Ruby, представляет собой экспериментальную систему, позволяющую пользователям создавать гибридные системы GE / GP. Он реализован на чистом Ruby.
- GERET , Исследовательский инструментарий Grammatical Evolution Ruby.
- gramEvol , Грамматический Evolution для R .