Shortest common supersequence with Genetic Algorithm

Question

I'm trying to solve the shortest common supersequence with Genetic Algorithm. I found it a little bit hard to reduce the size of the chromosomes in each generation.

I know that the maximum size of the chromosome is the total length of the strings. Even if we create a "naive" genetic algorithm: Totally random strings (with different length) as initial population, mutation that replace a character, fitness that return how much strings that chromosome contains etc. How the crossover can reduce the size of the chromosome length? If we choose n-points crossover, the length of the children cannot be smaller than the shorter parent.

So how genetic algorithm can solve such problems that need the shortest chromosome length? How crossover can reduce the chromosome length?

Answer 1

As is usual, you will really have to think for yourself what makes sense for the crossover function. But here is the naive approach (without really knowing your problem).

Let $s_1$ and $s_2$ be the strings you want to find the shortest common supersequence for. Let $\text{superseq}(x, s_1)$ be the number of characters in $x$ that form a supersequence.

For individuals $x$, $x'$, define

1. fitness: $f(x) = \text{length}(x) - \text{superseq}(x, s_1) - \text{superseq}(x, s_2)$ (we want to minimize $f$)
2. mutation: $m(x) = \hat x$, where we obtain $\hat x$ from $x$ by randomly changing, deleting, or adding a character
3. crossover: $c(x, x') = x[i, j] + x'[i', j']$ for randomly drawn $i \leq j$, $i' \leq j'$.

In other words, the crossover simply picks a random (consecutive) substring of each of the individuals and concatenates it to make a new. There are many more options, you can pick a string smarter (keeping only certain missing characters), you can interleave the strings, e.g. shuffle the string $\chi = 0^{\text{length(x)}}1^{\text{lenth(x')}}$ and let the result of the crossover be

$$ \left[ x[i] \text{ if } \chi_i = 0 \text{ else } x'[i] \text{ for } i \in \text{range}(\text{length}(\chi) \right]. $$