我正在尝试使用随机二叉树实现遗传编程。这本质上是一个解析树，包含一组特殊的操作符，包括：and、>、<。请注意，在我的实现中，我只是在比较数字。因此，很明显，在给定的最大深度下，叶节点不能是操作符。我正在寻找关于这种实现类型所涉及规则的参考资料。我可以提出一些规则，但我想验证我的逻辑是否正确，以便将来在添加更多复杂的操作符时，能够设计一个易于更改的类结构。

一些规则：

给定最大深度为N，在深度N处必须是数字。根节点不能是数字。根节点必须是操作符。如果一个节点的父节点不是and操作符，则当前节点不能是and操作符。

回答：

纯粹形式的遗传编程使用一组非终结符（NTs）和终结符（Ts）。NTs通常是操作符、函数等，而Ts通常是变量、常量，或者可以看作是零元函数。在进行交叉操作时，你在每个父节点中选择一个子树并交换它们。在进行变异操作时，你删除一个子树并生成一个随机子树（深度有限）。在生成树时（无论是在初始化阶段还是在变异中），你有一些深度限制。在达到这个限制之前，你可以放置来自NTs和Ts的节点。当达到限制时，你只能放置来自Ts的节点。

纯粹的GP还要求闭包属性：任何非终结符必须接受任何非终结符或终结符作为其任何子节点。这在你的案例中似乎不成立：例如，and对两个数字没有意义。

我建议你看看强类型GP。它基本上是带有非终结符子节点类型约束和非终结符及终结符输出类型信息的GP。在你的案例中，例如，你的操作符<将要求其子节点为数值类型，其输出类型为布尔类型。

另一种可能性是语法进化。这是我最喜欢的一种，因为它通过仅修改语法就具有巨大的灵活性。它采用了与（ST）GP完全不同的方法，并且可以编码相同的要求（甚至更多）。它使用线性变长基因组，通过Backus-Naur形式的上下文无关语法翻译成程序。语法是定义你的解决方案结构的唯一东西。在你的案例中，语法可能看起来像

<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算法。如果你唯一的深度相关约束是最大解决方案深度，那么可以通过为违反此约束的解决方案分配最差的适应度（或只是惩罚）来轻松建模。

像这样的约束

如果一个节点的父节点不是“and”操作符，则当前节点不能是“and”操作符。

是可以实现的，但你将不得不使用自定义的交叉和变异操作符来检查约束（如果你打算使用（ST）GP类似的方法），或者，在GE的情况下，你可以更详细地定义语法，以便它不会产生这样的解决方案。该约束的示例可能是：

<bool-expr> ::= <and-expr>              | <not-expr>              | <or-expr># <not-expr>不是“and”，所以它的子节点可以是<or-expr>或<not-expr><not-expr> ::= not <or-expr>             | not <not-expr># 对于<or-expr>也是如此，但你必须写下所有组合<or-expr> ::= <not-expr> or <not-expr>            | <not-expr> or <or-expr>            | <or-expr> or <not-expr>            | <or-expr> or <or-expr>