在 GA 中执行依赖项交叉的好方法是什么？

Question

我正在编写一个遗传算法来寻找表达目标数字的表达式，即如果目标数字是 10，则解决方案将是 2*5。现在我正在使用固定大小的染色体，我想将其更改为随机长度，但只有在我找到执行交叉的方法之后。

以下是可能的染色体，遵守数字和运算符交替出现在字符串中的规则，任何两个数字或两个运算符都不相邻。合法的字符串将以数字或 +/- 运算符开头。表达式将按原样从左到右计算（忽略算术运算的顺序）：

1/2+3+5
-2+4+1+8
-7+6*2+8
+2/5-1+8 2+1*2-2
+2*7*7+3
+1/2/2/6 5/5*9*1
+3-1+1*8 3-8+7*1

尝试实现交叉我尝试了以下（伪代码）：

crossover(chrom-a, chrom-b):
    min_length = min(length(chrom-a), length(chrom-b))
    locus = random(1, min_length-1)

    while (chrom-a[locus] & chrom-b[locus] aren't both digit or operator)
        ocus = random(1, min_length-1)

    chrom-a = chrom-a[:locus] + chrom-b[locus:]
    chrom-b = chrom-b[:locus] + chrom-a[locus:]

    return chrom-a, chrom-b

但是这个功能并没有像预期的那样工作，有时需要花费太多时间才能找到正确的位点。我必须找到一种方法使交叉与随机大小的染色体一起工作，但我不知道如何（当然要确保没有被零除）。

Answer 1

处理时间长很可能是因为两条染色体在同一位置上具有不同类型（运算符或数字）字符的事件的概率很小。请注意，对于 1 位数字，两条染色体将始终在同一位置具有相同的类型。解决方法是分别在每条染色体上寻找分裂点：

find_loci(chrom-a, chrom-b):
    return pair(random(1, length(chrom-a)-1), random(1, length(chrom-b)-1))

crossover(chrom-a, chrom-b):
    locus-a, locus-b = find_loci(chrom-a, chrom-b)

while (chrom-a[locus-a] & chrom-b[locus-b] aren't both digit or operator)
    locus-a, locus-b = find_loci(chrom-a, chrom-b)

chrom-a = chrom-a[:locus-a] + chrom-b[locus-b:]
chrom-b = chrom-b[:locus-a] + chrom-a[:locus-b]
chrom-c = chrom-a[locus-a:] + chrom-b[locus-b:]
chrom-d = chrom-b[locus-a:] + chrom-a[:locus-b]

return chrom-a, chrom-b, chrom-c, chrom-d

结果当然是您将有四种可能的结果，而不是两种。您可以全部使用，也可以忽略一半。

另一个解决方法是先枚举所有可能的分裂点：

enumerate_possible_loci(chrom-a, chrom-b):
    for all indexes i in (1, chrom-a):
        for all indexes j in (1, chrom-b):
            if type(chrom-a[i]) != type(chrom-b[j]):
                yield return pair(i, j)

crossover(chrom-a, chrom-b):
   possible_loci = enumerate_possible_loci(chrom-a, chrom-b)
   locus_pair = possible_loci[random(0, length(possible_loci) - 1)]

   locus-a = locus_pair[0]
   locus-b = locus_pair[1]

    chrom-a = chrom-a[:locus-a] + chrom-b[locus-b:]
    chrom-b = chrom-b[:locus-a] + chrom-a[:locus-b]
    chrom-c = chrom-a[locus-a:] + chrom-b[locus-b:]
    chrom-d = chrom-b[locus-a:] + chrom-a[:locus-b]

    return chrom-a, chrom-b, chrom-c, chrom-d

如果你总是只有 1 位数字，那么枚举可能位点的算法就更简单了，因为当一个索引为偶数而另一个为奇数时，它总是 return 所有可能的对，反之亦然-相反。

在 GA 中执行依赖项交叉的好方法是什么？

What would be a good way to perform crossover with dependencies in GA?

algorithm

artificial-intelligence

arithmetic-expressions

genetic-algorithm