Shortest common supersequence with Genetic Algorithm 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?
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


fitness: $f(x) = \text{length}(x) - \text{superseq}(x, s_1) - \text{superseq}(x, s_2)$ (we want to minimize $f$)
mutation: $m(x) = \hat x$, where we obtain $\hat x$ from $x$ by randomly changing, deleting, or adding a character
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]. $$