Genetic Quine

Genetic algorithm to write a quine.

Posted by dbunker on July 26, 2011

Have just come across an interesting fact from a NOVA documentary on evolution. Bacteria are among the few creatures that use a rotary motor, their bacterial flagellum, for propulsion. The comments about it in this documentary also point out one of the fundamental flaws in genetic algorithms. From the perspective of the genetic algorithm there is a point A which is bad and point B which is substantially better, however in order for the genetic algorithm to venture from point A to point B most of the steps along the way have to show improvement. It may happen that there was an in between stage that was useful, as evidence shows happened in the bacteria’s case, but that relies a lot on luck.

However, genetic algorithms still have the potential to create unique solutions to problems. For instance, a genetic algorithm could be set up that would, with a little luck, eventually write a quine in C. To set up the environment, start by cutting the size to 200 characters (27 letters + 10 numbers + 20 misc = 57 possible chars) which is 57^200 possible programs. Put another way, many times more than the number of atoms in the universe (a mere 10^82), though ideally quickly narrows this number. Breeding is done by sporadic character insertion of two programs.

Next, to set up the reward structure. If the breeding produces a program that compiles, points for that offspring, increasing its longevity. If it produces output, more points. And if it starts to produce output identical to the front of its output, many more points. Finally, if it produces the exact same output as itself, it wins and the algorithm completes.

It does of course matter greatly how the environment is set up, in particular the breeding and rewards system. Using a language which offers fewer characters and is more likely to produce compilable output also increases the chance of success.

DNA is particularly elegant because so much produces viable candidates (creatures), which is ideal in genetic algorithms. The genetic algorithms batches just do the best they can with the parameters they are given. Living creatures are the same.