Evolving reversible circuits for
the even-parity problem

MEP genes are represented by substrings of a variable length. The number of genes per chromosome is constant and it defines the length of the chromosome. Each gene encodes a terminal or a function symbol. A gene encoding a function includes references towards the function arguments. Function arguments always have indices of lower values than the position of that function in the chromosome.

This representation is similar to the way in which C and Pascal compilers translate mathematical expressions into machine code.

MEP representation ensures that no cycle arises while the chromosome is decoded (phenotypically transcripted). According to the representation scheme the first symbol of the chromosome must be a terminal symbol. In this way only syntactically correct programs (MEP individuals) are obtained.

Example

We employ a representation where the numbers on the left positions stand for gene labels (or memory addresses). Labels do not belong to the chromosome, they are provided here only for explanation purposes.

For this example, we use the set of functions $F$ = {+, *} and the set of terminals $T$ = {$a$, $b$, $c$, $d$}. An example of chromosome using the sets $F$ and $T$ is given below:

1: $a$

2: $b$

3: + 1, 2

4: $c$

5: $d$

6: + 4, 5

7: * 3, 6

In this section we described the way in which MEP individuals are translated into computer programs and the way in which the fitness of these programs is computed.

This translation is achieved by reading the chromosome top-down. A terminal symbol specifies a simple expression. A function symbol specifies a complex expression obtained by connecting the operands specified by the argument positions with the current function symbol.

For instance, genes 1, 2, 4 and 5 in the previous example encode simple expressions formed by a single terminal symbol. These expressions are:

$E_{1}=a$,

$E_{2}=b$,

$E_{4}=c$,

$E_{5}=d$,

Gene 3 indicates the operation + on the operands located at positions 1 and 2 of the chromosome. Therefore gene 3 encodes the expression:

$E_{3}=a+b$.

Gene 6 indicates the operation + on the operands located at positions 4 and 5. Therefore gene 6 encodes the expression:

$E_{6}=c+d$.

Gene 7 indicates the operation * on the operands located at position 3 and 6. Therefore gene 7 encodes the expression:

$E_{7}=(a+b)*(c+d)$.

There is neither practical nor theoretical evidence that one of these expressions is better than the others. Moreover Wolpert and McReady [17] proved that we cannot use the search algorithm’s behavior so far for a particular test function to predict its future behavior on that function. Thus we cannot choose one of the expressions (let us say expression $E_{7}$) to store the output of the chromosome. Even this expression proves to be useful for the first 10 generations we cannot guarantee that it will be the best option for all generations.

This is why each MEP chromosome is allowed to encode a number of expressions equal to the chromosome length. Each of these expressions is considered as being a potential solution of the problem.

This is very important because we can get many solutions within the same running time as in the case of one solution/chromosome.

The value of these expressions may be computed by reading the chromosome top down. Partial results are computed by Dynamic Programming [1] and are stored in a conventional manner.

As MEP chromosome encodes more than one problem solution, it is interesting to see how the fitness is assigned. Usually the chromosome fitness is defined as the fitness of the best expression encoded by that chromosome. For instance, if we want to solve symbolic regression problems the fitness of each sub-expression $E_{i}$ may be computed using the formula:

The fitness of an individual is set to be equal to the lowest fitness of the expressions encoded in chromosome:

When we have to deal with other problems we compute the fitness of each sub-expression encoded in the MEP chromosome and the fitness of the entire individual is given by the fitness of the best expression encoded in that chromosome.

Search operators used within MEP algorithm are crossover and mutation. These operators preserve the chromosome structure. All offspring are syntactically correct expressions.

Each symbol (terminal, function or function pointer) in the chromosome may be the target of mutation operator. By mutation some symbols in the chromosome are changed with a fixed mutation probability $p_{m}$. To preserve the consistency of the chromosome its first gene must encode a terminal symbol.

Standard MEP algorithm uses steady state [15] as its underlying mechanism. MEP algorithm starts by creating a random population of individuals. The following steps are repeated until a given number of generations ¹¹1In a steady-state algorithm, a generation is considered when the number of newly created individuals is equal to the population size. is reached. Two parents are selected using a selection procedure. The parents are recombined in order to obtain two offspring. The offspring are considered for mutation. The best offspring replaces the worst individual in the current population if the offspring is better than the worst individual.

The algorithm returns as its answer the best expression evolved along a fixed number of generations.

The interpretation for a MEP chromosome needs to be modified because reversible gates have more than one output. Thus an MEP chromosome containing $N$ Fredkin gates actually provides $3*N$ outputs (plus the outputs provided directly from the inputs). MEP representation will be unchanged, but during the fitness evaluation we will have to handle more circuits than the case of standard gates.

Another modification is related to the number of inputs. Two constant inputs 0 (always-OFF) and 1 (always-ON) have been added. These 2 inputs are very important in simulating the standard gates (such as NOT, AND) [3]. Moreover, without these 2 inputs we are not able to build a circuit for the even-parity problems. For instance, in the case of even-3-parity problem our circuits must signal 0 when all inputs are 1. But, the Fredkin gate can never generate a 0 value when all inputs are 1 (see Figure 1).

Our aim is to find a Boolean function that satisfies a set of fitness cases. The particular function that we want to find is the Boolean even-parity function. This function has $k$ Boolean arguments and it returns T (True) if an even number of its arguments are T. Otherwise the even-parity function returns F (False) [6]. According to [6] the Boolean even-parity functions appear to be the most difficult Boolean functions to detect via a blind random search.

The terminal set $T$ consists of the $k+2$ Boolean arguments $d_{0}$, $d_{1}$, $d_{2}$, … $d_{k-1}$, 0, 1.

The function set $F$ consists of one three-argument gate: the Fredkin gate.

The set of fitness cases for this problem consists of the 2^k combinations of the $k$ Boolean arguments. We have also added two constants inputs which are always signals 0 (respectively 1). These 2 fixed inputs are very important in simulating standard gates (such as NOT, AND, see [3] for more details). Thus each fitness case will have $k+2$ inputs and one output.

In this section we perform several experiments with MEP for solving several instances of the even-parity problem. General parameter settings for MEP are given in Table 2.

For reducing the chromosome length we keep all the terminals on the first positions of the MEP chromosomes.

The results along with the particular parameters used for obtaining them are given in Table 3. Success rate is computed as the number of successful runs over the total number of runs.

Table 3 shows that MEP algorithm is able to evolve reversible circuits for the even-parity problem. The shortest (regarding the number of gates) evolved reversible circuits for the even-3-parity and even-4-parity problem are depicted in Figures 2 and 3.

Multi Expression Programming has been used [12] for designing standard digital circuits for the even-parity problem. Using the gates AND, OR, NAND, NOR we have been able to evolve up to even-5-parity problem using a population of 4000 individuals with 600 genes each evolved for 50 generations. The shortest evolved standard digital circuit has 6 gates for the even-3-parity problem, and 9 gates for the even-4-parity problem, whereas the reversible ones requires 4 (even-3-parity) and 5 (even-4-parity) gates. The first remark is that reversible circuits might require less gates than the standard circuits.

However, when the entire set of 16 binary gates (including EQ, NOT, etc) was employed [12] the length of the evolved standard circuit is considerable shorter. Only 4 gates are required for a circuit implementing the even-5-parity problem and 5 standard gates are required for the even-6-parity problem [12]. The results obtained by using the Fredkin gate are similar (regarding the number of gates) to those obtained using the entire set of 16 gates with 2 binary inputs.