Body: <p>Consider the following digital logic circuit, which has multiple inputs and one output:</p>
  <p><a href="https://i.sstatic.net/3HBJU.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/3HBJU.png" alt="Digital logic circuit drawn using Logisim" /></a></p>
  <p>The logic circuit above can be represented in tree form:</p>
  <p><a href="https://i.sstatic.net/sx4Wg.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/sx4Wg.png" alt="Tree drawn using Graphviz" /></a></p>
  <p>This tree representation could then be used in a tree-based genetic programming framework to evolve the circuit. For example, this tree could be represented as a Lisp list <code>(or (and A B) (not C))</code>, which could then be used with the <a href="http://www.genetic-programming.org/gplittlelisp.html" rel="nofollow noreferrer">Little LISP</a> genetic programming framework from John R. Koza's <em>Genetic Programming</em> textbook.</p>
  <p>However, I now want to deal with digital logic circuits that have more than one output. For example, in the half-adder circuit below, there are two outputs <span class="math-container">$S$</span> and <span class="math-container">$C$</span>, each of which is affected by both inputs <span class="math-container">$A$</span> and <span class="math-container">$B$</span>.</p>
  <p><a href="https://i.sstatic.net/gmIEQ.gif" rel="nofollow noreferrer" title="Half adder"><img src="https://i.sstatic.net/gmIEQ.gif" alt="Half adder" title="Half adder" /></a></p>
  <p><sub>(Image source: <a href="https://mitpress.mit.edu/sites/default/files/sicp/full-text/sicp/book/node64.html" rel="nofollow noreferrer">SICP by Abelson et al. Section 3.3.4 A Simulator for Digital Circuits</a>. <a href="https://creativecommons.org/licenses/by-sa/4.0/" rel="nofollow noreferrer">CC BY-SA 4.0</a>)</sub></p>
  <p>How do I represent and evolve such a circuit in tree-based genetic programming? How do I represent the circuit above as a tree that could then be used to evolve the circuit using a tree-based genetic programming framework?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-02-16T18:56:46.153Z
Comments.Text: Maybe you can do this with a custom function that gets $s$ and $c$ as input and that would produce the final return type, i.e. a binary vector.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-02-17T05:39:50.633Z
Comments.Text: @nbro Thank you for the suggestion, but how would such a tree look like exactly? With the binary vector return type, $S$ and $C$ can each be influenced by either $A$ or $B$ but not both. That is the consequence of a tree representation. Perhaps I am not fully understanding your suggestion because I don't see how it could represent things like half-adders (shown in the question) and flip-flops.
Comments.UserDisplayName: Flux
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-02-17T09:41:17.210Z
Comments.Text: I didn't realise that you didn't want both A and B to affect both S or C, because you didn't explain this in the post. In any case, my suggestion was more about how you could possibly deal with 2 outputs. You can could create a function like `id(s, a) = [s, a]`, and the output of the circuit/tree is of type `list`. Here, `id` is the custom function that you need to add to you function set, in addition to `and`, `or` and `not`. If I have some time, later, I will try to create a simple proof-of-concept that illustrates my idea.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-02-17T09:46:35.053Z
Comments.Text: @nbro Sorry for not making that clear. In the half-adder circuit shown in the question, The output at $S$ is affected by both inputs $A$ and $B$. Similarly for the output at $C$.
Comments.UserDisplayName: Flux
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-02-17T09:49:20.693Z
Comments.Text: Ok, that's fine. My suggestion above still applies.
Comments.UserDisplayName: nbro
Tags: <ai-design><applications><evolutionary-algorithms><logic><genetic-programming>
Title: How to represent multiple-output logic circuits in tree-based genetic programming
UserDisplayName: Flux
ThreadText: # How to represent multiple-output logic circuits in tree-based genetic programming
  
  (Asked by: username_0 on 2022-02-16)
  
  Consider the following digital logic circuit, which has multiple inputs and one output:
  
  [![Digital logic circuit drawn using Logisim](https://i.sstatic.net/3HBJU.png)](https://i.sstatic.net/3HBJU.png)
  
  The logic circuit above can be represented in tree form:
  
  [![Tree drawn using Graphviz](https://i.sstatic.net/sx4Wg.png)](https://i.sstatic.net/sx4Wg.png)
  
  This tree representation could then be used in a tree-based genetic programming framework to evolve the circuit. For example, this tree could be represented as a Lisp list `(or (and A B) (not C))`, which could then be used with the [Little LISP](http://www.genetic-programming.org/gplittlelisp.html) genetic programming framework from John R. Koza's *Genetic Programming* textbook.
  
  However, I now want to deal with digital logic circuits that have more than one output. For example, in the half-adder circuit below, there are two outputs $S$ and $C$, each of which is affected by both inputs $A$ and $B$.
  
  [![Half adder](https://i.sstatic.net/gmIEQ.gif "Half adder")](https://i.sstatic.net/gmIEQ.gif "Half adder")
  
  (Image source: [SICP by Abelson et al. Section 3.3.4 A Simulator for Digital Circuits](https://mitpress.mit.edu/sites/default/files/sicp/full-text/sicp/book/node64.html). [CC BY-SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/))
  
  How do I represent and evolve such a circuit in tree-based genetic programming? How do I represent the circuit above as a tree that could then be used to evolve the circuit using a tree-based genetic programming framework?
  
  **Tags:** ai-design, applications, evolutionary-algorithms, logic, genetic-programming
  > **Comments:**
  > **username_1**: Maybe you can do this with a custom function that gets $s$ and $c$ as input and that would produce the final return type, i.e. a binary vector.  
  > **username_0**: @nbro Thank you for the suggestion, but how would such a tree look like exactly? With the binary vector return type, $S$ and $C$ can each be influenced by either $A$ or $B$ but not both. That is the consequence of a tree representation. Perhaps I am not fully understanding your suggestion because I don't see how it could represent things like half-adders (shown in the question) and flip-flops.  
  > **username_1**: I didn't realise that you didn't want both A and B to affect both S or C, because you didn't explain this in the post. In any case, my suggestion was more about how you could possibly deal with 2 outputs. You can could create a function like `id(s, a) = [s, a]`, and the output of the circuit/tree is of type `list`. Here, `id` is the custom function that you need to add to you function set, in addition to `and`, `or` and `not`. If I have some time, later, I will try to create a simple proof-of-concept that illustrates my idea.  
  > **username_0**: @nbro Sorry for not making that clear. In the half-adder circuit shown in the question, The output at $S$ is affected by both inputs $A$ and $B$. Similarly for the output at $C$.  
  > **username_1**: Ok, that's fine. My suggestion above still applies.  
  
  ---
  
  ## 0 answers
  
  