遗传编程语义
Genetic Programming Semantics
我正在尝试使用随机二叉树实现遗传编程。它本质上是一个具有特殊运算符子集的解析树，包括：and、>、<。请注意，在我的实现中，我只是比较数字。因此很明显，给定某个预定义的最大深度，叶节点不能成为运算符。我正在寻找有关此类实施所涉及规则的一些参考资料。我可以想出一些，但想验证我的逻辑是否正确，以便将来当我添加更多更复杂的运算符时，我可以设计一个易于更改的 class 结构。
一些规则：
给定最大深度N，在深度N处，它必须是数字。根节点不能是数字。根节点必须是运算符。如果节点的父节点不是 and 运算符，则当前节点不能是 and 运算符。
纯粹形式的遗传编程与一组非终端（NT）和终端（Ts）一起工作。 NT 通常是运算符、函数等，而 T 通常是变量、常量，或者您可以将它们视为 zero-arity 函数。当你进行交叉时，你在每个 parent 中选择一个子树并切换它们。当你进行变异时，你会删除一个子树并生成一个随机的子树（深度有限）。生成树时（无论是在初始化阶段还是在变异中），您都有一些深度限制。在达到此限制之前，您将同时放置来自 NT 和 T 的节点。当你达到限制时，你只放置来自 Ts 的节点。
纯 GP 还需要 闭包 属性：任何非终结符必须接受任何非终结符或终结符作为其 children。这似乎不适用于您的情况：例如，and 对两个数字没有意义。
我建议你看看Strongly Typed GP。它基本上是一个 GP，对非终端的 children 以及非终端和终端输出的类型信息具有类型约束。例如，在您的情况下，您的运算符 < 将要求其 children 为数字类型，其输出类型为布尔值。
另一种可能性是Grammatical Evolution。它是我最喜欢的一个，因为它仅通过修改语法就具有巨大的灵活性。它采用与 (ST)GP 完全不同的方法，并且可以编码相同的要求（甚至更多）。它使用线性 variable-length 基因组，这些基因组使用 Backus-Naur 形式的 context-free 语法翻译成程序。语法是唯一定义解决方案结构的东西。在你的情况下，语法可能看起来像
<expr> ::= <bool-expr>
| <num-expr>
<bool-expr> ::= (<num-expr> > <num-expr>)
| (<num-expr> < <num-expr>)
| (<bool-expr> and <bool-expr>)
<num-expr> ::= ...
以<expr>作为开始符号。
关于depth-related规则，这个在GP中用的不多。唯一 depth-related 的事情是初始化过程（你必须以某种方式限制解决方案的大小）和膨胀控制（你想要比大解决方案更小的解决方案）。我没有遇到任何基于深度的结构约束的 GP 算法。如果您唯一的 depth-related 约束是最大解决方案深度，那么可以通过将最差适应性（或只是惩罚）分配给违反此约束的解决方案来轻松建模。
类似
的约束
If the parent of a node is not an "and" operator, the current node cannot be an "and" operator.
是可行的，但您要么必须使用自定义交叉和变异运算符来检查约束（如果您要使用 (ST)GP-like 方法），或者在这种情况下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>
我正在尝试使用随机二叉树实现遗传编程。它本质上是一个具有特殊运算符子集的解析树，包括：and、>、<。请注意，在我的实现中，我只是比较数字。因此很明显，给定某个预定义的最大深度，叶节点不能成为运算符。我正在寻找有关此类实施所涉及规则的一些参考资料。我可以想出一些，但想验证我的逻辑是否正确，以便将来当我添加更多更复杂的运算符时，我可以设计一个易于更改的 class 结构。
一些规则：
给定最大深度N，在深度N处，它必须是数字。根节点不能是数字。根节点必须是运算符。如果节点的父节点不是 and 运算符，则当前节点不能是 and 运算符。
纯粹形式的遗传编程与一组非终端（NT）和终端（Ts）一起工作。 NT 通常是运算符、函数等，而 T 通常是变量、常量，或者您可以将它们视为 zero-arity 函数。当你进行交叉时，你在每个 parent 中选择一个子树并切换它们。当你进行变异时，你会删除一个子树并生成一个随机的子树（深度有限）。生成树时（无论是在初始化阶段还是在变异中），您都有一些深度限制。在达到此限制之前，您将同时放置来自 NT 和 T 的节点。当你达到限制时，你只放置来自 Ts 的节点。
纯 GP 还需要 闭包 属性：任何非终结符必须接受任何非终结符或终结符作为其 children。这似乎不适用于您的情况：例如，and 对两个数字没有意义。
我建议你看看Strongly Typed GP。它基本上是一个 GP，对非终端的 children 以及非终端和终端输出的类型信息具有类型约束。例如，在您的情况下，您的运算符 < 将要求其 children 为数字类型，其输出类型为布尔值。
另一种可能性是Grammatical Evolution。它是我最喜欢的一个，因为它仅通过修改语法就具有巨大的灵活性。它采用与 (ST)GP 完全不同的方法，并且可以编码相同的要求（甚至更多）。它使用线性 variable-length 基因组，这些基因组使用 Backus-Naur 形式的 context-free 语法翻译成程序。语法是唯一定义解决方案结构的东西。在你的情况下，语法可能看起来像
<expr> ::= <bool-expr>
| <num-expr>
<bool-expr> ::= (<num-expr> > <num-expr>)
| (<num-expr> < <num-expr>)
| (<bool-expr> and <bool-expr>)
<num-expr> ::= ...
以<expr>作为开始符号。
关于depth-related规则，这个在GP中用的不多。唯一 depth-related 的事情是初始化过程（你必须以某种方式限制解决方案的大小）和膨胀控制（你想要比大解决方案更小的解决方案）。我没有遇到任何基于深度的结构约束的 GP 算法。如果您唯一的 depth-related 约束是最大解决方案深度，那么可以通过将最差适应性（或只是惩罚）分配给违反此约束的解决方案来轻松建模。
类似
的约束If the parent of a node is not an "and" operator, the current node cannot be an "and" operator.
是可行的，但您要么必须使用自定义交叉和变异运算符来检查约束（如果您要使用 (ST)GP-like 方法），或者在这种情况下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>