Answers.Body: <h3>Grammatical evolution</h3>
  <p>To understand what a codon is, we need to understand what GE is, so let me first provide a brief description of this approach.</p>
  <p>Grammatical evolution (GE) is an approach to genetic programming where the <strong>genotypes</strong> are binary (or integer) arrays, which are mapped to the <strong>phenotypes</strong> (i.e. the actual solutions, which can be represented as trees, which, in turn, represent programs or functions), using a grammar (for example, expressed in <a href="https://en.wikipedia.org/wiki/Backus%E2%80%93Naur_form" rel="nofollow noreferrer">Backus-Naur form</a>). So, the genotypes (i.e. what is mutated, combined, or searched) and the phenotypes (the actual solutions, which are programs) are different in GE, and the genotype needs to be mapped to the phenotype to get the actual solution (or program), but this is not the case in all GP approaches (for example, in tree-based GP, the genotype and the phenotype are the same, i.e. trees, which represent functions).</p>
  <h3>Codons</h3>
  <p>In GE, a <strong>codon</strong> is a subsequence of <span class="math-container">$m$</span> bits of the genotype (assuming that genotypes are binary arrays). For example, let's say that we have only two symbols in our grammar, i.e. <code>a</code> (a number) and <code>b</code> (another number). In this case, we only need 2 bits to differentiate the two. If we had 3 symbols,  <code>a</code>, <code>b</code> and <code>+</code> (the addition operator), we would need at least a sequence of 2 bits to define each symbol. So, in this case, we could have the following mapping</p>
  <ul>
  <li><code>a</code> is represented by <code>00</code> (or the integer <code>0</code>),</li>
  <li><code>b</code> is represented by <code>01</code> (or <code>1</code>), and</li>
  <li><code>+</code> is represented by <code>10</code> (or <code>2</code>)</li>
  </ul>
  <p>The operation <code>a+b</code> could then be represented by the binary sequence <code>001001</code> (or the integer sequence <code>021</code>). The 2-bit subsequences <code>00</code>, <code>01</code> and <code>10</code> (or their integer counterparts) are the <strong>codons</strong>.</p>
  <h3>What do we need codons for?</h3>
  <p>In GE, codons are used to index the specific choice of a production rule. To understand this, let's define a simple grammar, which is composed of</p>
  <ul>
  <li>a set of non-terminals (e.g. functions) <span class="math-container">$N = \{ \langle \text{expr} \rangle, \langle \text{op} \rangle, \langle \text{operand} \rangle, \langle \text{var} \rangle \}$</span>
  ,</li>
  <li>a set of terminals (e.g. specific numbers or letters) <span class="math-container">$\mathrm{T}=\{1,2,3,4,+,-, /, *, \mathrm{x}, \mathrm{y}\}$</span>,</li>
  <li>a set of production rules <span class="math-container">$P$</span>, and</li>
  <li>an initial production rule <span class="math-container">$S = \langle \text{expr} \rangle $</span>.</li>
  </ul>
  <p>In this case, the set of production rules <span class="math-container">$P$</span> is defined as follows</p>
  <p><span class="math-container">\begin{align}
  \langle \text{expr} \rangle &amp; ::= 
  \langle \text{expr} \rangle \langle \text{op} \rangle \langle \text{expr} \rangle \; | \;  \langle \text{operand} \rangle \\
  \langle \text{op} \rangle &amp; ::= + \;  | \;  - \;  | \; * \; | \; / \\
  \langle \text{operand} \rangle &amp; ::= 1 \;  | \; 2 \; | \;  3 \; | \;  4 \;  | \;  \langle \text{var} \rangle \\
  \langle \text{var} \rangle &amp; ::= \mathrm{x} \; | \;  \mathrm{y}
  \end{align}</span>
  So, there are four productions rules. To be clear, <span class="math-container">$\langle \text{var} \rangle  ::= \mathrm{x} \; | \;  \mathrm{y}$</span> is a production rule. The symbol <span class="math-container">$|$</span> means &quot;or&quot;, so the left-hand side of each production is a non-terminal (and note that all non-terminals are denoted with angle brackets <span class="math-container">$\langle \cdot \rangle$</span>), which is defined as (or can be replaced with) one of the right-hand choices, which can be a non-terminal or terminal. The first choice of each production rule is at index <span class="math-container">$0$</span>. The second choice at index <span class="math-container">$1$</span>, and so on. So, for example, in the case of the production <span class="math-container">$\langle \text{var} \rangle  ::= \mathrm{x} \; | \;  \mathrm{y}$</span>, <span class="math-container">$\mathrm{x}$</span> is the choice at index <span class="math-container">$0$</span> and <span class="math-container">$\mathrm{y}$</span> is the choice at index <span class="math-container">$1$</span>.</p>
  <p>The codons are the indices that we use to select the production rule's choice while transforming (or mapping) the genotype into a phenotype (an actual program).</p>
  <p>So, we start with the first production, in this case, <span class="math-container">$S = \langle \text{expr} \rangle$</span>. If it's a non-terminal, then we replace it with one of its right-hand side choices. In this case, there are two choices</p>
  <ul>
  <li><span class="math-container">$\langle \text{expr} \rangle \langle \text{op} \rangle \langle \text{expr} \rangle$</span> (choice at index <span class="math-container">$0$</span>)</li>
  <li><span class="math-container">$\langle \text{operand} \rangle$</span> (choice at index <span class="math-container">$1$</span>)</li>
  </ul>
  <p>If our genotype (integer representation) is, for example, <span class="math-container">$01$</span> (note that this is a sequence of integers), we would replace <span class="math-container">$\langle \text{expr} \rangle$</span> with <span class="math-container">$\langle \text{expr} \rangle \langle \text{op} \rangle \langle \text{expr} \rangle$</span>, then we would replace the first <span class="math-container">$\langle \text{expr} \rangle$</span> in <span class="math-container">$\langle \text{expr} \rangle \langle \text{op} \rangle \langle \text{expr} \rangle$</span> with <span class="math-container">$\langle \text{operand} \rangle$</span>, so we would get <span class="math-container">$\langle \text{operand} \rangle \langle \text{op} \rangle \langle \text{expr} \rangle$</span>, and so on and so forth, until we get an expression that only contains terminals, or the genotype is terminated. There can be other ways of mapping the genotype to the phenotype, but this is the purpose of codons.</p>
  <h3>Codons in biology</h3>
  <p>The term <em>codon</em> has its origins in <a href="https://en.wikipedia.org/wiki/Genetic_code" rel="nofollow noreferrer">biology</a>: a subsequence of 3 <a href="https://en.wikipedia.org/wiki/Nucleotide" rel="nofollow noreferrer">nucleotides</a> is known as a <em>codon</em>, which is mapped to an amino acid in order to produce the proteins. The set of all mappings from codons to amino acids is known as <em>genetic code</em>. Take a look at <a href="https://www.khanacademy.org/science/ap-biology/gene-expression-and-regulation/translation/a/the-genetic-code-discovery-and-properties" rel="nofollow noreferrer">this article</a> for a gentle introduction to the subject. So, in GE, codons also have a similar role to the role of codons in biology, i.e. they are used to build the actual phenotypes (in biology, the phenotypes would be the proteins or, ultimately, the organism).</p>
  <h3>Notes</h3>
  <p>Codons do not have to be 2-bit subsequences, but they can be <span class="math-container">$m$</span>-bit subsequences, for some arbitrary <span class="math-container">$m$</span>. The term <strong>codon</strong> is similar to the term <strong>gene</strong>, which is also often used to refer to specific subsequences of the genotype (for example, in genetic algorithms), although they may not be synonymous (at least in biology, <a href="https://en.wikipedia.org/wiki/Gene" rel="nofollow noreferrer">genes</a> are made up of sequences of codons, so they are not synonymous). Moreover, the binary <span class="math-container">$m$</span>-bit codons can first be mapped to integers, so codons can also just be integers, as e.g. used <a href="https://www.researchgate.net/publication/261165893_Termination_in_Grammatical_Evolution_grammar_design_wrapping_and_tails" rel="nofollow noreferrer">here</a> or illustrated in figure 2.2 of <a href="http://www.cs.uu.nl/docs/vakken/ias/stuff/Foundations%20in%20Grammatical%20Evolution%20-%20Dempsey%20et%20al.%20-%20Ch.%202%20-%202009.pdf" rel="nofollow noreferrer">this chapter</a>.</p>
  <h3>Further reading</h3>
  <p>You can find more info about codons in the book <a href="https://www.researchgate.net/publication/221900758_Genetic_Programming_An_Introduction_on_the_Automatic_Evolution_of_computer_programs_and_its_Applications" rel="nofollow noreferrer">Genetic Programming: An Introduction</a> by Wolfgang Banzhaf et al., specifically sections 9.2.2. (p. 255), 9.2.3. (an example) and 2.3 (p. 39), or in <a href="http://www.cs.uu.nl/docs/vakken/ias/stuff/Foundations%20in%20Grammatical%20Evolution%20-%20Dempsey%20et%20al.%20-%20Ch.%202%20-%202009.pdf" rel="nofollow noreferrer">chapter 2</a> of the book <a href="https://link.springer.com/book/10.1007%2F978-3-642-00314-1" rel="nofollow noreferrer">Foundations in Grammatical Evolution</a> by Dempsey et al.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-28T01:08:51.600Z
Answers.LastActivityDate: 2020-12-29T00:03:06.360Z
Answers.LastEditDate: 2020-12-29T00:03:06.360Z
Answers.UserDisplayName: nbro
Body: <p>The term <em>codon</em> is used in the context of grammatical evolution (GE), sometimes, without being explicitly defined. For example, it is used in <a href="https://arxiv.org/pdf/1703.08535.pdf" rel="nofollow noreferrer">this paper</a>, which introduces and describes <a href="https://github.com/PonyGE/PonyGE2" rel="nofollow noreferrer">PonyGE 2</a>, a Python library for GE, but it's not clearly defined.  So, what is a codon?</p>
  
Tags: <terminology><evolutionary-algorithms><genetic-programming><grammatical-evolution><codon>
Title: What is a codon in grammatical evolution?
UserDisplayName: nbro
ThreadText: # What is a codon in grammatical evolution?
  
  (Asked by: username_0 on 2020-12-28)
  
  The term *codon* is used in the context of grammatical evolution (GE), sometimes, without being explicitly defined. For example, it is used in [this paper](https://arxiv.org/pdf/1703.08535.pdf), which introduces and describes [PonyGE 2](https://github.com/PonyGE/PonyGE2), a Python library for GE, but it's not clearly defined. So, what is a codon?
  
  **Tags:** terminology, evolutionary-algorithms, genetic-programming, grammatical-evolution, codon
  
  ---
  
  ## 1 answers
  
  ### Answer by username_0 on 2020-12-28. Score: 1 | Accepted answer
  
  ### Grammatical evolution
  
  To understand what a codon is, we need to understand what GE is, so let me first provide a brief description of this approach.
  
  Grammatical evolution (GE) is an approach to genetic programming where the **genotypes** are binary (or integer) arrays, which are mapped to the **phenotypes** (i.e. the actual solutions, which can be represented as trees, which, in turn, represent programs or functions), using a grammar (for example, expressed in [Backus-Naur form](https://en.wikipedia.org/wiki/Backus%E2%80%93Naur_form)). So, the genotypes (i.e. what is mutated, combined, or searched) and the phenotypes (the actual solutions, which are programs) are different in GE, and the genotype needs to be mapped to the phenotype to get the actual solution (or program), but this is not the case in all GP approaches (for example, in tree-based GP, the genotype and the phenotype are the same, i.e. trees, which represent functions).
  
  ### Codons
  
  In GE, a **codon** is a subsequence of $m$ bits of the genotype (assuming that genotypes are binary arrays). For example, let's say that we have only two symbols in our grammar, i.e. `a` (a number) and `b` (another number). In this case, we only need 2 bits to differentiate the two. If we had 3 symbols, `a`, `b` and `+` (the addition operator), we would need at least a sequence of 2 bits to define each symbol. So, in this case, we could have the following mapping
  
  * `a` is represented by `00` (or the integer `0`),
  * `b` is represented by `01` (or `1`), and
  * `+` is represented by `10` (or `2`)
  
  The operation `a+b` could then be represented by the binary sequence `001001` (or the integer sequence `021`). The 2-bit subsequences `00`, `01` and `10` (or their integer counterparts) are the **codons**.
  
  ### What do we need codons for?
  
  In GE, codons are used to index the specific choice of a production rule. To understand this, let's define a simple grammar, which is composed of
  
  * a set of non-terminals (e.g. functions) $N = \{ \langle \text{expr} \rangle, \langle \text{op} \rangle, \langle \text{operand} \rangle, \langle \text{var} \rangle \}$
    ,
  * a set of terminals (e.g. specific numbers or letters) $\mathrm{T}=\{1,2,3,4,+,-, /, \*, \mathrm{x}, \mathrm{y}\}$,
  * a set of production rules $P$, and
  * an initial production rule $S = \langle \text{expr} \rangle $.
  
  In this case, the set of production rules $P$ is defined as follows
  
  \begin{align}
  \langle \text{expr} \rangle & ::=
  \langle \text{expr} \rangle \langle \text{op} \rangle \langle \text{expr} \rangle \; | \; \langle \text{operand} \rangle \\
  \langle \text{op} \rangle & ::= + \; | \; - \; | \; \* \; | \; / \\
  \langle \text{operand} \rangle & ::= 1 \; | \; 2 \; | \; 3 \; | \; 4 \; | \; \langle \text{var} \rangle \\
  \langle \text{var} \rangle & ::= \mathrm{x} \; | \; \mathrm{y}
  \end{align}
  So, there are four productions rules. To be clear, $\langle \text{var} \rangle ::= \mathrm{x} \; | \; \mathrm{y}$ is a production rule. The symbol $|$ means "or", so the left-hand side of each production is a non-terminal (and note that all non-terminals are denoted with angle brackets $\langle \cdot \rangle$), which is defined as (or can be replaced with) one of the right-hand choices, which can be a non-terminal or terminal. The first choice of each production rule is at index $0$. The second choice at index $1$, and so on. So, for example, in the case of the production $\langle \text{var} \rangle ::= \mathrm{x} \; | \; \mathrm{y}$, $\mathrm{x}$ is the choice at index $0$ and $\mathrm{y}$ is the choice at index $1$.
  
  The codons are the indices that we use to select the production rule's choice while transforming (or mapping) the genotype into a phenotype (an actual program).
  
  So, we start with the first production, in this case, $S = \langle \text{expr} \rangle$. If it's a non-terminal, then we replace it with one of its right-hand side choices. In this case, there are two choices
  
  * $\langle \text{expr} \rangle \langle \text{op} \rangle \langle \text{expr} \rangle$ (choice at index $0$)
  * $\langle \text{operand} \rangle$ (choice at index $1$)
  
  If our genotype (integer representation) is, for example, $01$ (note that this is a sequence of integers), we would replace $\langle \text{expr} \rangle$ with $\langle \text{expr} \rangle \langle \text{op} \rangle \langle \text{expr} \rangle$, then we would replace the first $\langle \text{expr} \rangle$ in $\langle \text{expr} \rangle \langle \text{op} \rangle \langle \text{expr} \rangle$ with $\langle \text{operand} \rangle$, so we would get $\langle \text{operand} \rangle \langle \text{op} \rangle \langle \text{expr} \rangle$, and so on and so forth, until we get an expression that only contains terminals, or the genotype is terminated. There can be other ways of mapping the genotype to the phenotype, but this is the purpose of codons.
  
  ### Codons in biology
  
  The term *codon* has its origins in [biology](https://en.wikipedia.org/wiki/Genetic_code): a subsequence of 3 [nucleotides](https://en.wikipedia.org/wiki/Nucleotide) is known as a *codon*, which is mapped to an amino acid in order to produce the proteins. The set of all mappings from codons to amino acids is known as *genetic code*. Take a look at [this article](https://www.khanacademy.org/science/ap-biology/gene-expression-and-regulation/translation/a/the-genetic-code-discovery-and-properties) for a gentle introduction to the subject. So, in GE, codons also have a similar role to the role of codons in biology, i.e. they are used to build the actual phenotypes (in biology, the phenotypes would be the proteins or, ultimately, the organism).
  
  ### Notes
  
  Codons do not have to be 2-bit subsequences, but they can be $m$-bit subsequences, for some arbitrary $m$. The term **codon** is similar to the term **gene**, which is also often used to refer to specific subsequences of the genotype (for example, in genetic algorithms), although they may not be synonymous (at least in biology, [genes](https://en.wikipedia.org/wiki/Gene) are made up of sequences of codons, so they are not synonymous). Moreover, the binary $m$-bit codons can first be mapped to integers, so codons can also just be integers, as e.g. used [here](https://www.researchgate.net/publication/261165893_Termination_in_Grammatical_Evolution_grammar_design_wrapping_and_tails) or illustrated in figure 2.2 of [this chapter](http://www.cs.uu.nl/docs/vakken/ias/stuff/Foundations%20in%20Grammatical%20Evolution%20-%20Dempsey%20et%20al.%20-%20Ch.%202%20-%202009.pdf).
  
  ### Further reading
  
  You can find more info about codons in the book [Genetic Programming: An Introduction](https://www.researchgate.net/publication/221900758_Genetic_Programming_An_Introduction_on_the_Automatic_Evolution_of_computer_programs_and_its_Applications) by Wolfgang Banzhaf et al., specifically sections 9.2.2. (p. 255), 9.2.3. (an example) and 2.3 (p. 39), or in [chapter 2](http://www.cs.uu.nl/docs/vakken/ias/stuff/Foundations%20in%20Grammatical%20Evolution%20-%20Dempsey%20et%20al.%20-%20Ch.%202%20-%202009.pdf) of the book [Foundations in Grammatical Evolution](https://link.springer.com/book/10.1007%2F978-3-642-00314-1) by Dempsey et al.
  
  
  ---
  
  