Answers.Body: <p>In tree-based genetic programming (TGP), you have a tree that represents a program or a function. The nodes in this tree are functions, while the edges represent the interactions between these functions. The leaves of this tree are the inputs (or random numbers) that you pass to this function. The incoming edges into a node represent the inputs, while the outgoing edges represent the output of the associated function.</p>
  <p>So, for example, consider the following function</p>
  <p><span class="math-container">\begin{align}
  f(x) 
  &amp;= \sin(x^2) \\
  &amp;= \sin(y) 
  \tag{1}\label{1},
  \end{align}</span>
  where <span class="math-container">$y = g(x)$</span> (note that this is just a change of variable in order to illustrate the corresponding tree more clearly below!).</p>
  <p>The function <span class="math-container">$f$</span> will be represented by the following tree</p>
  <pre><code>sin(y)
    |
   g(x)
    |
    x
  </code></pre>
  <p>So, how do we read this diagram? Essentially, we read it from the bottom-up. So, <span class="math-container">$x$</span> is first passed to <span class="math-container">$y = g(x) = x^2$</span>, which then passed to <span class="math-container">$\sin(y)$</span>. In this case, given that we are dealing with mathematical operations, you expect <span class="math-container">$x$</span> to be a number, because, otherwise, what would <span class="math-container">$x^2$</span> or <span class="math-container">$\sin(x^2)$</span> mean?</p>
  <p>Let's now consider a function of 2 inputs.</p>
  <p><span class="math-container">\begin{align}
  f(x, y) 
  &amp;= x + y
  \tag{2}\label{2},
  \end{align}</span></p>
  <p>The corresponding tree would be</p>
  <pre><code>  +
   / \
  x   y
  </code></pre>
  <p>In this case, you naturally expect that <span class="math-container">$x$</span> and <span class="math-container">$y$</span> are also numbers. However, this may not be actually the case. Let's say that you're evolving Python functions, then <code>x + y</code> is well defined even if <code>x</code> and <code>y</code> are strings, i.e. that would be a concatenation operation.</p>
  <p>So, in this sense, we naturally expected the functions (the nodes in the tree) to get parameters/arguments with the right types, but, in some cases, more types are possible for the apparently same function.</p>
  <p>So, in general, types don't necessarily need to be enforced! It depends on the implementation of TGP.</p>
  <p>There's a specific approach to TGP where the idea is really to ensure type-safety, i.e. <strong>strongly-typed</strong> (tree-based) <strong>genetic programming</strong>, where functions can have a different number and type for their parameters and return values, but, in that case, only functions that are consistent with the signature of the function can be &quot;connected&quot; with that function in the tree.</p>
  <p>In weakly-typed GP, the types are not checked, so you could end up evolving functions of the form <span class="math-container">$f(x) = \sin(x)$</span>, where <span class="math-container">$x$</span> is a string. Of course, when you execute these programs/functions, the program may crash, but this is a different story, which you need to take care of (i.e. you need to ensure that your individuals can be evaluated), if you need this flexibility. This weakly-typed approach can also be viewed as a strongly-typed approach where all functions' parameters and return values have the same type.</p>
  <p><a href="https://github.com/DEAP/deap" rel="nofollow noreferrer">DEAP</a>, a well-known Python library for GAs and GP, provides both weakly and strongly-typed GP, so, if you are familiar with Python, you may want to start from it.</p>
  <p>To conclude and answer your question more directly, it's not true that in TGP you need all functions to have the same type for all parameters and return values.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-19T18:33:16.953Z
Answers.LastActivityDate: 2021-01-19T18:38:50.697Z
Answers.LastEditDate: 2021-01-19T18:38:50.697Z
Answers.UserDisplayName: nbro
Body: <p>Context: I'm a complete beginner to evolutionary algorithms and genetic algorithms and programming. I'm currently taking a course about genetic algorithms and genetic programming.</p>
  
  <p>One of the concepts introduced in the course is "closure," the idea that - with an expression tree representing a genetic program that we're evolving - all nodes in the tree need to be the same type. As a practical example, the lecturer mentions that implementing <code>greater_than(a, b)</code> for two integers <code>a</code> and <code>b</code> can't return a boolean like <code>true</code> or <code>false</code> (it can return, say, <code>0</code> and <code>1</code> instead).</p>
  
  <p>What he didn't explain is <em>why</em> the entire tree needs to match in all operators. It seems to me that this requirement would result in the entire tree (representing your evolved program) being composed of nodes that all return the same type (say, <code>integer</code>).</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-01-23T15:13:23.097Z
Comments.Text: Hello. [My answer below should answer your question, so you should accept it](https://ai.stackexchange.com/help/someone-answers).
Comments.UserDisplayName: nbro
Tags: <evolutionary-algorithms><genetic-programming><evolutionary-computation><tgp>
Title: Why do all nodes in a GP tree need to be the same type?
UserDisplayName: nightblade9
ThreadText: # Why do all nodes in a GP tree need to be the same type?
  
  (Asked by: username_0 on 2019-08-29)
  
  Context: I'm a complete beginner to evolutionary algorithms and genetic algorithms and programming. I'm currently taking a course about genetic algorithms and genetic programming.
  
  One of the concepts introduced in the course is "closure," the idea that - with an expression tree representing a genetic program that we're evolving - all nodes in the tree need to be the same type. As a practical example, the lecturer mentions that implementing `greater_than(a, b)` for two integers `a` and `b` can't return a boolean like `true` or `false` (it can return, say, `0` and `1` instead).
  
  What he didn't explain is *why* the entire tree needs to match in all operators. It seems to me that this requirement would result in the entire tree (representing your evolved program) being composed of nodes that all return the same type (say, `integer`).
  
  **Tags:** evolutionary-algorithms, genetic-programming, evolutionary-computation, tgp
  > **Comments:**
  > **username_1**: Hello. [My answer below should answer your question, so you should accept it](https://ai.stackexchange.com/help/someone-answers).  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2021-01-19. Score: 1
  
  In tree-based genetic programming (TGP), you have a tree that represents a program or a function. The nodes in this tree are functions, while the edges represent the interactions between these functions. The leaves of this tree are the inputs (or random numbers) that you pass to this function. The incoming edges into a node represent the inputs, while the outgoing edges represent the output of the associated function.
  So, for example, consider the following function
  \begin{align}
  f(x) 
  &= \sin(x^2) \\
  &= \sin(y) 
  \tag{1}\label{1},
  \end{align}
  where $y = g(x)$ (note that this is just a change of variable in order to illustrate the corresponding tree more clearly below!).
  The function $f$ will be represented by the following tree
  sin(y)
    |
   g(x)
    |
    x
  
  So, how do we read this diagram? Essentially, we read it from the bottom-up. So, $x$ is first passed to $y = g(x) = x^2$, which then passed to $\sin(y)$. In this case, given that we are dealing with mathematical operations, you expect $x$ to be a number, because, otherwise, what would $x^2$ or $\sin(x^2)$ mean?
  Let's now consider a function of 2 inputs.
  \begin{align}
  f(x, y) 
  &= x + y
  \tag{2}\label{2},
  \end{align}
  The corresponding tree would be
    +
   / \
  x   y
  
  In this case, you naturally expect that $x$ and $y$ are also numbers. However, this may not be actually the case. Let's say that you're evolving Python functions, then x + y is well defined even if x and y are strings, i.e. that would be a concatenation operation.
  So, in this sense, we naturally expected the functions (the nodes in the tree) to get parameters/arguments with the right types, but, in some cases, more types are possible for the apparently same function.
  So, in general, types don't necessarily need to be enforced! It depends on the implementation of TGP.
  There's a specific approach to TGP where the idea is really to ensure type-safety, i.e. strongly-typed (tree-based) genetic programming, where functions can have a different number and type for their parameters and return values, but, in that case, only functions that are consistent with the signature of the function can be "connected" with that function in the tree.
  In weakly-typed GP, the types are not checked, so you could end up evolving functions of the form $f(x) = \sin(x)$, where $x$ is a string. Of course, when you execute these programs/functions, the program may crash, but this is a different story, which you need to take care of (i.e. you need to ensure that your individuals can be evaluated), if you need this flexibility. This weakly-typed approach can also be viewed as a strongly-typed approach where all functions' parameters and return values have the same type.
  DEAP, a well-known Python library for GAs and GP, provides both weakly and strongly-typed GP, so, if you are familiar with Python, you may want to start from it.
  To conclude and answer your question more directly, it's not true that in TGP you need all functions to have the same type for all parameters and return values.
  
  
  ---
  
  