Answers.Body: <p>Before I answer your question, it is important to frame what a GA is, so please allow me to cover some history.</p>
  
  <p><a href="https://www.wiley.com/en-us/Evolutionary+Computation%3A+Toward+a+New+Philosophy+of+Machine+Intelligence%2C+3rd+Edition-p-9780471669517" rel="nofollow noreferrer">Friedman and Fraser</a> performed some of the earliest evolutionary computation experiments. Fraser presented the case of diploid organisms represented by <em>binary strings</em> of <em>a given length</em>. Each bit in the string represented a gene. Fraser proposed the process of single-point crossover for binary string reproduction. </p>
  
  <p>American computer scientist <a href="https://en.wikipedia.org/wiki/Genetic_algorithm" rel="nofollow noreferrer">John Henry Holland</a> and his colleagues at the University of Michigan formalised the evolutionary algorithms originally implemented by Bremermann, Fraser, Friedman and Friedberg.</p>
  
  <p>Holland's formal algorithm is known as a <em>Genetic Algorithm</em> (GA). A GA has a <em>fixed length chromosome structure</em>. Traditionally it was binary based. However due to <a href="https://en.wikipedia.org/wiki/Hamming_distance" rel="nofollow noreferrer">hamming</a> distances of various bit strings a GA using a binary encoded chromosome string can get stuck at local <a href="https://en.wikipedia.org/wiki/Maxima_and_minima" rel="nofollow noreferrer">minima</a>. Holland experimented with integer based GAs too.</p>
  
  <p>Getting back to your question, theoretically and in its strictest sense, a Genetic Algorithm has a fixed length chromosome vector. The primary reason for this is that each gene represents something. If it was variable then the meaning of the gene must be encoded into the chromosome, which makes evolution more difficult. However, there are other chromosome structures that are variable length. The chromosome structure itself <em>implies</em> meaning.</p>
  
  <p><a href="http://www.genetic-programming.com/johnkoza.html" rel="nofollow noreferrer">Koza</a> experimented with an alternative version of a GA called a <a href="https://en.wikipedia.org/wiki/Genetic_programming" rel="nofollow noreferrer">genetic programming</a> (<strong>GP</strong>). A GP replaces the fixed length vector structure used in a genetic algorithm with a <strong>variable length</strong>, non-linear, hierarchical abstract data structure, known as a <em>tree</em>. </p>
  
  <p>The tree consists of branch nodes and leaf nodes. Leaf nodes have no children and implement a number or constant from a terminal set. A leaf node is also known as a terminal node. A branch node is connected to other branch nodes or leaf nodes and implement an operator from a functional set. A branch node is also known as a non-terminal node.</p>
  
  <p>The <em>tree</em> structure naturally accommodates <strong>a game rule</strong>. A tree is not restricted to a fixed length. A tree is a natural structure to represent hierarchical decisions rules, and a tree can store both binary, logical, and numeric functions within its nodes. Logical functions allow the GP to evolve conditional execution of game play functions not easily implemented using a fixed length vector. Tree does need a traversal path and grammar (syntax and semantics).</p>
  
  <p><strong>In short to answer your questions</strong>:</p>
  
  <ol>
  <li>A GA (fixed length) is generally not used for games, but rather a GP (variable with decisions).  </li>
  <li>A GA is not the most suitable method for this kind of problem as it is fixed
  length, and each gene corresponds to a rule or value.</li>
  </ol>
  
  <p>I would implement a GP, where the operators of mutation and crossover are adapted for a GP. I would also use the game itself as a fitness function, where a pool of individuals either using a single population, or co-evolution evolve players that gradually increase their score.</p>
  
  <p>The paragraphs above were taken from Nicholls' MSc thesis. His thesis was on stock market trading rule generation which is similar to game rule generation. His thesis is available <a href="http://hdl.handle.net/2263/68477" rel="nofollow noreferrer">here</a> (Only available after April 2019).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-03-05T13:25:05.560Z
Answers.LastActivityDate: 2019-03-06T08:16:22.553Z
Answers.LastEditDate: 2019-03-06T08:16:22.553Z
Answers.UserDisplayName: Jason
Body: <p>Until now, I always thought that Genetic Algorithm can be used for problems of which the solution space can be encoded (modeled) as a chromosome of a specific length. However, some people claim that they used GA for <a href="https://www.codingame.com/multiplayer/optimization/code-vs-zombies" rel="nofollow noreferrer">this game</a> and <a href="https://www.codingame.com/multiplayer/bot-programming/coders-strike-back" rel="nofollow noreferrer">this game</a>. They are basically games in which we control an agent on a 2-dimensional area. </p>
  
  <p>Obviously, the length of the genome sequence depends on how fast the game is finished. So, how is GA used for such games?</p>
  
  <p>If you think GA is not the most suitable method for this kind of problems can you explain why and give better alternatives?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-03-05T14:55:57.293Z
Comments.Text: When it comes to alternative solutions, how about Evolutionary Algorithms (EA)?
  Seems to me EAs are more flexible then GAs and can find their use in more applications than GAs.
Comments.UserDisplayName: GKozinski
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-03-06T06:37:05.550Z
Comments.Text: Evolutionary Algorithm is a class of machine learning comprising of at least 3 sub-classes namely: Genetic Algorithms (GA) [Holland  et al](Including GPs), Evolutionary Programs (EP) [Fogel  et al], Evolutionary Strategies (ES)(Rechenberg et al). Back was the first to categorise these algorithms in 1997. See his book https://dl.acm.org/citation.cfm?id=548530
Comments.UserDisplayName: Jason
Tags: <game-ai><genetic-algorithms>
Title: How to use Genetic Algorithm for varying lengths of solutions
UserDisplayName: ozgur
ThreadText: # How to use Genetic Algorithm for varying lengths of solutions
  
  (Asked by: username_0 on 2018-11-02)
  
  Until now, I always thought that Genetic Algorithm can be used for problems of which the solution space can be encoded (modeled) as a chromosome of a specific length. However, some people claim that they used GA for [this game](https://www.codingame.com/multiplayer/optimization/code-vs-zombies) and [this game](https://www.codingame.com/multiplayer/bot-programming/coders-strike-back). They are basically games in which we control an agent on a 2-dimensional area.
  
  Obviously, the length of the genome sequence depends on how fast the game is finished. So, how is GA used for such games?
  
  If you think GA is not the most suitable method for this kind of problems can you explain why and give better alternatives?
  
  **Tags:** game-ai, genetic-algorithms
  
  > **Comments:**
  > **username_1**: When it comes to alternative solutions, how about Evolutionary Algorithms (EA)? Seems to me EAs are more flexible then GAs and can find their use in more applications than GAs.  
  > **username_2**: Evolutionary Algorithm is a class of machine learning comprising of at least 3 sub-classes namely: Genetic Algorithms (GA) [Holland  et al](Including GPs), Evolutionary Programs (EP) [Fogel  et al], Evolutionary Strategies (ES)(Rechenberg et al). Back was the first to categorise these algorithms in 1997. See his book https://dl.acm.org/citation.cfm?id=548530  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2019-03-05. Score: 1
  
  Before I answer your question, it is important to frame what a GA is, so please allow me to cover some history.
  
  [Friedman and Fraser](https://www.wiley.com/en-us/Evolutionary+Computation%3A+Toward+a+New+Philosophy+of+Machine+Intelligence%2C+3rd+Edition-p-9780471669517) performed some of the earliest evolutionary computation experiments. Fraser presented the case of diploid organisms represented by *binary strings* of *a given length*. Each bit in the string represented a gene. Fraser proposed the process of single-point crossover for binary string reproduction.
  
  American computer scientist [John Henry Holland](https://en.wikipedia.org/wiki/Genetic_algorithm) and his colleagues at the University of Michigan formalised the evolutionary algorithms originally implemented by Bremermann, Fraser, Friedman and Friedberg.
  
  Holland's formal algorithm is known as a *Genetic Algorithm* (GA). A GA has a *fixed length chromosome structure*. Traditionally it was binary based. However due to [hamming](https://en.wikipedia.org/wiki/Hamming_distance) distances of various bit strings a GA using a binary encoded chromosome string can get stuck at local [minima](https://en.wikipedia.org/wiki/Maxima_and_minima). Holland experimented with integer based GAs too.
  
  Getting back to your question, theoretically and in its strictest sense, a Genetic Algorithm has a fixed length chromosome vector. The primary reason for this is that each gene represents something. If it was variable then the meaning of the gene must be encoded into the chromosome, which makes evolution more difficult. However, there are other chromosome structures that are variable length. The chromosome structure itself *implies* meaning.
  
  [Koza](http://www.genetic-programming.com/johnkoza.html) experimented with an alternative version of a GA called a [genetic programming](https://en.wikipedia.org/wiki/Genetic_programming) (**GP**). A GP replaces the fixed length vector structure used in a genetic algorithm with a **variable length**, non-linear, hierarchical abstract data structure, known as a *tree*.
  
  The tree consists of branch nodes and leaf nodes. Leaf nodes have no children and implement a number or constant from a terminal set. A leaf node is also known as a terminal node. A branch node is connected to other branch nodes or leaf nodes and implement an operator from a functional set. A branch node is also known as a non-terminal node.
  
  The *tree* structure naturally accommodates **a game rule**. A tree is not restricted to a fixed length. A tree is a natural structure to represent hierarchical decisions rules, and a tree can store both binary, logical, and numeric functions within its nodes. Logical functions allow the GP to evolve conditional execution of game play functions not easily implemented using a fixed length vector. Tree does need a traversal path and grammar (syntax and semantics).
  
  **In short to answer your questions**:
  
  1. A GA (fixed length) is generally not used for games, but rather a GP (variable with decisions).
  2. A GA is not the most suitable method for this kind of problem as it is fixed
     length, and each gene corresponds to a rule or value.
  
  I would implement a GP, where the operators of mutation and crossover are adapted for a GP. I would also use the game itself as a fitness function, where a pool of individuals either using a single population, or co-evolution evolve players that gradually increase their score.
  
  The paragraphs above were taken from Nicholls' MSc thesis. His thesis was on stock market trading rule generation which is similar to game rule generation. His thesis is available [here](http://hdl.handle.net/2263/68477) (Only available after April 2019).
  
  
  ---
  
  