2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ OK, FWIW, I edited this a bit to distil it down to what I think is the core question, which is how to represent the "chromosome". If one can figure that out, the mechanics of evolving a population are well documented elsewhere. It is an interesting question, although I will say that at first blush I'm not actually sure that GA's are a good approach to this problem. I'm hoping somebody will come along and show that I'm wrong in thinking so. $\endgroup$ – mindcrime Jul 20 '17 at 0:13
  • $\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
1
$\begingroup$

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.

| 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.