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.

  • $\begingroup$ Yes, you are right. Sequences of moves, i.e. algorithm. I suggest you to read this site about GA, if you haven't already. $\endgroup$ – Eugene Zavidovsky Jul 20 '17 at 15:26

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.

  • $\begingroup$ This is an old question and answer, and, certainly, GP may solve the actual problem, but maybe you should have explained how exactly one could solve the specific problem. For example, how could one encode a solution/individual in the case of tree-based GP? In any case, of course, if you don't have time, you don't have to spend it on this old question (that probably everyone forgot about, apart from me, of course :P) $\endgroup$ – nbro Jan 19 at 18:47

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.