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

Question

I'm writing a genetic algorithm to find an expression that expresses a target number, i.e. if the target number is 10 a solution would be 2*5. For now I'm using fixed size chromosomes and I want to change it to random length but only after I will find a way to perform crossover.

The following are possible chromosomes, obeying the rules that numbers and operators appears in the string alternately, in a way that no two digits or two operators are adjacent. A legal string would start with a digit or +/- operators. The expression would be calculated from left to right as-is (ignoring the order of arithmetic operations):

• 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

Trying to implement a crossover I have tried the following (in pseudo-code):

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

But the function isn't working as expected, it sometimes takes too much time to find the right locus. I must find a way to make the crossover work with random sized chromosomes but I can't figure how (and of course make sure there's no division by zero).

Answer 1

Long processing time is most probably because of small probability of an event that two chromosomes have different types (operator or digit) of characters on the same position. Note that for 1 digit numbers two chromosomes will always have the same type on the same position. The solution is to find splitting points in each chromosome separately:

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

The consequence is of course that you'll have four possible results, not two. You can use all, or ignore half of them.

Another fix is to first enumerate all possible splitting points:

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

If you have always only 1-digit numbers, then the algorithm for enumerating possible loci is even easier, because it will always return all possible pairs when one index is even and the other odd, and vice-versa.