How can one use Genetic Algorithms to solve the "15 Puzzle" (Mystic Square)?

Question

How would one go about solving the 15 squares puzzle using a Genetic Algorithms approach? In particular, I'd like to understand how you would represent the "chromosome" in the evolving system. That is, what's the relationship between the (artificial) "genes" and some sort of phenotypical expression w/r/t the problem. It seems like genes would somehow represent moves or sequences of moves but I'm not entirely clear how this would work.

Answer 1

There are a few ways of handling this within GA's, but most of them actually amount to using some kind of Genetic Programming instead.

The simplest way, and most similar to what you've proposed is called linear genetic programming. In this representation, you break the genome into a set of equal-width pieces. Each piece is interpreted as a machine-language instruction for a virtual machine. In your case, plausible instructions might be "move left" or "move right". Most versions use variable-length genomes, so your program's length depends only on how many instructions there are.

Another approach is to use the standard LISP-like genetic programming system, which Koza documents in his book for other simple problems, like the Santa Fe Trail.

More complex encodings are also possible. Grammatical evolution is another one that is similar to a GA in spirit, but interprets a genome according to a CFG instead of as instructions to a virtual machine.