Семантика генетического программирования

Генетическое программирование в чистом виде работает с набором нетерминалов (НТ) и терминалов (Т). NT обычно являются операторами, функциями и т. д., в то время как T обычно являются переменными, константами, или вы можете рассматривать их как функции с нулевой арностью. Когда вы выполняете кроссовер, вы выбираете поддерево в каждом родительском элементе и переключаете их. Когда вы выполняете мутацию, вы удаляете поддерево и генерируете случайное (с ограниченной глубиной). При создании дерева (либо на этапе инициализации, либо при мутации) у вас есть некоторый предел глубины. Пока этот предел не достигнут, вы ставите узлы как из NT, так и из T. Когда вы достигаете предела, вы ставите узлы только из Ts.

Чистый GP также требует свойства замыкания: любой нетерминал должен принимать любой нетерминал или терминал в качестве любого из своих потомков. Кажется, это не относится к вашему случаю: например, and не имеет смысла для двух чисел.

Я предлагаю вам взглянуть на ГП со строгой типизацией. По сути, это GP с ограничениями типов для дочерних элементов нетерминалов и информацией о типах выходных данных нетерминалов и терминалов. В вашем случае, например, ваш оператор < потребует, чтобы его дочерние элементы имели числовой тип, а его тип вывода был бы логическим.

Другой вариант — Грамматическая эволюция. Это мой любимый из-за его огромной гибкости за счет простого изменения грамматики. Он использует совершенно другой подход, чем (ST)GP, и может кодировать идентичные требования (и даже больше). Он работает с линейными геномами переменной длины, которые транслируются в программы с использованием контекстно-свободной грамматики в форме Бэкуса-Наура. Грамматика — это единственное, что определяет структуру вашего решения. В вашем случае грамматика может выглядеть так

<expr> ::= <bool-expr>
         | <num-expr>
<bool-expr> ::= (<num-expr> > <num-expr>)
              | (<num-expr> < <num-expr>)
              | (<bool-expr> and <bool-expr>)
<num-expr> ::= ...

с <expr> в качестве начального символа.

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

Ограничения, такие как

Если родитель узла не является оператором «и», текущий узел не может быть оператором «и».

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

<bool-expr> ::= <and-expr>
              | <not-expr>
              | <or-expr>
# <not-expr> is not "and" so its child can be <or-expr> or <not-expr>
<not-expr> ::= not <or-expr>
             | not <not-expr>
# the same for the <or-expr> but you have to write down all the combinations
<or-expr> ::= <not-expr> or <not-expr>
            | <not-expr> or <or-expr>
            | <or-expr> or <not-expr>
            | <or-expr> or <or-expr>