在遗传编程中对AST进行交叉操作 [英] Perform crossover operation on AST in genetic programming

问题描述

因此，一般情况下，当您在GA中执行交叉时，直接翻转基因组中的随机部分，并在另一个父级中使用相应的部分，并根据突变率对其进行变异。



请考虑以下序列：

So in general when you perform a crossover in GA, you directly flip a random section in the "genome", with the corresponding section in the other parent, and mutate it based on the mutation rate.

Consider the sequences below:

0100 1000 0001 1011

0010 0110 1101 1111

没有任何突变的交叉可能如下所示：

A crossover without any mutation might look like this:

0100 0110 1101 1011

0010 1000 0001 1111

在这种情况下，第2和第3块被交换，第1和第4块保持不变。



我不确定如何在GP中使用抽象语法树，但是，因为无法保证在第一个父项中引用的抽象树中的点将与来自第二个父级的部分，例如，一个部分可能具有返回类型boolean而另一个部分具有返回类型的字符串，例如下面的示例：

In that case, blocks 2 and 3 were swapped and blocks 1 and 4 remained unchanged.

I'm unsure how that would work in GP with abstract syntax trees however, because there is no guarantee that the point in the abstract tree you reference in the first parent will be compatible with the section from the second parent, for example one section might have a return type of boolean while the other has a return type of string, such as in the example below:

    p1
   /  \
  b    i
 /\   /\
b  f i  s

    p2
   /  \
  s    b
 /\   /\
i  n s  i

如果您尝试交叉分支1来自父级1的返回类型为b，父级2的分支1的返回类型为s，如果要运行它会产生语法错误，那么如何才能正确执行AST的交叉，具体如何例子将不胜感激。



我尝试过：



我我已经对这个主题进行了一些研究，但从我所知道的算法中我发现假设返回类型之间的一致性。

if you were to try to crossover branch 1 from parent 1 which has a return type of b, with branch 1 from parent 2 which has a return type of s, it would create a syntax error if it were to be ran, so how would I correctly perform a crossover on an AST, specific examples would be appreciated.

What I have tried:

I have done some research on the subject but from what I can tell the algorithms I have found assume uniformity among return types.

推荐答案

在越过之前，检查它们的返回类型。如果返回类型不具有可比性，请选择另一条染色体。你应该有很多人可以选择。

Before crossing over, check their return types. If the return types are not comparable, pick another chromosome. You should have a large population to pick from.

这篇关于在遗传编程中对AST进行交叉操作的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！