# Programming a genetic algorithm with a non-fixed size

I am trying to write a genetic algorithm for a program. Most examples for genetic algorithms use something like this as the input:

aaaaaaaaaa


and mutate/crossover until they get

helloworld


or similar. This requires however that you start with something of length N, but my search space doesn't have a fixed length. How should I alter the mutation/crossover steps to allow for changes in unit size?

• "I am trying to write a genetic algorithm for a program." -- for what? – Raphael May 2 '14 at 21:25

There are plenty of possibilities:

• Add/remove a symbol at the end with probability $c$.
• Add/remove $k$ symbols at the end with probability $c \cdot 2^{-k}$.
• For every symbol, remove it with probability $c_1$;
for every gap, insert a symbol with probability $c_2$.
• For every symbol $a$, convert it to $a^k$ with probability $c \cdot 2^{-k-1}$.

And so on and so on. Basically, whatever works for you is good. Without any knowledge about the function you are trying to optimise, it is impossible to guess which strategies make more sense than others.

Another idea is to start with a very large genome, enough that it will cover any possible target. During evaluation you only check whether the start of your genome matches the target. For example, start with

aaaaaaaaaaaaaaaaaaaaaaaaaaa


end with

helloworldsdfkjiojerpweorke


As long as the first part matches we are happy and we ignore the junk in the end.