Разница между программированием генной экспрессии и декартовым генетическим программированием - PullRequest
12 голосов
/ 13 августа 2010

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

  1. (как) Это принципиально разные понятия?
  2. Я читал, что косвенное кодирование команд GP является эффективным методом (это делают и GEP, и CGP).Достигнут ли какой-то консенсус в отношении того, что косвенное кодирование устарело в классических древовидных базах GP?

Ответы [ 3 ]

7 голосов
/ 14 августа 2010

Ну, кажется, что есть некоторое различие между программированием генной экспрессии (GEP) и декартовым генетическим программированием (CGP или то, что я считаю классическим генетическим программированием), но разница может быть более раскрученной, чемэто действительно должно быть.Обратите внимание, что я никогда не использовал GEP, поэтому все мои комментарии основаны на моем опыте с CGP.

В CGP нет различия между генотипом и фенотипом, другими словами - если вы смотрите на"гены" CGP вы также смотрите на их выражение.Здесь нет кодировки, то есть дерево экспрессии - это сам ген.

В GEP генотип выражен в фенотипе, поэтому, если вы посмотрите на гены, вы не будете готовызнать, как будет выглядеть выражение.«Изобретатель» ГП, Кандида Феррейра, написала действительно хорошую статью , и есть другие ресурсы , которые пытаются дать краткий обзор всей концепции.

Ферриера говорит, что преимущества "очевидны", но я действительно не вижу ничего, что обязательно сделало бы GEP лучше, чем CGP.По-видимому, GEP является мультигенным, что означает, что в экспрессии признака (то есть дерева экспрессии) участвуют несколько генов.В любом случае, пригодность рассчитывается по выраженному дереву, так что не похоже, что GEP что-то делает для повышения пригодности.Автор утверждает, что GEP увеличивает скорость, с которой достигается пригодность (то есть за меньшее количество поколений), но, честно говоря, вы можете увидеть драматические сдвиги производительности по сравнению с CGP, просто имея другой алгоритм выбора, другую структуру турнира, разделяяпопуляция в племена, миграция образцов между племенами, в том числе разнообразие в приспособленности и т. д.

Выбор:

  • случайный
  • колесо рулетки
  • top-n
  • принять половину
  • и т. Д.

Частота турниров:

  • один раз за эпоху
  • один раз за каждый экземпляр данных
  • один раз за поколение.

Структура турнира:

  • Возьмите 3, убейте 1 и замените его на ребенка от двух других.
  • Сортировкавсе люди в турнире по фитнесу, убейте нижнюю половину и замените ее потомком верхней половины (где нижняя - худшая, а верхняя - лучшая)убить лишних людей.

Племена
Население может быть разделено на племена, которые эволюционируют независимо друг от друга:

  • Миграция-периодически отдельные лица из племени перемещаются в другое племя
  • Племена логически разделены, так что они похожи на свои собственные отдельные популяции, работающие в разных средах.

Пригодность разнообразия
Включите разнообразие в приспособленность, где вы подсчитываете, сколько людей имеют одинаковую ценность пригодности (таким образом, вероятно, имеют одинаковый фенотип), и уВы штрафуете их физическую форму пропорциональной ценностью: чем больше людей имеют одинаковую физическую ценность, тем больше штраф за них.Таким образом, образцы с уникальными фенотипами будут поощряться, поэтому застой населения будет намного меньше.

Это лишь некоторые из вещей, которые могут сильно повлиять на производительность CGP, и когда я говорю, я оченьЯ имею в виду, что это в том же порядке или выше, чем у Ферриеры.Так что, если бы Ферриера не слишком повозилась с этими идеями, она могла бы увидеть гораздо более медленную работу CGP ... особенно, если бы она ничего не сделала для борьбы со стагнацией.Поэтому я буду осторожен при чтении статистики производительности в GEP, потому что иногда люди не учитывают все имеющиеся «оптимизации».

2 голосов
/ 12 августа 2015

Кажется, в этих ответах есть некоторая путаница, которую необходимо уточнить.Картезианский GP отличается от классического GP (он же GP на основе дерева) и GEP.Несмотря на то, что они разделяют многие концепции и черпают вдохновение из одних и тех же биологических механизмов, репрезентация индивидуумов (решений) различна.

В CGP репрезентация (отображение между генотипом и фенотипом)косвенными, другими словами, не все гены в геноме CGP будут экспрессироваться в феноме (концепция также найдена в GEP и многих других).Генотипы могут быть закодированы в сетке или массиве узлов, и результирующий программный граф является выражением только активных узлов.

В GEP представление также является косвенным, и, аналогично, не всегены будут экспрессироваться в фенотипе.Представление в этом случае сильно отличается от treeGP или CGP, но генотипы также выражаются в дереве программ.На мой взгляд, GEP - более элегантное представление, более простое в реализации, но также страдающее от некоторых недостатков, таких как: вы должны найти подходящий размер хвоста и головы, который специфичен для проблемы, версия mnltigenic - это что-то вроде принудительного склеивания между деревьями выражений.и, наконец, он имеет слишком много раздувания .

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

2 голосов
/ 07 декабря 2010

В общем, GEP проще от GP. Допустим, вы разрешаете в своей программе следующие узлы: константы, переменные, +, -, *, /, if, ... Для каждого из таких узлов с GP вы должны создать следующие операции: - рандомизировать - мутировать - кроссовер - и, возможно, другие генетические операторы

В GEP для каждого из таких узлов требуется только одна операция: десериализация, которая принимает массив чисел (например, double в C или Java) и возвращает узел. Он напоминает десериализацию объектов в таких языках, как Java или Python (разница состоит в том, что десериализация в языках программирования использует байтовые массивы, где здесь у нас есть массивы чисел). Даже эта операция «десериализации» не должна быть реализована программистом: она может быть реализована с помощью универсального алгоритма, как это делается в десериализации Java или Python.

Эта простота с одной точки зрения может сделать поиск лучшего решения менее успешным, но с другой стороны: требует меньше работы от программиста, и более простые алгоритмы могут выполняться быстрее (легче оптимизировать, больше кода и данных помещается в кэш ЦП, и скоро). Поэтому я бы сказал, что GEP немного лучше, но, конечно, определенный ответ зависит от проблемы, и для многих проблем может быть верно обратное.

...