# Evolving Multi-Output Digital Circuits Using Multi-Genome Grammatical Evolution
## 3 Proposed Approach: Multi-Genome GE
### Cyclic Dependency Checking Algorithm
Given that output_1 is dependent on output_2 and output_2 is, in turn, dependent on output_3, if we extract output_1 without recursively substituting output variables with their corresponding expressions to obtain an expression devoid of output variables, output_1 will no longer be regarded as solved, as output_2 and output_3 are very likely to be different in the created best individual. Applying the substitution operator, we will obtain the solved expression devoid of any output variables as shown in Listing 3. Hence, the importance of the cyclic dependency checking algorithm is to ensure the substitution operator does not get stuck in a non-terminating loop as a result of cyclic dependency existing between output variables. ```
... output_1=cos(x)+output_2+output_2;(50/50) output_2=output_3+sin(y);(5/50) output_3=2^3+3;(1/50)...
```
Listing 2: An individual that completely evolves the solution to output_1 (50 out of 50 total cases). ```
...
```
Listing 3: Final perfect output_1 statement after applying the substitution operator. ```
...
```
Listing 4: Output_1=cos(x)+output_2+output_2;... Listing 5: Final perfect output_1 statement after applying the substitution operator. ```
...
```
Listing 5: A typed iteration of the substitution operator to rewrite the solved output_1 variable before it is extracted. As can be observed from Listing 4, output variable output_1 used output variable output_2 twice which were replaced by the same expression at the end of the substitution operation. That is, in cases where an output variable uses another output variable multiple times will result in an increase in the size of the phenotype. In the case of digital circuits, such a scenario will increase the total number of gates required to realise the gate-level design of the circuit. However, this is a post-processing issue and is not addressed in this work. ### Evolutionary Cycle

A steady-state EA is used to run the benchmark problems in this work. Unlike standard GE, where the best-performing individual is returned as the best-evolved solution, MG-GE creates its best individual by combining the best-performing genome for each output variable. However, when an output variable solution has been evolved, we perform substitution operations at the phenotype level described in Section 3.11. The function of the substitution operator is to rewrite an expression in terms of variables other than the output variables. Once an output variable has been solved, its solution is made available to all individuals in the population, and evolution no longer searches for it. However, this functionality can be modified if required for evolution to continue the search but for solutions with additional desirable properties, such as shorter expressions. ## 4 Experiments

Two combinational benchmark problems are used in this work: _ripple carry adder_ and _hamming code encoder_. Two instances of each problem are considered based on the number of inputs and outputs, Hamming Code (\(7\),\(A\)) and (\(15\),\(11\)) Encoders, and \(5\)-bit + \(5\)-bit and \(10\)-bit + \(10\)-bit Adders. Experiments are conducted to investigate the performance of standard GE versus MG-GE on these benchmark problems. For each experiment, we design two grammars. The first grammar variant, which we refer to as Grammar with Output Variable Sharing, allows output variables to use other output variables as building blocks as long as no cyclic dependency between output variables is formed. This is achieved by the definition of Output Variable Rules as described in Section 3.4. In other words, Output Variable Rules, together with the cyclic dependency algorithm, are how MG-GE evolves inter-output dependencies that may exist. This feature is modelled in the grammar by adding the Output Variable Rule non-terminal to the \(\langle\)expr-i\(\rangle\) rules as the last production (highlighted in both grammars).