# Evolving Multi-Output Digital Circuits Using Multi-Genome Grammatical Evolution
## 3 Proposed Approach: Multi-Genome GE
### Cyclic Dependency Checking Algorithm
To mitigate this effect, we implement a new wrapping operator called _perfect wrapping_. Perfect wrapping requires the grammar rules and productions to be labelled with the minimal number of codons required to map fully. The perfect wrapping operator requires a list of eligible productions as input. If the derived rule is an output variable rule, its corresponding dependency graph must be checked to determine its eligible productions. First, the list is populated with eligible productions which are non-recursive and require the minimum number of codons to expand fully. If the list is empty, then recursive productions requiring the minimum number of codons to expand are considered. Second, the mod rule is applied to determine if the chosen production is part of the list of eligible productions. If not, one of the productions in the list is uniformly selected at random, and Equation (1) is used to generate a new codon to replace the current codon, which, when used with the mod rule, dictates the same choice. This process continues while codons are reused from the genome until a valid sentence is attained. \[\text{new\_codon}=\text{random\_number}\,\%\Big{(}\frac{\text{max\_codon\_value}+ 1}{\text{choices}}\Big{)}\times\text{choices}\,+\,\text{chosen\_prod} \tag{1}\]

### Selection

The selection operator implemented for MG-GE does not rely on the total aggregated fitness of all genomes in MG. This is because it is possible the worst-performing parent might have completely solved one of the output variables but will rarely or never be selected as a parent. Instead, a _pseudo-parent_ is created by performing \(n\) number of selection events, where the best-performing genome per output variable is selected from the pool of potential parents. Any selection operator, such as tournament, lexicase, and roulette-wheel selections, can be used to select each genome. For example, in a standard crossover event, two pseudo-parents are created and used to create two offspring. The selection process is illustrated in Figure 4.

### Well-formed Crossover and Mutation

Each genome in MG evolves a solution to a single and unique target variable. As a result, crossover operations occur between genomes that evolve the same output variable. Mutation operations are applied per genome in MG. These genetic operations can be performed in several ways. Three types of events are currently implemented for genetic operation purposes. These include: _random single-event_, _binary mask-event_ and _all-event_. In a random single event, only a single genome is randomly chosen for crossover and mutation. For a random single event, a binary mask of bit size equal to the number of genomes is randomly generated. All genomes in MG with bit positions in the binary mask whose bit values are one are chosen for mutation and

Figure 4: Multi-Genome Selection. crossover. In all-event, all genomes undergo genetic operations subject to the specified probability of these events occurring by the user. ### Substitution Operator

In solving multi-output problems, there may exist inter-output dependencies as noted in Section 1. To facilitate the evolution of these dependencies, we introduced custom grammar rules as described in Section 3.4. Also, recall each genome in MG is meant to evolve a solution to a single unique output. Evolution is creative and can potentially exploit the inter-output dependency feature by using other sub-optimal output variable expressions as building blocks to solve another output perfectly. However, before extracting the solved output from an individual, if there exists a dependency on sub-optimal or optimal output variables, it is necessary to rewrite/substitute such output variables with their corresponding expression to obtain the final perfect expression for the solved output. From Listing 2, assuming output variable output_1 has completely been solved. Recall the best-evolved solution is a combination of the best-performing genome per output variable.