Grammatical evolution

Введение

Грамматическая эволюция (ГЭ) - это эволюционный вычисление и, более конкретно, генетическое программирование (ГП) техника (или подход), впервые разработанный Конором Райаном, Джей Джей Коллинз и Майкл О'Нилл в 1998 году в группе BDS в Университете Лимерика. Как и в любом другом подходе GP, цель состоит в том, чтобы найти исполняемую программу, фрагмент программы или функцию, которая достигнет хорошего значения пригодности для данной целевой функции. В большинстве опубликованных работ по ГП, LISP стиль дерево структурированное выражение непосредственно манипулируется, тогда как GE применяет генетические операторы к цельной строке, впоследствии отображается в программе (или аналогичной) с помощью грамматики, которая обычно выражается в форме BackusNaur. Одним из преимуществ GE является то, что это отображение упрощает применение поиска к различным языкам программирования и другим структурам.

Проблема решена

В свободном от типов, обычном Koza-стиле GP, набор функций должен соответствовать требованию закрытия: все функции должны быть способны принимать в качестве своих аргументов выход всех других функций в набор функций. Обычно это реализуется путем обработки одного типа данных, такого как двойная точность плавающей запятой. В то время как современные структуры генетического программирования поддерживают типизацию, такие типы систем имеют ограничения, от которых не страдает Grammatical Evolution.

Решение GE

GE предлагает решение ограничения одного типа путем разработки решений в соответствии с грамматикой, указанной пользователем (обычно грамматика в форме Backus Naur). Поэтому поисковое пространство может быть ограничено, а знание проблемы может быть включено. Вдохновение для этого подхода исходит из желания отделить "генотип" от "фенотипа": в GP объекты, на которых работает алгоритм поиска, и то, что интерпретирует функция оценки физической подготовленности, являются одним и тем же. В отличие от этого, "генотипы" GE - это упорядоченные списки целых чисел, которые кодируют правила выбора из предоставленной свободной грамматики. Фенотип, однако, такой же, как в Koza стиле GP: дерево, как структура, которая оценивается рекурсивно. Эта модель больше соответствует тому, как генетика работает в природе, где существует разделение между генотипом организма и окончательным выражением фенотипа в белках и т. Д. Разделение генотипа и фенотипа позволяет использовать модульный подход. В частности, поисковая часть парадигмы GE не должна выполняться каким-либо конкретным алгоритмом или методом. Обратите внимание, что объекты, на которых выполняется поиск GE, такие же, как и те, которые используются в генетических алгоритмах. Это означает, что любой существующий пакет генетических алгоритмов, такой как популярный GAlib, может быть использован для выполнения поиска, и разработчику, реализующему систему GE, нужно только беспокоиться о выполнении отображения из списка целых чисел в дерево программы. В принципе, поиск также можно выполнить с использованием какого-либо другого метода, такого как оптимизация роя частиц (см. примечание ниже); модульная природа ГЭ создает много возможностей для гибридов, поскольку решаемая проблема интереса диктует. Брабазон и О'Нилл успешно применяли GE для прогнозирования корпоративного банкротства, прогнозирования фондовых индексов, кредитных рейтингов облигаций и других финансовых приложений. ГЭ также использовались в классической модели хищника-добычи, чтобы исследовать влияние таких параметров, как эффективность хищника, число нишей и случайные мутации на экологическую стабильность. Можно структурировать ГЭ грамматику, которая для данной функции/терминального набора эквивалентна генетическому программированию.

GE offers a solution to the single type limitation by evolving solutions according to a user specified grammar (usually a grammar in Backus Naur form). Therefore the search space can be restricted, and domain knowledge of the problem can be incorporated. The inspiration for this approach comes from a desire to separate the "genotype" from the "phenotype": in GP, the objects the search algorithm operates on and what the fitness evaluation function interprets are one and the same. In contrast, GE's "genotypes" are ordered lists of integers which code for selecting rules from the provided context free grammar. The phenotype, however, is the same as in Koza style GP: a tree like structure that is evaluated recursively. This model is more in line with how genetics work in nature, where there is a separation between an organism's genotype and the final expression of phenotype in proteins, etc. Separating genotype and phenotype allows a modular approach. In particular, the search portion of the GE paradigm needn't be carried out by any one particular algorithm or method. Observe that the objects GE performs search on are the same as those used in genetic algorithms. This means, in principle, that any existing genetic algorithm package, such as the popular GAlib, can be used to carry out the search, and a developer implementing a GE system need only worry about carrying out the mapping from list of integers to program tree. It is also in principle possible to perform the search using some other method, such as particle swarm optimization (see the remark below); the modular nature of GE creates many opportunities for hybrids as the problem of interest to be solved dictates. Brabazon and O'Neill have successfully applied GE to predicting corporate bankruptcy, forecasting stock indices, bond credit ratings, and other financial applications. GE has also been used with a classic predator prey model to explore the impact of parameters such as predator efficiency, niche number, and random mutations on ecological stability. It is possible to structure a GE grammar that for a given function/terminal set is equivalent to genetic programming.

Критика

Несмотря на свои успехи, GE подвергалась некоторой критике. Одна из проблем заключается в том, что в результате операций картографирования генетические операторы GE не достигают высокой локальности, которая является высоко оцененным свойством генетических операторов в эволюционных алгоритмах.

Связанная работа

GE изначально была комбинацией линейного представления, используемого генетическим алгоритмом для разработки программного обеспечения (GADS) и грамматикой формы Backus Naur, которые первоначально использовались в GP на основе дерева Вонгом и Лёнг в 1995 году и Уигамом в 1996 году. Другие связанные работы, отмеченные в оригинальной статье GE, были Фредериком Груа, который использовал концептуально похожий "эмбриональный" подход, а также Келлера и Банжафа, которые аналогично использовали линейные геномы.

Реализация

Существует несколько вариантов реализации GE. К ним относятся следующие. +Название проектаЯзык ГодМестоположениеGELabMatlab2018https://github. com/adilraja/GELABPonyGE2Python2017https://arxiv. - Я не могу. - Я не могу. Проект. В этом случае, вы можете использовать только один из этих параметров. pdfPyNeurGenPython2012http://pyneurgen. Источник-подделка. net/Grammatical evolutionRuby2011http://www.grammaticalevolution.org/ умные алгоритмы. com/вдохновленная природой/эволюция/грамматическая эволюция. rbAGEC, Lua2011http://nohejl. name/age/pdf/AGE Документация 1.0.2. pdfPonyGEPython2010https://code. Гугл. - Я не могу. - Я не могу. В 2008 году в рамках программы "Глобальная стратегия развития" (ГРЭС) был создан проект "Глобальная стратегия развития" (ГРЭС). УКЗ. ie/Site/GEVA. htmlECJJava2008https://cs. ГМУ. edu/~eclab/projects/ecj/GENNC++2007https://ritchielab.org/ org/research/past research/52 грамматическая эволюция нейронных сетейlibGEC++, S Lang, tinycc2004http://bds. Ультразвуковые ie/libGE/

Ресурсы

Учебное пособие по грамматической эволюции. Грамматическая эволюция в Java jGE Java Grammatical Evolution. Группа биокомпьютерных и развивающихся систем (BDS) в Университете Лимерика. Страница "Грамматическая эволюция" Майкла О'Нилла, включая библиографию. DRP, Directed Ruby Programming, - это экспериментальная система, предназначенная для создания гибридных систем GE/GP. Он реализован в чистом Ruby. GERET, Грамматическая Эволюция Руби исследовательский набор инструментов. Grammatical Evolution for R. Грамматическая эволюция для R.