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

Часть серия на
Эволюционный алгоритм
Генетический алгоритм
Генетическое программирование

Грамматическая эволюция является эволюционные вычисления техника, впервые примененная Конором Райаном, Дж. Дж. Коллинзом и Майклом О'Нилом в 1998 году.[1] на БДС Группа в Лимерикский университет.

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

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

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

Решение GE

GE предлагает решение этой[который? ] проблема путем развития решений в соответствии с заданной пользователем грамматикой (обычно грамматика в Форма Бэкуса-Наура ). Следовательно, пространство поиска может быть ограничено, а знания предметной области могут быть включены. Источником вдохновения для этого подхода является желание отделить «генотип» от «фенотипа»: в GP объекты, с которыми работает алгоритм поиска, и то, что интерпретирует функция оценки пригодности, являются одними и теми же. Напротив, «генотипы» GE - это упорядоченные списки целых чисел, которые содержат код для выбора правил из предоставленной контекстно-свободной грамматики. Фенотип, однако, тот же, что и у GP в стиле Коза: древовидная структура, которая оценивается рекурсивно. Эта модель больше соответствует тому, как генетика работает в природе, где существует разделение между генотипом организма и конечным проявлением фенотипа в белках и т. Д.

Разделение генотипа и фенотипа позволяет использовать модульный подход. В частности, поисковая часть парадигмы GE не должна выполняться каким-либо одним конкретным алгоритмом или методом. Обратите внимание, что объекты, которые GE выполняет поиск, совпадают с объектами, используемыми в генетические алгоритмы. В принципе это означает, что любой существующий пакет генетических алгоритмов, например популярный GAlib, может использоваться для выполнения поиска, и разработчику, реализующему систему GE, нужно только беспокоиться о выполнении отображения из списка целых чисел в дерево программы. Также в принципе возможно выполнить поиск каким-либо другим методом, например оптимизация роя частиц (см. замечание ниже); Модульная природа GE создает много возможностей для гибридов, поскольку того требует решение интересующей проблемы.

Брабазон и О'Нил успешно применили GE для прогнозирования корпоративного банкротства, прогнозирования фондовых индексов, кредитные рейтинги облигаций и другие финансовые приложения.[нужна цитата ] GE также использовался с классическим модель хищник-жертва изучить влияние таких параметров, как эффективность хищников, количество ниш и случайные мутации, на экологическая стабильность.[2]

Можно структурировать грамматику GE, которая для данной функции / терминального набора эквивалентна генетическому программированию.

Критика

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

Варианты

Несмотря на то, что GE довольно новый, существуют уже улучшенные версии и варианты, которые были разработаны. Исследователи GE экспериментировали с использованием оптимизация роя частиц проводить поиск вместо генетических алгоритмов с результатами, сопоставимыми с результатами обычного GE; это упоминается как «грамматический рой»; Используя только базовую модель PSO, было обнаружено, что PSO, вероятно, в равной степени способна выполнять процесс поиска в GE, как и простые генетические алгоритмы. (Хотя PSO обычно представляет собой парадигму поиска с плавающей запятой, ее можно дискретизировать, например, просто округляя каждый вектор до ближайшего целого числа для использования с GE.)

Еще один возможный вариант, с которым экспериментировали в литературе, - это попытка закодировать семантическую информацию в грамматике, чтобы еще больше повлиять на процесс поиска.

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

Примечания

  1. ^ http://www.cs.bham.ac.uk/~wbl/biblio/gp-html/ryan_1998_geepal.html
  2. ^ Альфонсека, Мануэль; Солер Хиль, Франсиско Хосе (2 января 2015 г.). «Развитие экосистемы математических выражений хищник-жертва с грамматической эволюцией». Сложность. 20 (3): 66–83. Дои:10.1002 / cplx.21507. HDL:10486/663611.
  3. ^ а б DOI.org
  4. ^ http://www.cs.kent.ac.uk/pubs/2010/3004/index.html

Ресурсы