# Evolving Multi-Output Digital Circuits Using Multi-Genome Grammatical Evolution
## 3 Proposed Approach: Multi-Genome GE
### Cyclic Dependency Checking Algorithm
```
1 FunctionSubMap(start_symbol,mapped_outputs_rules,multi_genome,genome_index,phenotype, dependency_manager)
2 genome \(\leftarrow\) multi_genome[index];
3{derivation_stack,is_wrapperping} \(\leftarrow\) {stack,false} ;
4{codon_index,effective_size} \(\leftarrow\) {0,0} ;
5{genome is emptythen
6{return
7{derivation_stack} \(\leftarrow\) pushstart_symbol} ;
8
9 whilederivation_stack not emptydo
10{current_symbol} \(\leftarrow\) derivation_stack.top();
11 derivation_stack.top();
12
13 ifcurrent_symbol is TERMINALthen
14 phenotype \(\leftarrow\) append symbol ;
15
16 elseifrule is OUTPUT_RALE and rule \(\
otin\) mapped_output_rulesthen
17{mapped_output_rules} \(\leftarrow\) insertoutput_rule;
18 ifmapped_output_rulessize() > 1 then
19 SubMap(current_symbol,mapped_output_rules,genome,mapped_outputs.size()-1,phenotype,dependency_manager);
20
21 else
22 goto Continue_Mapping_Process from line 20;
23
24
25 else
26 Continue_Mapping_Process:
27
28 rule \(\leftarrow\) grammar.GetRule(current_symbol);
29
30 production_choice \(\leftarrow\) 0;
31 ifrule_productions.size() > 1 then
32 ifcadort_index = genome.length(0-1 then
33 codon_index \(\leftarrow\) 0;
34 is_wrapperping \(\leftarrow\) true
35
36 eligible_prods \(\leftarrow\) create vector to hold eligible predictions
37 ifnot is_wrapperpingthen
38 ifcurrent_rule = OUTPUT_RALE_VARthen
39 check if a dependency graph exists for this rule group else create one eligible_prods \(\leftarrow\) retrieve valid output vars from dm
40
41 prod_choice \(\leftarrow\) genome[codon_index] % current_rule.prods.size();
42
43 ifprod_choice nor in eligible_prods then
44
45 randomly choose a prod from eligible_prods \(\&\)& modify codon value accordingly
46
47 update the dependency graph to reflect chosen output variable
48
49 else
50 for\(\textit{prod}\in\textit{rule}\textit{preds}\)do
51 ifprod contains an output_var then
52 ifoutput_var has preds valid for selectionthen
53 eligible_prods \(\leftarrow\) prod
54
55
56 else
57
58
59
60
61
62
63
64
65
66
67
68
69
700
801
81
82
83
84
85
86
87
88
89
901
9102
92
93
9403
951
964
971
982
998
999
10001
9990
10112
1013
1014
10215
10316
1042
1053
1065
1076
1087
10991
1100
11117
1118
1119
12001
12121
1222
1231
1242
1253
1265
1276
1288
1291
2021
2292
293
2941
2952
2961
2971
2982
2999
30001
31012
3202
3334
3
```
1 FunctionUpdateGraphMatrix(\(M\), \(pos_{x,y}\))
2M[\(pos_{x}\), \(pos_{y}\)] \(\gets\) 0;
3 while\(i<n\)do
4 ifM[\(i\), \(pos_{y}\)] = 1 then
5\(M\leftarrow\) UpdateGraphMatrix(M, [\(pos_{x}\), \(i\)]);
6\(i\)++;
7 return M;
8 FunctionFillMatrix(\(n\), dependencies)
9M \(\leftarrow\) Initialise matrix;
10M[i,j] \(\leftarrow\) 0, where i = j;
11M[i,j] \(\leftarrow\) **u**, where i \(\
eq\) j;
12 forposindependenciesdo
13 ifM[\(pos_{x}\), \(pos_{y}\)] = 0 then
14 raise error;
15
16 else
17M[\(pos_{x}\), \(pos_{y}\)] = 1;
18M = UpdateGraphMatrix(M, [\(pos_{y}\), \(pos_{x}\)]);
19 while\(i<n\)do
20 ifM[\(i\), \(pos_{y}\)] = 0 then
21M = UpdateGraphMatrix(M, [i, \(pos_{x}\)]);
22
23
24
25
26 return M;
```
**Algorithm 3**Cyclic Dependency Checking

The main function FillMatrix initialises an empty matrix \(M\) with shape \(n\times n\). Since the variables cannot depend on themselves, the positions \(i,j\), where \(i=j\), are initialised with 0. The input dependencies is a list with the respective dependencies to be filled in the matrix. In the next step, the positions regarding each dependency are filled with 1 (if possible), and the updates in consequence of that are made by calling the function UpdateGraphMatrix. ### Perfect Wrapping

Given that multiple output variables are evolving simultaneously, a partially mapped output rule will render the entire individual invalid, negatively impacting the evolutionary performance. This means performing genetic operations in MG-GE will record higher invalid individuals than standard GE. In other words, the higher the number of output variables in a multi-output problem, the higher the number of invalid individuals created by genetic operations.