stringtranslate.com

Грамматическая эволюция

Грамматическая эволюция (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. К ним относятся следующие.

Смотрите также

Примечания

  1. ^ «Грамматическая эволюция: развитие программ для произвольного языка».
  2. ^ Альфонсека, Мануэль; Солер Хиль, Франсиско Хосе (2 января 2015 г.). «Развитие экосистемы математических выражений хищник-жертва с грамматической эволюцией». Сложность . 20 (3): 66–83. Бибкод : 2015Cmplx..20c..66A. дои : 10.1002/cplx.21507. hdl : 10486/663611 .
  3. ^ ab DOI.org
  4. ^ «Публикация: Позиционный эффект кроссовера и мутации в грамматической эволюции - Школа вычислительной техники - Кентский университет» .
  5. ^ О'Салливан, Джон; Райан, Конор (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 г.
  6. ^ Вонг, Ман Люн; Люн, Квонг Сак (ноябрь 1995 г.). «Применение логических грамматик для запуска подфункций в генетическом программировании». Материалы Международной конференции IEEE 1995 года по эволюционным вычислениям . Том. 2. С. 737–740, т. 2. дои : 10.1109/ICEC.1995.487477. ISBN 0-7803-2759-4. S2CID  16071918.
  7. ^ Уигэм, П. (1996). «Предвзятость поиска, языковая предвзятость и генетическое программирование». S2CID  16631215. {{cite web}}: Отсутствует или пусто |url=( помощь )
  8. ^ Груо, Фредерик (1994), Синтез нейронных сетей с использованием клеточного кодирования и генетического алгоритма , CiteSeerX 10.1.1.29.5939 
  9. ^ Келлер, Роберт Э. (1996). «Генетическое программирование с использованием мутации, репродукции и картирования генотипа-фенотипа из линейных бинарных геномов в линейные фенотипы Lalr (1) Категория статьи: Генетическое программирование (gp)». S2CID  18095204. {{cite web}}: Отсутствует или пусто |url=( помощь )

Ресурсы