Answers.Body: <p>There are a few ways of handling this within GA's, but most of them actually amount to using some kind of <a href="https://en.wikipedia.org/wiki/Genetic_programming" rel="nofollow noreferrer">Genetic Programming</a> instead.</p>
  
  <p>The simplest way, and most similar to what you've proposed is called <a href="https://en.wikipedia.org/wiki/Linear_genetic_programming" rel="nofollow noreferrer">linear genetic programming</a>. 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.</p>
  
  <p>Another approach is to use the standard LISP-like genetic programming system, which Koza documents in <a href="http://www.genetic-programming.org/gpbook1toc.html" rel="nofollow noreferrer">his book</a> for other simple problems, like the <a href="https://en.wikipedia.org/wiki/Santa_Fe_Trail_problem" rel="nofollow noreferrer">Santa Fe Trail</a>. </p>
  
  <p>More complex encodings are also possible. <a href="https://en.wikipedia.org/wiki/Grammatical_evolution" rel="nofollow noreferrer">Grammatical evolution</a> 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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-19T18:47:40.930Z
Answers.Text: 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)
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-08-08T16:33:19.103Z
Answers.LastActivityDate: 2018-08-08T16:33:19.103Z
Answers.UserDisplayName: John Doucette
Body: <p>How would one go about solving the <a href="https://en.wikipedia.org/wiki/15_puzzle" rel="nofollow noreferrer">15 squares puzzle</a> using a <a href="https://en.wikipedia.org/wiki/Genetic_algorithm" rel="nofollow noreferrer">Genetic Algorithms</a> 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 <a href="https://pdfs.semanticscholar.org/6f25/ac7608edfa5efe7d13e05f38abb171490676.pdf" rel="nofollow noreferrer">phenotypical expression</a> 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.</p>
  
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-07-20T15:26:33.547Z
Comments.Text: Yes, you are right. Sequences of moves, i.e. algorithm. I suggest you to read [this site](http://www.genetic-programming.org/gpbook4toc.html) about GA, if you haven't already.
Comments.UserDisplayName: Eugene Zavidovsky
Tags: <genetic-algorithms><evolutionary-algorithms><genetic-programming>
Title: How can one use Genetic Algorithms to solve the "15 Puzzle" (Mystic Square)?
UserDisplayName: Ahmad Kandil
ThreadText: # How can one use Genetic Algorithms to solve the "15 Puzzle" (Mystic Square)?
  
  (Asked by: username_0 on 2017-07-19)
  
  How would one go about solving the [15 squares puzzle](https://en.wikipedia.org/wiki/15_puzzle) using a [Genetic Algorithms](https://en.wikipedia.org/wiki/Genetic_algorithm) 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](https://pdfs.semanticscholar.org/6f25/ac7608edfa5efe7d13e05f38abb171490676.pdf) 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.
  
  **Tags:** genetic-algorithms, evolutionary-algorithms, genetic-programming
  > **Comments:**
  > **username_1**: Yes, you are right. Sequences of moves, i.e. algorithm. I suggest you to read [this site](http://www.genetic-programming.org/gpbook4toc.html) about GA, if you haven't already.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2018-08-08. Score: 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](https://en.wikipedia.org/wiki/Genetic_programming) instead.
  
  The simplest way, and most similar to what you've proposed is called [linear genetic programming](https://en.wikipedia.org/wiki/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](http://www.genetic-programming.org/gpbook1toc.html) for other simple problems, like the [Santa Fe Trail](https://en.wikipedia.org/wiki/Santa_Fe_Trail_problem).
  
  More complex encodings are also possible. [Grammatical evolution](https://en.wikipedia.org/wiki/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.
  
  > **Comments:**
  > **username_3**: 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)  
  
  ---
  
  