Грамматическая эволюция (GE) — это эволюционные вычисления и, более конкретно, метод (или подход) генетического программирования (GP), впервые предложенный Конором Райаном, Дж. Дж. Коллинзом и Майклом О'Нилом в 1998 году [1] в группе BDS в Университете штата Калифорния. Лимерик .
Как и в любом другом подходе GP, цель состоит в том, чтобы найти исполняемую программу, фрагмент программы или функцию, которая достигнет хорошего значения пригодности для данной целевой функции . В большинстве опубликованных работ по GP непосредственно манипулируют выражениями с древовидной структурой в стиле LISP , тогда как GE применяет генетические операторы к целочисленной строке, которая впоследствии отображается в программе (или аналогичной) с помощью грамматики, которая обычно выражается в виде Форма Бэкуса-Наура . Одним из преимуществ GE является то, что это отображение упрощает применение поиска к различным языкам программирования и другим структурам.
В обычном GP в стиле Koza без типов набор функций должен соответствовать требованию замыкания: все функции должны иметь возможность принимать в качестве аргументов выходные данные всех других функций в наборе функций. Обычно это реализуется путем работы с одним типом данных, например с плавающей запятой двойной точности. Хотя современные структуры генетического программирования поддерживают типизацию, такие системы типов имеют ограничения, от которых не страдает грамматическая эволюция.
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. К ним относятся следующие.
{{cite web}}
: Отсутствует или пусто |url=
( помощь ){{cite web}}
: Отсутствует или пусто |url=
( помощь )