我正在编写一个遗传算法，用于寻找一个能表示目标数字的表达式。例如，如果目标数字是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)        locus = 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

但是这个函数没有按预期工作，有时找到合适的交叉点需要太长时间。我必须找到一种方法，使交叉操作能够处理随机大小的染色体，但我不知道该怎么做（当然还要确保没有除以零的情况）。

回答：

处理时间过长的主要原因可能是两个染色体在相同位置上具有不同类型（操作符或数字）字符的概率较小。请注意，对于单数字，两个染色体在相同位置上的类型将总是相同的。解决方案是在每个染色体中单独寻找分割点：

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

如果你的数字总是只有一个数字，那么枚举可能的分割点的算法会更加简单，因为它将始终返回所有可能的对，其中一个索引是偶数，另一个是奇数，反之亦然。