Грамматическая эволюция
Грамматическая эволюция (GE) — это эволюционные вычисления , а точнее, генетического программирования (GP), впервые предложенный Конором Райаном, Дж. Дж. Коллинзом и Майклом О'Нилом в 1998 году. метод (или подход) [1] в группе BDS в Университете Лимерика .
Как и в любом другом подходе GP, цель состоит в том, чтобы найти исполняемую программу, фрагмент программы или функцию, которая достигнет хорошего значения пригодности для данной целевой функции . В большинстве опубликованных работ по GP LISP непосредственно манипулируют выражениями с древовидной структурой в стиле , тогда как GE применяет генетические операторы к целочисленной строке, которая впоследствии отображается в программу (или аналогичную) с помощью грамматики, которая обычно выражается в виде Форма Бэкуса-Наура . Одним из преимуществ GE является то, что это отображение упрощает применение поиска к различным языкам программирования и другим структурам.
Проблема решена
[ редактировать ]без типов В обычном GP в стиле Koza набор функций должен соответствовать требованию замыкания: все функции должны быть способны принимать в качестве аргументов выходные данные всех других функций в наборе функций. Обычно это реализуется путем работы с одним типом данных, например с плавающей запятой двойной точности. Хотя современные структуры генетического программирования поддерживают типизацию, такие системы типов имеют ограничения, от которых не страдает грамматическая эволюция.
Решение GE
[ редактировать ]GE предлагает решение ограничения одного типа путем разработки решений в соответствии с заданной пользователем грамматикой (обычно грамматикой в форме Бэкуса-Наура ). Следовательно, пространство поиска может быть ограничено и могут быть включены знания предметной области проблемы. Вдохновением для такого подхода послужило желание отделить «генотип» от «фенотипа»: в ГП объекты, над которыми работает алгоритм поиска, и то, что интерпретирует функция оценки приспособленности, — одно и то же. Напротив, «генотипы» GE представляют собой упорядоченные списки целых чисел, которые кодируют правила выбора из предоставленной контекстно-свободной грамматики. Фенотип, однако, тот же, что и в GP в стиле Коза: древовидная структура, которая оценивается рекурсивно. Эта модель больше соответствует тому, как работает генетика в природе, где существует разделение между генотипом организма и окончательным выражением фенотипа в белках и т. д.
Разделение генотипа и фенотипа позволяет использовать модульный подход. В частности, поисковая часть парадигмы GE не обязательно должна выполняться каким-то одним конкретным алгоритмом или методом. Обратите внимание, что объекты, на которых GE выполняет поиск, такие же, как те, которые используются в генетических алгоритмах . В принципе это означает, что любой существующий пакет генетических алгоритмов, такой как популярный GAlib , может использоваться для выполнения поиска, и разработчику, реализующему систему GE, нужно только беспокоиться о выполнении сопоставления списка целых чисел с деревом программы. . Также в принципе возможно выполнить поиск, используя какой-либо другой метод, например, оптимизацию роя частиц (см. примечание ниже); Модульная природа GE создает множество возможностей для гибридов, как того требует проблема, которую необходимо решить.
Брабазон и О'Нил успешно применили GE для прогнозирования корпоративного банкротства, прогнозирования фондовых индексов, кредитных рейтингов облигаций и других финансовых приложений. [ нужна ссылка ] GE также использовался с классической моделью хищник-жертва для изучения влияния таких параметров, как эффективность хищника, количество ниш и случайные мутации, на экологическую стабильность . [2]
Можно структурировать GE-грамматику, которая для данного набора функций/терминалов будет эквивалентна генетическому программированию.
Критика
[ редактировать ]Несмотря на свои успехи, GE подверглась некоторой критике. Одна из проблем заключается в том, что в результате операции картирования генетические операторы GE не достигают высокой локальности. [3] [4] это высоко ценимое свойство генетических операторов в эволюционных алгоритмах. [3]
Варианты
[ редактировать ]Хотя изначально GE описывался с точки зрения использования эволюционного алгоритма, в частности генетического алгоритма, существуют и другие варианты. Например, исследователи GE экспериментировали с использованием оптимизации роя частиц для проведения поиска вместо генетических алгоритмов с результатами, сравнимыми с результатами обычного GE; это называется «грамматическим рой»; Используя только базовую модель PSO, было обнаружено, что PSO, вероятно, в равной степени способен выполнять процесс поиска в GE, как и простые генетические алгоритмы. (Хотя PSO обычно представляет собой парадигму поиска с плавающей запятой, ее можно дискретизировать, например, просто округляя каждый вектор до ближайшего целого числа, для использования с GE.)
Еще один возможный вариант, с которым экспериментировали в литературе, — это попытка закодировать семантическую информацию в грамматике, чтобы еще больше исказить процесс поиска. Другая работа показала, что при наличии предвзятых грамматик, использующих знания предметной области, даже случайный поиск может использоваться для стимулирования GE. [5]
Связанные работы
[ редактировать ]Изначально GE представлял собой комбинацию линейного представления, используемого в Генетическом алгоритме разработки программного обеспечения (GADS). [ нужна ссылка ] и грамматики Бэкуса Наура, которые первоначально использовались Вонгом и Люнгом в древовидных GP. [6] в 1995 году и Уигэм в 1996 году. [7] Другой родственной работой, отмеченной в оригинальной статье GE, была работа Фредерика Груау, [8] который использовал концептуально схожий «эмбриональный» подход, как и подход Келлера и Банцхафа, [9] которые аналогичным образом использовали линейные геномы.
Реализации
[ редактировать ]Существует несколько реализаций GE. К ним относятся следующие.
| Название проекта | Язык | Год | Расположение |
| ГЛОБАЛЬНЫЙ | Матлаб | 2018 | https://github.com/adilraja/GELAB |
| ПониGE2 | Питон | 2017 | https://arxiv.org/abs/1703.08535 |
| gramEvol | Р | 2016 | https://cran.r-project.org/web/packages/gramEvol/vignettes/ge-intro.pdf |
| PyNeurGen | Питон | 2012 | http://pyneurgen.sourceforge.net/ |
| Грамматическая_ эволюция | Руби | 2011 | http://www.cleveralgorithms.com/nature-inspired/evolution/grammatical_evolution.rb |
| ВОЗРАСТ | С, возьми это | 2011 | http://nohejl.name/age/pdf/AGE-Documentation-1.0.2.pdf |
| PonyGE | Питон | 2010 | https://code.google.com/archive/p/ponyge/downloads |
| Он носит | Руби | 2010 | https://github.com/bver/GERET/ |
| ГЕВА | Ява | 2008 | http://ncra.ucd.ie/Site/GEVA.html |
| Европейский суд | Ява | 2008 | https://cs.gmu.edu/~eclab/projects/ecj/ |
| ЯН | С++ | 2007 | https://ritchielab.org/research/past-research/52-grammatical-evolution-neural-networks |
| libGE | C++, S-Lang, tinycc | 2004 | http://bds.ul.ie/libGE/ |
См. также
[ редактировать ]- Генетическое программирование
- Грамматическая эволюция Java
- Декартово генетическое программирование
- Программирование экспрессии генов
- Линейное генетическое программирование
- Мультивыраженное программирование
Примечания
[ редактировать ]- ^ «Грамматическая эволюция: развивающиеся программы для произвольного языка» .
- ^ Альфонсека, Мануэль; Солер Хиль, Франсиско Хосе (2 января 2015 г.). «Развитие экосистемы математических выражений хищник-жертва с грамматической эволюцией». Сложность . 20 (3): 66–83. Бибкод : 2015Cmplx..20c..66A . дои : 10.1002/cplx.21507 . hdl : 10486/663611 .
- ^ Jump up to: а б Ротлауф, Франц; Эцель, Мари (2006). «О локальности грамматической эволюции» . Генетическое программирование . Конспекты лекций по информатике. Том. 3905. С. 320–330. дои : 10.1007/11729976_29 . ISBN 978-3-540-33143-8 .
- ^ «Публикация: Позиционный эффект кроссовера и мутации в грамматической эволюции - Школа вычислительной техники - Кентский университет» .
- ^ О'Салливан, Джон; Райан, Конор (2002), Фостер, Джеймс А.; Луттон, Эвелин; Миллер, Джулиан; Райан, Конор (ред.), «Исследование использования различных стратегий поиска с грамматической эволюцией» , Genetic Programming , vol. 2278, Берлин, Гейдельберг: Springer Berlin Heidelberg, стр. 268–277, doi : 10.1007/3-540-45984-7_26 , ISBN 978-3-540-43378-1 , получено 8 августа 2022 г.
- ^ Вонг, Ман Люн; Люн, Квонг Сак (ноябрь 1995 г.). «Применение логических грамматик для запуска подфункций в генетическом программировании» . Материалы Международной конференции IEEE 1995 года по эволюционным вычислениям . Том. 2. С. 737–740, т. 2. дои : 10.1109/ICEC.1995.487477 . ISBN 0-7803-2759-4 . S2CID 16071918 .
- ^ Уигэм, П. (1996). «Предвзятость поиска, языковая предвзятость и генетическое программирование». S2CID 16631215 .
{{cite web}}: Отсутствует или пусто|url=( помощь ) - ^ Груо, Фредерик (1994), Синтез нейронных сетей с использованием клеточного кодирования и генетического алгоритма , CiteSeerX 10.1.1.29.5939
- ^ Келлер, Роберт Э. (1996). «Генетическое программирование с использованием мутации, репродукции и картирования генотипа-фенотипа из линейных бинарных геномов в линейные фенотипы Lalr (1) Категория статьи: Генетическое программирование (gp)». S2CID 18095204 .
{{cite web}}: Отсутствует или пусто|url=( помощь )
Ресурсы
[ редактировать ]- Учебное пособие по грамматической эволюции .
- Грамматическая эволюция в Java. Архивировано 11 марта 2010 г. в Wayback Machine .
- jGE — Грамматическая эволюция Java .
- Группа биокомпьютерных систем и систем развития (BDS) в Университете Лимерика .
- Страница грамматической эволюции Майкла О'Нила , включая библиографию.
- DRP , Directed Ruby Programming, — это экспериментальная система, предназначенная для того, чтобы пользователи могли создавать гибридные системы GE/GP. Он реализован на чистом Ruby.
- ГЕРЕТ , Набор инструментов для исследования грамматической эволюции Ruby.
- gramEvol грамматическая эволюция R. ,