0
$\begingroup$

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?

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

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.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.